codeforce 792C - Divide by Three（思维）

A positive integer number n is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a beautifulnumber by erasing some of the digits, and you want to erase as few digits as possible.

The number is called beautiful if it consists of at least one digit, doesn't have leading zeroes and is a multiple of 3. For example, 0, 99,10110 are beautiful numbers, and 00, 03, 122 are not.

Write a program which for the given n will find a beautiful number such that n can be transformed into this number by erasing as few digits as possible. You can erase an arbitraty set of digits. For example, they don't have to go one after another in the number n.

If it's impossible to obtain a beautiful number, print -1. If there are multiple answers, print any of them.

Input

The first line of input contains n — a positive integer number without leading zeroes (1 ≤ n < 10100000).

Output

Print one number — any beautiful number obtained by erasing as few as possible digits. If there is no answer, print  - 1.

题意:有一个串，叫你删除最少的数字使得这个串代表的数能够被3整除，注意结果不能有前导零。

满足情况下要么删一个，要么删两个，当输入的长度为1或2时特殊判断，因为怕全被删除没了。

接下来以为有前导零，所以贪心逆着来。

AC代码：

 

#include <stdio.h> #include <iostream> #include<vector> #include <string.h> using namespace std; char a[100010]; int length; vector<int> v[10]; void print(int cur1, int cur2){//删除cur1， cur2位置后输出 if(cur1!=-1){ a[cur1]='0'; } if(cur2!=-1){ a[cur2]='0'; } int k=0; while(a[k]=='0'){ k++; if(k==length){ break; } } if(k==length){ printf("0"); } else{ for(int i=k; i<length; i++){ if(i==cur1||i==cur2){ continue; } printf("%c", a[i]); } } } int calc(int cur1, int cur2){ //删除cur1， cur2位置后判断删除了多少个，因为出现前导零是要去掉的 char c1, c2; if(cur1!=-1){ c1=a[cur1];a[cur1]='0'; } if(cur2!=-1){ c2=a[cur2];a[cur2]='0'; } int k=0; while(a[k]=='0'){ k++; if(k==length){ break; } } if(k==length){ if(cur1!=-1)a[cur1]=c1; if(cur2!=-1)a[cur2]=c2; return length-1; } else{ int cnt=0; for(int i=k; i<length; i++){ if(i==cur1||i==cur2){ continue; } cnt++; } if(cur1!=-1)a[cur1]=c1; if(cur2!=-1)a[cur2]=c2; return length-cnt; } } int main(){ int i, j, k; scanf("%s", &a); length=strlen(a); if(length==1){//长度为一特判 if((a[0]-'0')%3==0){ printf("%s", a);return 0; } else{ printf("-1");return 0; } } if(length==2){//长度为2特判 if((a[0]-'0'+a[1]-'0')%3==0){ printf("%s", a);return 0; } else{ if((a[0]-'0')%3==(a[0]-'0'+a[1]-'0')%3){ printf("%c", a[1]);return 0; } else if((a[1]-'0')%3==(a[0]-'0'+a[1]-'0')%3){ printf("%c", a[0]);return 0; } else{ printf("-1");return 0; } } } int sum=0; for(i=0; i<length; i++){ sum=(sum+a[i]-'0')%3; v[(a[i]-'0')%3].push_back(i); } if(sum==0){ printf("%s", a);//恰好整除 } else{ for(i=length-1; i>=1; i--){//贪心从后往前 if((a[i]-'0')%3==sum){ print(i, -1); return 0; } } int Min1=2000000000;//表示删除第一个总的要删除的位数，注意不能出现前导零 if((a[0]-'0')%3==sum){//因为刚好是第一个，所以先别急，与删除两个的情况比较一下。 //cout<<Min1<<'\n'; Min1=calc(0, -1); } int Min2=2000000000;//表示删除两个最少要删除的位数 if(v[sum^3].size()>=2){//贪心从后往前 Min2=calc(v[sum^3][v[sum^3].size()-2], v[sum^3][v[sum^3].size()-1]); } if(Min2==2000000000&&Min1==2000000000){ printf("-1"); } else{ if(Min1<=Min2){ print(0, -1); } else { print(v[sum^3][v[sum^3].size()-2], v[sum^3][v[sum^3].size()-1]); } } } return 0; }