Edu18 -- Divide by Three --- 题解

���录

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 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 = 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 list = map.get(p);            for (Integer l : list) {                ans = Math.max(ans, (sum[r] - sum[l - 1]) / (r - l + 1));            }        }        if (cur > cur) & 1;        if (ch[p][1 - c] != 0 && res + (1L = k) get(x, r, ch[p][1 - c], cur-1, res + (1L > i) & 1);            if (ch[p][c] == 0) ch[p][c] = ++ tot;            p = ch[p][c];        }        tag[p] = 1;        if (map.containsKey(p)){            ArrayList list = map.get(p);            list.add(id);        }else {            ArrayList 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());        }    }}