目录
Divide by Three：
题目大意：
编辑编辑思路解析：
代码实现：
Divide by Three：
题目大意：
思路解析：
一个数字是3的倍数，那么他的数位之和也是3的倍数，所以我们可以O(N)的得到这个数字数位之和模3的结果，如果模3为0，则这个数就是一个美丽的数，如果模3不为0，则他需要取除某些数字.
那我们想它最多去除几个数字，最多取除两个，因为在模3系统下，任意1-9的数都会等价与1-2，当总体剩下1时，只要有1就删除1，否则就删除两个2，当总体剩下2时，只要有2就删除2，否则就删除两个1，这里删除的1和2是等价的1和2.
删除之后我们比较这两个情况那个更优秀，删除时从后往前删，因为如果从前往后删，我们还需要考虑删除这个数，后面的是否会变成前缀为0，但是如果从后往前删，就不需要考虑，除非它只能删除这个数使得前缀为0。
还有特殊情况，删除后没数字剩余了，或者删除后只剩下0了；
代码实现：
import java.beans.IntrospectionException;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
static int tot = 0;
static int maxn = 123460;
static int[][] ch;
static int[] tag;
static long ans = 0;
static long[] sum = new long[maxn];
static int[] arr = new int[maxn];
static HashMap<Integer, ArrayList<Integer>> map;
static int k;
public static void main(String[] args) throws IOException {
char[] s = f.next().toCharArray();
int n = s.length;
int sum = 0;
int[] cnt = new int[3];
for (int i = 0; i < n; i++) {
sum = (sum + s[i] - '0') % 3;
cnt[(s[i] - '0') % 3]++;
}
if (sum == 0){
for (int i = 0; i < n; i++) {
w.print(s[i]);
}
w.flush();
w.close();
return;
}
char[] ans = new char[n];
char[] res = new char[n];
int p = 0;
int q = 0;
if (sum == 1){
if (cnt[1] >= 1){
int tag = 1;
for (int i = n-1; i >= 0; i--) {
if ((s[i] - '0') % 3 == 1 && tag >= 1){
tag--;
}else ans[p++]= s[i];
}
}
if (cnt[2] >= 2){
int tag = 2;
for (int i = n-1; i >= 0; i--) {
if ((s[i] - '0') % 3 == 2 && tag >= 1){
tag--;
}else res[q++]= s[i];
}
}
}else {
if (cnt[1] >= 2){
int tag = 2;
for (int i = n-1; i >= 0; i--) {
if ((s[i] - '0') % 3 == 1 && tag >= 1){
tag--;
}else ans[p++]= s[i];
}
}
if (cnt[2] >= 1){
int tag = 1;
for (int i = n-1; i >= 0; i--) {
if ((s[i] - '0') % 3 == 2 && tag >= 1){
tag--;
}else res[q++]= s[i];
}
}
}
int flag1 = 0, flag2 = 0;
while (p >= 1 && ans[p - 1] == '0') {p--; flag1 = 1;}
while (q >= 1 && res[q - 1] == '0') {q--; flag2 = 1;}
if (flag1 == 1 && p == 0) ans[p++] ='0';
if (flag2 == 1 && q == 0) res[q++] ='0';
if (p == 0 && q == 0) w.println(-1);
else {
if (q > p){
for (int i = q - 1; i >= 0; i--) {
w.print(res[i]);
}
}else {
for (int i = p - 1; i >= 0; i--) {
w.print(ans[i]);
}
}
}
w.flush();
w.close();
}
public static void get(int x, int r, int p , int cur, long res){
if (res >= k && tag[p] == 1){
ArrayList<Integer> list = map.get(p);
for (Integer l : list) {
ans = Math.max(ans, (sum[r] - sum[l - 1]) / (r - l + 1));
}
}
if (cur < 0)return;
int c = (x >> cur) & 1;
if (ch[p][1 - c] != 0 && res + (1L << (cur + 1)) - 1>= k) get(x, r, ch[p][1 - c], cur-1, res + (1L <<cur));
if (ch[p][c] != 0 && res + (1L << (cur)) - 1 >= k) get(x, r, ch[p][c], cur-1, res);
}
public static void insert(int x, int id){
int p = 0;
for (int i = 30; i >= 0; i--) {
int c = ((x >> i) & 1);
if (ch[p][c] == 0) ch[p][c] = ++ tot;
p = ch[p][c];
}
tag[p] = 1;
if (map.containsKey(p)){
ArrayList<Integer> list = map.get(p);
list.add(id);
}else {
ArrayList<Integer> list = new ArrayList<>();
list.add(id);
map.put(p, list);
}
}
public static long qkm(long a, long mod){
long res = 1;
long b = mod - 2;
while(b > 0){
if ((b & 1) == 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
static Input f = new Input(System.in);
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Input {
public BufferedReader reader;
public StringTokenizer tokenizer;
public Input(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
String str = null;
try {
str = reader.readLine();
} catch (IOException e) {
// TODO 自动生成的 catch 块
e.printStackTrace();
}
return str;
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
public BigInteger nextBigInteger() {
return new BigInteger(next());
}
}
}