Solution - Codeforces Round 1051 (Div. 2)

Posted on Edited on

Codeforces Round 1051 (Div. 2)

A. All Lengths Subtraction

Solution

可以发现第一次必须弄最大的，第二次必须弄前两大的，以此类推，所以操作是固定的，模拟即可。

另解：这说明原始序列是单峰（先增后减）的序列。

Code

Show 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
#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int n, pos[N];
signed main() {
    int t; cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            int x; cin >> x;
            pos[x] = i;
        }
        int l = pos[n], r = pos[n];
        bool flag = true;
        for (int i = n - 1; i >= 1; --i) {
            if (pos[i] < l) l = pos[i];
            if (pos[i] > r) r = pos[i];
            if (r - l + 1 != n - i + 1) {
                flag = false;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;

    }
}

B. Discounts

Solution

可以免费若干个数，显然尽可能让大的免费好，所有将aa和bb都排序，bb从小到大使用，每次取出aa中最大的若干个，如果干不了就直接买。

Code

Show 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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1;
int n, k, A[N], B[N];
signed main() {
    cin.tie(0), cout.tie(0); ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        cin >> n >> k;
        for (int i = 1; i <= n; ++i) {
            cin >> A[i];
        }
        sort(A + 1, A + 1 + n);
        reverse(A + 1, A + 1 + n);
        for (int i = 1; i <= k; ++i) {
            cin >> B[i];
        }
        sort(B + 1, B + 1 + k);
        LL ans = 0;
        int j = 0;
        for (int i = 1; i <= k; ++i) {
            if (j + B[i] > n) {
                while (j < n) {
                    ans += A[++j];
                }
                break;
            }
            for (int x = 1; x < B[i]; ++x) {
                ans += A[++j];
            }
            ++j;
        }
        while (j < n) {
            ans += A[++j];
        }
        cout << ans << endl;
    }
}

C. Max Tree

Solution

理论最大值为∑i=1n−1max⁡{xi,yi}\sum_{i = 1}^{n - 1} \max\{x_i, y_i\}。

如果想要取到最大值，需要建立n−1n-1个约束(ai,bi)(a_i, b_i)，表示aia_i点编号大于bib_i，且不存在环，所以一定存在一种排序方式，让所有约束被满足。

具体而言，拓扑排序即可。

Code

Show 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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1;
int n, d[N], p[N];
struct Q {
    int u, v, x, y;
} q[N];
vector<int> G[N];
LL judger() {
    LL ans = 0;
    for (int i = 1; i < n; ++i) {
        if (p[q[i].u] > p[q[i].v]) {
            ans += q[i].x;
        } else {
            ans += q[i].y;
        }
    }
    return ans;
}
signed main() {
    cin.tie(0), cout.tie(0); ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) d[i] = 0, G[i].clear();
        LL ans = 0;
        for (int i = 1; i < n; ++i) {
            int u, v, x, y;
            cin >> u >> v >> x >> y;
            if (u > v) {
                swap(u, v);
                swap(x, y);
            }
            q[i] = {u, v, x, y};
            if (x > y) {
                ++d[u];
                G[v].push_back(u);
                ans += x;
            } else {
                ++d[v];
                G[u].push_back(v);
                ans += y;
            }
            
        }
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (d[i] == 0) {
                q.push(i);
            }
        }
        int idx = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            p[x] = ++idx;
            for (const auto& y : G[x]) {
                --d[y];
                if (!d[y]) {
                    q.push(y);
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            cout << p[i] << ' ';
        }
        cout << endl;
        assert(judger() == ans);
    }
}

D1/D2 Inversion Graph Coloring

如果出现三元下降序列，则不可能。否则，把大的设为red，小的设为blue就行了。

所以问题转化为求子序列中不含三元下降子序列的个数。

令f[i][j][k]f[i][j][k]表示[1,i][1,i]区间内的合法子序列中，最大数为jj，最大的逆序对的第二个数为kk的子序列个数。

考虑转移。

初始化时f[0][0][0]=1f[0][0][0]=1。

