CodeForces 691 Educational Codeforces Round 14

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 字数： 3.1k

A Fashion in Berland

A 题目大意

给定一种时尚的夹克衫系纽扣的方式：

所有的纽扣必须有且仅有一个纽扣不系紧，其他的全都系紧。

若是这件衣服只有一个纽扣，则必须系紧。

给定一件有 $n$ $(1 \le n \le 1000)$ 个纽扣的夹克衫，请问是否满足上述时尚方式。

A 解题思路

按照题意模拟即可。

A 代码实现

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
import java.util.*;
import java.io.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;


import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int maxn = (int) (1e6 + 5);
    static int inf = 0x3f3f3f3f;
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        int n = in.nextInt();
        int cnt = 0;
        for(int i = 1; i <= n; ++i) {
            int x = in.nextInt();
            if(x == 0) ++cnt;
        }
        if((n == 1 && cnt == 0) || (n > 1 && cnt == 1)) System.out.println("YES");
        else System.out.println("NO");
    }
    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());
        }
    }
}

C Exponential notation

C 题目大意

给定一个正实数 $x$，长度不超过 $10 ^ {6}$，按照要求将其转化成下述简单指数表示形式：

将 $x = a \times 10 ^ {b}$ 而且 $1 \le a \lt 10$

表示为 $aEb$

若 $b$ 为零，则 $Eb$ 部分可以省略。

C 解题思路

按照题意模拟，注意一些细节:

处理无效的前导零。

处理无用的后导零。

处理 $b = 0$ 的情况。

C 代码实现

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
import java.io.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;


import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int maxn = (int) (1e6 + 5);
    static int inf = 0x3f3f3f3f;
    static void solve(String s) {
        int len = s.length();
        int pPos = -1, pNz = -1, rNz = -1;
        for(int i = 0; i < len; ++i) {
            char ch = s.charAt(i);
            if(ch == '.') {
                pPos = i;
            } else {
                if(ch != '0') {
                    if(pNz == -1) {
                        pNz = i;
                    }
                    rNz = i;
                }
            }
        }
        if(pNz == -1) {
            System.out.println(0);
            return ;
        }
        StringBuilder ans = new StringBuilder();
        if(pPos == -1) {
            pPos = len;
        }
        int k = 0;
        if(pNz < pPos) {
            k = pPos - pNz - 1;
        } else {
            k = pPos - pNz;
        }
        ans.append(s.charAt(pNz));
        if(pNz != rNz) {
            ans.append('.');
            for(int i = pNz + 1; i <= rNz; ++i) {
                char ch = s.charAt(i);
                if(ch != '.') {
                    ans.append(ch);
                }
            }
        }
        if(k != 0) {
            ans.append("E");
            ans.append(k);
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        String s = in.next();
        solve(s);
    }
    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());
        }
    }
}

D Swaps in Permutation

D 题目大意

给定一个 $n$ 的全排列，你有 $m$ 种交换。$(1 \le n, m \le 10 ^ 6)$

每种交换用一个数对 $(a, b)$ 表示，表示该交换可以将 $a$ 位置上的数字，与 $b$ 位置上的数字交换。

每次操作你可以进行任意一种交换，你可以进行任意次操作。

每种交换可以进行任意次。

请输出进行若干次操作能够得到的字典序最大的排列。

D 解题思路

我们将每一个位置考虑为一个节点，将每对交换考虑成一条边。

这样便得到了一张图，我们根据其联通关系将其分成若干个联通块。

在某一个联通块内，很容易想到，通过这些交换，可以将这个联通块内的位置上的数字，进行任意的排列。

因此，我们若想要得到字典序最大的排列，则尽可能将大数字放到靠前的位置上去。

所以，在每一个联通块内构造字典序最大的序列，一起组合起来，得到的便是可得到的字典序最大的排列。

使用并查集处理联通关系，在联通块内按照位置从小到大，数字降序放置即可。

D 代码实现

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
93
94
95
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.StringTokenizer;


