题解归档 - cf2230B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2230B
• 本地来源：problems/cf2230B/idea.md
• 题目链接：https://codeforces.com/contest/2230/problem/B
• 原始标题：cf2230B

思路

cf2230B

pattern: forbidden subsequence by divisibility modulo 4.

claim: The maximum safe remaining subsequence has the form: some kept 2s from a prefix, followed by some kept 1/3 digits from the suffix. Answer is n minus the best such length.

necessary: A one-digit 4 is divisible by 4, so every 4 must be deleted. Among digits 1,2,3, the only two-digit multiples of 4 are 12 and 32, so a kept 1 or 3 cannot appear before a kept 2.

sufficient: If all kept 2s are before all kept 1/3 digits and no 4 is kept, then no non-empty subsequence can be divisible by 4: single digits are not multiples of 4, and every two-or-more-digit number has last two digits not equal to 12 or 32.

brute/check: For small strings enumerate all subsequences to find the maximum one with no divisible-by-4 subsequence, then compare against all split positions.

edge: Empty string after deleting everything is allowed.

代码

来源：problems/cf2230B/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
char s[maxn+5];
ll pre[maxn+5],suf[maxn+5];
int main(){
    ll t,n,i,cur,ans;
    scanf("%lld",&t);
    while(t--){
        scanf("%s",s+1);
        n=strlen(s+1);
        pre[0]=0;
        for(i=1;i<=n;i++){
            pre[i]=pre[i-1];
            if(s[i]=='2') pre[i]++;
        }
        suf[n+1]=0;
        for(i=n;i>=1;i--){
            suf[i]=suf[i+1];
            if(s[i]=='1' or s[i]=='3') suf[i]++;
        }
        ans=0;
        for(i=0;i<=n;i++){
            cur=pre[i]+suf[i+1];
            if(cur>ans) ans=cur;
        }
        printf("%lld\n",n-ans);
    }
    return 0;
}