抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

Codeforces Div.2 VP 记录

更新于 2022年11月14日

12.3k 字

65 分钟

次浏览

我不会做普及题了。

只有有意思的题目才会写题解（当然对笔者这种普及组选手来说，可能所有题都有意思）。

11 月记录

新征途。

Codeforces Round #830 (Div.2)

Portal.

A. Bestie

Portal.

(n,n−1)=1(n,n-1)=1，所以最多只需要改 n,n−1n,n-1 两次，讨论一下即可。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;

int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

int main(void) {
    int T;
    cin >> T;
    while (T--) {
        int n, a[25], g = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i], g = gcd(g, a[i]);
        if (g == 1) puts("0");
        else if (gcd(g, n) == 1) puts("1");
        else if (gcd(g, n - 1) == 1) puts("2");
        else puts("3");
    }
    return 0;
}

B. Ugu

Portal.

查看代码 
#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

int main(void)
{
    int T, n;
    cin >> T;
    while (T--) {
        string s;
        cin >> n >> s;
        bool rev = 0;
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            int a = s[i] - '0', b = s[i - 1] - '0';
            if (a == rev && b != rev)
                ++ans, rev = !rev;
        }
        cout << ans << endl;
    }
    return 0;
}

C. Sheikh (Hard Version)

Portal.

一个数列的价值是数列的总和减去所有元素的异或和。每个询问形如 Li,RiL_i,R_i，含义是希望找到一个区间 [l,r][l,r]，满足 Li≤l≤r≤RiL_i\le l\le r\le R_i，使得这个区间的价值最大。输出所有价值最大的区间中最短的一个（多解则任意）。n,q≤2×105n,q\le 2\times 10^5

由于异或是不进位的，所以当区间长度变长的时候，价值必然不会变小。

如果一个数是零，那么显然它对答案是没有贡献的，所以可以删掉左右两端的零，中间的也可以删掉。由于最多有 3232 位会导致异或与加法等价，所以去掉 00 之后可以暴力计算。

查看代码 
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long i64;

int n, q;
int a[100005];
int pre[100005], nxt[100005];
i64 sum[100005], xxor[100005];

i64 calc(int l, int r) {
    return (sum[r] - sum[l - 1]) - (xxor[r] ^ xxor[l - 1]);
}

int main(void) 
{
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> q;
        for (int i = 1; i <= n; ++i)
            cin >> a[i], sum[i] = sum[i - 1] + a[i], xxor[i] = (xxor[i - 1] ^ a[i]);
        for (int i = 1; i <= n; ++i)
            if (a[i]) pre[i] = i;
            else pre[i] = pre[i - 1];
        nxt[n + 1] = n + 1;
        for (int i = n; i >= 1; --i)
            if (a[i]) nxt[i] = i;
            else nxt[i] = nxt[i + 1];
        while (q--) {
            int l, r;
            cin >> l >> r;
            l = min(r, nxt[l]);
            r = max(l, pre[r]);
            if (l == r) {
                cout << l << ' ' << l << '\n';
                continue;
            }
            int u = l, v = r, ans = r - l + 1;
            i64 res = calc(l, r);
            for (int i = l; i <= r && calc(i, r) == res; i = nxt[i + 1])
                for (int j = r; j >= i && calc(i, j) == res; j = pre[j - 1])
                    if (j - i + 1 < ans) ans = j - i + 1, u = i, v = j;
            cout << u << ' ' << v << '\n';
        }
    }   
    return 0;
}

D. Balance (Hard version)

Portal.

最初你有一个集合，该集合仅包括一个元素 00，而且它会一直存在。你需要处理 q(≤2×105)q(\le 2\times 10^5) 个下述类型的操作：

  • + x 向集合中添加一个整数 xx 。数据保证集合中原来没有这个整数。
  • - x 从集合中移除整数 xx 。数据保证集合包含这个就要删除的整数。
  • ? k 找出当前是 kk 的倍数且不被包含在集合中的最小非负整数 xx。

考虑乱搞，用四个 map 分别记录：s，数是否在集合内；ans，用于类似离线直接跳到之前枚举的最大位置的 ansans（即对于查询过的 kk 所查询到的 ansans）；del，有哪些是被查询过的，但是后来被无情删除的；vis，有哪些数可以被作为 kk 的答案（查询的时候顺带统计）。

修改的时候要利用 vis 来更新 del。查询的时候一开始直接拿 00 搞，之后再查就从 ans[x]ans[x] 开始暴力跳，并且在 visvis 中插入；最后再与被删除的当中（因为删除了，又可以取了）取个最小值。

时间复杂度的严格证明很困难，不打算研究了。

查看代码 
#include <iostream>
#include <cstdio>
#include <set> 
#include <map>

using namespace std;
typedef long long i64;

map <i64, i64> s, ans;
map <i64, set<i64>> del, vis;

int main(void) 
{
    int q; cin >> q;
    s[0] = 1;
    while (q--) {
        char opt; i64 x;
        cin >> opt >> x;
        if (opt == '+') {
            s[x] = true;
            for (auto i : vis[x])
                del[i].erase(x);
        } else if (opt == '-') {
            s[x] = false;
            for (auto i : vis[x])
                del[i].insert(x);
        } else {
            while (s[ans[x]]) {
                vis[ans[x]].insert(x);
                ans[x] += x;
            }
            i64 res = ans[x];
            if (!del[x].empty()) res = min(res, *del[x].begin());
            cout << res << '\n';
        }
    }
    return 0;
}

E. Location

Portal.

初始给定序列 a,ba,b，需要维护以下操作：

  1. 给定 l,r,xl,r,x，对于 ∀i∈[l,r]\forall i\in[l,r]，令 ai=xa_i=x。
  2. 给定 l,rl,r，求 min⁡i∈[l,r]lcm⁡(ai,bi)gcd⁡(ai,bi)\min_{i\in[l,r]}\frac{\operatorname{lcm}(a_i,b_i)}{\gcd(a_i,b_i)}。

数据范围 1≤n,q,ai≤5×1041\leq n,q,a_i\leq 5\times 10^4。

说点题外话，这道题对我来说很有实力，也让我更加期待 NOIP 结束后学习数据结构的生活了。

看到这么诡异的查询当然分块。

这玩意相当于是求 f(i)=ai×bigcd⁡(ai,bi)2f(i)=\cfrac{a_i\times b_i}{\gcd(a_i,b_i)^2}，显然一开始这玩意的值可以预处理出来。

现在考虑如何修改，零散块当然暴力维护，但是整块怎么办？注意这里修改操作的特殊性，是区间赋值，而且数的值域也很小，因此可以预处理 vi,jv_{i,j} 代表 ii 块修改为 jj 之后的答案。

