首页 > 代码库 > [BestCoder] Round #6
[BestCoder] Round #6
1001
http://acm.hdu.edu.cn/showproblem.php?pid=4981
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1002;
int num[maxn];
int n;
int main()
{
while(rd(n)!=EOF)
{
int sum=0;
for(int i=1;i<=n;i++)
{
rd(num[i]);
sum+=num[i];
}
sort(num+1,num+1+n);
if(1.0*sum/n>=num[(1+n)/2])
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
1002
http://acm.hdu.edu.cn/showproblem.php?pid=4982
题意为：
给出n,k，问能不能把n拆成k个不同的正整数相加，且其中k-1个数的和为完全平方数。
比如 n=22 ,k =4， 22可以拆成 1+5+6+10,且 1+5+10=4*4
BESTCODER主页上的题解：
PS：这道题目原来是要求输出一种可行方案的，所以下面题解是按照输出方案的思想搞的。
分析：
我们尝试枚举那个完全平方数 S,然后看能否将他拆分为 K-1 个数,并且不用到N-S
这一步可以用贪心+一次调整来搞定。为了保证 K-1 个数都不同,我们尝试尽量用 1,2,3...这些连续自然数来构造,如果 N-S 出现在这些数中,那么将 N-S 移除,再新加一个数。如果这样都不能拆分成 K-1 个数,那么这个 S 肯定不行。
现在考虑已经用上述方法拆分了,我们需要判断这个拆分是否可行。会产生问题的只有最后一个数,这个数可能和 N-S 一样,也可能出现在之前的序列。如果是出现在之前的序列,那么这个拆分也是不靠谱的。如果和 N-S 一样,那么分两种情况
1. N-S 曾出现在之前的序列,那么显然这个拆分也是不靠谱的
2. N-S 比倒数第二个数大,对于这种我们可以通过调整最后一个数和倒数第二个数的大小,来使得这个拆分成立,假设最后一个数为 a,倒数第二个为 b,只要 a-1,b+1 就好了。当然如果 a-1 = b+1 这个拆分也是不靠谱的这道题目就这样搞定了,其实没必要找所有的完全平方数,只要找小于 N 与 N 最接近的完全平方数就好了。
枚举出一个完全平方数，那么剩下的数就确定了，下面就开始判断剩下的那个数是否符合题意。
构造出完全平方数的k-1个数，从小到大，贪心，1,2,3.....
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,k;
bool ok(int s)
{
int last=n-s;//最后一个数，k-1个数以外的那个数
int k1=s,k2=1;//k1为k-1个数里面最后一个数，k2为倒数第二个数
///构造k-2个数
for(int i=1;i<=k-2;i++)
{
if(k2==last)//与最后一个数相等，不可以
k2++;
k1-=k2;//这里写成k1=s-k2了
if(k1<=k2)
return false;
k2++;
}
k2--;
while(1)//调整k-1个数中的最后两个
{
if(k1<=k2)
return false;
if(k1!=last)
return true;
k1--;//
k2++;
}
}
int main()
{
while(rd2(n,k)!=EOF)
{
int m=sqrt(n);
if(m*m>=n)
m--;
bool yes=0;
while(m)//枚举m，完全平方因子
{
if(ok(m*m))
{
yes=1;
break;
}
m--;
}
if(yes)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
1003
http://acm.hdu.edu.cn/showproblem.php?pid=4983
解题思路：
gcd(n-a,n)*gcd(n-b,n)=n^k
要求有多少(a,b)满足上面的式子,1<=a,b<=n , 1<=n,k<=10^9
gcd(n-a,n)<=n , gcd(n-b,n)<=n ,所以gcd(n-a,n)*gcd(n-b,n)<=n^2
当n=1时，只有(1,1)满足式子
当k>2时，有0个(a,b)满足式子
当k=2时，gcd(n-a,n)=n,gcd(n-b,n)=n, 只有(n,n)这种情况满足
当k=1时，gcd(n-a,n)*gcd(n-b,n)=n,也就是 gcd(n-a,n)，gcd(n-b,n)均为n的因子
令gcd(n-a,n)=x，即x为n的一个因子
gcd(n-a,n)=x, gcd((n-a)/x, n/x)=1, 满足条件的(n-a)/x也就是 n/x的欧拉函数
所以枚举n的因子，两个因子的欧拉函数相乘，再累加就可以了,注意当x!=n/x时，欧拉函数相乘再*2
,因为a,b两个值可以倒换位置。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n,k;
ll cnt;
int eular(int n)
{
int ans=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
ans-=ans/i;
while(n%i==0)
n/=i;
}
}
if(n>1) ans-=ans/n;
return ans;
}
int main()
{
while(rd2(n,k)!=EOF)
{
if(n==1||k==2)//注意这个语句和下面的if不能调换位置,
{
printf("1\n");
continue;
}
if(k>2)
{
printf("0\n");
continue;
}
ll ans=0;
for(int i=1;i<=sqrt(1.0*n);i++)
{
if(n%i==0)
{
if(i!=(n/i))
ans+=eular(n/i)*eular(i)*2%mod;
else
ans+=eular(n/i)*eular(i)%mod;
}
}
printf("%I64d\n",ans%mod);
}
return 0;
}[BestCoder] Round #6