codeforces刷题集

发表于 更新于

记录了一些值得学习的CF题目。

River Locks

显然，如果开 ii 根水管的话，只需要开前 ii 根水管就行。因为前面的水管的水可以流向后面。

使用 dp(i)dp(i) 表示当打开前 ii 根管子，需要多久才能把前 ii 个水库放满。转移方程为：dp(i)=max(dp(i−1),⌈prei/i⌉)dp(i)=max(dp(i-1), \lceil pre_i/i\rceil)，其中 prepre 数组表示前缀和。转移方程中第二个参数为水库总量除以水管数上取整，显然这是所需时间的下界。同时由于前 i−1i-1 个水库只能由前 i−1i-1 根水管填满，所以需要考虑前 i−1i-1 个水库的情况。

基于此，我们可以直接得到打开 ii 根水管填满 nn 个水库所需的时间：max(dp(i),⌈pren/i⌉)max(dp(i), \lceil pre_n/i\rceil)，其含义与转移方程基本一致。

对于每个询问，若时间小于 dp(n)dp(n)，则无法填满，输出-1，否则二分答案，对于一个水管数 midmid，若求出时间小于给定值，则减少并继续搜索，否则加大，直到 l=rl=r。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 2e5 + 10;

int n, m;
ll a[N];
ll p[N];  // 容量前缀和
ll dp[N]; // 当打开前 i 根管子，需要多久才能把前 i 个水库放满

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
        dp[i] = max(dp[i - 1], (p[i] + i - 1) / i);
    }
    cin >> m;
    while (m--)
    {
        int t;
        cin >> t;
        // 若所有管子都打开，仍无法在 t 秒内填满，则输出 - 1
        if (t < dp[n])
            cout << -1 << endl;
        else
        {
            // 二分需要开多少根管子
            // 如果开 mid 根管子可以在 t 秒之内完成，试着开少一点
            // 否则开多一点
            ll l = 1, r = n;
            while (l < r)
            {
                ll mid = (l + r) / 2;
                if (max(dp[mid], (p[n] + mid - 1) / mid) <= t)
                    r = mid;
                else
                    l = mid + 1;
            }
            cout << l << endl;
        }
    }
}

Chip Move

首先记 dp(i,j)dp(i,j) 表示到达坐标 jj，最后一步是 k+ik+i 的方案数。不难得出转移方程：