{f[i][j][ai]+=∑p=0aif[i−1][j][p]     j>aif[i][j][k]+=f[i−1][j][k]f[i][ai][k]+=∑p=0aif[i−1][p][k]     k<ai\begin{cases} f[i][j][a_i] += \sum_{p = 0}^{a_i} f[i - 1][j][p]\,\,\,\,\, j> a_i\\ f[i][j][k] += f[i - 1][j][k] \\ f[i][a_i][k] += \sum_{p = 0}^{a_i} f[i - 1][p][k]\,\,\,\,\, k<a_i\\ \end{cases}

最后答案就是∑j=1n∑k=0j−1f[i][j][k]\sum_{j = 1}^{n}\sum_{k = 0}^{j - 1}f[i][j][k]。

这样就可以O(n3)O(n^3)解决。

考虑优化。首先可以把ii维省掉，第二个式子就不需要了。然后第一个式子和第三个式子，可以构造两个前缀和函数：

[\begin{cases}
g[j][k] = \sum_{p = 0}^{k} f[j][p] \
h[j][k] = \sum_{p = 0}^{j} f[p][k] \
\end{cases}]

这两个函数需要实现O(n2)O(n^2)次单点加和O(n2)O(n^2)次前缀和，可以用树状数组维护。

时间复杂度O(n2log⁡n)O(n^2\log n)。

Code

Show 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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e3 + 5, MOD = 1e9 + 7;
int n, f[N][N];
inline int fpow(int a, int b) {
    int x = 1;
    while (b) {
        if (b & 1) x = LL(x) * a % MOD;
        a = LL(a) * a % MOD;
        b >>= 1;
    } 
    return x;
}
int s[N][N], r[N][N], maxn;
inline void add(int j, int k, int x) {
    ++j; ++k;
    for (int jj = j; jj <= maxn; jj += jj & -jj) {
        s[jj][k] = (s[jj][k] + x) % MOD;
    }
    for (int kk = k; kk <= maxn; kk += kk & -kk) {
        r[j][kk] = (r[j][kk] + x) % MOD;
    }
}
inline int queryS(int j, int k) {
    ++j; ++k;
    int res = 0;
    for (; j; j -= j & - j) {
        res = (res + s[j][k]) % MOD;
    }
    return res;
}
inline int queryR(int j, int k) {
    ++j; ++k;
    int res = 0;
    for (; k; k -= k & - k) {
        res = (res + r[j][k]) % MOD;
    }
    return res;
}
struct node {
    int j, k, x;
};
signed main() {
    cin.tie(0), cout.tie(0); ios::sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        cin >> n;
        maxn = n + 1;
        for (int i = 0; i <= n + 1; ++i) {
            for (int j = 0; j <= n + 1; ++j) {
                f[i][j] = 0;
                s[i][j] = 0;
                r[i][j] = 0;
            }
        }
        f[0][0] = 1;
        add(0, 0, 1);
        int ans = 0;
        vector<node> adds;
        for (int i = 1; i <= n; ++i) {
            adds.clear();
            int x; cin >> x;
            for (int k = 0; k < x; ++k) {
                int qS = queryS(x, k);
                f[x][k] += qS;
                adds.push_back({x, k, qS});
                // printf(">>1::::i = %d, f[%d][%d] += %d\n", i, x, k, qS);
            }
            for (int j = x + 1; j <= n; ++j) {
                int qR = (queryR(j, x)) % MOD;
                f[j][x] += qR;
                adds.push_back({j, x, qR});
                // printf(">>2::::i = %d, f[%d][%d] += %d\n", i, j, x, qR);
            }
            ans = ans * 2 % MOD;
            // for (int j = 0; j <= n; ++j) {
            //     for (int k = 0; k <= n; ++k) {
            //         printf("f[%d][%d] = %d\n",j,k,f[j][k]);
            //     }
            // }
            for (int j = 0; j <= n; ++j) {
                ans = (ans + (queryR(j, n) + MOD - queryR(j, x)) % MOD) % MOD;
            }
            for (auto a : adds) {
                add(a.j, a.k, a.x);
            }
            // printf("ans = %d\n", ans);
        }
        cout << (MOD - ans + fpow(2, n)) % MOD << endl;
    }
}/*

4
4
4 2 3 1
7
7 6 1 2 3 3 2
5
1 1 1 1 1
11
7 2 1 9 7 3 4 1 3 5 3
*/

E. Make Good

Solution

