pku1703,并查集的应用,比较常见的一种。
刚开始没什么思路,,想到一种方法,就是记录下每一个节点到根节点的距离,根据两个节点的距离之和的奇偶性来判断是敌是友。
这个代码没有写,不知道能行不能行。。
disscuss发现一种方法:用两个数组,一个存友f[],一个存敌d[]。
如果是D a b
就把a与的d[b]进行Union,b与d[a] 进行Union,
如果是A a b
先判断find(a) 是否等于find(b)
是就输入the same。
否的话判断find(a)是否等于find(f[b])
是的话输出the different
else 输出 条件不足。代码就不贴了。。
1027 和2062是两道模拟题,以前都没有做,感觉太麻烦了。。
今天闲来无事就给写了下,, 对于这类型的,关键是要理解透彻,细节要处理好。。
1027由于m最大只有10000 小于8的阶乘,所以只需要对n的后8位进行判断即可。。
2062 f[i]=i*(f[i-1]+1),m可以用__int64 来存储,其余的都和1027差不多。。
贴一下1027题得代码吧:
# include<stdio.h>
# include<string.h>
int f[10],visit[1005];
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,n,m,k,t,ans,flag;
f[0]=1;
for(i=1;i<=8;i++)
f[i]=f[i-1]*i;
while(scanf("%d%d",&n,&m)!=EOF)
{
flag=0;
memset(visit,0,sizeof(visit));
for(i=1;i<=n;i++)
{
ans=n-i+1;
if(ans>8)
{
visit[i]=1;
if(flag==0) {printf("%d",i);flag=1;}
else printf(" %d",i);
}
else
{
t=m/f[ans-1];
if(m%f[ans-1]!=0) t++;
k=0;
for(j=max(1,n-9);j<=n;j++)
{
if(visit[j]==0) k++;
if(k==t) break;
}
visit[j]=1;
if(flag==0) {printf("%d",j);flag=1;}
else printf(" %d",j);
m-=(t-1)*f[ans-1];
}
}
printf("\n");
}
return 0;
}