import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int maxn = (int) (1e6 + 5);
    static int[] p = new int[maxn];
    static int[] ans = new int[maxn];
    static int[] fa = new int[maxn];
    static int findfa(int x) {
        if(fa[x] != x) fa[x] = findfa(fa[x]);
        return fa[x];
    }
    static class node implements Comparable<node> {
        int x, id, ty;
        node(int _x, int _id, int _ty) {
            x = _x;
            id = _id;
            ty = _ty;
        }
        @Override
        public int compareTo(node rhs) {
            if(id == rhs.id) {
                if(ty == 1) return x - rhs.x;
                else return rhs.x - x;
            }
            return id - rhs.id;
        }
    }
    public static node[] pos = new node[maxn];
    public static node[] val = new node[maxn];
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1; i <= n; ++i) {
            fa[i] = i;
            p[i] = in.nextInt();
        }
        for(int i = 1; i <= m; ++i) {
            int u = in.nextInt();
            int v = in.nextInt();
            int fu = findfa(u);
            int fv = findfa(v);
            if(fu == fv) continue;
            fa[fu] = fv;
        }
        for(int i = 1; i <= n; ++i) {
            int fi = findfa(i);
            pos[i] = new node(i, fi, 1);
            val[i] = new node(p[i], fi, 2);
        }
        Arrays.sort(pos, 1, n + 1);
        Arrays.sort(val, 1, n + 1);
        for(int i = 1; i <= n; ++i) {
            ans[pos[i].x] = val[i].x;
        }
        StringBuilder res = new StringBuilder();
        for(int i = 1; i <= n; ++i) {
            if(i > 1) res.append(" ");
            res.append(ans[i]);
        }
        System.out.println(res);
    }
    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());
        }
    }
}

E Xor-sequences

E 题目大意

给定 $n$ $(1 \le n \le 100)$ 个数字。

求长度为 $k$ $(1 \le k \le 10^{18})$ 的 $”xor-sequences”$ 异或序列有多少种，结果对 $10^9 + 7$ 取模，异或序列定义如下：

一个序列 $x1, x_2, x_3, \cdots , x_k$ 被称为异或序列，当且仅当对于每一个 $1 \le i \lt k$，都满足 $a_i$ 二进制异或 $a {i + 1}$ 的值的二进制表示中 $1$ 的个数是 $3$ 的非负整数倍。

注意，给定的 $n$ 个数字中，即便存在数字值相同，也考虑为不同数字。

E 解题思路

显然，每个序列若后面想要加一个序列，只需要考虑最后一个数字即可，与再之前的数字无关。

若想在一个序列后面加另外一个序列，只需要考虑前面序列的最后一个数字，和最后一个序列的最前面一个数字即可。

根据此类特性，若我们将这 $n$ 个数字考虑成节点，若数字 $a_i$ 和数字 $a_j$ 满足上述条件，则存在一条 $(i, j)$ 边。

这样的话，我们要求的问题，其实就是在求在这张图中，有多少条经过且只经过 $k$ 个顶点的路径方案存在。

用可达矩阵 $A$ 来表示上述图，根据矩阵乘法定义可知， 在 $A$ 中， $A_{ij}$ 则表示以第 $i$ 个数字开头，以第 $j$ 个数字结尾的长度为 $2$ 异或序列有多少。

同理 $C = A ^{k - 1}$ 表示以第 $i$ 个数字开头，以第 $j$ 个数字结尾的长度为 $k$ 异或序列有多少。

因此，最终答案便是矩阵 $C$ 中所有位置数字在模意义下求和。

根据数据范围，矩阵累乘 $k$ 次显然不可行，因此需要借助快速幂的思想，通过矩阵快速幂求解 $C$ 即可通过此题。

