Codeforces Round 981 A~G

CF2033A

题意

数轴上原点有一个黑点，A和B两个人轮流操作，第$i$次操作移动黑点$2i-1$的距离，A往负数方向操作，B往正数操作，问谁能把它操作出距离原点$N$的距离。

解法

看一下样例就知道答案根据$N$的奇偶性变化。或者直接模拟也行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int Main()
{
    int n;
    read(n);
    if (n % 2 == 1)
        printf("Kosuke\n");
    else
        printf("Sakurako\n");
    return 0;
}

CF2033B

题目链接

题意

一个$n\times n$的棋盘，棋盘上的数有正有负，一次操作可以选一个子矩阵，然后把对角线都加1。问最少多少次操作所有数都是正数。

解法

不难发现每次选长到不能再长的$45°$线来操作，操作次数就是这条线所有负数的最小值。这样枚举线求个最小值即可。

 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



int Main()
{
    int n;
    read(n);
    std::vector diag(n + n + 1, std::vector<int>{});
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            int a;
            read(a);
            diag[i - j + n].push_back(a);
        }

    int ans = 0;
    for (int i = 0; i < n + n + 1; ++i)
    {
        if (diag[i].size() == 0)
            continue;
        int mn = *std::min_element(diag[i].begin(), diag[i].end());
        if (mn >= 0)
            continue;
        ans -= mn;
    }

    std::cout << ans << std::endl;
    return 0;
}

CF2033C

题目链接

题意

一个数组$a$，每次可以交换$a[i]$和$a[n-i+1]$，问所有操作后，最少有多少$a[i]=a[i+1]$。

解法

对同一个位置交换两次显然等价于不交换。那么每一个位置的决策要么交换要么不交换，一个线性dp即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


int Main()
{
    int n;
    read(n);
    std::vector<int> a(n + 2);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    const int INF = 1e9;
    std::vector dp(n + 1, std::array<int, 2>{INF, INF});
    dp[0][0] = 0;
    for (int i = 1; i <= n && i <= n - i + 1; ++i)
    {
        dp[i][0] = dp[i - 1][0] + (a[i] == a[i - 1]) + (a[n - i + 1] == a[n - i + 2]);
        dp[i][1] = dp[i - 1][0] + (a[i] == a[n - i + 2]) + (a[n - i + 1] == a[i - 1]);
        dp[i][0] = std::min(dp[i][0], dp[i - 1][1] + (a[i] == a[n - i + 2]) + (a[n - i + 1] == a[i - 1]));
        dp[i][1] = std::min(dp[i][1], dp[i - 1][1] + (a[i] == a[i - 1]) + (a[n - i + 1] == a[n - i + 2]));
    }

    int last = (n + 1) / 2;
    printf("%d\n", std::min(dp[last][0], dp[last][1]) + ((n % 2 == 0) ? a[last] == a[last + 1] : 0));

    return 0;
}

CF2033D

题目链接

题意

一个数组最多能分出来多少个不相交并且区间和为0的区间。

解法

经典dp，用$dp[i]$表示分到$i$时最多区间数，两种决策，是否把$i$作为右端点。

$dp[i]=max(dp[i-1],dp[j]+1(sum[i]-sum[j]=0))$。用桶存储下标为$sum[i]$的最大$dp[i]$即可。

 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


int Main()
{
    int n;
    read(n);
    std::vector<int> a(n + 1);
    std::vector<ll> sum(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
        sum[i] = sum[i - 1] + a[i];
    }

    std::map<ll, int> buc{};
    std::vector dp(n + 1, 0);
    buc[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (buc.count(sum[i]))
            dp[i] = buc[sum[i]] + 1;
        dp[i] = std::max(dp[i - 1], dp[i]);
        buc[sum[i]] = std::max(buc[sum[i]], dp[i]);
    }
    int ans = *std::max_element(dp.begin(), dp.end());
    std::cout << ans << std::endl;
    return 0;
}

CF2033E

题目链接

题意

一个排列，可以交换任意两个数。问最少多少次操作后能使得$p_i=i$或者$p_{p_i}=i$。

解法