但是这样预处理的复杂度就太高了，需要考虑优化。方法是开一个桶 tt，t[x]t[x] 记录含有因子 xx 的最小 bb，然后枚举每个 aa 的因数，如果 t[x]t[x] 存在 aa 就可能是最大公约数，尝试更新。

基本上不卡常，只要块长不离谱就很容易过的。

查看代码 
#include <iostream>
#include <vector>
#include <cstring>
#pragma GCC optimize(3, "Ofast")

using namespace std;
typedef unsigned int uint;
const uint BLOCK_SIZE = 160;
const uint INF = 0x9f9f9f9f;

uint read(void) {
    uint x = 0, c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return x;
}

void print(uint x) {
    if (x > 9) print(x / 10);
    putchar(x % 10 ^ 48);
}

uint n, q;
uint a[50005], b[50005];
uint L[334], R[334], minn[334];
uint setv[334], v[334][50005];
uint pos[50005];
vector<uint> d[50005];

uint gcd(uint x, uint y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}

inline uint F(uint x) {
    uint g = gcd(a[x], b[x]);
    return a[x] * b[x] / (g * g); 
}

inline void pushdown(uint o) {
    if (!setv[o]) return;
    for (uint i = L[o]; i <= R[o]; ++i) a[i] = setv[o];
    setv[o] = 0;
}

inline void maintain(uint l, uint r, uint x) {
    uint p = pos[l]; pushdown(p);
    for (uint i = l; i <= r; ++i) a[i] = x;
    minn[p] = INF;
    for (uint i = L[p]; i <= R[p]; ++i) minn[p] = min(minn[p], F(i));
}

void update(uint l, uint r, uint x) 
{
    uint p = pos[l], q = pos[r];
    if (p == q) {
        maintain(l, r, x);
        return;
    }
    for (uint i = p + 1; i < q; ++i) setv[i] = x, minn[i] = v[i][x];
    maintain(l, R[p], x); maintain(L[q], r, x);
}

uint Query(uint l, uint r) {
    uint p = pos[l]; pushdown(p);
    uint ans = INF;
    for (uint i = l; i <= r; ++i) ans = min(ans, F(i));
    return ans;
}

uint query(uint l, uint r)
{
    uint p = pos[l], q = pos[r];
    if (p == q) return Query(l, r);
    uint ans = INF;
    for (uint i = p + 1; i < q; ++i) ans = min(ans, minn[i]);
    ans = min(ans, Query(l, R[p])); ans = min(ans, Query(L[q], r));
    return ans;
}

int main(void)
{
    n = read(), q = read();
    for (uint i = 1; i <= n; ++i) a[i] = read();
    for (uint i = 1; i <= n; ++i) b[i] = read();
    uint t = n / BLOCK_SIZE;
    for (uint i = 1; i <= t; ++i)
        L[i] = R[i - 1] + 1, R[i] = i * BLOCK_SIZE;
    if (R[t] < n) { ++t; L[t] = R[t - 1] + 1; R[t] = n; }
    for (uint i = 1; i <= t; ++i) {
        minn[i] = INF;
        for (uint j = L[i]; j <= R[i]; ++j)
            pos[j] = i, minn[i] = min(minn[i], F(j));
    }

    for (uint i = 1; i <= 50000; ++i) // 预处理约数
        for (uint j = 1; j * j <= i; ++j)
            if (i % j == 0) {
                d[i].emplace_back(j);
                if (j * j != i) d[i].emplace_back(i / j);
            }

    static uint tmp[50005]; // tmp[x] 记录含有因子 x 的最小 b
    memset(v, 0x9f, sizeof(v));
    for (uint i = 1; i <= t; ++i) { // 预处理修改后的答案
        memset(tmp, 0x9f, sizeof(tmp));
        for (uint j = L[i]; j <= R[i]; ++j)
            for (uint a : d[b[j]]) tmp[a] = min(tmp[a], b[j]);
        for (uint j = 1; j <= 50000; ++j)
            for (uint a : d[j]) // 枚举 a 是 j 的因子
                if (tmp[a] != INF) v[i][j] = min(v[i][j], j * tmp[a] / (a * a)); // a 可能是最大公约数，尝试更新
    }

    while (q--) {
        uint op = read(), l = read(), r = read(), x;
        if (op == 1) {
            x = read();
            update(l, r, x);
        } else {
            print(query(l, r));
            putchar('\n');
        }
    }
    return 0;
}

Codeforces Round #822 (Div.2)

Portal.

A. Select Three Sticks

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int n;
int a[305];

inline void solve(void)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    sort(a + 1, a + n + 1);
    int ans = 2e9;
    for (int i = 2; i < n; ++i)
        ans = min(ans, a[i + 1] - a[i - 1]);
    cout << ans << endl;
}

int main(void)
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

B. Bright, Nice, Brilliant GNU

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

inline void solve(void)
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= i; ++j)
            if (j == 1 || j == i) cout << "1 ";
            else cout << "0 ";
        putchar('\n');
    }
}

int main(void)
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

C. Removing Smallest Multiples

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

char s[1000005];

inline void solve(void)
{
    int n;
    i64 ans = 0;
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i; j <= n; j += i)
            if (s[j] != '1')
            {
                if (s[j] == '0') ans += i;
                s[j] = '2';
            }
            else break;
    }
    printf("%lld\n", ans);
}

int main(void)
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

D. Slime Escape

Portal.

贪心的向左右走，只要是正的，就可以走，同时记录左右最大的和用以计算。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, k;
int a[200005];
i64 s[200005];

void solve(void)
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    if (a[k] < 0) return puts("NO"), void();
    s[k] = 0;
    for (int i = k - 1; i >= 1; --i) s[i] = s[i + 1] + a[i];
    for (int i = k + 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
    int l = k - 1, r = k + 1;
    i64 sl = a[k], sr = a[k];
    while (l > 0 && r <= n) {
        int ll = l, rr = r;
        while (s[l] + sr >= 0 && l > 0) sl = max(sl, a[k] + s[l]), l -= 1;
        while (s[r] + sl >= 0 && r <= n) sr = max(sr, a[k] + s[r]), r += 1;
        if (ll == l && rr == r) return puts("NO"), void();
    }
    puts("YES");
}

