Codeforces Round #829 (Div. 2)(A-C)

A.

对于每个Q，必有A在其后，先判断Q与A的个数是否符合题意，符合后
逆转字符串，查找每个A是否有对应的Q

import java.io.*;
import java.util.*;

public class Main {

    static class InputReader {
        public BufferedReader Reader;
        public StringTokenizer tokenizer;

        public InputReader(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 int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public float nextFloat() {
            return Float.parseFloat(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 123456;
    static int nums[] = new int[N];

    public static void main(String[] args) throws IOException {

        int N = in.nextInt();
        while (N-- > 0) {
            int n = in.nextInt();
            String s = in.next();
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
            }
            if (map.getOrDefault('Q', 0) > map.getOrDefault('A', 0)) {
                out.println("No");
            } else {
                ArrayList<Character> al = new ArrayList<>();
                for (int i = n - 1; i >= 0; i--) {
                    al.add(s.charAt(i));
                }
                for (; !al.isEmpty(); ) {
                    if (al.get(0) == 'A') {
                        for (int j = 0; j < al.size(); j++) {
                            if (al.get(j) == 'Q') {
                                al.remove(j);
                                al.remove(0);
                                map.replace('Q', map.get('Q') - 1);
                                break;
                            }
                        }
                    } else {
                        out.println("No");
                        break;
                    }
                    if (map.get('Q') == 0) {
                        out.println("Yes");
                        break;
                    }
                }
            }
        }


        out.flush();
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

B.

题意给定排列1-n，要求最大化答案min{Pi+1 - Pi}
找到一种排列，使得之间的差值最大，考虑1，2，3，4，……，n - 1，n从中间取一个，从两边取一个，再从中间取一个…

import java.io.*;
import java.util.*;
 
public class Main {
 
    static class InputReader {
        public BufferedReader Reader;
        public StringTokenizer tokenizer;
 
        public InputReader(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 int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }
 
        public float nextFloat() {
            return Float.parseFloat(next());
        }
 
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
 
    static InputReader in = new InputReader(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 123456;
    static int nums[] = new int[N];
 
    public static void main(String[] args) throws IOException {
 
        int N = in.nextInt();
 
        while (N-- > 0) {
 
 
            int n = in.nextInt();
            int left = n + 1 >> 1;
            int right = n;
 
            boolean flag = true;
 
            for (int i = 0; i < n; i++) {
                if (flag) {
                    out.print(left + " ");
                    left--;
                    flag = false;
                } else {
                    out.print(right + " ");
                    right--;
                    flag = true;
                }
            }
 
            out.println();
        }
 
        out.flush();
    }
 
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

C1.

给定只有1，-1组成的一个序列，定义操作s[l, r] = a1 - a2 + a3 - a4 + …
要求给出数个分段[L, R]，满足sum = 0
考虑单数个数字永远无法凑0，只能偶数个元素才有解
两个一考虑，若相等，则划到一起，=0，相当于减少题目序列长度
若不等，相加必=0，分别划分，总之两者都是将序列n简化为n-2，重复操作即可

    static void solve() {
        n = in.nextInt();
        for (int i = 1; i <= n; i++) {
            nums[i] = in.nextInt();
        }
 
        if ((n & 1) == 1) {
            out.println(-1);
            return;
        }
        long sum = 0;
        boolean flag = true;
        //1 == + ,0 == -
        for (int i = 1; i <= n; i++) {
            if (flag) {
                sum += nums[i];
                flag = false;
            } else {
                sum -= nums[i];
                flag = true;
            }
        }/*
        1
8
1 -1 -1 -1 -1 1 -1 -1
        */
        if (sum == 0) {
            out.println(1);
            out.println(1 + " " + n);
            return;
        }
 
        long res = 0;
        for (int i = 1; i <= n; i++) {
            res += nums[i];
        }
        if (res == 0) {
            out.println(n);
            for (int i = 1; i <= n; i++) {
                out.println(i + " " + i);
            }
            return;
        }
 
        Pair pair[] = new Pair[N];
        int k = 0;
        for (int i = 1; i <= n >> 1; i++) {
            if (nums[2 * i] == nums[2 * i - 1]) {
                pair[k++] = new Pair(2 * i - 1, 2 * i);
            } else {
                pair[k++] = new Pair(2 * i - 1, 2 * i - 1);
                pair[k++] = new Pair(2 * i, 2 * i);
            }
        }
 
        out.println(k);
        for (int i = 0; i < k; i++) {
            out.println(pair[i].x +  " " + pair[i].y);
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

C2.

0对求和没作用，但是会影响符号，考虑去掉0后的元素个数必须为偶数，否则无解
对相邻两个非0元素和上题一样，遇到0左边的自成区间，右边的带一个0不相等时，都自成区间即可

    static void solve() {
        n = in.nL();
        for (int i = 1; i <= n; i++) {
            nums[i] = in.nL();
        }

        long numOf1_2 = n;
        for (int i = 1; i <= n; i++) {
            if (nums[i] == 0) {
                numOf1_2--;
            }
        }
        if ((numOf1_2 & 1) == 1) {
            out.println(-1);
            return;
        }
        int now = 0;
        int k = 0;
        for (int i = 1; i <= n; i++) {
            if (nums[i] == 0) {
                //当前0下一个元素非0且下一个元素和上一个非0元素相等时才需要带上下一个元素
                if (nums[i + 1] == 0 || now == 0) {
                    pair[k][0] = i;
                    pair[k++][1] = i;
                } else if (nums[i + 1] == now) {
                    pair[k][0] = i;
                    pair[k++][1] = i + 1;
                    now = 0;
                    i++;
                } else {
                    pair[k][0] = i;
                    pair[k++][1] = i;
                    pair[k][0] = i + 1;
                    pair[k++][1] = i + 1;
                    now = 0;
                    i++;
                }
            } else {
                if (nums[i + 1] != 0) {
                    //直接相邻和C1一样
                    if (nums[i] == nums[i + 1]) {
                        pair[k][0] = i;
                        pair[k++][1] = i + 1;
                    } else {
                        pair[k][0] = i;
                        pair[k++][1] = i;
                        pair[k][0] = i + 1;
                        pair[k++][1] = i + 1;
                    }
                    i++;
                } else {
                    pair[k][0] = i;
                    pair[k++][1] = i;
                    now += nums[i];
                }
            }
        }
        out.println(k);
        for (int i = 0; i < k; i++) {
            out.println(pair[i][0] + " " + pair[i][1]);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

D.

若x是最小之一，必可整除
若不，排序，遍历a[1] + 1 - x。表示 (i - 1)!已经化简。sum记录当前化简留下来的1的个数。上一轮增加的sum可以通过找a中有多少个数等于i - 1。如果当前sum不能整除i，代表已经化简不下去了，不能整除。

    public static void main(String[] args) throws IOException {
//        int N = in.nI();
//        while (N-- > 0) {
//            solve();
//        }

        long n = in.nL();
        long x = in.nL();

        for (int i = 1; i <= n; i++) {
            nums[i] = in.nL();
        }

        Arrays.sort(nums, 1, (int) n + 1);
        if (nums[1] >= x) {
            out.println("Yes");
        } else {
            int l = 1, sum = 0;
            boolean ok = true;
            for (long i = nums[1] + 1; i <= x; i++) {
                while (nums[l] == i - 1) {
                    l++;
                    sum++;
                }
                if (sum % i != 0) {
                    ok = false;
                    break;
                }
                sum /= i;
            }
            if (ok) out.println("Yes");
            else out.println("No");
        }

        out.flush();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36