dp(i,j)={1i=0 & k∣j0(i=0 & k∤j) or j<(k+i)dp(i−1,j−(k+i))+dp(i−1,j−2∗(k+i))⋅⋅⋅i≠0 and j≥(k+i)dp(i,j)= \begin{cases} 1 & i=0\ \& \ k \mid j \\ 0 & (i=0\ \& \ k \nmid j) \ or \ j < (k+i)\\ dp(i-1,j-(k+i))+dp(i-1,j-2*(k+i))··· & i\ne 0 \ and\ j \ge (k+i) \end{cases}

考虑到在最后一情况下，有 dp(i,j−(k+i))=dp(i−1,j−2∗(k+i))⋅⋅⋅dp(i,j-(k+i))=dp(i-1,j-2*(k+i))···，故可化简为 dp(i,j)=dp(i,j−(k+i))+dp(i−1,j−(k+i))dp(i,j) = dp(i,j-(k+i))+dp(i-1,j-(k+i))

得

dp(i,j)={1i=0 & k∣j0(i=0 & k∤j) or j<(k+i)dp(i−1,j−(k+i))+dp(i,j−(k+i))i≠0 and j≥(k+i)dp(i,j)= \begin{cases} 1 & i=0\ \& \ k \mid j \\ 0 & (i=0\ \& \ k \nmid j) \ or \ j < (k+i)\\ dp(i-1,j-(k+i))+dp(i,j-(k+i)) & i\ne 0\ and\ j\ge(k+i) \end{cases}

同时，考虑到若最后一步为 k+ik+i，至少需要位于 k+(k+1)+(k+2)⋅⋅⋅(k+i)=(2∗k+i)∗(i+1)/2k+(k+1)+(k+2)···(k+i)=(2*k+i)*(i+1)/2，所以外层循环枚举只需要满足 (2∗k+i)∗(i+1)/2≤n(2*k+i)*(i+1)/2\le n 即可，整体时间复杂度为 O(nn)O(n\sqrt{n}) 。

使用滚动数组优化内存。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 2e5 + 10, MOD = 998244353;

int n, k;
ll dp[2][N]; // 滚动数组优化
ll s[N];     // 总和

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    for (int i = k; i <= n; i += k)
        dp[0][i] = 1, s[i] = 1;
    for (int i = 1; (2 * k + i) * (i + 1) / 2 <= n; i++)
    {
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));
        int t = (2 * k + i) * (i + 1) / 2;
        for (int j = t; j <= n; j++)
        {
            dp[i & 1][j] = (dp[(i + 1) & 1][j - k - i] + dp[i & 1][j - k - i]) % MOD;
            s[j] = (dp[i & 1][j] + s[j]) % MOD;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << s[i] << " ";
    cout << endl;
}

2+ doors

首先，由于位运算每位之间互不影响，所以每次只处理第 kk 位的数据。

原题转化为 aik∣ajk=0 or 1a_{i_k} | a_{j_k} = 0\ or\ 1，注意到如果或运算结果为 00，则两位必须都为 00。先确定这些位。对于其他位，先假定为 11。从前往后遍历所有元素，如果置 00 后检查所有相关的关系，不产生矛盾，则置 00。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, M = 4 * N;

int n, m;
int a[N];

int head[N], ne[M], edge[M], weight[M], tot = 1;

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

void solve(int k) // k-th bit
{
    for (int i = 1; i <= n; i++)
        a[i] |= 1 << k;
    // 首先找到所有或为 0 的边，将所有点置 0
    for (int i = 2; i <= tot; i += 2)
    {
        int x = edge[i];
        int y = edge[i + 1];
        if ((weight[i] & (1 << k)) == 0)
            a[x] &= ~(1 << k), a[y] &= ~(1 << k);
    }
    for (int i = 1; i <= n; i++)
    {
        // 考虑能否置零，置 0 后是否会出现矛盾（另一顶点的对应位置也是0）
        bool flag = true;
        for (int j = head[i]; ~j; j = ne[j])
        {
            if ((weight[j] & (1 << k)) == 0)
                continue;
            int y = edge[j];
            if ((a[y] & (1 << k)) == 0 || i == y)
            {
                flag = false;
                break;
            }
        }
        if (flag)
            a[i] &= ~(1 << k);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    for (int i = 0; i < 30; i++)
        solve(i);
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
}

Permutation Restoration

由 bi=⌊i/ai⌋b_i=\lfloor i/a_i\rfloor，可以得知 ⌈(i+1)/bi+1⌉≤ai≤⌊i/bi⌋\lceil (i+1)/b_{i+1}\rceil \le a_i \le \lfloor i/b_i\rfloor。

求出所有位置的可能数字范围，先按左区间排序。遍历每个数字，对于所有左区间符合的位置，将其存放到以右区间排序的小根堆中，每次从堆顶取出一个位置放置该数字。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 5e5 + 10;

struct Range
{
    int l, r, i; // 表示 a[i] 可能的范围
} ranges[N];

int n;
int a[N];
int b[N];

Range heap[N]; // 小根堆
int tot = 0;

void up(int p)
{
    while (p > 1)
    {
        if (heap[p].r < heap[p / 2].r)
        {
            swap(heap[p], heap[p / 2]);
            p /= 2;
        }
        else
            break;
    }
}

void down(int p)
{
    int s = 2 * p;
    while (s <= tot)
    {
        if (s < tot && heap[s + 1].r < heap[s].r)
            s++;
        if (heap[s].r < heap[p].r)
        {
            swap(heap[s], heap[p]);
            p = s, s = 2 * p;
        }
        else
            break;
    }
}

void insert(Range x)
{
    heap[++tot] = x;
    up(tot);
}

Range extract()
{
    Range a = heap[1];
    heap[1] = heap[tot--];
    down(1);
    return a;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> b[i];
        for (int i = 1; i <= n; i++)
        {
            if (b[i] == 0)
                ranges[i] = {(i + 1 + b[i]) / (b[i] + 1), 0x3f3f3f3f, i};
            else
                ranges[i] = {(i + 1 + b[i]) / (b[i] + 1), i / b[i], i};
        }
        sort(ranges + 1, ranges + n + 1, [](Range a, Range b) -> bool
             { return a.l == b.l ? a.r < b.r : a.l < b.l; });
        for (int i = 1, j = 1; i <= n; i++)
        {
            while (j <= n && ranges[j].l <= i)
                insert(ranges[j++]);
            a[extract().i] = i;
        }
        for (int i = 1; i <= n; i++)
            cout << a[i] << " ";
        cout << endl;
    }
}

Permutation Graph

思路比较简单，首先找到 11 和 nn，然后分别从两者开始向左右找能到达的最远点。例如，假设 11 在左边，位置为 kk，需要寻找 mx(1,k)mx(1, k) 的位置，接下来继续找相应的 mnmn 值。右边亦然。

需要预处理出从两端到点 ii 的最小/大值，总共四个数组。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 3e5 + 10;

int n;
int a[N];
int lb[N], ls[N], rb[N], rs[N]; // 举例：lb[i] 表示从 1~i 最大的数字的位置
deque<int> ans;
// t == 0 1 2 3 表示四种寻找数字的可能性
// 0 表示向左找最小值
// 1 表示向左找最大值
// 2 表示向右找最小值
// 3 表示向右找最大值
void find(int i, int t)
{
    if (t == 1)
        ans.push_front(ls[i - 1]);
    else if (t == 2)
        ans.push_front(lb[i - 1]);
    else if (t == 3)
        ans.push_back(rs[i + 1]);
    else
        ans.push_back(rb[i + 1]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        ans.clear();
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        if (n == 1)
        {
            cout << 0 << endl;
            continue;
        }
        lb[1] = 1, ls[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            if (a[i] > a[lb[i - 1]])
                lb[i] = i;
            else
                lb[i] = lb[i - 1];
            if (a[i] < a[ls[i - 1]])
                ls[i] = i;
            else
                ls[i] = ls[i - 1];
        }
        rb[n] = n, rs[n] = n;
        for (int i = n - 1; i >= 1; i--)
        {
            if (a[i] > a[rb[i + 1]])
                rb[i] = i;
            else
                rb[i] = rb[i + 1];
            if (a[i] < a[rs[i + 1]])
                rs[i] = i;
            else
                rs[i] = rs[i + 1];
        }
        int mn = ls[n], mx = lb[n];
        if (mn < mx)
        {
            ans.push_back(mn), ans.push_back(mx);
            int iter = 1;
            while (ans.front() != 1)
                find(ans.front(), iter ^ 3), iter ^= 3;
            iter = 4;
            while (ans.back() != n)
                find(ans.back(), iter ^ 7), iter ^= 7;
        }
        else
        {
            ans.push_back(mx), ans.push_back(mn);
            int iter = 2;
            while (ans.front() != 1)
                find(ans.front(), iter ^ 3), iter ^= 3;
            iter = 3;
            while (ans.back() != n)
                find(ans.back(), iter ^ 7), iter ^= 7;
        }
        cout << ans.size() - 1 << endl;
    }
}

Burenka and Traditions (easy version)

首先根据开销，不难发现只需要进行长度为 11 或 22的操作。不难发现操作结果与顺序无关。我们认为操作从前往后依次进行。使用 dp(i,v)dp(i,v) 数组表示将 a1∼ai−1a_1\sim a_{i-1} 置为 00 ，且 ai=va_i=v 时的最小操作数。

这种状态只可能由两种状态转移过来：a1∼ai−1a_1\sim a_{i-1} 已经为 00，将 aia_i 从其他值转换成 vv 或自身就是 vv；对 ai−1,aia_{i-1},a_i 进行了长度为 22 的操作，且 a1∼ai−2a_1\sim a_{i-2} 已经为 00。第二个转换可以表示为：dp(i,ai⊕j)=dp(i−1,j)+1dp(i, a_i\oplus j)=dp(i-1, j)+1。

第二维最大值为 81918191，为 1∼50001\sim 5000 按位或的积累值。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 5010;

int n;
int a[N];
int dp[N][8500]; // dp[i][j] 表示将 1~i-1置零，且a[i]==v 的最小步数

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 0; i <= 8191; i++)
            dp[1][i] = 1;
        dp[1][a[1]] = 0;
        for (int i = 2; i <= n; i++)
        {
            for (int j = 0; j < 8192; j++)
                dp[i][j] = dp[i - 1][0] + (a[i] != j);
            for (int j = 0; j < 8192; j++)
                dp[i][a[i] ^ j] = min(dp[i][a[i] ^ j], dp[i - 1][j] + 1);
        }
        cout << dp[n][0] << endl;
    }
}

