[ABC313E] Duplicate 题解

考虑什么时候无解。显然如果有两个相邻字符都不等于

1

一定无解。举最简单的例子

22

，这个串不管怎么删长度都不会减少；可以看出如果比它数字更大的串的长度会不减可能还反增。

那么其他情况是否都是有解的？答案是肯定的。考虑这样的字符串有什么性质：它必然是由单个大于

1

的数字和数字

1

的极长连续段构成。每次删掉最后一个大于

1

的数后（如果是），最后一个

1

连续段的长度就不会变了，一个一个删掉即可；而且因为每个大于

1

的数字后面的数都是

1

，所以它不会变多只会在接下来的操作内被删掉。如此往复一个串必然可以被删完。

至于计数，考虑一次操作会对每个

1

连续段造成什么影响。显然的如果一个

1

连续段后面的数字是

d

（如果有），一次操作内它的长度就会增加

d-1

（相当于把最后

1

个

1

替换成

d

个

1

），设当前已经进行了

c

次操作那么它的长度就增加了

c(d-1)

。用一个指针从右往左扫，扫到一个大于

1

的数就考虑前面的极长

1

连续段长度增加了多少。

注意特判最后一段

1

的连续段后没有大于

1

的数字的情况。因为长度删到

1

就结束，所以指针只要扫到

S_1

就不用统计答案了。

放代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,c=0; string s; cin>>n>>s;
  for(int i=1;i<n;i++)
    if(min(s[i],s[i-1])>49)
      cout<<"-1\n",exit(0); // 判断无解
  int r=n-1;
  while(r>0){
    if(r>0&&s[r]>49){
      (++c)%=mod; // 加上删除它本身一位的贡献
      int x=0,d=s[r]-48; r--;
      while(r>0&&s[r]==49)r--,x++; // 找极长 1 连续段
      (c+=c*(d-1)%mod+x%mod)%=mod; // 算贡献
    }
    else while(r>0&&s[r]==49)r--,(++c)%=mod; // 特判
  }
  cout<<c<<endl;
  return 0;
}

[ABC313E] Duplicate 题解

文章操作

相关推荐

评论

[ABC313E] Duplicate 题解