第一题 复制&粘贴：
文件的内容是一个字符串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[]所指的位置为原字符串的对应位置。（毕竟以后得到的所有字符都是由原字符串复制粘贴得到的）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200005
using namespace std;
int k,m,n,ans[];
int a[maxn],b[maxn],c[maxn];
char s[maxn];
int main()
{
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
cin>>k>>m;
scanf("%s",s+);
cin>>n;
for (int i=;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for (int i=;i<=k;i++)
ans[i]=i;//在第i位置的字符在哪个位置
for (int i=n;i>=;i--)
for (int j=;j<=k;j++)
{
if (ans[j]<=c[i]) continue;//< = 在c[i]前面没有影响
else if (ans[j]<=c[i]+b[i]-a[i])//粘贴过来的 ，还原为原位置
ans[j]=ans[j]-c[i]+a[i];
else ans[j]-=b[i]-a[i];//右移后的，还原为原位置
}
for (int i=;i<=k;i++)
putchar(s[ans[i]]);//putchar 的使用
return ;
}
第二题：愉快的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 | |
| 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 | ||
| 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)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1200005
using namespace std;
int k,f[(maxn<<)][],n,ki,ans=;
char c[(maxn<<)];
int main()
{
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
cin>>k;
n=(<<(k<<));
for (int i=;i<=n;i++)
{
char s=getchar();
while (s!='J'&&s!='O'&&s!='I') s=getchar();
c[i]=s;c[i+n]=s;
}
for (int i=;i<=(n<<);i++)//前缀和
{
f[i][]=f[i-][];
f[i][]=f[i-][];
f[i][]=f[i-][];
if (c[i]=='J') f[i][]++;
else if (c[i]=='O') f[i][]++;
else f[i][]++;
}
ki=(<<((k-)<<));
for (int i=;i<=n;i++)
{
int cur=ki,sum=,tmp=i;
while (cur)
{
sum+=f[tmp+cur-][]-f[tmp-][];
sum+=f[tmp+cur*-][]-f[tmp+cur-][];
sum+=f[tmp+cur*-][]-f[tmp+*cur-][];
tmp+=cur*;
cur=(cur>>);
}
ans=min(ans,n-sum-);
}
printf("%d",ans);
return ;
}