Path Prefixes

DFS，维护对应路径上A的前缀和。对于B，动态维护对应路径的前缀和序列。对于每个节点u，二分查找满足path[mid]<=sa[u]的最大值。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 2e5 + 10;

int n;
int head[N], ne[N], edge[N], A[N], B[N], tot;
ll sa[N];
int ans[N];
vector<ll> path;

void add(int x, int y, int a, int b)
{
    edge[++tot] = y, A[tot] = a, B[tot] = b;
    ne[tot] = head[x], head[x] = tot;
}

void dfs(int u)
{ // dfs 到 u 时，计算 ans[u]
  // 在 path 中，二分查找小于等于 sa[u] 的最大下标
    int l = 0, r = path.size() - 1;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (path[mid] <= sa[u]) // 可行，增大
            l = mid;
        else
            r = mid - 1;
    }
    ans[u] = r;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        sa[v] = sa[u] + A[i];
        path.push_back(path.back() + B[i]);
        dfs(v);
        path.pop_back();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    path.push_back(0);
    int t;
    cin >> t;
    while (t--)
    {
        memset(head, -1, sizeof(head));
        tot = 0;
        cin >> n;
        for (int i = 2; i <= n; i++)
        {
            int p, a, b;
            cin >> p >> a >> b;
            add(p, i, a, b);
        }

        for (int i = head[1]; ~i; i = ne[i])
        {
            int v = edge[i];
            sa[v] = A[i];
            path.push_back(B[i]);
            dfs(v);
            path.pop_back();
        }
        for (int i = 2; i <= n; i++)
            cout << ans[i] << " ";
        cout << endl;
    }
}

