CodeForces 792C - Divide by Three [ 分类讨论 ]

删除最少的数位和前缀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

 #include <bits/stdc++.h>

 using namespace std;

 const int MAXN = ;

 char s[MAXN];

 int a[MAXN], n;

 string ans, tmp;

 int b[MAXN], m;

 void Update()

 {

     tmp.clear();

     int i;

     for (i = ; i <= m && !b[i]; i++);

     if (i < m+)

     {

         for (i; i <= m; i++)

             tmp += b[i] + '';

     }

     else if (m)

         tmp += '';

     if (ans.length() < tmp.length())

         ans = tmp;

 }

 int main()

 {

     scanf("%s", s);

     n = strlen(s);

     for (int i = ; i <= n; i++)

         a[i] = s[i-] - '';

     int sum = ;

     for (int i = ; i <= n; i++)

         sum = (sum+a[i]%) % ;

     if (!sum)

     {

         m = ;

         for (int i = ; i <= n; i++)

             b[++m] = a[i];

         Update();

     }

     else

     {

         int p1 = , p2 = ;

         for (int i = n; i >  && !p1; i--)

             if (a[i]% == sum) p1 = i;

         if (p1)

         {

             m = ;

             for (int i = ; i <= n; i++)

             {

                 if (i == p1) continue;

                 b[++m] = a[i];

             }

             Update();

         }

         p1 = p2 = ;

         for (int i = n; i >  && (!p1 || !p2) ; i--)

             if (a[i]% +sum == ) p1 ? p2 = i : p1 = i;

         if (p1 && p2)

         {

             m = ;

             for (int i = ; i <= n; i++)

             {

                 if (i == p1 || i == p2) continue;

                 b[++m] = a[i];

             }

             Update();

         }

     }

     if (!ans.length())

     {

         bool flag = ;

         for (int i = ; i <= n; i++)

             if (!a[i]) flag = ;

         puts(flag? "": "-1");

     }

     else cout << ans << endl;

 }