题目描述

输入一个数字（数字位数 $n \le 10^5$）, 定义数位段为：本数字其中的连续一段，最少1位，也可以是其本身。比如对 1765 来说，176,765,5,76这些数字都是它的数位段。

我们要做的，就是找到其中最大的能够被3整除的数位段。保证一定有解。

输入

一个数字

输出

其能够被3整除的最大数位段

样例输入

1781

样例输出

81

提示

数位长度n：

对于 $30\%$ 的数据，$n\le18$

对于 $50\%$ 的数据，$n\le10^3$

对于 $100\%$ 的数据，$n\le10^5$

代码

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
namespace kkk{
	string s;
	int q[100005];
	int b1,l1,b0,l0,b2,l2; 
	bool operator>(string x,string y){
		if(x.size()!=y.size())return x.size()>y.size();
		else{
			for(int i=0;i<x.size();i++){
				if(x[i]!=y[i])return x[i]>y[i];
			}
		}
	}
	bool operator>=(string x,string y){
		return x>y||x==y;
	}
	string qwq(string x){
		string l="";
		int v=0;
		for(int i=0;i<x.size();i++){
			if(x[i]!='0')v=1;
			if(v)l=l+x[i];
		}
		return l;
	}
	void solve(){
		cin>>s;s=' '+s;
		for(int i=0;i<s.size()-1;i++){
			q[i+1]=q[i]+s[i+1]-'0';
		}
		for(int i=0;i<s.size();i++){
			if(q[i]%3==0){
				l0=i;
			}if(q[i]%3==1){
				l1=i;
				if(b1==0)b1=i+1;
			}if(q[i]%3==2){
				l2=i;
				if(b2==0)b2=i+1;
			}
		}
		string l="0";
		l=s.substr(b0+1,l0);
		string l12="0";
		if(b1!=0&&b1<=l1)l12=s.substr(b1,l1-b1+1);
		string l23="0";
		if(b2!=0&&b2<=l2)l23=s.substr(b2,l2-b2+1);
		l=qwq(l);l12=qwq(l12);l23=qwq(l23); 
		if(l>=l12&&l>=l23)cout<<l;
		if(l12>=l&&l12>=l23)cout<<l12;
		if(l23>=l12&&l23>=l)cout<<l23;
		
	}
}
signed main(){
	int Q=1;
//	cin>>Q;
	while(Q--)kkk::solve();
	return 0;
}