Fibonacci Strings

（以为会T但是过了）

首先预处理出小于 10910^9 的斐波那契数列项，最大为第 4545 项，数字较小。同时预处理出前缀和。首先计算所有输入数字之和，查找是否对应某个前缀和。若找不到输出NO，否则递归检测是否能构成对应的数列。方法为：找出对应的项数字，对于所有大于这个数字的字母数量，尝试使其成为最后一部分字符串的block，并递归检测剩余数字。

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>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e2 + 10;

int n;
ll a[N];
ll fib[N], tot;
ll prefib[N];

ll get_fib(int x)
{
    if (x == 1 || x == 2)
        return fib[x] = 1;
    if (fib[x] != 0)
        return fib[x];
    else
        return fib[x] = get_fib(x - 1) + get_fib(x - 2);
}

bool dfs(int k, int p = -1) // 目前的数列是否能构成前 n 项fib数列
{
    if (k == 0)
        return true;
    for (int i = 1; i <= n; i++)
    {
        if (i == p) // 不能重复使用相同的字母
            continue;
        if (a[i] >= fib[k])
        {
            a[i] -= fib[k];
            if (dfs(k - 1, i))
                return true;
            a[i] += fib[k];
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (tot = 1; get_fib(tot) <= 1e9; tot++)
        prefib[tot] = prefib[tot - 1] + fib[tot];
    int t;
    cin >> t;
    while (t--)
    {
        ll sum = 0;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i], sum += a[i];
        int fib_n = 0; // 找到字符串对应前 fib_n 项fib数列
        for (int i = 1; i <= tot; i++)
            if (sum == prefib[i])
            {
                fib_n = i;
                break;
            }
        if (fib_n == 0)
            cout << "NO" << endl;
        else
        {
            bool flag = dfs(fib_n);
            cout << (flag ? "YES" : "NO") << endl;
        }
    }
}

Burenka and Traditions (hard version)

首先根据开销，不难发现只需要进行长度为 11 或 22的操作。不难发现操作结果与顺序无关。我们认为操作从前往后依次进行。假设 al⊕al+1⊕⋅⋅⋅⊕ar=0a_l\oplus a_{l+1}\oplus ···\oplus a_r=0，则 cost=l−rcost=l-r，相较于逐个清零开销减一。这是唯一一种减少开销的方式。所以我们相当于需要找到最多的异或和为 00 的区间数。

使用集合贪心地解决问题。遍历异或前缀和，在集合中放置从上个区间结尾开始的异或前缀和。当遇到新的前缀和已经出现过时，说明出现了一个区间异或和为零，同时将集合清空。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

int a[N];
int p[N];
set<int> st;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i], p[i] = p[i - 1] ^ a[i];
        st.clear();
        st.insert(0);
        int ans = n;
        for (int i = 1; i <= n; i++)
        {
            if (st.count(p[i]))
            {
                ans--;
                st.clear();
            }
            st.insert(p[i]);
        }
        cout << ans << endl;
    }
}

Empty Graph

