首页 > 代码库 > 【65测试20161114】【字符串】【DP】
【65测试20161114】【字符串】【DP】
第一题 复制&粘贴：
文件的内容是一个字符串S，对其进行N次复制&粘贴的操作，第i次操作复制位置Ai和位置Bi之间的所有文字，然后在位置Ci粘贴。这里位置x表示字符串的第x个字符的后面那个位置(位置0表示字符串的开头)，例如字符串”copypaste”的位置6表示字符’a’和字符’s’之间的位置，位置9表示’e’后面的位置(即字符串的结尾)。不过，如果操作后的字符串长度超过了M，那么将超过的部分删除，只保留长度为M的前缀。
你的任务是写一个程序，输出N次操作后字符串的前K个字符。
对于40%的数据，N,M<=2000
对于100%的数据：
1<=K<=200
1<=M<=10^9
S 的每个字符都是小写字母(‘a’~’z’)
K<=|S|<=min(M,2*10^5)
1<=N<=2*10^5
设第i 次操作前的字符串长度为Li，那么0<=Ai<Bi<=Li 且0<=Ci<=Li (1<=i<=N)
解：
40% ：直接模拟，s.insert(), s.erase()就可以了。
100%：考虑到k的值很小，所以我们只需要知道前k个字符对应的在原字符串的位置就可以了。用ans[i]先表示第i 个位置的字符在最后修改后字符串的位置，然后一步步的推回原字符串的位置。因为最后ans[i]=i;所以从最后一个操作开始，枚举每个前k个位置，有三种情况：
1、如果x位置是在这个操作的c前面，对x位置没有影响；
2、x位置是由这个操作粘贴过来的，则粘贴前x位置的字符的位置在x-c[i]+a[i];
3、如果在这个操作的c[i]+b[i]-a[i]后，则x位置的字符为右移后得到的，则原位置为：x-(b[i]-a[i]).
这样一直递推到第一个操作，ans[]所指的位置为原字符串的对应位置。（毕竟以后得到的所有字符都是由原字符串复制粘贴得到的）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 200005 6 using namespace std; 7 int k,m,n,ans[205]; 8 int a[maxn],b[maxn],c[maxn]; 9 char s[maxn];10 int main()11 {12 freopen("A.in","r",stdin);13 freopen("A.out","w",stdout);14 cin>>k>>m;15 scanf("%s",s+1);16 cin>>n;17 for (int i=1;i<=n;i++)18 scanf("%d%d%d",&a[i],&b[i],&c[i]);19 for (int i=1;i<=k;i++)20 ans[i]=i;//在第i位置的字符在哪个位置21 for (int i=n;i>=1;i--)22 for (int j=1;j<=k;j++)23 {24 if (ans[j]<=c[i]) continue;//< = 在c[i]前面没有影响 25 else if (ans[j]<=c[i]+b[i]-a[i])//粘贴过来的 ，还原为原位置 26 ans[j]=ans[j]-c[i]+a[i];27 else ans[j]-=b[i]-a[i];//右移后的，还原为原位置 28 } 29 for (int i=1;i<=k;i++)30 putchar(s[ans[i]]);//putchar 的使用31 return 0; 32 }
第二题：愉快的logo设计
设计一个用’J’，’O’，’I’三种文字环形排列的logo。
如下所示，对于任意非负整数k，我们定义标号为k的JOI序列Sk为：
·S0为’J’，’O’，’I’中任一字符构成的长度为1的字符串
·S[k+1]为最初4^k个字符都是’J’，接下来的4^k个字符都是’O’，接下来的4^k个字符都是’I’，最后4^k个字符是字符串Sk的长为4^(k+1)的字符串
现在，K理事长在纸上写下了由4^K个文字构成的一个环形字符串，字符串中每个字符都是’J’，’O’，’I’中的一个。K理事长想要修改一些文字，使得得到的字符串从某个起点开始顺时针读一圈后可以得到SK。在满足条件的情况下，要求修改的文字数量最少。
【Sample Input】
2
JJOIJJOJOIOJOOOI
【Sample Output】
7
【HINT】
从○标记的位置顺时针阅读一圈得到“JJJJOOOOIIIIJOIJ”，满足S2的条件，且修改文字数达到最小值7。
【Data Constraint】
对于30%的数据，1<=K<=5
对于100%的数据，1<=K<=10
解：（读题都读了好久才读懂）
30%：直接挨个比较就可以了。
100%：考虑到目标字符串很有规律，是一段一段的重复的：
4^(k-1)个J，4^(k-1)个O，4^(k-1)个I，4^(k-2)个J，4^(k-2)个O，4^(k-2)个I,..........4^0个J,4^0个O，4^0个I，最后一个随意。
所以可以换一个角度去想这个问题。我们普通的思路是用原字符串来匹配目标字符串，而根据刚才的规律，我们可以换为用目标字符串来匹配原字符串。具体的操作如下：
第一次匹配：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| J | J | J | J | O | O | O | O | I | I | I | I | J | O | I | J |
| J | J | O | I | J | J | O | J | O | I | O | J | O | O | O | I |
第二次匹配：(目标串右移)
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| J | J | J | J | O | O | O | O | I | I | I | I | J | O | I | X | |
| J | J | O | I | J | J | O | J | O | I | O | J | O | O | O | I | J |
第三次匹配：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| J | J | J | J | O | O | O | O | I | I | I | I | J | O | I | X | ||
| J | J | O | I | J | J | O | J | O | I | O | J | O | O | O | I | J | J |
等等........
所以原串要*2。 O(4^N*K)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1200005 6 using namespace std; 7 int k,f[(maxn<<1)][5],n,ki,ans=12345678; 8 char c[(maxn<<1)]; 9 int main()10 {11 freopen("B.in","r",stdin);12 freopen("B.out","w",stdout);13 cin>>k;14 n=(1<<(k<<1));15 for (int i=1;i<=n;i++)16 {17 char s=getchar();18 while (s!=‘J‘&&s!=‘O‘&&s!=‘I‘) s=getchar();19 c[i]=s;c[i+n]=s;20 }21 for (int i=1;i<=(n<<1);i++)//前缀和 22 {23 f[i][1]=f[i-1][1];24 f[i][2]=f[i-1][2];25 f[i][3]=f[i-1][3];26 if (c[i]==‘J‘) f[i][1]++;27 else if (c[i]==‘O‘) f[i][2]++;28 else f[i][3]++;29 }30 ki=(1<<((k-1)<<1));31 for (int i=1;i<=n;i++)32 {33 int cur=ki,sum=0,tmp=i;34 while (cur)35 {36 sum+=f[tmp+cur-1][1]-f[tmp-1][1];37 sum+=f[tmp+cur*2-1][2]-f[tmp+cur-1][2];38 sum+=f[tmp+cur*3-1][3]-f[tmp+2*cur-1][3];39 tmp+=cur*3;40 cur=(cur>>2);41 }42 ans=min(ans,n-sum-1);43 }44 printf("%d",ans);45 return 0;46 }
【65测试20161114】【字符串】【DP】