Codeforces Round 657 Div2

发表于2020-08-14更新于2023-09-15字数统计3.6k阅读时长37分

比赛链接

A Acacius and String

题目链接

Solution

遇到可能匹配的位置 ii 暴力匹配即可。需要注意的是当前位置 ii 匹配后得到的串中 abacabaabacaba 子串的个数可能大于 1，因此每次匹配成功后要检查子串 abacabaabacaba 的个数。

Code

Acacius and String
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
#include <bits/stdc++.h>

using namespace std;

int T, n;
string s;
string t = "abacaba";

int check(const string &s) {
    int cnt = 0;
    for (int i = 0; i <= n - 7; i++) {
        cnt++;
        for (int j = i; j < i + 7; j++) {
            if (s[j] != t[j - i]) {
                cnt--;
                break;
            }
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cout << "\n";
        cin >> n >> s;
        int cnt = check(s);
        if (cnt > 1)
            cout << "No";
        else {
            if (cnt) {
                cout << "Yes\n";
                for (int i = 0; i < n; i++)
                    if (s[i] == '?') s[i] = 'z';
                cout << s;
            } else {
                bool flag = 0;
                for (int i = 0; i <= n - 7; i++) {
                    vector<int> v;
                    if (s[i] == t[0] || s[i] == '?') {
                        flag = 1;
                        for (int j = i; j < i + 7; j++) {
                            if (s[j] != t[j - i] && s[j] == '?')
                                s[j] = t[j - i], v.push_back(j);
                            else if (s[j] != t[j - i] && s[j] != '?') {
                                flag = 0;
                                break;
                            }
                        }
                    }
                    if (check(s) > 1) flag = 0;
                    if (flag) {
                        for (int j = 0; j < n; j++)
                            if (s[j] == '?') s[j] = 'z';
                        break;
                    } else
                        for (int j = 0; j < v.size(); j++) s[v[j]] = '?';
                    v.clear();
                }
                if (!flag)
                    cout << "No";
                else
                    cout << "Yes\n" << s;
            }
        }
    }
    return 0;
}

B Dubious Cyrpto

题目链接

Solution

枚举 a∈[l,r]a ∈ [l,r]，由于 b−c∈[l−r,r−l]b-c ∈ [l-r,r-l]，故 l−r≤m−na≤r−ll-r \le m-na \le r-l 且 n≥1n \ge 1，由此可得 ⌈m−(r−l)a⌉≤n≤⌊m+(r−l)a⌋\lceil \frac{m-(r-l)}a \rceil \le n \le \lfloor \frac{m+(r-l)}a \rfloor，且 n≥1n \ge 1。这个范围内的 nn 都对应一组解。为了方便，取上界代入, 可推出 b−cb-c。根据 b−cb-c 的正负分类构造即可。

Code

Dubious Cyrpto
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int T;
ll m, l, r;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> l >> r >> m;
        for (ll a = l; a <= r; a++) {
            ll k = (m + r - l) / a;
            if (k > 0) {
                ll delta = m - k * a;
                if (delta < 0 && delta >= l - r) {
                    cout << a << " " << r + delta << " " << r << endl;
                    break;
                } else if (delta >= 0 && delta <= r - l) {
                    cout << a << " " << l + delta << " " << l << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

C Choosing Flowers

题目链接

Solution

显然，价值大的花应尽可能多选，于是将所有价值从大到小排序后贪心的选取价值大的花。设当前枚举到的价值为 cic_i，对应编号为 fif_i 的花，有如下情形：

  • 若 ci=afic_i = a_{f_i}，则一定买 fif_i，得到价值 afia_{f_i}，且还需购买的花的数目减 1
  • 若 ci=bfic_i = b_{f_i}，则有三种情况：
    • 若 fif_i 没有被买过，先买一次 fif_i，得到价值 afia_{f_i}。剩下的全部买 fif_i, 每个价值为 bfib_{f_i}
    • 若 fif_i 已被买过，则剩下的全部买 fif_i, 每个价值为 bfib_{f_i}
    • 不买 fif_i，继续向后考虑

容易证明没有比上述方式更优的选法。

Code

Choosing Flowers
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 100005;
int a[MAXN], b[MAXN], n, m, T;
vector<tuple<int, bool, int> > cost;
bool vis[MAXN];

bool cmp(tuple<int, bool, int> &a, tuple<int, bool, int> &b) {
    return get<0>(a) > get<0>(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        cost.clear();
        fill(vis + 1, vis + m + 1, 0);
        ll tmp = 0, ans = 0;
        for (int i = 1; i <= m; i++) {
            cin >> a[i] >> b[i];
            cost.push_back(make_tuple(a[i], 0, i));
            cost.push_back(make_tuple(b[i], 1, i));
        }
        sort(cost.begin(), cost.end(), cmp);
        for (int i = 0; i < cost.size(); i++) {
            int val = get<0>(cost[i]);
            bool type = get<1>(cost[i]);
            int id = get<2>(cost[i]);
            if (type) {
                if (vis[id])
                    ans = max(ans, tmp + 1ll * n * val);
                else
                    ans = max(ans, tmp + a[id] + 1ll * (n - 1) * val);
            } else {
                tmp += val;
                n--;
                vis[id] = 1;
            }
            if (!n) {
                ans = max(ans, tmp);
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

D New Passenger Trams

题目链接

Solution

设第一辆客车发车时间为 tt，t∈[0,M2−1]t ∈ [0, \frac{M}2 - 1]，那么应该被删除的货车 ii 的发车时间应该满足 hiM+mi∈[t−k+1+j∗M2,t−1+j∗M2]h_iM+m_i ∈[t-k+1+j * \frac{M}2,t-1+j*\frac{M}2]，移项得 mi∈[t−k+1+(j−2hi)∗M2,t−1+(j−2hi)∗M2]m_i ∈[t-k+1+(j-2h_i) * \frac{M}2,t-1+(j-2h_i)*\frac{M}2]，其中 jj 为任意整数。由于 mi∈[0,M−1]m_i∈[0,M-1]，则可能的 jj 的取值为 2hi2h_i 以及 2hi+12h_i+1。将这两个取值分别代入可得 mi∈[t−k+1,t−1]∪[t−k+1+M2,t−1+M2]m_i ∈ [t-k+1,t-1]∪ [t-k+1 +\frac{M}2,t-1+\frac{M}2]。需要注意的是对于区间[t−k+1,t−1][t-k+1,t-1]，其左端点可能小于 00，此时需要将区间从 00 拆成两半，并将小于零的部分对 MM 取模，得mi∈[t−k+1+M,M−1]∪[0,t−1]∪[t−k+1+M2,t−1+M2]m_i∈[t-k+1+M,M-1]∪[0,t-1]∪[t-k+1 +\frac{M}2,t-1+\frac{M}2]。容易发现当 k=1k=1 时不存在包含货车发车时间的区间，即没有货车需要被删去，直接输出 00 00 即可。

从上述推导可知，一辆货车是否被删除仅取决于 mim_i 和 tt。注意到货车发车时间总数不超过 10510^5 个，且对于 mim_i 可以反推出会导致它被删除的 tt 的区间：

  • 若 t≥k−1t \ge k-1，则 t∈[mi+1,mi+k−1]∪[mi+1−M2,mi+k−1−M2]t∈[m_i+1, m_i+k-1]∪[m_i+1 -\frac{M}2, m_i+k-1-\frac{M}2]
  • 若 t≤k−2t \le k-2，则 t∈[0,mi+k−1−M]∪[mi+1−M2,mi+k−1−M2]∪[mi+1,k−2]t∈[0, m_i+k-1-M]∪[m_i+1 -\frac{M}2, m_i+k-1-\frac{M}2]∪[m_i+1, k-2]

因此可以枚举所有货车 ii，对 mim_i 对应的不合法时间段进行区间增值操作，最后统计区间最小值就是需要被删去的货车的最少数目，且区间最小值的位置对应最优发车时间。这样问题转化成区间更新与求区间最值，用动态开点线段树维护即可。

Code

New Passenger Trams
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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 5;
ll n, H, M, k;
ll h[MAXN], m[MAXN];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Node {
    Node *lson, *rson;
    int l, r;
    ll id, lazy;
    ll mi;
} * root, node[MAXN * 64];

Node* newNode(ll l, ll r) {
    static int tot;
    node[tot].l = l, node[tot].r = r;
    node[tot].lazy = 0;
    node[tot].mi = 0, node[tot].id = l;
    return &node[tot++];
}

void pushdown(Node* cur) {
    if (cur->lson) {
        cur->lson->mi += cur->lazy;
        cur->lson->lazy += cur->lazy;
    }
    if (cur->rson) {
        cur->rson->mi += cur->lazy;
        cur->rson->lazy += cur->lazy;
    }
    cur->lazy = 0;
}

void update(Node* cur) {
    if (cur->lson->mi <= cur->rson->mi)
        cur->mi = cur->lson->mi, cur->id = cur->lson->id;
    else
        cur->mi = cur->rson->mi, cur->id = cur->rson->id;
}

void insert(Node* cur, ll l, ll r) {
    if (cur->l == l && cur->r == r) {
        cur->mi++;
        cur->lazy++;
        return;
    }
    int mid = cur->l + cur->r >> 1;
    if (!cur->lson) cur->lson = newNode(cur->l, mid);
    if (!cur->rson) cur->rson = newNode(mid + 1, cur->r);
    pushdown(cur);
    if (r <= mid)
        insert(cur->lson, l, r);
    else if (l > mid)
        insert(cur->rson, l, r);
    else
        insert(cur->lson, l, mid), insert(cur->rson, mid + 1, r);
    update(cur);
}

int main() {
    read(n), read(H), read(M), read(k);
    if (k == 1) cout << 0 << " " << 0, exit(0);
    root = newNode(0, M / 2 - 1);
    for (int i = 1; i <= n; i++) {
        read(h[i]), read(m[i]);

        if (m[i] + 1 <= M / 2 - 1)
            insert(root, max(k - 1, m[i] + 1), min(M / 2, m[i] + k) - 1);
        if (m[i] + k - 1 - M / 2 >= k - 1 && m[i] + 1 - M / 2 <= M / 2 - 1)
            insert(root, max(k - 1, m[i] + 1 - M / 2), min(M / 2, m[i] + k - M / 2) - 1);

        if (m[i] + k - 1 - M >= 0)
            insert(root, 0, min(k - 2, m[i] + k - 1 - M));
        if (m[i] + 1 <= k - 2) 
            insert(root, m[i] + 1, k - 2);
        if (m[i] + k - 1 - M / 2 >= 0 && m[i] + 1 - M / 2 <= k - 2)
            insert(root, max(0ll, m[i] + 1 - M / 2), min(k - 2, m[i] + k - 1 - M / 2));
    }
    cout << root->mi << " " << root->id << endl;
    int t = root->id;
    for (int i = 1; i <= n; i++) {
        if (t >= k - 1) {
            if (t - k + 1 <= m[i] && m[i] <= t - 1)
                cout << i << " ";
            else if (t - k + 1 + M / 2 <= m[i] && m[i] <= t - 1 + M / 2)
                cout << i << " ";
        } else {
            if (t >= 1 && m[i] <= t - 1)
                cout << i << " ";
            else if (t - k + 1 + M <= m[i] && m[i] <= M - 1)
                cout << i << " ";
            else if (t - k + 1 + M / 2 <= m[i] && m[i] <= t - 1 + M / 2)
                cout << i << " ";
        }
    }
    return 0;
}

E Inverse Genealogy

题目链接

Solution

结论题。设当前有 nn 个节点，其中有 kk 个不平衡点。显然，有最多不平衡点的树是毛毛虫树，即 nn 个节点中最多有 n−32\frac{n-3}2 个不平衡点。如果 k=0k = 0，则应有 n=2p−1n=2^p-1；如果 k=1k=1，则 n≠2p−1n \neq 2^p-1。同时当 n=9,k=2n=9,k=2 时无解。验证 nn 个节点，构造 kk 个不平衡点的可行性后暴力构造即可。具体的，让左子树不平衡点数目为 0，即使左子树大小为 2p−12^p-1，接下来在右子树中构造剩余的不平衡点。

Code

Inverse Genealogy
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
#include <bits/stdc++.h>

using namespace std;

int n, k, cnt;

bool check(int cntNode, int cntCritical) {
    if (cntNode % 2 == 0) return 0;
    if (!cntCritical) return !(cntNode & (cntNode + 1));
    if (cntCritical == 1) return cntNode & (cntNode + 1);
    if (cntNode == 9 && cntCritical == 2) return 0;
    return cntCritical > 0 && cntCritical <= (cntNode - 3) / 2;
}

void dfs(int cntNode, int cntCritical, int cur) {
    cout << cur << " ";
    int fa = ++cnt;
    if (cntNode == 1) return;
    for (int lsize = 1; lsize < cntNode; lsize = lsize * 2 + 1) {
        int rsize = cntNode - lsize - 1;
        int rem = cntCritical - (max(lsize, rsize) >= (min(lsize, rsize) * 2));
        if (check(lsize, 0) && check(rsize, rem)) {
            dfs(lsize, 0, fa);
            dfs(rsize, rem, fa);
            return;
        }
    }
}

int main() {
    cin >> n >> k;
    if (!check(n, k)) cout << "NO" << endl, exit(0);
    cout << "YES" << endl;
    dfs(n, k, 0);
    return 0;
}

F Chess Strikes Back

题目链接（Easy Version）

题目链接（Hard Version）

Solution

将 2n∗2m2n*2m 的棋盘分割为 n∗mn*m 个 2∗22*2 的小方格，则问题转化为判断在每个小方格的左上角或右下角放入一个棋子的可行性。规定左上角不能放棋子的方格为 LL 型，右下角不能放棋子的为 RR 型。

若当前方格 (i,j)(i,j) 为 RR 型，即只能在左上角放棋子，则满足 i′≤ii'\le i 且 j′≤jj' \le j 的方格 (i′,j′)(i',j') 不能是 LL 型。换而言之，设 minLiminL_i 表示第 ii 行第一个 LL 型方格的列坐标，maxRimaxR_i 为第 ii 行最后一个 RR 型方格的列坐标，则对 ∀j≤i,minLj>maxRi\forall j\le i,minL_j>maxR_i。

考虑线段树维护区间 [1,n][1,n] 的 minLminL 和 maxRmaxR，每次更新后合并区间时可以判断左子树 minLminL 是否大于右子树 maxRmaxR，若不是则无解。至于 minLiminL_i 和 maxRimaxR_i，由于有删除操作，可用 nn 个 setset 存储，每次询问时取相应 setset 的元素并在线段树上进行单点修改即可。

Code

Chess Strikes Back
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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 5;
int n, m, q, x, y;
unordered_map<int, unordered_map<int, int> > state[2];
set<int> L[MAXN], R[MAXN];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

struct Node {
    Node *lson, *rson;
    int l, r;
    int miL, mxR;
    bool tag;
    Node(int _l, int _r) {
        l = _l, r = _r;
        miL = m + 1, mxR = 0;
        tag = 1;
    }
} * root;

void update(Node* cur) {
    cur->miL = min(cur->lson->miL, cur->rson->miL);
    cur->mxR = max(cur->lson->mxR, cur->rson->mxR);
    if (!cur->lson->tag || !cur->rson->tag || cur->lson->miL <= cur->rson->mxR)
        cur->tag = 0;
    else
        cur->tag = 1;
}

void build(Node*& cur, int l, int r) {
    cur = new Node(l, r);
    if (l == r) return;
    int mid = l + r >> 1;
    build(cur->lson, l, mid);
    build(cur->rson, mid + 1, r);
}

void modify(Node* cur, int x, int val, int tag) {
    if (cur->l == x && cur->r == x) {
        if (tag == 2)
            cur->mxR = val;
        else
            cur->miL = val;
        cur->tag = cur->miL > cur->mxR;
        return;
    }
    int mid = cur->l + cur->r >> 1;
    if (x <= mid)
        modify(cur->lson, x, val, tag);
    else
        modify(cur->rson, x, val, tag);
    update(cur);
}

int main() {
    read(n), read(m);
    read(q);
    build(root, 1, n);
    while (q--) {
        read(x), read(y);
        int i = x + 1 >> 1, j = y + 1 >> 1;
        if (!state[x & 1][i][j]) {
            if (x & 1) {
                state[x & 1][i][j] = 1;
                L[i].insert(j);
                modify(root, i, *L[i].begin(), 1);
            } else {
                state[x & 1][i][j] = 1;
                R[i].insert(j);
                auto it = R[i].end();
                modify(root, i, *(--it), 2);
            }
        } else {
            if (x & 1) {
                state[x & 1][i][j] = 0;
                L[i].erase(j);
                modify(root, i, L[i].empty() ? m + 1 : *L[i].begin(), 1);
            } else {
                state[x & 1][i][j] = 0;
                R[i].erase(j);
                auto it = R[i].end();
                modify(root, i, R[i].empty() ? 0 : *(--it), 2);
            }
        }
        if (!root->tag)
            puts("NO");
        else
            puts("YES");
    }
    return 0;
}