int main(void)
{
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

E. Rectangular Congruence

Portal.

给定一个质数 nn（n≤350n \leq 350） 和一个序列 b1,b2,...,bnb_1, b_2, ..., b_n（对于 ∀i\forall i 有 0≤bi<n0 \leq b_i < n），你需要构造一个 n×nn \times n 的矩阵 aa，满足：

  • 对于 ∀i,j≤n\forall i, j \leq n 有 0≤ai,j<n0 \leq a_{i, j} < n。

  • 对于 ∀1≤r1<r2≤n,1≤c1<c2≤n\forall 1 \leq r_1 < r_2 \leq n, 1 \leq c_1 < c_2 \leq n 有 ar1,c1+ar2,c2≢ar1,c2+ar2,c1(modn)a_{r1, c1} + a_{r2, c2} \not\equiv a_{r1, c2} + a_{r2, c1} \pmod n。

  • 对于 ∀1≤i≤n\forall 1 \le i \le n 有 ai,i=bia_{i,i}=b_i。

将条件二转化为 ar2,c2−ar2,c1≢ar1,c2−ar1,c1(modn)a_{r_2,c_2}-a_{r_2,c_1}\not\equiv a_{r_1,c_2}-a_{r_1,c_1}\pmod n，这就相当于构造每一行的差不一样即可，分别为 0∼n−10\sim n-1，然后根据 bb 做相应调整即可。

因为 nn 是质数，所以列出同余方程之后发现无解，这样构造是成立的。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;

int main(void)
{
    int n, b;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b);
        int diff = ((i - 1) * (i - 1) % n - b + n) % n;
        for (int j = 1; j <= n; ++j)
            printf("%d ", ((i - 1) * (j - 1) % n - diff + n) % n);
        putchar('\n');
    }
    return 0;
}

F. Zeros and Ones

Portal.

SS 是一个由以下方式生成的无限长 01 字符串：

  • 最初，令 SS 为 “0”。
  • 随后进行以下操作无穷多次：将 SS 与各位取反后的 SS 连接。以前 4 次操作为例：
次数SS取反后的 SS操作后得到的 SS
10101
201100110
30110100101101001
401101001100101100110100110010110

给定 T(1≤T≤100)T(1\le T \le 100) 组 22 个正整数 n,m(1≤n,m≤1018)n,m(1\le n,m\le 10^{18})，求 S0S1⋯Sm−1S_0S_1 \cdots S_{m-1} 和 SnSn+1⋯Sn+m−1S_{n}S_{n+1} \cdots S_{n+m-1} 有几位不同。

也就是说我们要求解对于多少个 0≤i<m0\le i<m 有 Si≠Si+nS_i\ne S_{i+n}。可以发现 SiS_i 代表 ii 的二进制中 11 的个数的奇偶性。

记 dfs(n, m, flag) 代表 n,mn,m 时，flagflag 为真代表相同，假为不同。

当 2∣i2\mid i 时设 i=2ki=2k，那么 Si=Sk,Si+n=Sk+⌊n/2⌋⊕(n mod 2)S_i=S_k,S_{i+n}=S_{k+\lfloor n/2\rfloor}\oplus (n\bmod 2)。前者显然成立，后者分类讨论：

  • 当 2∣n2\mid n 时，有 Si+n=S(i+n)/2S_{i+n}=S_{(i+n)/2}，二进制最后一位是 00，所以成立。
  • 当 2∤n2\nmid n 时，有 Si+n≠S⌊(i+n)/2⌋S_{i+n}\ne S_{\lfloor(i+n)/2\rfloor}，前者是奇数，最后一位 11 被搞掉了，所以也成立。

我们可以将求解 Si≠Si+nS_{i}\ne S_{i+n} 转换为求解 SkS_{k} 与 Sk+⌊n/2⌋S_{k+\lfloor n/2\rfloor} 的关系。也就是 dfs(n, m, flag) 中 2∣i2\mid i 的一部分，答案是 dfs(n >> 1, m + 1 >> 1, n & 1)（最大到 ⌊n/2⌋\lfloor n/2\rfloor，满足 2∣i2\mid i 的一共有 ⌊(m+1)/2⌋\lfloor(m+1)/2\rfloor 个）。

当 2∤i2\nmid i 时也可以通过相应的方式讨论出来。

查看代码 
#include <iostream>
#include <cstdio>
#include <map>
#define lowbit(x) (x & -x)

using namespace std;
typedef long long i64;

int bitcount(i64 x) {
    int ans = 0;
    while (x) {
        x -= lowbit(x);
        ++ans;
    }
    return ans;
}

map<pair<i64, i64>, i64> f;

i64 calc(i64 n, i64 m, bool flag) {
    if (m == 0) return 0;
    if (flag) return m - calc(n, m, 0);
    if (m == 1) return bitcount(n) % 2 != 0;
    if (f.count({n, m})) return f[{n, m}];
    i64 ans = calc(n >> 1, m + 1 >> 1, n & 1) + calc(n + 1 >> 1, m >> 1, n & 1);
    return f[{n, m}] = ans;
}

int main(void) {
    int T; cin >> T;
    while (T--) {
        i64 n, m;
        cin >> n >> m;
        cout << calc(n, m, 0) << "\n";
    }   
    return 0;
}

Codeforces Round #833 (Div.2)

Portal.

A. The Ultimate Square

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    int n;
    cin >> n;
    cout << (n + 1) / 2 << endl;   
}

int main(void) {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

B. Diverse Substrings

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int a[15];

void solve(void) {
    int n, ans = 0;
    static char s[100005];
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        memset(a, 0, sizeof(a));
        int maxx = 0, flag = 0;
        for (int j = i; j < n; ++j) {
            int x = s[j] - '0';
            if (a[x] == 0) ++flag;
            a[x] += 1;
            maxx = max(a[x], maxx);
            if (maxx <= flag) ++ans;
            if (a[s[j] - '0'] > 10) break;
        }
    }
    cout << ans << endl;
}

int main(void) {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

C. Zero-Sum Prefixes

Portal.

给定一个长为 nn 的数列 aa，你可以将其中的每个 00 分别改成任意整数。求出你最多能让多少个 kk 满足 a1+⋯+ak=0a_1+\dots+a_k=0。

考虑 00 干了什么，可以变动后面一段的前缀和，这样用一个 STL map 记录一下哪一个前缀和最多，然后就把这个 00 变成这个的相反数。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[200005];
i64 s[200005];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int ans = 0, maxt = 0;
    bool fs = true;
    map<i64, int> se;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0) {
            if (fs) fs = false;
            else {
                ans += maxt;
                maxt = 0; se.clear();
                s[i] = 0;
            }
        }
        s[i] = s[i - 1] + a[i];
        if (fs) ans += (s[i] == 0);
        else maxt = max(maxt, se[s[i]] += 1);
    }
    if (!fs) ans += maxt;
    cout << ans << '\n';
}