首先需要求一个给定数组形成的图的直径。不难发现，最短路最长只有两步：路过全局最小值。此时最短路长度为全局最小值的两倍。当最短路只有一步时，也就是区间最小值。不难发现区间越长最短值越小，所以只需要考虑长度为2的区间，也就是相邻数字的最小值。

综上，对于一个已经确定的数组形成的完全图，其直径为：

min(maxi−1n−1min(ai,ai+1),2×mini=1nai)min(max_{i-1}^{n-1}min(a_i,a_{i+1}), 2\times min_{i=1}^{n}a_i)

使用二分答案。对于一个给定的 ansans 值，首先需要满足 ∀i,ai×2≥ans\forall i, a_i\times 2 \ge ans，对于不满足的 aia_i 必须赋值 10910^9。若不满足该条件的数字多于 kk，则答案不可取。当两者相等时，求出所有相邻数字中较小值的最大值，判断是否大于等于 ansans。

若余下 11，则将最大值的相邻数赋值 10910^9，此时这个最大值就是相邻数较小值的最大值，判断其是否大于等于 ansans 即可。若余下数字大于 11，则可令两个相邻数字均为 10910^9，此时必定满足要求。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

int n, k;
ll a[N];
ll b[N];

bool check(ll ans)
{
    // 若答案为ans，则满足
    // all a[i] >= ans/2
    // min(a[i],a[i+1]) >= ans
    memcpy(b, a, (n + 1) * sizeof(ll));
    int p = k;
    for (int i = 1; i <= n; i++)
        if (b[i] * 2 < ans)
            b[i] = 1e9, p--;
    if (p < 0)
        return false;
    else if (p == 0)
    {
        ll res = 0;
        for (int i = 1; i < n; i++)
            res = max(res, min(b[i], b[i + 1]));
        return res >= ans;
    }
    else if (p == 1)
    {
        ll res = 0;
        for (int i = 1; i <= n; i++)
            res = max(res, b[i]);
        return res >= ans;
    }
    else
        return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        ll l = 1, r = 1e9;
        while (l < r)
        {
            ll mid = (l + r + 1) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        cout << l << endl;
    }
}

Passable Paths (hard version)

使用LCA。首先找到最深点，接下来找到满足不是最深点的祖先的次深点。如果不存在，说明所给点都在根到最深点的路径上，符合要求。否则，所求路径只能是：次深点到两点LCA到最深点。对于所给的每个点，检测是否符合在该条路径上。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, M = 2 * N;

int n, q, k;
int head[N], ne[M], edge[M], tot = 0;
int depth[N];
set<int> st;
int f[N][19];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

