/** 题目：C. Divide by Six 链接：https://oj.ejq.me/problem/24 题意：给定一个数，这个数位数达到1e5,可能存在前导0.问为了使这个数是6的倍数，且没有前导0，删除尽量少的位数，可以任意位置删除。 输出剩余的位数。如果找不到，输出-1s。 思路： 一开始心想，这么多个位置，又不知道删除几个，排列组合的情况下，简直不可能完成。 这题是我的队友tzq想出来的。在此重新思考一下。 常规想法不可能完成。一定存在某些特殊的地方。观察题目要求，6的倍数。一个数是6的倍数有什么特殊性？ 尾数一定是偶数。那么枚举尾数为偶数，仍然很大。 假设确定了一定是2的倍数，那么只要判断是否是3的倍数就行了。而判断一个数是否是3的倍数，只要各个数位的和是3的倍数这个数就一定是3的倍数。很容易证明。 如果找到一个尾数为偶数，且从它为尾的数%3==0.那么这个可能是答案。 %3==1.那么要删除一个某个位的数%3==1的位。或者删除两个数位上的数%3==2的位。为了避免删除后出现前导0，为了答案最优，从右边开始找。如果找不到，所以这种情况无解。 如果删除后出现前导0，去掉前导0，不会有影响。注意把数删完了的情况。此时无解。 %3==2.那么删除一个某个位的数%3==2的位，或者删除两个数位上的数%3==1的位，同上。 问题是：尾数为偶数有很多种情况。我们知道为了让剩余的位数越来越多。所以选择尾数为偶数应该尽量右才好。 如果某两个位作为尾数。以他们为尾数的数%3==0，则显然取尾数更右的更优。 同理%3==1, %3==2，都是选更右的更优，这样删除的选择更多，且剩余的数位也更多。 至此，本体解法为分析+模拟。 细节：只要有前导0，肯定有答案。即剩余的数位0.那么输出1； */ #include<bits/stdc++.h> #define LL long long using namespace std; typedef long long ll; const int maxn = 1e5+100; char s[maxn]; int r[maxn]; int rr[maxn]; char temp[maxn]; int r0, r1, r2;///%3==0, %3==1, %3==2的尾数位置。 int leadzero, len, ans; int getR(int type) { for(int i = len-1; i>=0 ; i--){ if(r[i]==type&&(s[i]-'0')%2==0){ return i; } } return -1; } void f(int r,int type) { if(r==-1) return ; ///type==1 if(type==1) { /// 删除一个1 for(int i = r; i >= 0&&r>0; i--){ if(rr[i]==1){ if(i==0){ int t = i+1; while(t<=r&&temp[t]=='0'){ t++; } if(t>r){ ans = max(ans,1); }else { ans = max(ans,r-t+1); } }else { ans = max(ans,r); } } } /// 删除两个2 int cnt = 2, pos = -1; char tt; for(int i = r; i >= 0&&r>1; i--){ if(rr[i]==2){ cnt--; if(cnt==0){ if(i==0){ int t = i+1; while(t<=r&&temp[t]=='0'){ t++; } if(t>r){ ans = max(ans,1); }else { ans = max(ans,r-t+1); } }else { ans = max(ans,r); } }else { pos = i; tt = temp[i]; temp[i]='0'; } } } if(pos!=-1) temp[pos] = tt; }else ///type==2 { ///删除一个2 for(int i = r; i >= 0&&r>0; i--){ if(rr[i]==2){ if(i==0){ int t = i+1; while(t<=r&&temp[t]=='0'){ t++; } if(t>r){ ans = max(ans,1); }else { ans = max(ans,r-t+1); } }else { ans = max(ans,r); } } } ///删除两个1 int cnt = 2, pos = -1; char tt; for(int i = r; i >= 0&&r>1; i--){ if(rr[i]==1){ cnt--; if(cnt==0){ if(i==0){ int t = i+1; while(t<=r&&temp[t]=='0'){ t++; } if(t>r){ ans = max(ans,1); }else { ans = max(ans,r-t+1); } }else { ans = max(ans,r); } }else { pos = i; tt = temp[i]; temp[i]='0'; } } } if(pos!=-1) temp[pos] = tt; } } int main() { while(scanf("%s",s)==1) { r0 = r1 = r2 = -1; leadzero = 0; while(s[leadzero]!=' '&&s[leadzero]=='0'){ leadzero++; } if(s[leadzero]==' '){ printf("1 "); continue; } if(leadzero>0) ans = 1;///只要有前导0，那么肯定可以一个0作为结果。 strcpy(temp,s+leadzero); // printf("temp = %s ", temp); strcpy(s,temp); len = strlen(s); int p = 0; for(int i = 0; s[i]!=' '; i++){ p = p+(s[i]-'0'); p %= 3; r[i] = p; rr[i] = (s[i]-'0')%3; } ans = -1; r0 = getR(0); if(r0!=-1) ans = r0+1; r1 = getR(1); r2 = getR(2); f(r1,1); //strcpy(temp,s); f(r2,2); if(ans!=-1){ printf("%d ",ans); }else printf("-1s "); } return 0; }