根据置换环理论，就是要把所有大于2的环都变成长度为1或者2的。一次交换相当于改边。那么在每次把环上点的后继和点的前继交换一下即可。一次操作吧一个环的点数减2。对于一个长度为$l$的环，操作次数就是$\frac{l+1}{2}-1$，因为最后等于4或者3的时候只需要一次操作。

 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


int Main()
{
    int n;
    read(n);
    std::vector<int> p(n + 1);
    std::vector<int> vis(n + 1);
    for (int i = 1; i <= n; ++i)
        read(p[i]);

    auto dfs = [&](auto &&self, int u) -> int
    {
        if (vis[u])
            return 0;
        vis[u] = true;
        int ret = self(self, p[u]);
        return ret + 1;
    };

    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (vis[i])
            continue;
        int cnt = dfs(dfs, i);

        ans += (cnt + 1) / 2 - 1;
    }

    std::cout << ans << std::endl;
    return 0;
}

CF2033F

题目链接

题意

给出$n$和$k$,求斐波那契数列上第$n$个能被$k$整除的数是第几个。

解法

手玩几组样例可以发现，这个模$k$的斐波那契数列存在循环节。于是目标是找到循环节。

这取模的斐波那契数列的循环节的学名叫做皮萨诺周期，一个听起来让人有点饿的名字。

OEIS链接：https://oeis.org/A001175

实际上皮萨诺周期的长度不会超过$6k$，于是暴力求解出循环节，以及循环节里的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



int Main()
{
    ll n;
    int k;
    read(n, k);
    const int P = 1000000007;

    if (k == 1)
        return printf("%lld\n", n % P), 0;
    ll cycle = 0;
    int cnt = 0;
    std::vector<int> idx{};
    for (int i = 3, f1 = 1, f2 = 1; i <= 10 * k + 5; ++i)
    {
        f1 = (f2 + f1) % k;
        std::swap(f1, f2);
        if (f2 == 0)
            idx.push_back(i);
        if (f1 == 1 && f2 == 0)
        {
            cycle = i;
            break;
        }
    }
    ll ans = (n / idx.size()) % P;
    ans = ans * cycle % P;
    if (n % idx.size())
        ans += idx[n % idx.size() - 1] % P;
    ans %= P;
    std::cout << ans << std::endl;

    return 0;
}

CF2033G

题目链接

题意

有一棵以1为根的树，从节点$a$向子节点走不花费体力，向父亲走花费1单位的体力。

现在有$q$个询问，每次询问给出$v,k$，问从$v$开始，花费不超过$k$的体力最远能走多远。

解法

考虑一条路径$(u,v)$的长度和它的花费。

设$dep[u]$为节点深度，长度是$dep[u]+dep[v]-2dep[LCA(u,v)]$,花费是$dep[u]-dep[LCA(u,v)]$。

要让花费不超过$k$，即在$u$的$k$级祖先以内，找到除$u$这棵子树之外的最长向下的链。

我的做法是离线，把操作挂到点上之后dfs。dfs时，维护一棵线段树，下标是节点深度，存储最长的向下的链。

从$u$换根到$v$时，用$v$兄弟子树内最大的节点深度去更新线段树$dep[u]$处的值。

一开始将题意看反了，往下走有花费，但是往上走没花费。做法大差不差。可以思考一下。

这样的话用子树内最长的向下链长度做线段树下标，存储的值是节点深度。查询的时候分两步查，第一步查$[0,k]$之内最长链和节点深度的差的最大值，第二步查$[k+1,n]$之内节点深度的最小值并用k减掉。

  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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180