int main(void) {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

D. ConstructOR

Portal.

给定 a,b,d(<230)a,b,d(<2^{30})，要求构造一个 x(x<260)x(x<2^{60}) 使得 d∣(aor⁡x),d∣(bor⁡x)d\mid (a\operatorname{or} x),d\mid(b\operatorname{or} x)。

当 lowbit(aor⁡b)<lowbit(d)\text{lowbit}(a\operatorname{or}b)<\text{lowbit}(d)，显然无解。

否则可以考虑构造一个 xx 使得 aor⁡x=bor⁡x=xa\operatorname{or} x=b\operatorname{or} x=x。为了使得 d∣xd\mid x，xx 需要由若干 dd 构成。

枚举 aor⁡ba\operatorname{or} b 二进制下的每一位，如果当前位是 11，而且已经构造出来的答案的当前位是 00，那么这一位就需要变成 11，同时满足加进去的是由若干 dd 构成的，因此加上的内容必须是由 dd 左移得到的。左移多少位呢？要想让第 ii 位恰好为 11，那么令 dd 第一个 11 出现在第 kk 位，就需要让它左移 i−ki-k 位。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;
inline int lowbit(int x) { return x & -x; }

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        i64 a, b, d;
        cin >> a >> b >> d;
        if (lowbit(a | b) < lowbit(d)) cout << "-1\n";
        else {
            i64 x = 0, k = 0;
            while ((d >> k & 1) ^ 1) ++k;
            for (int i = 0; i < 30; ++i)
                if (((a | b) >> i & 1) && (x >> i & 1) == 0)
                    if (i >= k) x += (d << i - k);
            cout << x << "\n";
        }
    }
    return 0;
}

Codeforces Round #802 (Div.2)

Portal.

A. Optimal Path

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    i64 n, m;
    cin >> m >> n;
    cout << n * (n - 1) / 2 + (n + n * m) * m / 2 << "\n";
}

int main(void) {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

B. Palindromic Numbers

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    int n;
    static char a[100005], b[100005], c[100005];
    cin >> n >> b;
    if (b[0] == '9') {
        for (int i = 0; i <= n; ++i) a[i] = 1;
        for (int i = 0; i < n; ++i) b[i] -= '0';
        for (int i = n - 1; i >= 0; --i)
            if (a[i] < b[i]) {
                a[i] += 10;
                a[i - 1] -= 1;
                c[i] = a[i] - b[i]; 
            } else c[i] = a[i] - b[i];
        for (int i = 0; i < n; ++i)
            putchar(c[i] + '0');
        return;
    }
    for (int i = 0; i < n; ++i)
        putchar('9' - b[i] + '0');
}

int main(void) {
    int T; cin >> T;
    while (T--) {
        solve();
        puts("");
    }
    return 0;
}

C. Helping the Nature

Portal.

给定一个长度为 nn 的序列 AA，支持以下三种操作：

  • 将 A1,…,AiA_1,\dots,A_i 都减去一；
  • 将 Ai,…,AnA_i,\dots,A_n 都减去一；
  • 全局加上一。

将序列差分，那么前两种操作对应：

  • Bi+1B_{i+1} 加上一；
  • BiB_{i} 减去一。

那么除了第一个数，剩下的所有数我们都可以将其变成 00，这样序列中的所有数都相等，把第一个数作为“标准”进行维护即可。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[200005], b[200005];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; 
        b[i] = a[i] - a[i - 1];
    }
    i64 ans = 0, h = a[1];
    for (int i = 2; i <= n; ++i) {
        ans += abs(b[i]);
        if (b[i] < 0) h += b[i];
    }
    cout << ans + abs(h) << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D. River Locks

Portal.

有 nn 个容器，第 ii 个容器容量为 viv_i 升，可以容纳 [0,vi][0,v_i] 升的水。

满出去的水会将从容器 ii 转移到容器 i+1i+1，如果 i+1i+1 也满了会转移得更远。满出最后一个容器的水会倒到河中。

现在要将所有容器填满。你可以选择一些容器注水，让这些容器每秒进入一升水。qq 次询问，问最初所有容器都是空的，最少选择多少个容器注水使得 tit_i 秒内能填满所有容器。

1≤n,q≤2×1051\leq n,q\leq 2\times 10^5，1≤vi,ti≤1091\leq v_i,t_i\leq 10^9。

容器一定是要从 11 往 nn 开的，这样如果能装满，答案就是 ⌈∑vn⌉\left\lceil\frac{\sum v}{n}\right\rceil，不能装满当且仅当无法将前 ii 个容器在 tt 的时间内装满。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int n, q;
i64 a[200005], res = 0;

int main(void) {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) { 
        cin >> a[i];
        a[i] += a[i - 1];
        res = max(res, a[i] / i + (a[i] % i == 0 ? 0 : 1));
    }
    cin >> q;
    while (q--) {
        int t; cin >> t;
        cout << (t < res ? -1 : a[n] / t + (a[n] % t == 0 ? 0 : 1)) << '\n';
    }
    return 0;
}

E. Serega the Pirate

Portal.

一个 n×mn \times m 的表格中填入了 1,2,...,n×m1,2,...,n \times m 的所有数恰一次。

称一种填法可解，当可以找出一条路径，它第一次到达每个格子的顺序与格内所填的数同序。换言之，这条路径应该先经过 xx，再经过 x+1x+1。路径的起点，终点，长度任意，可以重复经过同一个格子。

问对给定的填法，至少需要交换几对格子，才能使填法可解。若最小值为 00，输出 00；若最小值为 11，输出 11 和交换方法数；若最小值大于 11，输出 22。

n×m≤400000n \times m \le 400000。

啊这题不难，就是很恶心（当然仅对于笔者）！

首先看看什么时候答案是 00：一个点能够走到，要么它是 11，要么在一个四联通块中有点可以走到它，也就是上下左右有一个数比它小。

当有一些点不满足上述条件时，就必须要执行交换操作了。交换什么？只有交换这个四联通块中的点和局外的一个点才可能让这个点变得合法。但是这道题并不需要我们输出操作数，只有在操作数为 11 的时候才要求我们输出方案数，因此可以暴力枚举：选择其中任意一个不能被走到的点，枚举与它交换的点，交换后看能影响到的 1010 个点（相当于改变了两个四联通块，共 1010 个点）和剩下的原本就不能到的点是否满足条件，满足条件就是一种方案。

如果一开始就不能到达的节点超过了 1010 个，那么一次交换操作就肯定不能完成了（一次交换只能影响至多 1010 个点）。

时间复杂度 O(nm)O(nm)，因为需要枚举方向带一个约百倍的常数。但实际上很快就会因为不符合条件而跳出循环，根本跑不满，可以轻松通过。

查看代码 
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;
const int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};

int n, m, X[400005], Y[400005];
vector<vector<int> > a;
vector<int> v;

bool check(int x, int y) {
    if (a[x][y] == 1) return true;
    for (int i = 1; i <= 4; ++i) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] < a[x][y]) return true;
    }
    return false;
}

