P8932 [JRKSJ R7] Clock Paradox 题解

· · 题解

题意

给定一个字符串 S=\overline{s_1s_2\dots s_n}，有另一个字符串 T=S。可以进行若干次操作，每次选择 T 的一段字串插入 T 的任意位置，希望能用最少的操作次数使 T=\overline{s_1s_1s_2s_2\dots s_ns_n}。同时还有 q 次改变，每次改变会把 S 的第 p 个字符改为 c。

题目希望你求出初始的 S 和每次改变后的 S 最少用几次操作能变为 T。

思路

我们定义 S 的段数 x 为连续的相同字符组成的段的数量。例如当 S=aaabbbcca 时，S 的段数为 4，分别为 aaa,bbb,cc,a。

不难看出，每次操作可以使 S 中的连续两段变为最终状态。还是用 S=aaabbbcca 举例子，第一次操作可以选择 aaabbb ，插入到 aaa 和 bbb 的中间，变成 aaaaaabbbbbbcca，第二次选择 cca，插入cc 和 a 的中间，就变成 aaaaaabbbbbbccccaa，即操作数为 2 次。

总结一下，f(S)=\lceil \frac{x}{2} \rceil，即查询的时间复杂度是 O(1)。

然后来考虑修改，先预处理 S 的段数，复杂度 O(|S|)。第 i 次修改会把第 p_i 个字符改成 c_i。那我们只要分类讨论 p_i 与 p_i+1 和 p_i-1 的字符之间的关系就可以了。有以下几种情况：

  1. 如果 p_i 和 p_i-1 本来不同，但修改后相同了，那么段数减 1。
  2. 如果 p_i 和 p_i+1 本来不同，但修改后相同了，那么段数减 1。
  3. 如果 p_i 和 p_i-1 本来相同，但修改后不同了，那么段数加 1。
  4. 如果 p_i 和 p_i+1 本来相同，但修改后不同了，那么段数加 1。

这样可以做到 O(1) 的修改，总的时间复杂度是 O(|S|+q)。

还要注意，用 cin 和 cout 输入输出会超时，要用 scanf 和 printf。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int q,cnt,len;
char s[3000009];
void solve(){
    len=1;
    cnt=1;
    while(s[len]>='a'&&s[len]<='z'){
        if(s[len]!=s[len-1])  cnt++;
        len++;
    }
    len--;
    return ;
}
void change(int pos,char c){
    if(pos==0){
        if(s[0]!=s[1]&&c==s[1])  cnt--;
        if(s[0]==s[1]&&c!=s[1])  cnt++;
    }
    else if(pos==len){
        if(s[pos]!=s[pos-1]&&c==s[pos-1])  cnt--;
        if(s[pos]==s[pos-1]&&c!=s[pos-1])  cnt++;
    }
    else{
        if(s[pos]!=s[pos-1]&&s[pos]!=s[pos+1]&&c==s[pos-1]&&c==s[pos+1])  cnt-=2;
        if(s[pos]==s[pos-1]&&s[pos]==s[pos+1]&&c!=s[pos-1]&&c!=s[pos+1])  cnt+=2;
        if(s[pos]!=s[pos-1]&&s[pos]!=s[pos+1]&&c==s[pos-1]&&c!=s[pos+1])  cnt-=1;
        if(s[pos]!=s[pos-1]&&s[pos]!=s[pos+1]&&c!=s[pos-1]&&c==s[pos+1])  cnt-=1;
        if(s[pos]==s[pos-1]&&s[pos]!=s[pos+1]&&c!=s[pos-1]&&c!=s[pos+1])  cnt+=1;
        if(s[pos]!=s[pos-1]&&s[pos]==s[pos+1]&&c!=s[pos-1]&&c!=s[pos+1])  cnt+=1;
    }
    s[pos]=c;
    return ;
}
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(ll x)
{
    if (x<0){putchar('-'); x = -x;}
    if (x>9)write(x / 10);
    putchar(x % 10 + '0');
}
int main(){
    q=read();
    scanf("%s",&s);
    solve();
    write((cnt+1)/2);
    putchar('\n');
    for(int i=1;i<=q;i++){
        int p;
        char c,tmp;
        p=read(),c=getchar(),tmp=getchar();
        change(p-1,c);
        write((cnt+1)/2);
        putchar('\n');
    }
    return 0;
}