CodeForces 920 Educational Codeforces Round 37

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

A Water The Garden

A 题目大意

给定 $n$ 块连续的土地，编号 $1 ~ n$。有 $k$ 块土地上有水龙头（第 $i$ 个水龙头位于编号 $x_i$ 的土地上）。

当在 $x_i$ 土地上的水龙头打开后，$j$ 秒后，编号在 $[x_i - (j - 1), x_i + (j - 1)]$ 区间里的土地均会被灌溉。

注意，可以认为水流为离散的，当不到整秒数时，水流没有任何变化，一到整秒数，瞬间灌溉下一块土地。

A 解题思路

根据题意，每两个水龙头之间的所有空地全部灌溉所需要的时间是 $(delta - 1)/2 + 1$

因此对所有相邻两两水龙头之间空地灌溉所需要的时间，取最大值，即基本解决问题。

注意考虑第一个水龙头以前的所有空地，和最后一个水龙头以后的所有空地。

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
50
51
52
53
54
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) (2e2 + 5);
    static int[] x = new int[maxn];
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        int T = in.nextInt();
        for(int cs = 1; cs <= T; ++cs) {
            int n = in.nextInt();
            int k = in.nextInt();
            for(int i = 1; i <= k; ++i) {
                x[i] = in.nextInt();
            }
            int ans = Math.max(x[1], n - x[k] + 1);
            for(int i = 1; i < k; ++i) {
                int dt = x[i + 1] - x[i] + 1;
                ans = Math.max(ans, (dt + 1)/2);
            }
            System.out.println(ans);
        }
        // Scanner in = new Scanner(System.in);
        // in.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());
        }
    }
}

B Tea Queue

B 题目大意

现有一队人排长队接水喝。

第 $i$ 个人在第 $l_i$ 分钟开始时来到队尾。如果同时有多个人来到队尾，下标小的排在前面。

每分钟队首那个人可以接水，就在这一分钟接水，下一分钟开始前离开队列。

如果某人等到第 $r_i$ 分钟开始还没排到接水，他也会空瓶离开。

请计算每个人接到水的时刻，或者接不到水输出0。

B 解题思路

根据题意，按照时间顺序模拟即可。

B 代码实现

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
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 {
    public static int maxn = (int) (1e3 + 5);
    static class stu implements Comparable<stu>{
        public int lf;
        public int rt;
        public int id;
        stu(int l, int r, int i) {
            lf = l;
            rt = r;
            id = i;
        }
        @Override
        public int compareTo(stu rhs) {
            if(lf == rhs.lf) return id - rhs.id;
            return lf - rhs.lf;
        }
    }
    static int[] ans = new int[maxn];
    static stu[] s = new stu[maxn];
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        int T = in.nextInt();
        for(int cs = 1; cs <= T; ++cs) {
            int n = in.nextInt();
            for(int i = 0; i < n; ++i) {
                int lf = in.nextInt();
                int rt = in.nextInt();
                s[i] = new stu(lf, rt, i);
            }
            Arrays.sort(s, 0, n);
            int now = 0;
            for(int i = 0; i < n; ++i) {
                // System.out.println(s[i].id + ": " + s[i].lf + ", " + s[i].rt);
                if(now < s[i].lf) {
                    ans[s[i].id] = s[i].lf;
                    now = s[i].lf + 1;
                } else if(now > s[i].rt) {
                    ans[s[i].id] = 0;
                } else {
                    ans[s[i].id] = now;
                    ++now;
                }
            }
            for(int i = 0; i < n; ++i) {
                if(i > 0) System.out.print(" ");
                System.out.print(ans[i]);
            }
            System.out.println();
        }
        // Scanner in = new Scanner(System.in);
        // in.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());
        }
    }
}

C Swap Adjacent Elements

C 题目大意

给定一个 $n$ 的全排列 $a$，$1 ~ n$ 每个数字在序列里出现且仅出现一次。

给定一个长度为 $n - 1$ 的布尔数组 $b$，$b_i$ 表示 $a$ 数组中的 $i$ 位置，能否与 $i + 1$ 位置交换。

你可以对任何允许交换的相邻位置，以任意顺序，交换任意次。

请问能否将序列 $a$ 变为升序序列。

C 解题思路

考虑冒泡排序过程，主要操作便是相邻位置两两交换。

显然，序列 $a$ 中的第 $i$ 数字 $a_i$ 能否交换到它应该在的位置，也就是第 $a_i$ 个位置，只需要看，$a_i$ 位置与 $i$ 位置之间的所有 $b$ 数组，是否都为允许交换。

也就是说，把每一个位置看成一个点，每个允许交换看成一条边，则只需要判断点 $i$ 与点 $a_i$ 是否在同一联通块内。

