hdu 5776 sum
题意：
给一个n个数的数列，求是否存在一个连续和是m的倍数，存在输出YES。
分析：
预处理前缀和，一旦有两个数模m的值相同，说明中间一部分连续子列可以组成m的倍数。 另外，利用抽屉原理，我们可以得到，一旦n大于等于m，答案一定是YES 复杂度 O（n）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+9;
int n,m,a[N],sum[N],cnt[N];
int main()
{
//freopen("f.txt","r",stdin);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sum[0]=0;
memset(cnt,0,sizeof(cnt));
bool flag=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
cnt[sum[i]%m]++;
}
for(int i=1;i<m;i++)if(cnt[i]>1){flag=1;break;}
if(flag||cnt[0])printf("YES
");
else printf("NO
");
}
return 0;
}
/*
要注意一个例子：
2 3
1 2
所以要特判cnt[0]
*/hdu 5777 domino
题意：
分析：
一共有k次机会，也就是把n个骨牌分成k段，也就是把中间的距离抹去k-1个，那就可以分成k段骨牌了。贪心，要想高度和最小，那么就要抹去最大的距离。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+9;
int n,k;
int a[N];
int main()
{
//freopen("f.txt","r",stdin);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
ll ans=0;
for(int i=0;i<n-1;i++)scanf("%d",&a[i]),ans+=a[i];
sort(a,a+n-1);
int t=0;
for(int i=n-2;i>=0&&k>=2;i--){
ans-=a[i];
k--;
}
ans+=n;
printf("%I64d
",ans);
}
return 0;
}
hdu 5778 abs
分析：
由于y质因数分解式中每个质因数均出现2次，那么y是一个完全平方数，设y=z*z，题目可转换成求z，使得每个质因数出现1次. 我们可以暴力枚举z，检查z是否符合要求，显然当z是质数是符合要求，由素数定理可以得，z的枚举量在logn级别。
因为y=x-abs或者y=x+abs，所以z在sqrt(x)左右，那么就向左向右枚举z，因为我是一遇到符合条件的z就break，因为刚开始以为这时的abs(z*z-x)就是最小的，但是忽略了一个事，就是sqrt(x)是向下取整，如果z向右枚举的时候，在遇到一个最小值之前就break了，这个其实仔细想想就明白了，WA了三次后才发现QAQ。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
bool ok(ll x)
{
if(x<2)return false;
for(ll i=2;i*i<=x;i++){
if(x%i==0){
if(x%(i*i)==0)return false;
x/=i;
}
}
return true;
}
int main()
{
//freopen("f.txt","r",stdin);
int T;scanf("%d",&T);
while(T--){
ll x;
scanf("%I64d",&x);
ll t=sqrt(x+0.5);
ll ans;
while(t*t<x)t++; //这里注意
for(ll i=t;;i++){
if(ok(i)){
ans=i*i-x; //y>=x
break;
}
}
for(ll i=t-1;i>0;i--)
if(ok(i)){
ans=min(ans,x-i*i);break; //y<=x
}
printf("%I64d
",ans);
}
return 0;
}