E 代码实现

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import java.io.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {
    static int maxn = (int)(1e2 + 5);
    static long mod = (long)(1e9 + 7);
    static class Matrix {
        int n;
        long[][] a;
        Matrix(int _n) {
            n = _n;
            a = new long[n][n];
        }
        Matrix(Matrix m) {
            n = m.n;
            a = new long[n][n];
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    a[i][j] = m.a[i][j];
                }
            }
        }
        Matrix mul(Matrix m) {
            Matrix ret = new Matrix(n);
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    long x = 0;
                    for(int k = 0; k < n; ++k) {
                        x = (x + a[i][k]*m.a[k][j]%mod)%mod;
                    }
                    ret.a[i][j] = x;
                }
            }
            return ret;
        }
        Matrix Pow(long k) {
            Matrix ret = new Matrix(n);
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    ret.a[i][j] = 0;
                }
                ret.a[i][i] = 1;
            }
            Matrix bs = new Matrix(this);
            while(k > 0) {
                if((k & 1) == 1) {
                    ret = ret.mul(bs);
                }
                bs = bs.mul(bs);
                k >>= 1;
            }
            return ret;
        }
        void show() {
            System.out.println("n: " + n);
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    System.out.print(a[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
    static long[] b = new long[maxn];
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        long k = in.nextLong();
        for(int i = 0; i < n; ++i) {
            b[i] = in.nextLong();
        }
        Matrix m = new Matrix(n);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                long x = (b[i] ^ b[j]);
                int cnt = 0;
                while(x > 0) {
                    if((x & 1) == 1) ++cnt;
                    x >>= 1;
                }
                if(cnt%3 == 0) m.a[i][j] = 1;
                else m.a[i][j] = 0;
            }
        }
//        m.show();
        m = m.Pow(k - 1);
//        m.show();
        long ans = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                ans = (ans + m.a[i][j])%mod;
            }
        }
        out.println(ans);
        out.flush();
        out.close();
    }
    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());
        }
    }
}

F Couple Cover

F 题目大意

给定 $n$ $(1 \le n \le 10 ^ 6)$ 个正整数 $a_i$ $(1 \le a_i \le 3 \times 10 ^ 6)$。

有 $m$ $(1 \le m \le 10 ^ 6)$ 次询问。

每次询问一个 $p$ $(1 \le p \le 3 \times 10 ^ 6)$，问满足 $a_i * b_j \ge p$ $(i \ne j)$ 的有序对 $(i, j)$ 有多少。

F 解题思路

显然， 合法的有序对共有 $n \times (n - 1)$ 种，暴力枚举每一种方案肯定不可行。

我们发现每次询问的 $p$ 小于等于 $3 \times 10 ^ 6$。

这样的话，我们构造数组 $dp[i]$ 表示乘积小于等于 $i$的方案数有多少。

每次询问的解，显然为 $n \times (n - 1) - dp[p - 1]$。

如何在规定时间内完成 $dp$ 数组的预处理呢。

我们考虑 $cnt[i]$ 表示，值为 $i$ 的数有多少个。

这样的话，考虑值为 $i$ 为 $dp$ 数组造成的贡献有：

若满足 $i*j \le 3 \times 10 ^ 6$

$dp[i*j] += cnt[i] \times cnt[j] (i \ne j)$

$dp[i*j] += cnt[i]\times (cnt[i] - 1) (i = j)$

上述 $dp$ 很容易想到，但是时间复杂度是否允许呢？

根据分析我们可以知道，上述转移的复杂度为 $\Sigma _ {i = 1} ^ {3 \times 10 ^ 6} （3 \times 10 ^ 6 \div i）$

我们令 $mx = 3 \times 10 ^ 6$

也就是 $\frac{mx}{1} + \frac{mx}{2} + \cdots + \frac{mx}{mx}$

上述为调和级数，可以估算为 $mx \times log(mx)$。

F 代码实现

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
import java.io.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {
    static int maxn = (int)(3e6 + 5);
    static long[] a = new long[maxn];
    static long[] b = new long[maxn];
    static long[] c = new long[maxn];
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        for(int i = 1; i <= n; ++i) {
            int x = in.nextInt();
            ++a[x];
        }
        for(int i = 1; i < maxn; ++i) {
            for(int j = 1; j < maxn; ++j) {
                int x = i*j;
                if(x >= maxn) break;
                long now = 0;
                if(i == j) now = a[i]*(a[j] - 1);
                else now = a[i]*a[j];
                b[x] += now;
            }
        }
        for(int i = 1; i < maxn; ++i) {
            c[i] = c[i - 1] + b[i];
        }
        long tot = (long)n*(long)(n - 1);
        int m = in.nextInt();
        for(int i = 0; i < m; ++i) {
            int x = in.nextInt();
            long ans = tot - c[x - 1];
            out.println(ans);
        }
        out.flush();
        out.close();
    }
    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());
        }
    }
}