1004 Cut the Cake http://acm.hdu.edu.cn/showproblem.php?pid=4762
一个很小的大数。。。解为M/(N^M) ，N、M最大为20，说大不大，说小还不能用long long，一个问题就是约分，所以直接一个一下乘
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000;
long long a[30];
void work (int x)
{
for(int j=1;j<30;j++) a[j]*=x;
for(int j=1;j<30;j++)
{
if(a[j]>=10)
{
a[j+1]+=a[j]/10;
a[j]%=10;
}
}
}
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int T;cin>>T;
int n,m;
while (T--)
{
scanf("%d %d",&n,&m);
memset(a,0,sizeof(a));
a[1]=1;
int nn=n;
int len=m,c;
int ans=gcd(n,m);
while (ans!=1)
{
m/=ans;
c=n/ans;
work(c);
ans=gcd(n,m);
len--;
}
for(int i=1;i<len;i++) work(nn);
int i=29;
while (a[i]==0) i--;
printf("%d/",m);
for(;i>=1;i--)
{
printf("%d",a[i]);
}
puts("");
}
return 0;
}
1005 Theme Section http://acm.hdu.edu.cn/showproblem.php?pid=4763
目测全场最坑题，开始不敢动，想着说用KMP加线段树各种复杂怎么才能做，就搁置了，等过了好多人之后，据说是水题。。。没办法，KMP怒水一下，果断AC，坑的一手好爹！直接KMP，从字符串最后一个的next为最大值往下搜，只要在[Max--Len-Max]之间有一个next的值是Max，那就是它了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x7fffffff;
const int maxn=1001000;
int p[maxn];
char a[maxn];
int t[maxn*3];
void KMP ()
{
int l=strlen(a+1);
int k=0;
for(int i=2;i<=l;i++)
{
while (k>0 && a[1+k]!=a[i])
k=p[k];
if(a[k+1]==a[i]) k++;
p[i]=k;
}
}
int main()
{
int T;cin>>T;getchar();
while (T--)
{
memset(p,0,sizeof(p));
memset(t,0,sizeof(t));
scanf("%s",a+1);getchar();
KMP();
int Max=p[strlen(a+1)];
int L=strlen(a+1);
bool flag=false;
int i,j;
for(i=Max;i>0;i--)
{
if(i>=L-i) continue;
else{
for(j=i+1;j<=L-i;j++)
if(p[j]==i) {flag=true;break;}
}
if(flag) break;
}
printf("%d\n",i);
}
return 0;
}
1006 Stone http://acm.hdu.edu.cn/showproblem.php?pid=4764
这是签到题，一开始在看别的题，过了二十来分钟才发现它。。。。简单博弈，找必胜态，N-1、N-1-k……
#include <cstdio>
int main()
{
int n,k;
while (scanf("%d %d",&n,&k),n||k)
{
int b=(n-1)%(k+1);
if(b==0)
printf("Jiang\n");
else
printf("Tang\n");
}
return 0;
}
1010 Flyer http://acm.hdu.edu.cn/showproblem.php?pid=4768
这题最后敲出来了，但没时间debug，不幸挂了。思路是，题目上说要么无解，要么解唯一，所以可以直接从1-INF二分，每次分开的两个区间，如果两个区间的人都是偶数，直接跳出来输出，否则必然是一个区间是奇一个区间是偶，然后一直搜下去，就会找到那个为奇数的人。
代码坑爹啊，先贴我写的挫死代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x7fffffff;
const int maxn=21000;
int N;
struct node
{
int a,b,c;
}t[maxn];
int work(int L,int R)
{
int ans=0;
for(int i=0;i<N;i++)
{
if(L>t[i].b) continue;
if(R<t[i].a) continue;
if(t[i].a>=L && t[i].b<=R)
ans+=(t[i].b-t[i].a)/t[i].c+1;
else if (t[i].a<L && t[i].b<=R)
{
if((L-t[i].a)%t[i].c==0)
{
ans++;
ans+=(t[i].b-L)/t[i].c;
}
else
{
int kk=(L-t[i].a)/t[i].c+1;
int t2=t[i].a+t[i].c*kk;
if(t2<=t[i].b)
{
ans++;
ans+=(t[i].b-t2)/t[i].c;
}
}
}
else if (t[i].b>R && t[i].a>=L)
{
ans++;
ans+=(R-t[i].a)/t[i].c;
}
else if(t[i].a<=L && t[i].b >=R)
{
if((L-t[i].a)%t[i].c==0) ans++;
int kk=(L-t[i].a)/t[i].c+1;
int t2=t[i].a+t[i].c*kk;
if(t2<=R){
ans++;
ans+=(R-t2)/t[i].c;
}
}
}
return ans;
}
int work2 (int x)
{
int ans=0;
for(int i=0;i<N;i++)
if(t[i].a<=x && t[i].b>=x &&(x-t[i].a)%t[i].c==0) ans++;
return ans;
}
int main()
{
while (scanf("%d",&N)==1)
{
int Max=-INF;
for(int i=0;i<N;i++){
scanf("%d %d %d",&t[i].a,&t[i].b,&t[i].c);
Max=max(Max,t[i].b);
}
int L=1,R=INF;
int x,y;
x=y=0;
while (L<R)
{
int M=L+(R-L)/2;
x=work(L,M);
y=work(M+1,R);
//printf("L=%d x=%d R=%d y=%d\n",L,x,R,y);
if(x&1) R=M;
if(y&1) L=M+1;
if(x%2==0 && y%2==0) break;
//if(L==R) break;
}
if(L<R) printf("DC Qiang is unhappy.\n");
else printf("%d %d\n",L,work2(L));
}
return 0;
}
下面贴一个北大大牛的代码，提醒我自己代码是有多挫。。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s[200010],e[200010],d[200010],t,n,i,ans,cnt;
unsigned int l,r,mid;
int main()
{
while(cin>>n)
{
for(i=1;i<=n;i++) scanf("%d%d%d",&s[i],&e[i],&d[i]);
l=0,r=1ll<<31;
while(l<r)
{
mid=(l+r)>>1;
ans=0;
for(i=1;i<=n;i++)
if(mid>=s[i]) ans+=(min(mid,(unsigned)e[i])-s[i])/d[i]+1;
if(ans&1) r=mid; else l=mid+1;
}
if(l==(1ll<<31)) {puts("DC Qiang is unhappy."); continue;}
cnt=0;
for(i=1;i<=n;i++)
if(l>=s[i]&&l<=e[i]&&(l-s[i])%d[i]==0) cnt++;
cout<<l<<' '<<cnt<<endl;
}
return 0;
}