int main(void) {
    scanf("%d%d", &n, &m);
    a.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        a[i].resize(m + 1);
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &a[i][j]);
            X[a[i][j]] = i, Y[a[i][j]] = j;
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (!check(i, j)) v.push_back(a[i][j]);
    if (v.empty()) return puts("0"), 0;
    if (v.size() >= 10) return puts("2"), 0;
    set<pair<int, int>> s;
    for (int i = 0; i < 5; ++i) {
        int x = X[v[0]] + dx[i], y = Y[v[0]] + dy[i];
        if (x < 1 || x > n || y < 1 || y > m) continue;
        for (int xx = 1; xx <= n; ++xx)
            for (int yy = 1; yy <= m; ++yy) {
                swap(a[x][y], a[xx][yy]);
                bool ok = true;
                for (int j = 0; j < v.size() && ok; ++j)
                    if (!check(X[v[j]], Y[v[j]])) ok = false;
                for (int j = 0; j < 5 && ok; ++j) {
                    int tx = x + dx[j], ty = y + dy[j];
                    if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && !check(tx, ty)) ok = false;
                }
                for (int j = 0; j < 5 && ok; ++j) {
                    int tx = xx + dx[j], ty = yy + dy[j];
                    if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && !check(tx, ty)) ok = false;
                }
                if (ok) {
                    int u = a[x][y], v = a[xx][yy];
                    if (u > v) swap(u, v);
                    s.insert(make_pair(u, v));
                }
                swap(a[x][y], a[xx][yy]);
            }
    }
    if (s.empty()) puts("2");
    else printf("1 %d\n", s.size());
    return 0;
}

Codeforces Round #813 (Div. 2)

Portal.

A. Wonderful Permutation

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, k;
int p[105];
bool a[105];

void solve(void)
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++i) scanf("%d", p + i);
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= k; ++i)
		a[p[i]] = true;
	int ans = 0;
	for (int i = 1; i <= k; ++i)
		if (!a[i]) ++ans;
	cout << ans << endl;
}

int main(void)
{
	int T; scanf("%d", &T);
	while (T--) solve();
	return 0;
}

B. Woeful Permutation

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[100005];

void solve(void) {
	cin >> n;
	for (int i = 1; i <= n; ++i) a[i] = i;
	for (int i = n; i >= 1; i -= 2)
		if (i > 1) swap(a[i], a[i - 1]);
	for (int i = 1; i <= n; ++i)
		printf("%d ", a[i]);
	putchar('\n');
}

int main(void) {
	int T; scanf("%d", &T);
	while (T--) solve();
	return 0;
}

C. Sort Zero

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[100005];
bool b[100005];

void solve(void)
{
	scanf("%d", &n);
	memset(b, 0, sizeof(b));
	set<int> s;
	int maxx = 0, ans = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		if (b[a[i]]) a[i] = 0;
		if (a[i] < maxx) {
			ans += s.size();
			for (auto x : s) b[x] = true;
			s.clear();
			maxx = 0;
		}
		if (b[a[i]]) a[i] = 0;
		if (a[i] != 0) s.insert(a[i]);
		maxx = max(maxx, a[i]);
	}
	cout << ans << '\n';
}

int main(void)
{
	int T; scanf("%d", &T);
	while (T--) solve();
	return 0;
}

D. Empty Graph

Portal.

给定一个长为 nn 的序列 aa。

定义一 nn 个点的无向完全图，点 ll 和点 rr 之间的距离为 min⁡i∈[l,r]{ai}\min\limits_{i\in[l,r]}\{a_i\}。

你可以进行 kk 次操作，每次操作可以选定 ∀i∈[1,n]\forall i \in [1,n] 并将 aia_i 赋值为一个 [1,109][1,10^9] 的整数。请最大化这个图的直径。

设 d(u,v)d(u,v) 表示 uu 到 vv 的最短路径长度，图的直径定义为 max⁡1≤u<v≤nd(u,v)\max\limits_{1\leq u < v \leq n} d(u,v)。

二分答案。直径显然只能是 d(ai,ai+1)d(a_i,a_{i+1})，距离要么是直接走，要么是二倍全局最小，根据此 check 即可。

查看代码 
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int INF = 1e9;

int n, k;
int a[100005], b[100005];

bool P(int x) // 最小值最大，现在最小值为 x 
{
	int res = 0;
	for (int i = 1; i <= n; ++i) b[i] = a[i];
	for (int i = 1; i <= n; ++i)
		if (2 * b[i] < x) ++res, b[i] = INF;
	int t = 2;
	for (int i = 1; i < n; ++i)
		t = min(t, (b[i] < x) + (b[i + 1] < x));
	return res + t <= k;
}

void solve(void) 
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	int L = 0, R = INF + 1;
	while (L + 1 != R) {
		int mid = L + R >> 1;
		if (P(mid)) L = mid;
		else R = mid;
	}
	cout << L << '\n';
}

int main(void)
{
	ios::sync_with_stdio(false);
	int T; cin >> T;
	while (T--) solve();		
	return 0;
}

12 月记录

sto KH.

Codeforces Round #825 (Div. 2)

Portal.

打的老垃圾了。

A. Make A Equal to B

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[105], b[105];

void solve(void) {
    cin >> n;
    int acnt = 0, bcnt = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i], acnt += a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i], bcnt += b[i];
    for (int i = 1; i <= n; ++i)
        if (a[i] != b[i]) ++cnt;
    int t = abs(acnt - bcnt);
    if (cnt > t) ++t;
    cout << t << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

B. Playing with GCD

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[100005];
int b[100005];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    b[1] = a[1]; b[n + 1] = a[n];
    for (int i = 2; i <= n; ++i)
        b[i] = a[i - 1] / __gcd(a[i - 1], a[i]) * a[i];
    for (int i = 1; i <= n; ++i)
        if (__gcd(b[i], b[i + 1]) != a[i]) {
            cout << "NO\n";
            return;
        }
    cout << "YES\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

C2. Good Subarrays (Hard Version)

Portal.

我们定义一个序列 bb 是好的当且仅当所有的 bi≥ib_i \ge i。

现在给你 qq 次询问，每次询问有两个数 pp 和 xx，问把 apa_p 赋值成 xx 后 aa 数组好的子段的个数，询问之间相互独立。

  • 1≤n≤2×1051\le n \le 2 \times 10^5，1≤q≤2×1051 \le q \le 2 \times 10^5。
  • 1≤ai≤n1\le a_i \le n，1≤pj,xj≤n1 \le p_j,x_j \le n。
查看代码 
//

D. Equal Binary Subsequences

Portal.

给你一个长为 2n2n 的01串 ss ，你需要将其分成两个相等的子序列。