void build()
{
    queue<int> q;
    q.push(1);
    depth[1] = 1;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = ne[i])
        {
            int v = edge[i];
            if (depth[v])
                continue;
            depth[v] = depth[u] + 1;
            f[v][0] = u;
            for (int j = 1; j < 19; j++)
                f[v][j] = f[f[v][j - 1]][j - 1];
            q.push(v);
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] > depth[y])
        swap(x, y);
    for (int i = 18; i >= 0; i--)
        if (depth[f[y][i]] >= depth[x])
            y = f[y][i];
    if (x == y)
        return x;
    for (int i = 18; i >= 0; i--)
        if (f[x][i] != f[y][i] && f[x][i] != 0)
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    memset(head, -1, sizeof(head));
    int n;
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    build();
    cin >> q;
    while (q--)
    {
        st.clear();
        cin >> k;
        for (int i = 1; i <= k; i++)
        {
            int x;
            cin >> x;
            st.insert(x);
        }
        if (k == 1)
        {
            cout << "YES" << endl;
            continue;
        }
        int d1 = 1; // 找到最深的两个点
        for (auto x : st)
        {
            if (depth[x] >= depth[d1])
                d1 = x;
        }
        int d2 = 0;
        for (auto x : st)
        {
            if (x == d1)
                continue;
            if (lca(x, d1) != x && depth[x] >= depth[d2])
                d2 = x;
        }
        if (!d2)
        {
            cout << "YES" << endl;
            continue;
        }
        int plca = lca(d1, d2);
        bool flag = true;
        for (auto x : st)
        {
            if (x == d1 || x == d2)
                continue;
            if (!(lca(d1, x) == x && lca(d2, x) == plca || lca(d2, x) == x && lca(d1, x) == plca))
            {
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

Fake Plastic Trees

虽然题干中要求以路径方式填充，但实际上我们应该从根节点和子树的关系来考虑。

对于叶节点，显然应该为叶节点赋值最大值。考虑非叶节点，显然，填充它的值需要满足小于所有子节点填充值的和。

假如和小于最小值，需要额外花费一个填充次数，为了不浪费，直接填充至最大值。假如和大于最大值，需要调整回最大值。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 2e5 + 10;

int n;
int a[N];
int head[N], ne[N], edge[N], tot;
ll l[N], r[N];
ll val[N]; // 填到 i 的值
int ans;

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

void dfs(int u)
{
    if (head[u] == -1)
    {
        val[u] = r[u];
        ans++;
        return;
    }
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        dfs(v);
        val[u] += val[v];
    }
    if (val[u] < l[u])
    {
        val[u] = r[u];
        ans++;
    }
    else if (val[u] > r[u])
        val[u] = r[u];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        tot = 0;
        ans = 0;
        memset(head, -1, sizeof(head));
        memset(val, 0, sizeof(val));
        cin >> n;
        for (int i = 2; i <= n; i++)
        {
            int p;
            cin >> p;
            add(p, i);
        }
        for (int i = 1; i <= n; i++)
            cin >> l[i] >> r[i];
        dfs(1);
        cout << ans << endl;
    }
}

Circular Spanning Tree

这是一道难度比较高的构造题。在两种情况下无解：

  1. 所有点度数都是偶数。因为一棵树至少有两棵叶子节点。
  2. 奇数度数的点有奇数个。因为所有点度数的和一定是偶数。

只要满足上述条件就可以构造出可行解：

  1. 找到第一个’1’
  2. 将整个数组（环）向左旋转（逆时针旋转），直到第一个’1’被旋转到末尾。此时，我们把 s[2..n]s[2..n] 看作 0101 段，其中 00 可以不存在。将此时的第一个节点连向每段的第一个节点，同时段内部相邻节点之间连边，即构成符合要求的树。

证明：

  1. 这种情况下除了第一个节点，其他所有节点都只与相邻节点连边，所以不会有交错。
  2. 考虑度数。在 2∼n2\sim n 中，所有’1’要么与第一个节点连边，要么与前一个节点连边，所以是奇数度数。所有’0’一定与右边相连，而左边要么是另一个’0’，要么与第一个节点相连，所以是偶数度数。
  3. 对于第一个节点，假如是’0’，那么一定有偶数个段；假如是’1’，一定有奇数个段，所以第一个节点的度数也一定符合要求。
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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        string s;
        cin >> n >> s;
        vector<int> v(n), nv(n);
        int odd = count(s.begin(), s.end(), '1');
        if (odd == 0 || odd & 1)
            cout << "NO" << endl;
        else
        {
            cout << "YES" << endl;
            int head = find(s.begin(), s.end(), '1') - s.begin();
            for (int i = 0; i < n; i++)
                v[i] = i + 1;
            string ns(n, '0');
            for (int i = 0; i < n; i++)
            {
                int j = (i + head) % n; // 这次移动第 j 位的数，需要旋转(head+1)次
                ns[(j + n - (head + 1)) % n] = s[j];
                nv[(j + n - (head + 1)) % n] = v[j];
            }
            // cout << ns << endl;
            int p = 1;
            while (p < n)
            {
                cout << nv[0] << " " << nv[p] << endl;
                while (ns[p] != '1')
                {
                    p++;
                    cout << nv[p - 1] << " " << nv[p] << endl;
                }
                p++;
            }
        }
    }
}

Letter Picking

博弈论思维的一道题目。

首先，显然当只剩两个字母时，若两者相同则Alice赢，否则平局。所以，只可能是Alice赢或平局这两种情况。

其次，对于从 S[L,R] 中挑选字母，一轮下来只可能有四种情况：

Alice Bob
S[L] S[L+1]
S[L] S[R]
S[R] S[R-1]
S[R] S[L]

由于Alice先挑选，故若Alice要赢，需要保证在其挑完之后，剩下的两种情况都是Alice赢。只要选S[L]、S[R]中有任意一种情况能让Alice赢，她就能赢。否则平局。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2010;

char str[N];
int f[N][N];

int dp(int l, int r)
{
    if (f[l][r] != -1)
        return f[l][r];
    if (l + 1 == r)
        return f[l][r] = str[l] != str[r];
    f[l][r] = 0;
    // A 选 L
    if ((str[l] < str[l + 1] || dp(l + 2, r)) && (str[l] < str[r] || dp(l + 1, r - 1)))
        f[l][r] = 1;

    // A 选 R
    if ((str[r] < str[r - 1] || dp(l, r - 2)) && (str[r] < str[l] || dp(l + 1, r - 1)))
        f[l][r] = 1;
    return f[l][r];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> (str + 1);
        memset(f, -1, sizeof(f));
        dp(1, strlen(str + 1));
        if (f[1][strlen(str + 1)])
            cout << "Alice" << endl;
        else
            cout << "Draw" << endl;
    }
}

