CF-731-div3

Posted on Edited on In Views:
Symbols count in article: 10k
题目 A B C D E F G
通过情况 O O O O O O O
难度 800 800 1100 1300 1500 1900 2100

A. Shortest Path with Obstacle

题面

略

解法

略

代码

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
/*
 * @题目: A. Shortest Path with Obstacle
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:37:44
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-13 22:52:45
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int main()
{
    int t = read();
    while (t--)
    {
        int x1 = read(), y1 = read();
        int x2 = read(), y2 = read();
        int x3 = read(), y3 = read();
        int dis = abs(x1 - x2) + abs(y1 - y2);
        if (x1 == x2 && x1 == x3)
        {
            if ((y1 - y3) * (y2 - y3) < 0)
                dis += 2;
        }
        if (y1 == y2 && y1 == y3)
        {
            if ((x1 - x3) * (x2 - x3) < 0)
                dis += 2;
        }
        printf("%d\n", dis);
    }
    return 0;
}

B. Alphabetical Strings

题面

略

解法

略

代码

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
/*
 * @题目: B. Alphabetical Strings
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:37:44
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-13 22:47:25
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
char s[30];
int in[30];
int main()
{
    int t = read();
    while (t--)
    {
        memset(in, 0, sizeof(in));
        scanf("%s", s);
        int len = strlen(s);
        int f = 0;
        int i;
        in[s[0] - 'a']++;
        for (i = 1; i < len; i++)
        {
            in[s[i] - 'a']++;
            if (s[i] > s[i - 1])
                break;
        }
        i++;
        for (; i < len; i++)
        {
            in[s[i] - 'a']++;
            if (s[i] < s[i - 1])
            {
                f = 1;
                break;
            }
        }
        rep(j, 0, len - 1)
        {
            if (in[j] != 1)
            {
                f = 1;
                break;
            }
        }
        if (f)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}

C. Pair Programming

题面

略

解法

双指针，能操作就操作

代码

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
/*
 * @题目: 
 * @算法: 
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:37:58
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-13 23:07:02
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 400
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int ans[maxn << 1];
int a[maxn], b[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int k = read(), n = read(), m = read();
        rep(i, 1, n) a[i] = read();
        rep(i, 1, m) b[i] = read();
        int p1 = 1, p2 = 1, p = 0, f = 0;
        while (p1 <= n || p2 <= m)
        {
            f = 0;
            while (p1 <= n && a[p1] <= k)
            {
                if (a[p1] == 0)
                    k++;
                ans[++p] = a[p1];
                p1++, f = 1;
            }
            while (p2 <= m && b[p2] <= k)
            {
                if (b[p2] == 0)
                    k++;
                ans[++p] = b[p2];
                p2++, f = 1;
            }
            if (f == 0)
                break;
        }
        if (p != n + m)
            puts("-1");
        else
        {
            rep(i, 1, p) printf("%d ", ans[i]);
            puts("");
        }
    }
    return 0;
}

D. Co-growing Sequence

题面

略

解法

第一位一定为0，后面按规则来即可

代码

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
/*
 * @题目: D. Co-growing Sequence
 * @算法: 位运算
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:38:01
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-14 08:51:54
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 200010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int a[maxn], b[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        int n = read();
        rep(i, 1, n) a[i] = read();
        b[1] = 0;
        rep(i, 2, n)
        {
            b[i] = ((a[i - 1] ^ b[i - 1]) | a[i]) ^ a[i];
        }
        rep(i, 1, n) printf("%d ", b[i]);
        puts("");
    }
    return 0;
}

E. Air Conditioners

题面

略

解法

先将dp置于inf，有空调的位置置空调的温度，按下面规则扫描两遍即可：
从左向右扫描
$dp\left[ i \right] =\min \left( dp\left[ i \right] ,dp\left[ i-1 \right] +1 \right) $
从右向左扫描
$dp\left[ i \right] =\min \left( dp\left[ i \right] ,dp\left[ i+1 \right] +1 \right) $

代码

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
/*
 * @题目: E. Air Conditioners
 * @算法: 线性DP
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:38:07
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-14 08:29:08
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 300010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int f[maxn];
int a[maxn], b[maxn];
int main()
{
    int t = read();
    while (t--)
    {
        memset(f, 0x3f, sizeof(f));
        int n = read(), m = read();
        rep(i, 1, m) a[i] = read();
        rep(i, 1, m) b[i] = read();
        rep(i, 1, m) f[a[i]] = b[i];
        rep(i, 2, n) f[i] = min(f[i], f[i - 1] + 1);
        per(i, n - 1, 1) f[i] = min(f[i], f[i + 1] + 1);
        rep(i, 1, n) printf("%d ", f[i]);
        puts("");
    }
    return 0;
}

F. Array Stabilization (GCD version)

题面

略

解法

和#736D比较像，本质是数据结构维护数列$gcd$
根据观察可知，经过k次操作后，当前位置上的值为$gcd\left( a_i,a_{i+1},…,a_{i+k} \right) $那么只需将初始值都除去所有数的最大公约数，断环为链后，找可以使所有值为$1$的最小长度$k$

代码

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
/*
 * @题目: F. Array Stabilization (GCD version)
 * @算法: 线段树
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:38:11
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-14 09:23:51
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 400010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
const int inf = 0x7fffffff;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
int n;
int seg[maxn << 2], a[maxn];
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void build(int rt, int l, int r)
{
    if (l == r)
    {
        seg[rt] = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(rt << 1, l, m);
    build(rt << 1 | 1, m + 1, r);
    seg[rt] = gcd(seg[rt << 1], seg[rt << 1 | 1]);
}
int query(int rt, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return seg[rt];
    int m = (l + r) >> 1;
    int res = 0;
    if (ql <= m)
        res = gcd(res, query(rt << 1, l, m, ql, qr));
    if (qr > m)
        res = gcd(res, query(rt << 1 | 1, m + 1, r, ql, qr));
    return res;
}
int main()
{
    int t = read();
    while (t--)
    {
        n = read();
        rep(i, 1, n) a[i] = read();
        int gd = a[1];
        rep(i, 2, n) gd = gcd(gd, a[i]);
        rep(i, 1, n) a[i] /= gd;
        rep(i, 1, n) a[i + n] = a[i];
        build(1, 1, n << 1);
        int j = 1;
        int ans = 0;
        rep(i, 1, n)
        {
            while (query(1, 1, n << 1, i, j) != 1)
                j++;
            ans = max(ans, j - i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

G. How Many Paths?

题面

给定一个有$n$个点$m$条边的有向图，统计有多少条路径从$1$到$2,…,n$点（没有输出$-1$，有一条输出$1$，至少有两条不同输出$2$）

解法

模板题，缩点后统计（具体见代码）

代码

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
142
/*
 * @题目: G. How Many Paths?
 * @算法: 缩点、拓扑排序
 * @Author: Blore
 * @Language: c++11
 * @Date: 2021-08-13 22:38:16
 * @LastEditors: Blore
 * @LastEditTime: 2021-08-14 10:37:36
 */
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define maxn 400010
#define maxm 200010
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, r, l) for (int i = r; i >= l; i--)
#define ll long long
using namespace std;
int read()
{
    int p = 0, f = 1;
    char c = getchar();
    while (c < 48 || c > 57)
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= 48 && c <= 57)
        p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
    return p * f;
}
vector<int> g1[maxn], g2[maxn];
int low[maxn], dfn[maxn], vis[maxn], siz[maxn], color[maxn], cic[maxn], inv[maxn], status[maxn], cc, tim;
int sta[maxn], top;
int n, m;
void init()
{
    top = 0, cc = 0, tim = 0;
    rep(i, 1, n)
    {
        g1[i].clear();
        g2[i].clear();
        dfn[i] = low[i] = vis[i] = siz[i] = status[i] = cic[i] = 0;
    }
}
void tarjan(int u)
{
    low[u] = dfn[u] = ++tim;
    sta[++top] = u;
    vis[u] = 1;
    for (vector<int>::iterator it = g1[u].begin(); it != g1[u].end(); it++)
    {
        int v = *it;
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v])
        {
            low[u] = min(low[u], low[v]);
        }
    }
    if (dfn[u] == low[u])
    {
        ++cc;
        while (1)
        {
            color[sta[top]] = cc, vis[sta[top]] = 0;
            siz[cc]++, inv[cc] = sta[top];
            if (sta[top] == u)
            {
                top--;
                break;
            }
            top--;
        }
    }
}
void topo()
{
    queue<int> q;
    q.push(color[1]);
    status[color[1]] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        if (cic[inv[u]] || siz[u] != 1)
            status[u] = -1;
        for (int i = 0; i < g2[u].size(); i++)
        {
            int v = g2[u][i];
            if (status[u] == -1)
                status[v] = -1;
            else if (status[v] != -1)
                ++status[v];
            if (status[v] <= 50)
                q.push(v);
        }
    }
}
int main()
{
    int t = read();
    while (t--)
    {
        init();
        n = read(), m = read();
        rep(i, 1, m)
        {
            int u = read(), v = read();
            if (u == v)
                cic[u] = 1;
            else
                g1[u].pb(v);
        }
        rep(u, 1, n) if (!dfn[u]) tarjan(u);
        rep(u, 1, n)
        {
            for (vector<int>::iterator it = g1[u].begin(); it != g1[u].end(); it++)
            {
                int v = *it;
                if (color[u] != color[v])
                    g2[color[u]].pb(color[v]);
            }
        }
        topo();
        for (int u = 1; u <= n; u++)
        {
            if (status[color[u]] >= 2)
                printf("2 ");
            else
                printf("%d ", status[color[u]]);
        }
        puts("");
    }
    return 0;
}