由于题目的性质，无需使用并查集维护联通关系，只需要从左到右顺序染色即可（具体实现见代码）。

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
import java.util.*;
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int maxn = (int) (2e5 + 5);
    static int[] col = new int[maxn];
    static int[] id = new int[maxn];
    static String s;
    static boolean solve(int n) {
        for(int i = 0; i < n; ++i) {
            if(col[i] != col[id[i]]) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        int n = in.nextInt();
        for(int i = 0; i < n; ++i) {
            id[i] = in.nextInt();
            --id[i];
        }
        s = in.next();
        col[0] = 0;
        for(int i = 0; i < n - 1; ++i) {
            char ch = s.charAt(i);
            if(ch == '0') col[i + 1] = col[i] + 1;
            else col[i + 1] = col[i];
        }
        if(solve(n)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
        // Scanner in = new Scanner(System.in);
        // in.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());
        }
    }
}

E Connected Components

E 题目大意

给定一张 $n$ 个点，$(1 \le n \le 2 \times 10 ^5)$， $m$ 条边 $(0 \le m \le 2 \times 10 ^5)$ 的无向图。

求它的补图共有多少个联通块。并按照升序输出这些联通块的大小。

E 解题思路

由于补图的边数规模最大可达 $\frac{n \times (n - 1)}{2}$，因此正常建图跑 $bfs$ 或 $dfs$ 显然不可行。

考虑改进 $bfs$，我们考虑对某一个未访问点过的点 $x$ 进行 $bfs$，然后依次访问点 $x$ 在原图中连出去的边 $xy$，显然与 $x$ 相邻的这些 $y$，在补图中与 $x$ 不相邻。

同时我们维护一个链表，存储未访问过的所有点。

这时我们只需要遍历链表，将所有在补图中与 $x$ 相邻的点，全都加入到 $bfs$ 队列中，顺便在链表中删除对应的点，并将其状态设定为已访问过即可。

