1005 hdu3924题意每个树有三个子树，求第N个数的形状。
先求出不同个数的X方法数，然后先计算所有X的个数，然后不断地递归算出左中右三个子树的个数。
rejudge了。。。注意左子树相同时，中子树的个数多的不一事实上在中子树个数少的后面，因为此时要看左子树的状态
//rejudge后WA
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const __int64 maxint=1000000000000001;
__int64 f[100],sum[100];
void Cal()//计算不同X的方法数
{
__int64 i,j,k,r,ii;
f[0]=1,f[1]=1,sum[0]=1,sum[1]=2;
for(i=2;;i++)
{
f[i]=0;
ii=i-1;
for(j=0;j<=ii;j++)
for(k=0;k<=ii-j;k++)
{
r=ii-j-k;
f[i]+=f[j]*f[k]*f[r];
}
sum[i]=sum[i-1]+f[i];
if(sum[i]>=maxint) break;
}
// printf("%I64d %I64d\n",i,sum[i]);
}
void DFS(__int64 n,__int64 step)//step个X的第n种情况
{
__int64 i,j,k,r,ii,jj,kk,s=0;
r=step-1;
for(i=0;i<=r;i++)
{
for(j=0;j<=r-i;j++)
{
k=r-i-j;
s+=f[i]*f[j]*f[k];
if(s>n)
{
s-=f[i]*f[j]*f[k];
s=n-s;
kk=s%f[k];
jj=(s/f[k])%f[j];
ii=s/(f[j]*f[k]);
break;
}
}
if(j<=r-i) break;
}
if(i)
{
printf("(");
DFS(ii,i);
printf(")");
}
if(j)
{
printf("(");
DFS(jj,j);
printf(")");
}
if(k)
{
printf("(");
DFS(kk,k);
printf(")");
}
printf("X");
}
int main()
{
Cal();
__int64 t,test=1,n,i;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d",&n);
n++;
for(i=0;;i++)
{
if(sum[i]>=n) break;
}
printf("Case #%I64d: ",test++);
DFS(n-sum[i-1]-1,i);
printf("\n");
}
return 0;
}
//rejudeg后AC
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const __int64 maxint=1000000000000001;
__int64 f[100],sum[100];
void Cal()//计算不同X的方法数
{
__int64 i,j,k,r,ii;
f[0]=1,f[1]=1,sum[0]=1,sum[1]=2;
for(i=2;;i++)
{
f[i]=0;
ii=i-1;
for(j=0;j<=ii;j++)
for(k=0;k<=ii-j;k++)
{
r=ii-j-k;
f[i]+=f[j]*f[k]*f[r];
}
sum[i]=sum[i-1]+f[i];
if(sum[i]>=maxint) break;
}
//printf("%I64d %I64d %I64d\n",i,f[i],sum[i]);
}
void DFS(__int64 n,__int64 step)//step个X的第n种情况
{
__int64 i,j,k,r,ii,jj,kk,s=0,s1;
r=step-1;
for(i=0;i<=r;i++)//枚举左子树的结点数
{
for(s1=0,j=0;j<=r-i;j++)
{
k=r-i-j;
s1+=f[i]*f[j]*f[k];
}
if(s+s1>n)//由此确定了左子树有i个结点
{
s=n-s;//左子树i个结点的第s种情况
//左子树有i个结点时，共有s1种情况。s1/f[i]表示对于左子树i个结点的某种形状(总共有f[i]种形状)的方法数
ii=s/(s1/f[i]);//左子树为i个结点且排列是第ii种情况（左子树的排列）
s=s%(s1/f[i]);//后面两棵子树的排列情况
for(s1=0,j=0;j<=r-i;j++)//枚举中子树的结点个数
{
k=r-i-j;
s1+=f[j]*f[k];
if(s1>s)//可确定中子树结点个数为j
{
s1-=f[j]*f[k];
s=s-s1;//中子树结点个数为j的第s种情况
jj=s/f[k];
kk=s%f[k];
break;
}
}
break;
}
else s+=s1;
}
if(i)
{
printf("(");
DFS(ii,i);
printf(")");
}
if(j)
{
printf("(");
DFS(jj,j);
printf(")");
}
if(k)
{
printf("(");
DFS(kk,k);
printf(")");
}
printf("X");
}
int main()
{
Cal();
__int64 t,test=1,n,i;
scanf("%I64d",&t);
while(t--)
{
scanf("%I64d",&n);
n++;
for(i=0;;i++)
{
if(sum[i]>=n) break;
}
printf("Case #%I64d: ",test++);
DFS(n-sum[i-1]-1,i);
printf("\n");
}
return 0;
}
1006 hdu3925 a至少加上多少，会含有b（把它们看作字符串）。我首先讨论了b本身就是a的字串，还有b的长度比a大的情况。对于其它的情况，我枚举b的最后一个位置对应a的位置（这里因为可能有进位的情况，所以多加了一位，有进位的话就是1，没的话就是0，后面再去掉），最后对于b的第一位是1的情况，特殊考虑。
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=120;
char s1[maxn],s2[maxn],s[maxn],ss[maxn],s3[maxn];
int len1,len2;
void DFS(int now)//s1的now位为结尾
{
int i,j;
for(j=now+2;j<=len1;j++)
ss[j]='0';
ss[j]=0;
ss[0]='0';
for(j=0;j<now-len2+1;j++)
ss[j+1]=s1[j];
for(;j<=now;j++)
ss[j+1]=s2[j-now+len2-1];
if(strcmp(s2,s1+now-len2+1)<0)
ss[now-len2+1]++;
i=now-len2+1;
while(ss[i]>'9')
{
ss[i]-=10;
ss[i-1]++;
i--;
}
if(strcmp(ss,s3)<0) strcpy(s3,ss);
}
void A(char s2[],char s1[],char s[])//s=s2-s1
{
int ii,i,j,len2=strlen(s2),len1=strlen(s1);
s[len2]=0;
for(i=len1-1;i>=0;i--)
{
if(s1[i]<=s2[i+len2-len1])
s[i-len1+len2]=s2[i+len2-len1]-s1[i]+'0';
else
{
s[i-len1+len2]=s2[i+len2-len1]+10-s1[i]+'0';
s2[i+len2-len1-1]--;
}
}
for(ii=i-len1+len2;ii>=0;ii--)
{
if(s2[ii]<'0')
{
s[ii]=s2[ii]+10;
s2[ii-1]--;
}
else s[ii]=s2[ii];
}
j=0;
while(s[j]=='0') j++;
for(i=0;i<len2;i++)
s[i]=s[i+j];
s[i]=s[i+j];
}
bool OK(char s1[],char s2[])//s1是否含有s2
{
int i,j,len2=strlen(s2);
for(i=0;i+len2<=len1;i++)
{
for(j=i;j<i+len2;j++)
if(s1[j]!=s2[j-i])
break;
if(j>=i+len2) return true;
}
return false;
}
int main()
{
int t,test=1,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",s1,s2);
printf("Case #%d: ",test++);
len1=strlen(s1);
len2=strlen(s2);
if(OK(s1,s2))//s1包含s2
{
printf("0\n");
continue;
}
if(len1<len2)//s1长度小于s2，那么结果是s2-s1
{
A(s2,s1,s);
printf("%s\n",s);
continue;
}
s3[0]='1';
for(i=1;i<110;i++)
s3[i]='9';
s3[i]=0;
for(i=len1-1;i>=len2-1;i--)
DFS(i);
if(s2[0]=='1')//s2是以1开始特殊考虑
{
for(i=0;i<len2;i++)
ss[i]=s2[i];
for(i=len2;i<=len1;i++)
ss[i]='0';
ss[i]=0;
if(strcmp(ss,s3)<0) strcpy(s3,ss);
}
A(s3,s1,s);
printf("%s\n",s);
}
return 0;
}
1007 hdu3927同构就是每个连通分量的点和边都相等。所以统计每个连通分量的点和边，然后排序，判断即可
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=11000;
vector<int>e[maxn],e1[maxn];
int DFN[maxn],DFN1[maxn],num,num1;
struct edge
{
int num,e;
}ee[maxn],ee1[maxn];
void Input(vector<int>e[],int &n,int &m)
{
int i,u,v;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
e[i].clear();
for(i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
}
void Tarjan(int t,int p,vector<int>e[],int DFN[],int num,edge ee[])//统计每个连通分量的点和边数
{
DFN[t]=1;
ee[num].num++;
int i,j;
for(i=0;i<e[t].size();i++)
{
j=e[t][i];
if(j==p) continue;
ee[num].e++;
if(!DFN[j])
Tarjan(j,t,e,DFN,num,ee);
}
}
bool cmp(edge a,edge b)//先按点数排序，点数相等的按边数从小到大排序
{
if(a.num!=b.num) return a.num<b.num;
else return a.e<b.e;
}
int main()
{
int t,test=1,i,n,m,n1,m1;
scanf("%d",&t);
while(t--)
{
Input(e,n,m);
Input(e1,n1,m1);
printf("Case #%d: ",test++);
if(n!=n1||m!=m1)
{
printf("NO\n");
continue;
}
memset(DFN,0,sizeof(DFN));
memset(DFN1,0,sizeof(DFN1));
num=0,num1=0;
for(i=1;i<=n;i++)
if(!DFN[i])
{
ee[num].num=0;
ee[num].e=0;
Tarjan(i,-1,e,DFN,num++,ee);
}
for(i=1;i<=n;i++)
if(!DFN1[i])
{
ee1[num1].num=0;
ee1[num1].e=0;
Tarjan(i,-1,e1,DFN1,num1++,ee1);
}
if(num!=num1)//连通分量个数不相等
{
printf("NO\n");
continue;
}
// printf("%d\n",num);
sort(ee,ee+num,cmp);
sort(ee1,ee1+num,cmp);
for(i=0;i<num;i++)
if(ee[i].num!=ee1[i].num||ee[i].e!=ee1[i].e)
{
printf("NO\n");
break;
}
if(i>=num)
printf("YES\n");
}
return 0;
}