题意简述
给定一个由A C G T四个字母组成的密码锁(每拨动一次 A变C C变G G变T T变A)
密码锁有n位 规定每次操作可以选取连续的一段拨动1~3次
问最少几次操作可以将初始状态变到末状态
并且把每次操作输出
(此题有spj)
---------------------------------------------------------------------------------------------------------
为了方便叙述 所有没有明确说明的位置均是在$mod4$意义下的
首先我们显然可以明白一个性质 操作顺序是没关系的
有关系的只是每个位置被拨动的次数
比赛的时候一开始想的是比较随意的贪心 然而是有反例的
最后剩下30min的时候 从数据范围想到了区间Dp
然而这题并不是一般的区间Dp
最小操作数好求然而操作方案难以记录
补题的时候 最终又去想象有没有什么更好的贪心思路
---------------------------------------------------------------------------------------------------------
我们用一个高度数组h记录从初始状态到末状态每个位置需要拨动的次数
比如样例
AGGTCAT
AAACTAA
高度数组h便是 0222201
我们再定义一个delta数组 代表所有的$h[i]-h[i-1]$
那么从$1$到$n+1$delta数组的值便是 02000213
(这样的构造类似与用树状数组维护区间加减值的做法 不过这种思想的具体名称我也不知道)
显然我们每次最优可以将两个2变为0 或者将一个1和一个3变为0
于是这样就可以做了?
然而只是这样做的话会RE11
---------------------------------------------------------------------------------------------------------
比如这样一个样例
AA
GT
高度数组h为 23
delta数组为 211
于是并不能找出两个2或者一个1一个3来配对消除
既然无法一次消两个 我们就一次消一个吧
不过显然是不能使一些已经消除的部分又出现
所以直接找两个非0的进行处理 把其中一个变为0就好了
(注意到delta数组之和为0 所以最后一定不会只剩下一个非0的)
#include <bits/stdc++.h>
using namespace std;
const int N=;
char s1[N],s2[N];
int h[N],delta[N],cnt[];
int L[N],R[N],d[N];
int n,ans;
int main()
{
#ifdef ONLINE_JUDGE
freopen("transform.in","r",stdin);
freopen("transform.out","w",stdout);
#endif
scanf("%s%s",&s1[],&s2[]);
n=strlen(&s1[]);
for(int i=;i<=n;++i)
{
if(s1[i]=='A')
h[i]=-;
else if(s1[i]=='C')
h[i]=-;
else if(s1[i]=='G')
h[i]=-;
else
h[i]=-;
if(s2[i]=='A')
h[i]+=;
else if(s2[i]=='C')
h[i]+=;
else if(s2[i]=='G')
h[i]+=;
else
h[i]+=;
h[i]=h[i]<?h[i]+:h[i];
}
for(int i=;i<=n+;++i)
{
delta[i]=(h[i]-h[i-]+)%;
cnt[delta[i]]++;
}
while(cnt[]!=n+)
{
++ans;
int i=;
while(!delta[i])
++i;
int j=i+;
while(delta[j]+delta[i]!=&&j<=n+)
++j;
if(j<=n+)
{
L[ans]=i;
R[ans]=j-;
d[ans]=delta[i];
cnt[delta[i]]--;
cnt[delta[j]]--;
cnt[]+=;
delta[i]=delta[j]=;
}
else
{
j=i+;
while(!delta[j])
++j;
L[ans]=i;
R[ans]=j-;
d[ans]=delta[i];
cnt[delta[i]]--;
cnt[delta[j]]--;
cnt[]++;
cnt[(delta[j]+delta[i])%]++;
delta[j]=(delta[j]+delta[i])%;
delta[i]=;
}
}
printf("%d\n",ans);
for(int i=;i<=ans;++i)
printf("%d %d %d\n",L[i],R[i],d[i]);
return ;
}