套路（拓扑排序）

/*    对每个联通块单独考虑。    每个联通块是一个环套树，树边拎出来可以随意定向，记树边为 m，所以树的方案数为2^m 。    对于环来说只有两种方向，顺时针和逆时针，记环边为 n，所以环的方案就是 2^n - 2。    最后把每个联通块的方案乘起来即可。    注意，自环无论如何定向都是环，但这并不违反环的公式，故可以不特判。*/#include
      
       #include
       
        #include
        
         using namespace std;#define maxn 200010#define mod 1000000007int con[maxn],deg[maxn],seq[maxn];int n,m;long long ans;long long Pow(long long a,long long b){    long long res=1;    while(b){        if(b&1)res=res*a%mod;        a=a*a%mod;        b>>=1;    }    return res;}void dfs(int x){    m++;    deg[x]=0;    if(deg[con[x]])dfs(con[x]);}int main(){    freopen("road.in","r",stdin);freopen("road.out","w",stdout);    //freopen("Cola.txt","r",stdin);    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&con[i]);        deg[con[i]]++;    }    int h=1,t=0;    for(int i=1;i<=n;i++){        if(!deg[i])seq[++t]=i;    }    while(h<=t){        int to=con[seq[h]];        deg[to]--;        if(!deg[to])seq[++t]=to;        ++h;    }    ans=Pow(2,t);    for(int i=1;i<=n;i++){        if(deg[i]){            m=0;            dfs(i);            ans=(ans*(Pow(2,m)-2))%mod;        }    }    ans=(ans+mod)%mod;    cout<
        
       
      

 

exLCS（动态规划）

 

#include
      
       #include
       
        #include
        
         #define maxn 1000010#define INF 0x7fffffffusing namespace std;char a[1010],b[maxn];int f[1010][1010],nxt[maxn][26];int n,m;void solve(){    f[0][1]=nxt[0][a[0]-'a'];    for(int i=0;i<=n;i++)f[i][0]=-1;    for(int i=0;i
         
          =0;i--){        memcpy(nxt[i],nxt[i+1],sizeof(nxt[i]));        nxt[i][b[i]-'a']=i;    }    solve();    int ans=0;    for(int i=n;i;i--)        if(f[n-1][i]
         
        
       
      

 

魔方（模拟）

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          int c[30],n,flag=false,out[30],ans;inline void read(int &now){    char Cget;now=0;while((Cget=getchar())<'0'&&Cget>'9');    while(Cget>='0'&&Cget<='9')now=now*10+Cget-'0',Cget=getchar();}void operation_A(){    int tmp,tmp2;    tmp=c[1];    c[1]=c[3],c[3]=c[4],c[4]=c[2],c[2]=tmp;    tmp=c[23],tmp2=c[24];    c[23]=c[10],c[24]=c[9],c[9]=c[5],c[10]=c[6];    c[5]=c[13],c[6]=c[14],c[13]=tmp2,c[14]=tmp;}void operation_B(){    int tmp,tmp2;    tmp=c[9];    c[9]=c[11],c[11]=c[12],c[12]=c[10],c[10]=tmp;    tmp=c[1],tmp2=c[3];    c[1]=c[21],c[3]=c[23],c[23]=c[19],c[21]=c[17];    c[19]=c[7],c[17]=c[5],c[7]=tmp2,c[5]=tmp;}void operation_C(){    int tmp=c[5],tmp2;    c[5]=c[7],c[7]=c[8],c[8]=c[6],c[6]=tmp;    tmp=c[17],tmp2=c[18];    c[17]=c[15],c[18]=c[13],c[15]=c[4],c[13]=c[3];    c[3]=c[12],c[4]=c[10],c[10]=tmp,c[12]=tmp2;}bool check(){    return c[1]==c[2]&&c[2]==c[3]&&c[3]==c[4]&&        c[5]==c[6]&&c[6]==c[7]&&c[7]==c[8]&&        c[9]==c[10]&&c[10]==c[11]&&c[11]==c[12]&&        c[13]==c[14]&&c[14]==c[15]&&c[15]==c[16]&&        c[17]==c[18]&&c[18]==c[19]&&c[19]==c[20]&&        c[21]==c[22]&&c[22]==c[23]&&c[23]==c[24];}void dfs(int now,int last){    if(check())    {        flag=true,ans=now;        return;    }    if(now>=n) return;    if(last!=1)    {        for(int i=1;i<=3;i++)        {            operation_A();            out[now+1]=i;            dfs(now+1,1);            if(flag) return;        }        operation_A();    }    if(last!=2)    {        for(int i=1;i<=3;i++)        {            operation_B();            out[now+1]=3+i;            dfs(now+1,2);            if(flag) return;        }        operation_B();    }    if(last!=3)    {        for(int i=1;i<=3;i++)        {            operation_C();            out[now+1]=6+i;            dfs(now+1,3);            if(flag) return;        }        operation_C();    }}void dfs2(int now,int last){    if(check())    {        flag=true,ans=now;        return;    }    if(now>=n) return;    if(last!=1)    {        for(int i=1;i<=3;i++)        {            operation_A();            out[now+1]=i;            dfs(now+1,1);            if(flag) return;        }        operation_A();    }    if(last!=2)    {        for(int i=1;i<=3;i++)        {            operation_B();            out[now+1]=3+i;            dfs(now+1,2);            if(flag) return;        }        operation_B();    }}int main(){    freopen("cube.in","r",stdin);    freopen("cube.out","w",stdout);    read(n);    for(int i=1;i<=24;i++) read(c[i]);    if(n<=3)    {        dfs(0,0);        for(int i=1;i<=ans;i++) printf("%d ",out[i]);    }    else    {        if(n<=6) dfs2(0,0);        if(!flag) dfs(0,0);        for(int i=1;i<=ans;i++) printf("%d ",out[i]);    }    fclose(stdin),fclose(stdout);    return 0;}