题解 | #小红的数字删除#

#include<bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin>>tt;
    while(tt--){
        string n;
        cin>>n;
        vector<int>p(10),dis(10);//p存每位数字（mod3）出现的最后一位，dis存每位数字（mod3）的个数
        int sum=0,ans=0,num0=0;//sum存各个数位上的数的和，ans：答案
        for(int i=0;i<(int)n.size();i++){
            p[(n[i]-'0')%3]=i;
            sum+=n[i]-'0';
            dis[(n[i]-'0')%3]++;
        }
        int k=sum%3;
        if(!k){//该数本身就是3的倍数，只能删除dis[0]的情况，注意当所有数位mod3都为0时要保留一位
            if(dis[0]==n.size())
            dis[0]--;
            ans+=dis[0];
        }
        else if(dis[k]){//不是3的倍数时，先删除一位与（sum%3）同余的数位
            if(p[k]==0){//如果最后一个在第一位，要把后面的0（即删除第一位后的前导0）去除
                int i=1;
                while(n[i]=='0'){//去除紧接的0
                    dis[0]--;
                    i++;
                    num0++;//记录删除的0的个数
                }
            }
            if(1+num0+dis[0]==n.size())//保留一位
            ans--;
            ans+=dis[0]+1;
        }
        cout<<ans<<endl;
    }
}