The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

航电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])//上一个循环可能因为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 阅读(1194) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理