在此之前你需要执行以下操作一次：

  • 选一个 ss 的子序列（可能为空），然后将其向右循环移位一位。

你能在执行以上操作一次后把 ss 分成两个相等的子序列吗？要求给出方案。

1≤n≤1051\le n\le 10^5 。

元素出现次数必须是偶数，然后呢？我们将两个数分为一组，如果一样那肯定是一个子序列一个，否则就按照顺序排列成一个 0101...01 的子序列，一个 1010...10 的子序列，然后翻转其中一个即可。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int p[200005];
bool d[200005];
char s[200005];

void solve(void) {
    cin >> n >> s + 1;
    int res = 0;
    for (int i = 1; i <= n * 2; ++i) {
        s[i] -= '0';
        if (s[i] == 0) ++res;
    }
    if (res & 1) return cout << "-1\n", void();
    memset(d, 1, sizeof(d));
    int ans = n, t = 0;
    for (int i = 1; i <= n; ++i) {
        int x = i * 2 - 1, y = i * 2;
        if (s[x] == s[y]) {
            p[i] = x;
            --ans;
            d[i] = 0;
        } else {
            t ^= 1;
            if (s[x] == t) p[i] = x;
            else p[i] = y;
        }
    }
    cout << ans << ' ';
    for (int i = 1; i <= n; ++i)
        if (d[i]) {
            int x = i * 2 - 1, y = i * 2;
            int t = (p[i] == x ? y : x);
            cout << t << ' ';
        }
    cout << '\n';
    for (int i = 1; i <= n; ++i)
        cout << p[i] << ' ';
    cout << '\n';
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

E. Swap and Take

Portal.

给定一个长为 n(1≤n≤500)n(1\le n \le 500) 的正整数序列 aa。初始你的分数为 00，需要进行 nn 轮操作。

在第 ii 轮，你可以选择交换两个相邻的数并将其中一个变为 00，也可以啥都不干。无论是否交换，第 ii 轮结束后你的分数会多 aia_i。

求你最大能得到的分数。

先考虑一下交换的意义。贡献的指针是从左跑到右，且速度为 11，而我们的交换也只能一次交换相邻的一对，肯定不能跑过这个指针。也就是说，如果把贡献的数字在原序列中的下标写出来记作序列 pp，那么一定有 p1≤p2≤⋯≤pnp_1\le p_2\le\cdots\le p_n。若枚举这一轮要获得的分数，那么这个交换次数 kk 就可以用来简单地判断当前这个分数是否可以拿到。

设 fi,j,kf_{i,j,k} 代表当前为第 ii 轮，要获取的贡献是 aja_j，这一轮之后有 kk 次操作没有使用能够获得的最大价值，初始时有 f1,1,1=a1,f1,2,0=a2f_{1,1,1}=a_1,f_{1,2,0}=a_2。这样我们的交换有两种选择：一种是将 ii 前面的交换到 ii 来获取其价值，二是在 ii 后选择两个数进行交换，为第 ii 轮以后做“准备“。因此有转移：

  • 将上一轮的 jj 转过来，fi,j,k=fi−1,j,k+ajf_{i,j,k}=f_{i-1,j,k}+a_j；
  • 将 aja_j 从 jj 换到 ii，需要消耗 j−ij-i 次操作，那么 fi,j,k=fi−1,t,k−1+j−i(j≥i,t<j)f_{i,j,k}=f_{i-1,t,k-1+j-i}(j\ge i,t<j)，t<jt<j 的原因是贡献下标单调不降，相等是上一种转移；j≥ij\ge i 的原因是我们之前说的“速度”。

现在的问题就成了如何快速找到这个最大的 f[i-1][t][k-1+j-i]。我们单独记录一个数组 gg，用 gi,j,kg_{i,j,k} 代表 max⁡{fi,t,k∣1≤t<j}\max\{f_{i,t,k}\mid 1\le t < j\} 即可。

查看代码 
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, a[505], INF;
int f[2][505][505]; // 进行 i 轮，第 i 轮获得的分数是 a[j]，k 次没用
int g[2][505][505];

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    memset(f, 0xbf, sizeof(f)); INF = -f[0][0][0];
    memset(g, 0xbf, sizeof(g));
    f[1][1][1] = a[1]; f[1][2][0] = a[2];
    for (int i = 2; i <= n; ++i) g[1][i][1] = a[1];
    for (int i = 3; i <= n; ++i) g[1][i][0] = a[2];
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 0; k <= n; ++k) {
                int &dp = f[i & 1][j][k]; dp = -INF;
                if (f[(i - 1) & 1][j][k] != -INF) dp = f[(i - 1) & 1][j][k] + a[j];
                if (j >= i && k - 1 + j - i >= 0 && k - 1 + j - i <= n) {
                    if (g[(i - 1) & 1][j][k - 1 + j - i] != -INF) 
                        dp = max(dp, g[(i - 1) & 1][j][k - 1 + j - i] + a[j]);
                }
                g[i & 1][j + 1][k] = max(g[i & 1][j][k], dp);
            }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            ans = max(ans, f[n & 1][i][j]);
    printf("%d\n", ans);
    return 0;
}

Educational Codeforces Round 67 (Rated for Div. 2)

Portal.

打的越来越垃圾，没救了。

A. Stickers and Toys

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    int n, s, t;
    cin >> n >> s >> t;
    cout << max(s, t) - (s + t - n) + 1 << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

B. Letters Shop

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, m;
int sum[26][200005];
string s, t;

void solve(void) {
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 26; ++j)
            sum[j][i] = (i == 0 ? 0 : sum[j][i - 1]);
        sum[s[i] - 'a'][i]++;
    }
    cin >> m;
    static int c[26];
    while (m--) {
        memset(c, 0, sizeof(c));
        int ans = 0;
        cin >> t;
        for (int i = 0; i < t.length(); ++i)
            c[t[i] - 'a']++;
        for (int op = 0; op < 26; ++op) {
            int res = lower_bound(sum[op], sum[op] + n, c[op]) - sum[op];
            ans = max(ans, res);
        }
        cout << ans + 1 << "\n";
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

C. Vasya And Array

Portal.

给定 m(1≤m≤1000)m(1\le m\le 1000) 条限制信息，形如 op l r，代表 [l,r][l,r] 是否不降排序。问是否能构造出合法的长度为 nn 的序列，并给出方案。

我们先看一看排好序意味着什么。我们维护一个数组 cc，c[i]c[i] 为真代表需要满足 ai≥ai−1a_i\ge a_{i-1}（实际上相等就可以了）。然后我们看没有排好序的，如果能够让它没排好的区间 (l,r](l,r] 都需要排好序，那么就完蛋了。输出的时候不需要排序的直接令输出的数减一即可。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, m, c[1005], s[1005];
int l[1005], r[1005], tot = 0;

int main(void) {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t) ++c[x + 1], --c[y + 1];
        else l[++tot] = x, r[tot] = y;
    }
    for (int i = 1; i <= n; ++i) c[i] += c[i - 1];
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + (c[i] != 0);
    for (int i = 1; i <= tot; ++i)
        if (s[r[i]] - s[l[i]] == r[i] - l[i])
            return cout << "NO\n", 0;
    cout << "YES\n";
    for (int i = 1, p = n + 2; i <= n; ++i) {
        if (!c[i]) --p;
        cout << p << " ";
    }
    cout << "\n";
    return 0;
}