Kirei and the Linear Function

首先，有 (a∗b+c)mod  9=(a∗b+cmod  9)mod  9(a*b+c)\mod9=(a*b+c\mod9)\mod9，所以只需要预处理 v(l,r)mod  9v(l,r)\mod9。

又有一个数模9的值等于每一位模9的值的和，证明如下：

若这个数是个位数，则显然得证；若这个数超过两位，将其分解为 x=a∗9+a+bx=a*9+a+b，其中 a=⌊x/10⌋a=\lfloor x/10\rfloor，b=amod  10b=a\mod10。因为 9∗amod  9=09*a\mod9=0，所以上式转为 xmod  9=amod  9+bmod  9x\mod9=a\mod9+b\mod9，于是得到递推式，得证。

所以我们只需要计算字符串每一位上数字的前缀和就能计算得到 v(l,r)v(l,r)。

只需要预处理每一段结果即可，每个结果保留前两个解。

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>
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 2e5 + 10;

int n, w, m;
char str[N];
vector<int> mp[9]; 
ll pre[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        for (int i = 0; i < 9; i++)
            mp[i].clear();
        cin >> (str + 1);
        n = strlen(str + 1);
        cin >> w >> m;
        for (int i = 1; i <= n; i++)
            pre[i] = (pre[i - 1] + str[i] - '0') % 9;
        for (int i = 1; i + w - 1 <= n; i++)
        { // 计算每段的数值
            ll sum = (pre[i + w - 1] - pre[i - 1] + 9) % 9;
            if (mp[sum].size() < 2)
                mp[sum].push_back(i);
        }
        while (m--)
        {
            int l, r, k;
            cin >> l >> r >> k;
            ll sum = (pre[r] - pre[l - 1] + 9) % 9;
            int a = 0x3f3f3f3f, b = 0x3f3f3f3f;
            for (int i = 0; i < 9; i++)
                for (int j = 0; j < 9; j++)
                {
                    if (mp[i].size() == 0 || mp[j].size() == 0)
                        continue;
                    if ((i * sum + j) % 9 == k)
                    {
                        if (i == j && mp[i].size() == 2 && (a > mp[i][0] || a == mp[i][0] && b > mp[i][1]))
                            a = mp[i][0], b = mp[i][1];
                        else if (i != j && (a > mp[i][0] || a == mp[i][0] && b > mp[j][0]))
                            a = mp[i][0], b = mp[j][0];
                    }
                }
            if (a == 0x3f3f3f3f && b == 0x3f3f3f3f)
                cout << -1 << " " << -1 << endl;
            else
                cout << a << " " << b << endl;
        }
    }
}

Slime Escape

这题的想法是很简单的，也就是从中间向两边扩展，自身的值越大越好。

实际实现时，需要把总和为非负值的史莱姆数量最少地打包为一组并记录获取该组所需的值，只有一组一组地合并才是有必要的。

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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
const int N = 2e5 + 10;

int n, m;
ll a[N];
ll p[N];

