2 条题解

  • 0
    @ 2025-10-8 16:58:27

    题目图片```cpp #include<bits/stdc++.h> using namespace std; const int Mod=97654321,N=250+5; vectorG[57]; int f[N<<1][N][57]; inline int id(char c){return c>='a'&&c<='z'?c-'a'+1:c-'A'+1+26;}

    int main(){ios::sync_with_stdio(False);cin.tie(0);cout.tie(0); int U,L,P;cin>>U>>L>>P;char c1,c2; for(int i=1;i<=P;++i){cin>>c1>>c2;G[id(c1)].push_back(id(c2));} memset(f,0,sizeof(f)); for(int i=1;i<=26;++i){f[1][0][i]=1;f[1][1][i+26]=1;} for(int i=2;i<=U+L;++i) for(int j=0;j<=U;++j) for(int x=1;x<=52;++x) for(int y:G[x]) if(y<=26)(f[i][j][y]+=f[i-1][j][x])%=Mod; else (f[i][j+1][y]+=f[i-1][j][x])%=Mod; int ans=0;for(int i=1;i<=52;++i)(ans+=f[U+L][U][i])%=Mod; cout<<ans<<endl;return 0;}

    • 0
      @ 2025-10-8 16:57:47


      #include<bits/stdc++.h>
      using namespace std;
      const int Mod=97654321,N=250+5;;
      vector<int>G[57];
      int f[N<<1][N][57];
      inline int id(char c){return c>='a'&&c<='z'?c-'a'+1:c-'A'+1+26;}
      
      int main(){
      	ios::sync_with_stdio(False);cin.tie(0);cout.tie(0);
      	int U,L,P;cin>>U>>L>>P;
      	char c1,c2;
      	for(int i=1;i<=P;++i){
      		cin>>c1>>c2;
      		G[id(c1)].push_back(id(c2));
      	}
          memset(f,0,sizeof(f));
      	for(int i=1;i<=26;++i){
      		f[1][0][i]=1;
      		f[1][1][i+26]=1;
      	}
      	for(int i=2;i<=U+L;++i)
      		for(int j=0;j<=U;++j)
      			for(int x=1;x<=52;++x)
      				for(int y:G[x])
      					if(y<=26)(f[i][j][y]+=f[i-1][j][x])%=Mod;
      					else           (f[i][j+1][y]+=f[i-1][j][x])%=Mod;
          int ans=0;
      	for(int i=1;i<=52;++i)
      		(ans+=f[U+L][U][i])%=Mod;
      	cout<<ans<<endl;
      	return 0;
      }

      • 1

      *【动态规划设计】单词接龙[USACO11FEB] Cowlphabet G

      信息

      ID
      1562
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      2
      已通过
      2
      上传者