D. Subarray Sorting

Portal.

给定长度为 nn 的数组 aa 和 bb。你每次可以选择一段区间 [l,r][l,r]，令 al∼ara_l\sim a_r 的元素从小到大排序。你可以进行任意次操作。问能否使 aa 与 bb 完全相等。

强大的题！

首先它们的数的集合必须相等，否则肯定无解。

我们依次扫描 bb，尝试找到一个 aa 与它相等。有最大可能出解的方式是找第一个可以匹配的 aa 与它匹配（否则要排序的内容更多，可能造成它不是最小值）。匹配成功的条件是令它的位置为 pp，它必须是 [1,p][1,p] 的最小值（将 [i,p][i,p] 排序是操作），这样排序之后序列剩下元素的相对位置不会改变，使用线段树维护即可。

查看代码 
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;
const int INF = 1e9;

int n;
int a[300005], b[300005];
int cnt[300005], pos[300005];
queue<int> Q[300005];

int T[1200005];
void build(int o, int l, int r) {
    if (l == r) return T[o] = a[l], void();
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    T[o] = min(T[o << 1], T[o << 1 | 1]);
}
void update(int o, int l, int r, int x) {
    if (l == r) return T[o] = INF, void();
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x);
    else update(o << 1 | 1, mid + 1, r, x);
    T[o] = min(T[o << 1], T[o << 1 | 1]);
}
int query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o];
    int mid = l + r >> 1, res = INF;
    if (x <= mid) res = min(res, query(o << 1, l, mid, x, y));
    if (mid < y) res = min(res, query(o << 1 | 1, mid + 1, r, x, y));
    return res;
}

int main(void) {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n); fill(cnt + 1, cnt + n + 1, 0);
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), ++cnt[a[i]];
        for (int i = 1; i <= n; ++i) scanf("%d", b + i), --cnt[b[ i]];
        bool flag = true;
        for (int i = 1; i <= n; ++i) 
            if (cnt[i]) { puts("NO"); flag = false; break; }
        if (!flag) continue;
        for (int i = 1; i <= n; ++i) Q[a[i]].push(i);
        for (int i = 1; i <= n; ++i) pos[i] = Q[b[i]].front(), Q[b[i]].pop();
        build(1, 1, n);
        for (int i = 1; i <= n; ++i) {
            if (query(1, 1, n, 1, pos[i]) != b[i]) {
                flag = false;
                break;
            }
            update(1, 1, n, pos[i]);
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

E. Tree Painting

Portal.

板子！发现当第一个点选定之后，剩下的就无所谓了！那么使用换根 DP！多的价值是父亲所对应的子树，少的价值是当前子树！

查看代码 
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;
typedef long long i64;

int n, siz[200005];
i64 f[200005], g[200005];
vector<int> G[200005];

void dp(int x, int fa) {
    siz[x] = 1;
    for (int y : G[x])
        if (y != fa) {
            dp(y, x);
            siz[x] += siz[y];
            f[x] += f[y];
        }
    f[x] += siz[x];
}

void dfs(int x, int fa) {
    if (x != 1) g[x] = g[fa] + n - siz[x] * 2;
    for (int y : G[x])
        if (y != fa) dfs(y, x);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    dp(1, 0);
    g[1] = f[1];
    dfs(1, 0);
    i64 ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, g[i]);
    printf("%lld\n", ans);
    return 0;
}

Educational Codeforces Round 126 (Rated for Div. 2)

Portal.

呜呜呜。

A. Array Balancing

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int a[30], b[30];

void solve(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    i64 ans = 0;
    for (int i = 2; i <= n; ++i) {
        i64 x = abs(a[i] - a[i - 1]) + abs(b[i] - b[i - 1]);
        i64 y = abs(a[i] - b[i - 1]) + abs(b[i] - a[i - 1]);
        ans += min(x, y);
    }
    cout << ans << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

B. Getting Zero

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;
const int INF = 1e9;

int calc(int x) {
    if (x % 32768 == 0) return 0;
    if (x % 2) return INF;
    int res = 15, ans = 0;
    while (x % 2 == 0) {
        x /= 2;
        --res;
    }
    return ans + res;
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) {
        int a; cin >> a;
        int ans = 1e9;
        for (int i = 0; i < 24; ++i)
            ans = min(ans, calc(a + i) + i);
        cout << ans << " ";
    }
    cout << "\n";
    return 0;
}

C. Water the Trees

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
int h[300005];

i64 calc(int x) {
    i64 a = 0, b = 0; // 1day, 2day
    for (int i = 1; i <= n; ++i)
        a += (x - h[i]) % 2, b += (x - h[i]) / 2;
    if (a == b) return a * 2;
    if (a > b) return a * 2 - 1;
    // a < b
    i64 t = (b - a) * 2;
    i64 ans = a * 2 + t / 3 * 2;
    return ans + t % 3;
}