void solve()
{
    for (int i = 1; i <= n; i++)
        p[i] = a[i] + p[i - 1];
    vector<PII> L, R;
    int l = m - 1, r = m + 1;
    // 检测 [i, l] 是否构成一个 good group
    // 即 p[l]-p[i-1] >= 0
    for (int i = m - 1; i >= 1; i--)
    {
        if (p[l] - p[i - 1] >= 0 || i == 1)
        {
            ll cur = 0, worst = 0;
            for (int j = l; j >= i; j--)
            {
                cur += a[j];
                worst = min(cur, worst);
            }
            L.push_back({cur, -worst});
            l = i - 1;
        }
    }

    // 检测 [r, i] 是否构成一个good group
    // 即 p[i] - p[r - 1] >= 0
    for (int i = m + 1; i <= n; i++)
    {
        if (p[i] - p[r - 1] >= 0 || i == n)
        {
            ll cur = 0, worst = 0;
            for (int j = r; j <= i; j++)
            {
                cur += a[j];
                worst = min(worst, cur);
            }
            R.push_back({cur, -worst});
            r = i + 1;
        }
    }

    reverse(L.begin(), L.end());
    reverse(R.begin(), R.end());

    ll cur = a[m];
    while (true)
    {
        bool acted = false;
        if (!L.empty() && cur >= L.back().second)
        {
            cur += L.back().first;
            L.pop_back();
            acted = true;
        }
        if (!R.empty() && cur >= R.back().second)
        {
            cur += R.back().first;
            R.pop_back();
            acted = true;
        }
        if (L.empty() || R.empty())
        {
            cout << "YES" << endl;
            return;
        }
        if (!acted)
        {
            cout << "NO" << endl;
            return;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        solve();
    }
}

Meeting on the Line

每一个人(xi, yi)都可以转化为(xi+yi,0)和(xi-yi,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
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;

int n;
int x[N];
int y[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> x[i];
        for (int i = 1; i <= n; i++)
            cin >> y[i];
        set<int> st;
        for (int i = 1; i <= n; i++)
        {
            st.insert(x[i] - y[i]);
            st.insert(x[i] + y[i]);
        }
        int ans = *st.begin() + *st.rbegin();
        if (ans & 1)
            cout << ans / 2 << ".5" << endl;
        else
            cout << ans / 2 << endl;
    }
}

Counting Arrays

首先，对于任意一个数组 aa，[1,1,...,1][1,1,...,1] 一定是一个合法的删除序列。而任意unambiguous的数组一定只有一个删除序列，故这个删除序列一定是这个序列。

题目需要输出ambiguous的数组数量，我们应该反过来求unambiguous的数组数量，与所有的数组总数做差。

我们记 f(i)f(i) 为含有 ii 个数的unambiguous的数组的数量。由于第 ii 个数一定是被移到第一位后最终删除的，所以它不能在 2∼i−12\sim i-1 的位置上被删除，即 aia_i 满足 ∀j∈[2,i−1],gcd(ai,j)≠1\forall j\in [2, i-1],gcd(a_i,j)\ne 1。

这一条件等价于 aia_i 是 [2,i−1][2, i-1] 中所有质数的倍数。从充分性的角度来看，此时 aia_i 一定会与 ∀j∈[2,i−1]\forall j\in[2,i-1] 中的任意一个数有公共的质因数；从必要性的角度上来说，与质数的最小公约数不为 11 等价于是这个质数的倍数。

不难得出，在 [1,N][1,N] 中，质数 pp 的倍数有 ⌊Np⌋\lfloor \cfrac{N}{p} \rfloor 个，而是否是质数的倍数是独立判定的，即一个数是不是 p1p_1 的倍数与它是不是 p2p_2 的倍数无关。由容斥原理，ai=⌊Np1p2...pm⌋a_i =\lfloor \cfrac{N}{p_1p_2...p_m}\rfloor 。我们可以在迭代 ii 的同时维护 ⌊Np1p2...pm⌋\lfloor\cfrac{N}{p_1p_2...p_m}\rfloor 。时间复杂度等同于埃氏筛法，为 O(nlognlogn)O(nlognlogn)。

需要注意的是，乘法取模不满足 a×bmod  P=(amod  P)×(bmod  P)mod  Pa\times b\mod P=(a\mod P)\times(b\mod P)\mod P，所以对于可能long long溢出的大数乘法需要使用数学方法进行计算。

由于题目中所求为长度小于等于 nn 的所有数组数量，所以我们累计每次迭代的答案。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 10, MOD = 998244353;
 
ll n, m;
ll f[N];
ll p[N];

ll mul(ll a, ll b)
{
    a %= MOD, b %= MOD;
    ll c = (long double)a * b / MOD;
    ll ans = a * b - c * MOD;
    if (ans < 0)
        ans += MOD;
    else if (ans >= MOD)
        ans -= MOD;
    return ans;
}
 
ll qmi(ll x, ll n)
{
    ll res = 1;
    while (n)
    {
        if (n & 1)
            res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}
 
bool st[N];
int prime[N], tot = 0;
 
int main()
{
    cin >> n >> m;
    f[1] = m;
    ll cut = m;
    ll sum = 0;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            prime[tot++] = i;
            cut /= i;
        }
        for (int j = 2 * i; j <= n; j += i)
            st[j] = true;
        f[i] = mul(cut, f[i - 1]);
        p[i] = (p[i - 1] + f[i]) % MOD;
        sum = (sum + qmi(m, i)) % MOD;
    }
    cout << (sum - p[n] + MOD) % MOD << endl;
}