codeforces792C 2000分 分类讨论

题目传送门

题意：

没有前导0的n位十进制数，让你去掉尽可能少的若干位，使剩余十进制数是3的倍数。

限制：剩余的数不能有前导0，但可以是0。

数据范围：$\dpi{150} 1 \leqslant n \leqslant 10^5$ 。

题解：

一个数是3的倍数，那么该数的十进制位累加后是3的倍数。

数论知识就用到了上面这句话，然后就是下面的分类讨论。

（1）如果这个数是3的倍数，那么不变就行了。

（2）如果这个数模3余1，那么你删除靠后的1个1或者2个2，比较一下删除哪一个剩余位数更大。

（3）如果这个数模3余2，那么你删除靠后的1个2或者2个1，比较一下删除哪一个剩余位数更大。

注意：考虑前导0，以及考虑剩余数为0。

感受：

细节考虑有问题，以及少考虑一种情况 。

一直在面向数据编程。

虽说我是看数据修改过后才过的，但是我不懂这道题为什么有2000分，1600分差不多吧。

一点也不难，就是分类讨论一下就好。

代码： 

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef pair<int , int> pii ;
const int maxn = 1e5 + 5 ;
int len , num[5] ;
int sum = 0 ;
char s[maxn] ;
bool vis[maxn] ;
bool wujie()
{
	if(num[0] + num[3] > 0)  return 0 ;
	if(num[1] >= 3 || num[2] >= 3)  return 0 ;
	if(num[1] >= 1 && num[2] >= 1)  return 0 ;
	return 1 ;
}
int djian1()
{
	bool flag = 0 ;
	int cnt = 0 ;
	if(num[1] == 0)  return -1 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	  if((s[i] - '0') % 3 == 1)  {vis[i] = 1 ; break ;}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		cnt ++ ;
	}
	return cnt ;
}
void ddojian1()
{
	int cnt = 0 ;
	bool flag = 0 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	  if((s[i] - '0') % 3 == 1)  {vis[i] = 1 ; break ;}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		printf("%c" , s[i]) ;
	}
	if(!flag)  printf("0") ;
	printf("\n") ;
}
int djian2()
{
	int cnt = 0 ;
	bool flag = 0 ;
	int cas = 2 ;
	if(num[2] < 2)  return -1 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	{
	   if((s[i] - '0') % 3 == 2)  vis[i] = 1 , cas -- ;
	   if(cas == 0)  break ;	
	}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		cnt ++ ;
	}
	return cnt ;
}
void ddojian2()
{
	int cnt = 0 ;
	bool flag = 0 ;
	int cas = 2 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	{
	   if((s[i] - '0') % 3 == 2)  vis[i] = 1 , cas -- ;
	   if(cas == 0)  break ;	
	}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		printf("%c" , s[i]) ;
	}
	if(!flag)  printf("0") ;
	printf("\n") ;
}
void solve1()
{
	int x = djian2() ;
	int y = djian1() ;
	if(x >= y)  ddojian2() ;
	else  ddojian1() ;
}
int jian2()
{
	bool flag = 0 ;
	int cnt = 0 ;
	if(num[2] == 0)  return -1 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	  if((s[i] - '0') % 3 == 2)  {vis[i] = 1 ; break ;}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		cnt ++ ;
	}
	return cnt ;
}
void dojian2()
{
	int cnt = 0 ;
	bool flag = 0 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	  if((s[i] - '0') % 3 == 2)  {vis[i] = 1 ; break ;}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		printf("%c" , s[i]) ;
	}
	if(!flag)  printf("0") ;
	printf("\n") ;
}
int jian1()
{
	int cnt = 0 ;
	bool flag = 0 ;
	int cas = 2 ;
	if(num[1] < 2)  return -1 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	{
	   if((s[i] - '0') % 3 == 1)  vis[i] = 1 , cas -- ;
	   if(cas == 0)  break ;	
	}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		cnt ++ ;
	}
	return cnt ;
}
void dojian1()
{
	int cnt = 0 ;
	bool flag = 0 ;
	int cas = 2 ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = len - 1 ; i >= 0 ; i --)
	{
	   if((s[i] - '0') % 3 == 1)  vis[i] = 1 , cas -- ;
	   if(cas == 0)  break ;	
	}
	for(int i = 0 ; i < len ; i ++)
	{
		if(vis[i] || !flag && s[i] == '0')  continue ;
		flag = 1 ;
		printf("%c" , s[i]) ;
	}
	if(!flag)  printf("0") ;
	printf("\n") ;
}
void solve2()
{
	int x = jian2() ;
	int y = jian1() ;
	if(x >= y)  dojian2() ;
	else  dojian1() ;
}
int main()
{
	scanf("%s" , s) ;
	len = strlen(s) ;
	memset(num , 0 , sizeof(num)) ;
	memset(vis , 0 , sizeof(vis)) ;
	for(int i = 0 ; i < len ; i ++)
	{
		int x = s[i] - '0' ;
		sum += x , sum %= 3 ;
		if(x == 0){num[0] ++ ; continue ;}
		x %= 3 ;
		if(x == 0) x = 3 ;
		num[x] ++ ;	
	}
	if(wujie())  printf("-1\n") ;
	else if(sum == 0)  printf("%s\n" , s) ;
	else if(sum == 1)  solve1() ;
	else solve2() ;
	return 0 ;
}