巧妙思想：将所有偶数位反转，那么操作变为：

  1. 取偶数ii，若si=),si+1=(s_i = ), s_{i + 1} = (，则交换sis_i和si+1s_{i+1}；
  2. 取奇数ii，若si=(,si+1=)s_i = (, s_{i + 1} = )，则交换sis_i和si+1s_{i+1}；
  3. 取偶数ii，若si=(,si+1=)s_i = (, s_{i + 1} = )，则交换sis_i和si+1s_{i+1}；
  4. 取奇数ii，若si=),si+1=(s_i = ), s_{i + 1} = (，则交换sis_i和si+1s_{i+1}；

也就是说我们可以交换任意两个相邻的元素，换言之，可以任意排序整个数列。

假设反转偶数位后，有xx个((和yy个))。设最后排放中，有x1x_1个((在奇数位，x2x_2个((在偶数位，y1y_1个))在奇数位，y2y_2个))在偶数位，则满足以下约束：

[\begin{cases}
n是偶数 \
x + y = n \
x_1 + x_2 = x \
y_1 + y_2 = y \
x_1 + y_2 = n/2 \
x_1 + y_1 = n/2 \
\end{cases}]

四个方程，四个未知数，那么很容易把x1,x2,y1,y2x_1,x_2,y_1,y_2全部解出来（x1=x2=x/2,y1=y2=y/2x_1=x_2=x/2,y_1=y_2=y/2），然后尽量先放x1x_1和y2y_2，再放x2x_2和y1y_1就好了。

Code

Show 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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
inline bool get() {
    char ch = getchar();
    while (ch != '(' && ch != ')') ch = getchar();
    return ch == ')';
}
int n, sum[2];
bool ans[N];
signed main() {
    int t; cin >> t;
    while (t--) {
        cin >> n;
        sum[0] = sum[1] = 0;
        for (int i = 1; i <= n; ++i) {
            int x = get();
            sum[1 ^ x ^ (i & 1)]++;
        }
        if (n % 2 != 0) {
            cout << -1 << endl;
            continue;
        } else if (sum[0] % 2 != 0 || sum[0] == 0) {
            cout << -1 << endl;
            continue;
        }
        for (int i = 1, j = (sum[0] >> 1), k = (sum[1] >> 1); i <= n; ++i) {
            if (i & 1) {
                if (j) {
                    --j;
                    ans[i] = 0;
                } else {
                    ans[i] = 1;
                }
            } else {
                if (k) {
                    --k;
                    ans[i] = 0;
                } else {
                    ans[i] = 1;
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            cout << (ans[i] ? ')' : '(');
        }
        cout << endl;
    }
    return 0;
}/*
x1 + x2 = x
y1 + y2 = y
x + y = n
x1 + y2 = n
x2 + y1 = n
x1 + y1 = n
y1 = y2
x1 = x2
*/

F. Increasing Xor

Solution

首先可以发现区间内所有数可以变成它以及它之前的所有数的任意异或和，以及00。有个贪心的做法，每次从左往右加入数，加入的数会更新可能的所有数，选最小的一个（但比之前的大），如果有一个没得选，就一定不可能单增。

现在考虑如何高效完成这个动作。首先引入异或基：

类似线性代数中的向量组，一个数值组中也可以取若干个线性无关的数值（最多为二进制位数个），使得数值组中任意一个数都可以由这几个数值的线性组合（异或和）得到，这样的几个数称为异或基。对于一组数值组，异或基的个数是固定的。

那么，我们只需求出[l,r][l,r]内数值组的异或基中字典序最小的一组，就可以判断每个数是否能够取得大于上一个数的值。

异或基有这样一个性质：如果已知当前数值组的一组异或基，现在新加入一个数（不为00），如果这个数能被异或基表示，则一定存在一种方案，让原先的异或基中去除一个数，再加入新的数，构成新的异或基。证明如下：

假设当前数xx能被表示为aj1⊕aj2⊕⋯⊕ajka_{j_1}\oplus a_{j_2}\oplus \cdots \oplus a_{j_k}，其中aj1,aj2,⋯ ,ajka_{j_1}, a_{j_2}, \cdots ,a_{j_k}是原先异或基中的数，则可以去掉这些数中的任意一个，xx就不能被表示（表示方法唯一，否则和异或基的性质矛盾）。去掉这个数后，再加入xx，就构成了一个新的异或基。

于是我们可以这样操作：从后往前遍历每一个数，并维护当前的字典序最小的异或基。如果新的数不能被表示，那么异或基加入新的数，这是新的字典序最小的异或基（否则之前那个也不是最小的）；如果新的数可以被表示，则去除能表示新的数的若干数中排序最靠右的一个，再加入新的数，这样操作得到新的异或基一定也是字典序最小的（如果不是，之前那个也不是最小的）。

但是找到异或基中表示新的数的基需要一点技巧。具体而言，我们储存异或基时使用以下规则：

假设现在要加入新的数xx：

  1. 从大到小枚举每个数位，这个数位如果xx为11并且异或基有以这个数位为最大数位的数，则让x→x⊕aix\rightarrow x\oplus a_i；
  2. 最后如果x≠0x\neq 0，则将xx加入到xx的最高数位那个节点（此时运算后的xx不可以被表示，并且异或基中没有最高数位为xx当前数位的节点），并储存xx在数组中的位置；
  3. 最后如果x=0x=0，则跟xx做过运算的数中，找到数组位置最靠右的数，更改它的数组位置为新的数组位置。

这样就可以完成O(log⁡ai)O(\log a_i)的查询。不过由于后面我们是要排序所有的位置，所有操作33不妨改为将所有异或基以及新的数全部拿出来，重新按从左到右的顺序插入异或基。这样的操作是O(log⁡2ai)O(\log^2 a_i)的。

将所有询问按照ll排序，就可以得到所有从ll开始的字典序最小的异或基。这个时候，由于xx个异或基可以表示2x2^x个不同的数，每次在新的异或基节点加入时，都会多一倍的数出现，我们需要知道上一个节点选择的数在新的所有可能的数中排的位次（可以用类似树状数组二分的方法计算）。

总复杂度O(nlog⁡2ai)O(n\log^2 a_i)。

Code

Show 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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1, M = 21;
int n, q, A[N], r[N];
class XorBasis {
public:
    vector<int> val, idx;

    XorBasis() {
        reset();
    }
    void reset() {
        val.assign(M, 0);
        idx.clear();
    }
    bool add(int x, int pos) {
        for (int i = M - 1; ~i; --i) {
            if ((x >> i) & 1) {
                if (!val[i]) {
                    val[i] = x;
                    idx.push_back(pos);
                    return true;
                }
                x ^= val[i];
            }
        }
        return false;
    }
    int rank(int x) {
        int rk = 0;
        int now = 0;
        for (int i = M - 1; ~i; --i) {
            if (val[i]) {
                rk <<= 1;
                if ((x >> i) & 1) {
                    rk |= 1;
                }
                if (((now >> i) & 1) != ((x >> i) & 1)) {
                    now ^= val[i];
                }
            }
            
        }
        assert(now == x);
        return rk + 1;
    }
    int kth(int x) {
        --x;
        int res = 0;
        for (int i = M - 1, j = idx.size() - 1; ~i; --i) {
            if (val[i]) {
                if ((x >> j) & 1) {
                    if (((res >> i) & 1) == 0) {
                        res ^= val[i];
                    }
                } else {
                    if (((res >> i) & 1)) {
                        res ^= val[i];
                    }
                }
                // printf("kth::::j = %d, res = %d\n",j,res);
                --j;
            }
        }
        return res;
    }
};
signed main() {
    // ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tt; cin >> tt;
    while (tt--) {
        cin >> n >> q;
        for (int i = 1; i <= n; ++i) {
            cin >> A[i];
        }
        XorBasis xb;
        for (int i = n; i >= 1; --i) {
            bool flag = xb.add(A[i], i);
            if (!flag) {
                vector<int> pre = xb.idx;
                xb.reset();
                xb.add(A[i], i);
                sort(pre.begin(), pre.end());
                for (auto j : pre) {
                    xb.add(A[j], j);
                }
            }
            sort(xb.idx.begin(), xb.idx.end());
            XorBasis now;
            for (int j = 0, pre = -1; j < (int)xb.idx.size(); ++j) {
                int pos = xb.idx[j];
                now.add(A[pos], pos);
                // if (j==1)for (int k = 1; k <= (1 << (j + 1)); ++k) {
                //     printf("kth %d = %d\n", k, now.kth(k));
                // }
                if (j + 1 == (int)xb.idx.size()) {
                    if (pre == -1) {
                        r[i] = i + 1;
                        break;
                    } else {
                        int rk = now.rank(pre);
                        // printf("rk = %d\n", rk);
                        r[i] = pos + (1 << (j + 1)) - rk - 1;
                    }
                } else {
                    int nxt = xb.idx[j + 1];
                    if (pre == -1) {
                        r[i] = i + 1;
                        if (nxt - 1 <= r[i]) {
                            pre = now.kth(nxt - pos);
                        } else {
                            break;
                        }
                    } else {
                        int rk = now.rank(pre);
                        r[i] = pos + (1 << (j + 1)) - rk - 1;
                        if (nxt - 1 <= r[i]) {
                            pre = now.kth(nxt - pos + rk);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 1; i <= q; ++i) {
            int le, ri; cin >> le >> ri;
            if (r[le] >= ri) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
}/*
1
14 1
10 8 14 15 2 8 7 7 14 6 14 13 11 15
9 13


*/