template <typename Info, typename Merge = std::plus<Info>>
struct SegmentTree
{
    const int n;
    const Merge merge;
    struct node
    {
        Info info;
    };
    std::vector<node> tree;
    SegmentTree(int _n) : n(_n), merge(Merge()), tree(_n * 4 + 9)
    {
    }
    SegmentTree(std::vector<Info> &init, int _n) : SegmentTree(_n)
    {
        std::function<void(int, int, int)> build = [&](int p, int l, int r)
        {
            if (l == r)
            {
                tree[p].info = init[l];
                return;
            }
            int mid = (l + r) / 2;
            build(p << 1, l, mid);
            build(p << 1 | 1, mid + 1, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p)
    {
        tree[p].info = merge(tree[p << 1].info, tree[p << 1 | 1].info);
    }
    void modify(int p, int l, int r, int x, const Info &v)
    {
        if (l == r)
            return tree[p].info = v, void();
        int mid = (l + r) >> 1;
        if (x <= mid)
            modify(p << 1, l, mid, x, v);
        else
            modify(p << 1 | 1, mid + 1, r, x, v);
        pull(p);
    }
    void modify(int p, const Info &v)
    {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y)
    {
        if (l == x && r == y)
            return tree[p].info;
        int mid = (l + r) >> 1;
        if (y <= mid)
            return query(p << 1, l, mid, x, y);
        else if (x > mid)
            return query(p << 1 | 1, mid + 1, r, x, y);
        else
            return merge(query(p << 1, l, mid, x, mid), query(p << 1 | 1, mid + 1, r, mid + 1, y));
    }
    Info query(int l, int r)
    {
        return query(1, 0, n, l, r);
    }
};

int Main()
{
    int n;
    read(n);
    std::vector adj(n + 1, std::vector<int>{});

    for (int i = 1; i < n; ++i)
    {
        int u, v;
        read(u, v);
        adj[u].push_back(v), adj[v].push_back(u);
    }

    std::vector<int> mxdep(n + 1), dep(n + 1);

    std::function<void(int, int)> dfs = [&](int u, int fa) -> void
    {
        if (fa != 0)
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), fa));

        dep[u] = dep[fa] + 1;
        mxdep[u] = dep[u];
        for (int v : adj[u])
        {
            dfs(v, u);
            mxdep[u] = std::max(mxdep[u], mxdep[v]);
        }
    };

    dfs(1, 0);

    std::vector<int> pre(n + 1), suf(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        int mx = 0;
        for (int j = 0; j < adj[i].size(); ++j)
        {
            int v = adj[i][j];
            pre[v] = mx;
            mx = std::max(mxdep[v], mx);
        }
        mx = 0;
        for (int j = adj[i].size() - 1; j >= 0; --j)
        {
            int v = adj[i][j];
            suf[v] = mx;
            mx = std::max(mxdep[v], mx);
        }
    }

    std::vector qry(n + 1, std::vector<std::pair<int, int>>{});
    int q;
    read(q);
    std::vector<int> ans(q + 1);

    for (int i = 1; i <= q; ++i)
    {
        int v, k;
        read(v, k);
        qry[v].push_back({k, i});
    }

    struct Info
    {
        int p;
        int mx;
        int sum;
    };

    struct Merge
    {
        Info operator()(const Info &lhs, const Info &rhs) const
        {
            Info res;
            res.p = lhs.p;
            res.mx = std::max(lhs.mx, rhs.mx);
            res.sum = std::max(lhs.sum, rhs.sum);
            return res;
        }
    };

    std::vector<Info> init(n + 1);
    for (int i = 0; i <= n; ++i)
        init[i] = {i, 0, -i};

    SegmentTree<Info, Merge> segment_tree(init, n);

    std::function<void(int)> reroot = [&](int u)
    {
        for (auto [k, i] : qry[u])
        {
            ans[i] = std::max(mxdep[u] - dep[u], ans[i]);
            ans[i] = std::max(ans[i], dep[u] + segment_tree.query(std::max(1, dep[u] - k), dep[u]).sum);
        }

        for (int v : adj[u])
        {
            int mx = std::max({dep[u], pre[v], suf[v]}) - dep[u];
            Info cur = segment_tree.query(dep[u], dep[u]);
            Info next = Merge{}(cur, {dep[u], mx, -dep[u] + mx});
            segment_tree.modify(dep[u], next);
            reroot(v);
            segment_tree.modify(dep[u], cur);
        }
    };

    reroot(1);

    for (int i = 1; i <= q; ++i)
        printf("%d%c", ans[i], " \n"[i == q]);

    return 0;
}