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

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e5 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e6 + 10;

int main() {
    int t;
    cin >> t;
    while (t --) {
        string s;
        cin >> s;
        //根据数据范围可知用o(n^2)
        int n = s.size();
        s = ' ' + s;
        ll sum = 0;
        int c0 = 0, c1 = 0, c2 = 0, c3 = 0;

        for (int i = 1; i <= n; i ++) {
            sum += (int)(s[i] - '0');
            int o = s[i] - '0';
            if (o == 0) c0 ++;
            if (o % 3 == 1) c1 ++;
            if (o % 3 == 2) c2 ++;
            if (o % 3 == 0 && o != 0) c3 ++;
        }
        if (sum % 3 == 0) { //如果是3的倍数首先去0
            if (c1 || c2) cout << c3 + c0 << endl; //确保大于0
            else cout << c0 + c3 - 1 << endl;
        } else {
            //先去掉一个//换成三的倍数去掉前导0之后在按照上述规律
            if (sum % 3 == 1) {
                if (c1) {
                    int ss = 0;//记录和
                    int f = 0;//标记一下
                    for (int i = n; i >= 1; i --) { //从后往前，避免前导0
                        int o = s[i] - '0';
                        if (o % 3 == 1) {
                            f = i;
                            break;
                        }
                    }//记录是不是首位
                    c1 --;
                    if (f == 1) {
                        for (int i = 2; i <= n; i ++) {
                            if (s[i] == '0') c0 --;
                            else break;
                        }
                        if (c1 || c2) cout << c3 + c0 + 1 << endl;
                        else cout << c0 + c3 << endl;
                    } else {
                        if (c1 || c2) cout << c3 + c0 + 1 << endl;
                        else cout << c0 + c3 << endl;
                    }
                } else cout << 0 << endl;
            }
            if (sum % 3 == 2) {
                if (c2) {
                    int ss = 0;//记录和
                    int f = 0;//标记一下
                    for (int i = n; i >= 1; i --) { //从后往前，避免前导0
                        int o = s[i] - '0';
                        if (o % 3 == 2) {
                            f = i;
                            break;
                        }
                    }//记录是不是首位
                    c2 --;
                    if (f == 1) {
                        for (int i = 2; i <= n; i ++) {
                            if (s[i] == '0') c0 --;
                            else break;
                        }
                        if (c1 || c2) cout << c3 + c0 + 1 << endl;
                        else cout << c0 + c3 << endl;
                    } else {
                        if (c1 || c2) cout << c3 + c0 + 1 << endl;
                        else cout << c0 + c3 << endl;
                    }
                } else cout << 0 << endl;
            }
        }
    }
    return 0;
}