void solve(void) {
    cin >> n;
    int maxn = 0;
    for (int i = 1; i <= n; ++i) 
        cin >> h[i], maxn = max(maxn, h[i]);
    cout << min(calc(maxn), calc(maxn + 1)) << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D. Progressions Covering

Portal.

你有两个长度为 nn 的数组 aa，bb。
aa 数组初始为 00。你每次可以执行一个操作，选定一段长度为 kk 的区间（设区间左端点为 ll，则有 1≤l≤l+k−1≤n1\leq l\leq l+k−1 \leq n ），把第一个元素加 11，第二个元素加 22，以此类推。
给定 nn，kk 与 bb，求令 ∀i∈[1,n]\forall i \in [1, n]，满足 ai≥bia_i \ge b_i 的最小操作数。

好题！我们从后往前扫描数组，这样就可以发现贪心加就可以了，因为加的是最大的还不会浪费。那么记录总操作数 opop 和当前加的和 ss。对于当前的数，操作数是 ⌈b[i]−sk⌉\left\lceil \cfrac{b[i]-s}{k}\right\rceil（实际这个 kk 需要根据 ii 调整），往前扫一个，当前的和就减少了操作数，操作数会减少 i+k−1i+k-1 时增加的操作数。

查看代码 
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long i64;

int n, k;
i64 a[300005], b[300005];

int main(void) {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%lld", b + i);
    i64 ans = 0, s = 0, op = 0;
    for (int i = n; i >= 1; --i) {
        if (b[i] > s) {
            int t = (i >= k ? k : i);
            a[i] = (b[i] - s + t - 1) / t;
            ans += a[i];
            op += a[i];
            s += a[i] * t;
        }
        s -= op;
        if (i + k - 1 <= n) op -= a[i + k - 1];
    }
    printf("%lld\n", ans);
    return 0;
}

Codeforces Round #746 (Div. 2)

Portal.

好棒！！！

A. Gamer Hemose

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, H;
int a[1005];

void solve(void) {
    cin >> n >> H;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + n + 1);
    if (H <= a[n]) return cout << "1\n", void();
    int t = H / (a[n] + a[n - 1]) * 2;
    H = H % (a[n] + a[n - 1]);
    if (H == 0) cout << t << "\n";
    else if (a[n] >= H) cout << t + 1 << "\n";
    else cout << t + 2 << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

B. Hemose Shopping

Portal.

只要能换到 11 和 nn 就可以随便换了。所以当 2x>n2x>n 时，[n−x+1,x][n-x+1,x] 会无法进行交换操作，因此它们排好序即可。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, x;
int a[100005], b[100005];

void solve(void) {
    cin >> n >> x;
    for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i];
    sort(b + 1, b + n + 1);
    for (int i = n - x + 1; i <= x; ++i)
        if (b[i] != a[i]) return puts("NO"), void();
    puts("YES");
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

C. Bakry and Partitioning

Portal.

显然只有断一条边或者两条边有用。一条边是整棵树异或和为 00；两条边要找出三部分的异或和相等，相当于找两棵子树异或和相等（计入答案的子树要断掉再继续计算），dfs 检查一下即可。

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n, k, xc, flag;
int a[100005], s[100005];
vector<int> G[100005];

void dfs(int x, int fa) {
    s[x] = a[x];
    for (int y : G[x]) if (y != fa) {
        dfs(y, x);
        if (s[y] == xc) ++flag;
        else s[x] ^= s[y];
    }
}

void solve(void) {
    cin >> n >> k; xc = flag = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        xc ^= a[i];
        G[i].clear();
    }
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        G[u].push_back(v); G[v].push_back(u);
    }
    if (xc == 0) return cout << "YES\n", void();
    if (k == 2) return cout << "NO\n", void();
    //cout << xc << endl;
    dfs(1, 0);
    cout << (flag >= 2 ? "YES" : "NO") << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

D. Hemose in ICPC ?

Portal.

给定一棵树，但是不知道边权。定义距离 d(u,v)d(u,v) 为路径上的边权的 gcd⁡\gcd。你可以询问交互库一个点集，交互库会回答这些点两两点对的距离的最大值。你最多可以询问交互库 1212 次，要找出 d(u,v)d(u,v) 最大的 (u,v)(u,v)。可以输出任意一组解，2≤n≤1032\le n\le 10^3。

初做交互题！非常开心！

可以发现距离定义 gcd⁡\gcd，那么距离就相当于找出最大边权！
首先询问一次所有点来找出最大的边权！对树进行一次 dfs，求出遍历的顺序！这样每两个树上相邻的点都可以在序列中找到！于是就可以对序列二分！这样就可以找到最大值！

为什么我写这题解的时候这么喜欢感叹号！

查看代码 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int n, maxx, a[2005], tot = 0;
vector<int> G[1005];

void dfs(int x, int fa) {
    a[++tot] = x;
    for (int y : G[x]) if (y != fa) {
        dfs(y, x);
        a[++tot] = x;
    }
}

int p[1005];
int check(int L, int R) {
    memset(p, 0, sizeof(p)); int cnt = 0;
    for (int i = max(0, L); i <= R; ++i) p[a[i]] = true;
    for (int i = 1; i <= n; ++i) if (p[i]) ++cnt;
    printf("? %d ", cnt);
    for (int i = 1; i <= n; ++i) if (p[i]) printf("%d ", i);
    cout << endl;
    int t; scanf("%d", &t); return t;
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v); 
        G[u].emplace_back(v), G[v].emplace_back(u);
    }
    printf("? %d ", n); for(int i = 1; i <= n; ++i) printf("%d ", i); 
    cout << endl; scanf("%d", &maxx); dfs(1, 0);
    int L = 1, R = tot;
    while (L + 1 != R) {
        int mid = L + R >> 1;
        if (check(L, mid) != maxx) L = mid;
        else R = mid;
    }
    int x = a[L], y = a[R];
    printf("! %d %d\n", a[L], a[R]);
    return 0;
}

Codeforces Round #836 (Div. 2)

Portal.

这应该是近期打的最后一场了，接下来会把前面的补掉。

A. SSeeeeiinngg DDoouubbllee

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

int n;
char s[200005];

void solve(void) {
    cin >> s; n = strlen(s);
    cout << s;
    reverse(s, s + n);
    cout << s << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

B. XOR = Average

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    int n; cin >> n;
    if (n % 2) {
        for (int i = 1; i <= n; ++i)
            cout << "1 ";
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n - 2; ++i)
        cout << n + 1 << ' ';
    cout << "1 " << n + 1 << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

Codeforces Round #838 (Div. 2)

Portal.

今年最后一场！

A. Divide and Conquer

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    int d = 1e9, s = 0, n, x;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x; s += x;
        bool flag = (x & 1);
        int ret = 0;
        while (1) {
            x >>= 1; ++ret;
            if ((x & 1) != flag) {
                d = min(d, ret);
                break;
            }
        }
    }
    if (s % 2 == 0) cout << "0\n";
    else cout << d << "\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}

B. Make Array Good

Portal.

查看代码 
#include <bits/stdc++.h>

using namespace std;
typedef long long i64;

void solve(void) {
    int n, x; cin >> n;
    cout << n << "\n";
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        int t = ceil(log2(x));
        cout << i << ' ' << int(pow(2, t) - x) << '\n';
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    int T; cin >> T; 
    while (T--) solve();
    return 0;
}
Codeforces Div.2 VP 记录
https://james1badcreeper.github.io/d71fa5a7/
本文作者
james1BadCreeper
发布于
2022年11月14日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

发布于 2022年11月14日
算法竞赛比赛记录

Div.2

Codeforces

比赛

评论

若无法加载，请尝试刷新，欢迎讨论、交流和提出意见，支持 Markdown 与 LaTeX 语法（公式与文字间必须有空格）！