首页 > 代码库 > CodeForces 792C - Divide by Three [ 分类讨论 ]

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

2024-09-11 05:40:13   225人阅读

删除最少的数位和前缀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     else40     {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 }
View Code

 

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


联系
我们