删除最少的数位和前缀0，使得剩下的数能被3整除
等价于各数位数字之和能被3整除。
当前数位和可能是 0, 1, 2(mod 3)
0： 直接处理
1： 删除一个a[i]%3 == 1 或者 两个a[i]%3 == 2
2: 同1
对于删完的数列，去掉前置0（只剩前置0就当作0）
若删啥都不满足，则判断原数列中有没有0，不然就输出-1
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 100005; 4 char s[MAXN]; 5 int a[MAXN], n; 6 string ans, tmp; 7 int b[MAXN], m; 8 void Update() 9 { 10 tmp.clear(); 11 int i; 12 for (i = 1; i <= m && !b[i]; i++); 13 if (i < m+1) 14 { 15 for (i; i <= m; i++) 16 tmp += b[i] + '0'; 17 } 18 else if (m) 19 tmp += '0'; 20 if (ans.length() < tmp.length()) 21 ans = tmp; 22 } 23 int main() 24 { 25 scanf("%s", s); 26 n = strlen(s); 27 for (int i = 1; i <= n; i++) 28 a[i] = s[i-1] - '0'; 29 int sum = 0; 30 for (int i = 1; i <= n; i++) 31 sum = (sum+a[i]%3) % 3; 32 if (!sum) 33 { 34 m = 0; 35 for (int i = 1; i <= n; i++) 36 b[++m] = a[i]; 37 Update(); 38 } 39 else 40 { 41 int p1 = 0, p2 = 0; 42 for (int i = n; i > 0 && !p1; i--) 43 if (a[i]%3 == sum) p1 = i; 44 if (p1) 45 { 46 m = 0; 47 for (int i = 1; i <= n; i++) 48 { 49 if (i == p1) continue; 50 b[++m] = a[i]; 51 } 52 Update(); 53 } 54 p1 = p2 = 0; 55 for (int i = n; i > 0 && (!p1 || !p2) ; i--) 56 if (a[i]%3 +sum == 3) p1 ? p2 = i : p1 = i; 57 if (p1 && p2) 58 { 59 m = 0; 60 for (int i = 1; i <= n; i++) 61 { 62 if (i == p1 || i == p2) continue; 63 b[++m] = a[i]; 64 } 65 Update(); 66 } 67 } 68 if (!ans.length()) 69 { 70 bool flag = 0; 71 for (int i = 1; i <= n; i++) 72 if (!a[i]) flag = 1; 73 puts(flag? "0": "-1"); 74 } 75 else cout << ans << endl; 76 }