目录

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());
        }
    }
}