航電3月月賽
最后一題 1010 傳遞閉包
#include<iostream>
using namespace std;

int mm[200][200];
int main()

{
int n,m;
while(scanf("%d%d",&n,&m))
{
memset(mm,0,sizeof(mm));
int flag=0;
if(n==0)
break;
int i,j;
for(i=1;i<=m;i++)
{
int t1,t2;
scanf("%d%d",&t1,&t2);
mm[t1][t2]=1;
}
int k;
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(mm[i][k]==1&&mm[k][j]==1)
mm[i][j]=1;
}
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(mm[i][j]==1&&mm[j][i]==1)
{
flag=1;
break;
}
}
if(flag)
break;
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}
1004 KMP算法
#include<iostream>
using namespace std;
char str[200010];
int next[200010];
int dp[200010];
inline void calnext(char s[],int next[])

{
int i;
int j;
int len=strlen(s);
next[0]=-1;
j=-1;
for(i=1;i<len;i++)
{
while(j>=0&&s[i]!=s[j+1])
j=next[j];
if(s[j+1]==s[i])//上一個循環(huán)可能因為j=-1而不做,此時不能知道s[i]與s[j+1]的關系。故此需要此條件。
j++;
next[i]=j;
}
}
int main()

{
int n;
int t;
scanf("%d",&t);
int i,j;
int sum;
for(i=1;i<=t;i++)
{
scanf("%d",&n);
scanf("%s",str);
calnext(str,next);
dp[0]=1;
sum=1;
for(j=1;j<n;j++)
{
if(next[j]==-1)
{
dp[j]=1;
sum++;
sum%=10007;
}
else
{
dp[j]=dp[next[j]]+1;
sum+=dp[j];
sum%=10007;
}
}
printf("%d\n",sum);
}
return 0;
}posted on 2010-03-06 17:15 abilitytao 閱讀(1215) 評論(0) 編輯 收藏 引用

