Educational Codeforces Round 132 (Rated for Div. 2)

By xiaruize

题目名突现Minecraft，莫名喜感，放上Creeper aw man一首

A. Three Doors

问题有解，当且仅当递归访问可以遍历所有的点

Code
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
// Problem: A. Three Doors
// Contest: Educational Codeforces Round 132 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1709/problem/A
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int x;
int a[4];
int t;
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> t;
    while (t--)
    {
        cin >> x;
        for (int i = 1; i <= 3; i++)
            cin >> a[i];
        if (a[x] && a[a[x]])
            YES;
        else
            NO;
    }
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

B. Also Try Minecraft

首先，很明显，暴力会TLE，那么可以考虑去优化

考虑使用前缀和，后缀和将查询的复杂度做到O(1)O(1)

Code
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
// Problem: B. Also Try Minecraft
// Contest: Educational Codeforces Round 132 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1709/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 1e5 + 10;

// bool st;
int n, q;
int a[N];
int sum[N];
int b[N];
// bool en;

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1];
        if (a[i] < a[i - 1])
            sum[i] += a[i - 1] - a[i];
    }
    for (int i = n; i >= 1; i--)
    {
        b[i] = b[i + 1];
        if (a[i] < a[i + 1])
            b[i] += a[i + 1] - a[i];
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        if (l < r)
            cout << sum[r] - sum[l] << endl;
        else
            cout << b[r] - b[l] << endl;
    }
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

C. Recover an RBS

赛后被叉了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
考场TLE做法

明显前面的问号填(,后面的填)是一种方案

我由前到后枚举每个问号，如果可以把一个右括号提前至一个左括号的位置，输出NO

最坏时间复杂度是呃呃呃O(n2)O(n^2)，但是由于跑不满而且Codeforces的评测机跑得飞快，我就。。。

qwq

正解：

还是考虑先填左括号再填右括号

可以发现如果把第一个右括号和最后一个左括号调换后仍然成立，那么输出NO,否则一定是YES

感觉不靠谱的感性证明

假设最后一个填左括号的位置为x1x_1,在x1x_1之前的一位为tt，St=′?′S_t='?',第一个左括号在x2x_2上

此时，若到第ii位的左右括号差值为DIFiDIF_i

那么，通过计算,不论tt与x1x_1或x2x_2交换，DIF(x1,t)DIF_{(x_1,t)}这一段的值不会改变，而DIF(x2,x1−1)DIF_{(x_2,x_1-1)}的值相较于x1x_1交换会减少11

这显然是不优的，所以贪心正确

Code
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
// Problem: C. Recover an RBS
// Contest: Educational Codeforces Round 132 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1709/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int t;
string s;
int l, r;
// bool en;

void solve()
{
    cin >> s;
    l = r = 0;
    int n = s.size();
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
            l++;
        else if (s[i] == ')')
            r++;
    }
    if (l + r == n)
    {
        YES;
        return;
    }
    int cnt = 0;
    for (int i = 0; i < s.size(); i++)
        if (s[i] == '?')
        {
            cnt++;
            s[i] = '(';
            if (cnt == n / 2 - l || cnt >= n / 2 - l + 2)
                s[i] = ')';
        }
    int tmp = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
            tmp++;
        else
            tmp--;
        if (tmp < 0)
        {
            YES;
            return;
        }
    }
    if (tmp)
        YES;
    else
        NO;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    scanf("%lld\n", &t);
    while (t--)
        solve();
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

D. Rorororobot

这题明显比C水多了。。。

首先通过模k的余数做第一轮判断

明显可以线段树维护区间最大值，O(logn)O(logn)求出起点和终点之间最高的有多高，检查能不能通过就行，没啥思维含量。。。

注意线段树会被卡常，注意优化读入方式！！！！！
Code
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
// Problem: D. Rorororobot
// Contest: Educational Codeforces Round 132 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1709/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/*
    Name:
    Author: xiaruize
    Date:
*/
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define repp(i, x, y) for (int i = x; i >= y; i--)
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

// bool st;
int n, m;
int a[N];
int q;
int x, xx, y, yy, k;
// bool en;

#define ls u << 1
#define rs u << 1 | 1

struct Node
{
    int l, r;
    int val;
} tr[N << 2];

void pushup(int u)
{
    tr[u].val = max(tr[ls].val, tr[rs].val);
}

void build(int u, int l, int r)
{
    if (l == r)
        tr[u] = {l, r, a[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].val;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid)
            res = max(res, query(u << 1, l, r));
        if (r > mid)
            res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    // auto t_1=chrono::high_resolution_clock::now();
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d", &a[i]);
    build(1, 1, m);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d%d%d%d", &x, &y, &xx, &yy, &k);
        if (x > xx)
            swap(xx, x);
        if (y > yy)
            swap(yy, y);
        if ((xx - x) % k != 0 || (yy - y) % k != 0)
        {
            puts("NO");
            continue;
        }
        if (y == yy)
        {
            puts("YES");
            continue;
        }
        int tmp = (n - x) / k * k + x;
        // cerr << query(1, y, yy) << endl;
        if (query(1, y, yy) < tmp)
            puts("YES");
        else
            puts("NO");
    }
    // auto t_2=chrono::high_resolution_clock::now();
    // cout <<". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t_2 - t_1).count() << endl;
    return 0;
}

未完待更