[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 就不用统计答案了。

放代码：

#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;
}