首页 > 代码库 > POJ 3007 Organize Your Train part II

POJ 3007 Organize Your Train part II

2024-11-17 00:29:02   203人阅读

技术分享

题意：

 　　如上图所示，将一个字符串进行分割，反转等操作后不同字符串的个数：

      例如字符串abba：可以按三种比例分割；1:3；2:2；3:1

      部分反转可以得到如下所有的字符串：

　　

技术分享
　　去掉重复可以得到六个不同的字符串，输出6；
解题思路：
　　此题用反转函数reverse比较方便，然后就和模拟差不多，要列出所有情况，把不同的字符串保存在一个字符数组中，每次得到一个字符串都和该字符数字中的每一个比较，如果都不相同，把它存入字符数组；、
直接看代码吧：
 1 //Organize Your Train part II 2 #include<stdio.h> 3 #include<string> 4 #include<string.h> 5 #include<algorithm> 6 using namespace std; 7 int t; 8 char s1[201],s2[201]; 9 char map[1000][201];10 int ans;//全局变量，记录字符串的个数11 void check(char s[])//检测是否有新的字符串12 {13     for(int i=0;i<ans;i++)14     {15         if(strcmp(s,map[i])==0)16             return;17     }18     strcpy(map[ans++],s);19     return;20 }21 int main()22 {23     scanf("%d",&t);24     int n;25     while(t--)26     {27         ans=0;28         scanf("%s",s1);29         n=strlen(s1);30         for(int i=0;i<n-1;i++)31         {32             strcpy(s2,s1);33             check(s2);34             reverse(s2,s2+i+1);35             check(s2);36             reverse(s2+i+1,s2+n);37             check(s2);38             reverse(s2,s2+i+1);39             check(s2);40             reverse(s2,s2+n);41             check(s2);42             reverse(s2,s2+n-i-1);43             check(s2);44             reverse(s2+n-i-1,s2+n);45             check(s2);46             reverse(s2,s2+n-i-1);47             check(s2);48         }49         printf("%d\n",ans);50     }51     return 0;52 }

 

 

　　

POJ 3007 Organize Your Train part II


联系
我们