通过均摊分析时间复杂度，每个节点会且只会入队一次，每条边会且只会被访问两次，时间复杂度为 $O(n + m)$，可以通过此题。

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
132
133
134
135
136
137
138
139
import java.util.*;
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) (2e6 + 5);
    static class Edge {
        int nxt;
        int to;
        Edge(int _nxt, int _to) {
            nxt = _nxt;
            to = _to;
        }
    }
    static Edge[] E = new Edge[maxn*2];
    static int[] head =  new int[maxn];
    static int[] lnxt =  new int[maxn];
    static int[] llst =  new int[maxn];
    static int fst;
    static int Etot;
    static int Ctot;
    static int[] C = new int[maxn];
    static int[] q = new int[maxn];
    static int lf;
    static int rt;
    static boolean[] vis = new boolean[maxn];
    static int[] cnt = new int[maxn];
    static int[] col = new int[maxn];
    static void addEdge(int u, int v) {
        E[Etot] = new Edge(head[u], v);
        head[u] = Etot++;
    }
    public static void bfs(int x, int n) {
        lf = rt = 0;
        q[rt++] = x;
        col[Ctot] = 0;
        vis[x] = true;
        if(x == fst) {
            fst = lnxt[fst];
        } else {
            if(lnxt[x] != -1) llst[lnxt[x]] = llst[x];
            if(llst[x] != -1) lnxt[llst[x]] = lnxt[x];
        }
        while(lf < rt) {
            int now = q[lf++];
            ++col[Ctot];
            for(int i = head[now]; i != -1; i = E[i].nxt) {
                int to = E[i].to;
                ++cnt[to];
            }
            int id = fst;
            while(id != -1) {
                if(!vis[id] && cnt[id] == 0) {
                    vis[id] = true;
                    q[rt++] = id;
                    if(id == fst) {
                        fst = lnxt[fst];
                        if(fst != -1) llst[fst] = -1;
                    } else {
                        if(lnxt[id] != -1) llst[lnxt[id]] = llst[id];
                        if(llst[id] != -1) lnxt[llst[id]] = lnxt[id];
                    }
                }
                id = lnxt[id];
            }
            for(int i = head[now]; i != -1; i = E[i].nxt) {
                int to = E[i].to;
                --cnt[to];
            }
        }
        ++Ctot;
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        int n = in.nextInt();
        int m = in.nextInt();
        llst[1] = -1;
        lnxt[n] = -1;
        Etot = Ctot = lf = rt = 0;
        fst = 1;
        for(int i = 1; i <= n; ++i) {
            head[i] = -1;
            vis[i] = false;
            cnt[i] = 0;
            if(i > 1) llst[i] = i - 1;
            if(i < n) lnxt[i] = i + 1;
        }
        for(int i = 0; i < m; ++i) {
            int u = in.nextInt();
            int v = in.nextInt();
            addEdge(u, v);
            addEdge(v, u);
        }
        for(int i = 1; i <= n; ++i) {
            if(vis[i]) continue;
            bfs(i, n);
        }
        Arrays.sort(col, 0, Ctot);
        System.out.println(Ctot);
        for(int i = 0; i < Ctot; ++i) {
            if(i > 0) System.out.print(" ");
            System.out.print(col[i]);
        }
        System.out.println();
        // Scanner in = new Scanner(System.in);
        // in.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 SUM and REPLACE

F 题目大意

给定一个长度为 $n$ $(1 \le n \le 3 \times 10 ^5)$ 的正整数数组 $(1 \le a _ i \le 10 ^ 6)$，并对数组进行 $m$ $(1 \le m \le 3 \times 10 ^5)$ 次询问。

询问分为两种：

询问一：对区间 $[l, r]$ 的所有数字，值变为其正因数个数。

询问二：询问区间 $[l, r]$ 的总和。

F 解题思路

由于因数个数为积性函数，且数组值域为 $[1, 10 ^ 6]$，因此可以使用积性函数线性筛，预处理值域内所有数的因数个数。

我们观察因数个数数组，我们发现 $1, 2$ 这两个点为不动点，对这两个值求因数个数已经不再变化。

而且对于值域内的任何一个数连续进行取因数个数操作，很快就会收敛到不动点。

因此我们借鉴区间开平方类似题目的做法，用线段树进行相应维护。

若区间最大值小于等于 $2$，则无需下放，操作不会再对对应区间产生影响。

若区间最大值大于 $2$，则暴力下放，由于其性质，每个点最多被操作不超过 $10$ 次。

修改时用线段树顺手维护区间和即可。

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
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
132
133
134
135
136
137
138
139
140
141
import java.util.*;
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) (3e5 + 5);
    static int maxm = (int) (1e6 + 5);
    static int[] a = new int[maxn];
    static int[] d = new int[maxm];
    static int[] num = new int[maxm];
    static int[] p = new int[maxm];
    static int tot;
    static boolean[] np = new boolean[maxm];
    static void getD() {
        np[0] = np[1] = true;
        d[1] = 1;
        tot = 0;
        for(int i = 2; i < maxm; ++i) {
            if(np[i] == false) {
                p[tot++] = i;
                d[i] = 2;
                num[i] = 1;
            }
            for(int j = 0; j < tot; ++j) {
                int x = p[j]*i;
                if(x >= maxm) break;
                np[x] = true;
                if(i%p[j] == 0) {
                    d[x] = d[i]/(num[i] + 1)*(num[i] + 2);
                    num[x] = num[i] + 1;
                    break;
                } else {
                    d[x] = 2*d[i];
                    num[x] = 1;
                }
            }
        }
    }
    public static class SegTree {
        int lf, rt;
        int mx;
        long sum;
    }
    static SegTree[] st = new SegTree[maxn<<2];
    static void PushUp(int x) {
        st[x].mx = Math.max(st[x << 1].mx, st[x << 1 | 1].mx);
        st[x].sum = st[x << 1].sum + st[x << 1 | 1].sum;
    }
    static void Build(int x, int lf, int rt) {
        st[x] = new SegTree();
        SegTree now = st[x];
        now.lf = lf;
        now.rt = rt;
        if(lf == rt) {
            now.mx = a[lf];
            now.sum = a[lf];
            return ;
        }
        int mid = (lf + rt) >> 1;
        Build(x << 1, lf, mid);
        Build(x << 1 | 1, mid + 1, rt);
        PushUp(x);
    }
    static void Update(int x, int lf, int rt) {
        SegTree now = st[x];
        if(now.mx <= 2) return ;
        if(now.lf == now.rt) {
            now.mx = d[now.mx];
            now.sum = now.mx;
            return ;
        }
        int mid = (now.lf + now.rt) >> 1;
        if(lf <= mid) Update(x << 1, lf, rt);
        if(rt > mid) Update(x << 1 | 1, lf ,rt);
        PushUp(x);
    }
    static long Query(int x, int lf, int rt) {
        SegTree now = st[x];
        if(lf <= now.lf && rt >= now.rt) return now.sum;
        long ret = 0;
        int mid = (now.lf + now.rt) >> 1;
        if(lf <= mid) ret += Query(x << 1, lf, rt);
        if(rt > mid) ret += Query(x << 1 | 1, lf ,rt);
        return ret;
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(System.out);
        getD();
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1; i <= n; ++i) {
            a[i] = in.nextInt();
        }
        Build(1, 1, n);
        for(int i = 1; i <= m; ++i) {
            int t = in.nextInt();
            int l = in.nextInt();
            int r = in.nextInt();
            if(t == 1) {
                Update(1, l, r);
            } else {
                out.println(Query(1, l, r));
            }
        }
        out.flush();
        // Scanner in = new Scanner(System.in);
        // in.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());
        }
    }
}