Solution Of LDOI

Dr1fty · 2024-03-31 16:06:52 · 题解

T1

Author: Drifty.

Solution

我们注意到对于任意长度为 k 的序列 p，都有：

\mathrm{W}(p) \ge \sum^{k - 1}_{i=1}\mathrm{W}(\{p_i,p_{i+1}\})

证明显然。

因此我们对于每一次 (x, y) 的询问，不妨令 x\le y，则最短走法即为一步一步走：x\rightarrow x+1\rightarrow \dots\rightarrow y-1\rightarrow y。前缀和维护即可。

AC-Code

以下是 Drifty 给出的实现。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 3e5 + 7;
int a[N], n, q, s[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n >> q;
    for (int i=1; i<=n; i++) 
        cin >> a[i], s[i] = s[i - 1] + (a[i] < a[i - 1]);
    for (int x, y; q--; ) {
        cin >> x >> y;
        if (x > y) swap(x, y);
        cout << s[y] - s[x] << '\n';
    }
    return 0;
}

T2

Author: Drifty.

Preface

啊？

Solution

对于 \forall (a,b)，若其是靓点二元组的充要条件为：

为什么？

第一条是为了保证顺序（即 i<j）。

第二条则是真正的关键。由于 b 的最高位必定为 1，若 b 的最高位对应的 a 这一位为 1，则那一位异或后的结果必定为 0，而 a 那一位原来为 1，因此导致 a\ \mathrm{xor}\ b 必定小于 a，又由第一条知 a>b，\therefore a\ \mathrm{xor}\ b<\max\{a,b\}，违背题意。

如何实现？

我们可以开设两个桶 t,p，对于每一个 a_i，把它的二进制分离出来，枚举每一位。如果对于从右到左的第 i 位为 0，则 t_i+1\to t_i；如果对于从右到左的第 i 位为 1，则 p_i+1\to p_i。

这样，从 1 枚举到 \log_2{\max\{a_i\}}+1，把 ans 不断加上 t_i\times p_i 即是答案。

时间复杂度 O(n\times\log_2{\max\{a_i\}})，空间复杂度 O(n+\log_2{\max\{a_i\}})。

AC-Code

以下是 Pentatonic_Vi0lin 给出的实现。

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int x=0, f=1; char c = getchar();
    while (c<'0' || c>'9') {if (c == '-') f = -1; c = getchar();}
    while (c>='0' && c<='9') x = (x << 3) + (x << 1) + (c ^ 48), c=getchar();
    return x * f;
}
constexpr int N = 3e6 + 5, add = 1, del = -1;
long long a[N], b[305], c[305], n, ans, Q, x, y;
inline void change(long long num, int op) {
    int k = 1;
    for (; num; k ++, num >>= 1) 
        if (!(num & 1)) b[k] += op;
    c[k-1] += op;
}
signed main() {
    int n = read(), Q = read(); 
    for (int i=1; i<=n; i++)
        a[i] = read(), change(a[i], add);
    while (Q--) {
        x = read(), y = read();
        change(a[x], del), change(y, add);
        a[x] = y, ans = 0;
        for(int i=1; i<=32; i++) ans += b[i] * c[i];
        printf("%lld\n", ans); 
    }
    return 0;
}

T3

Author: c_y_y.

Solution

称一棵树中的子图为牵制地点，当且仅当 hgcnxn 和 Drifty只在该子图中走动，且 hgcnxn 无法在有限步抓到 Drifty。

事实上，Drifty 想不要被 hgcnxn 抓住，必须要找到合适的牵制地点。

故第一步，我们需要找到牵制地点的共同特点。

以下称“节点”为房间。

推论 1：一条链不存在牵制地点。

形式化的，设 V 为一个树的点集，则对于 \forall i \in V，均有节点 i 的度数 \le 2，则该图不存在牵制地点。

事实上，hgcnxn 只需往 Drifty 所在的地方走就可以了。由于没有岔路，Drifty 必败。

由推论 1 可以得出，一棵树中存在牵制地点的必要条件是，该图中存在度数 \ge 3 的点。

考虑到这种点是特殊点，故定义一棵树中度数 \ge 3 的节点称为该树的小根。小根并不唯一。

以下表示的“图”默认为一棵树的子图。

推论 2：设图中一个小根的度数为 n。

若以其为该图的根，n 个儿子中有 \ge n-2 个为叶子节点，则该小根及其儿子构成的子图不是牵制地点。

先证明 n 个儿子全部为叶子结点的情况。

在某一回合，不妨设 hgcnxn 站在小根，Drifty 在某个叶子节点上。

那么，在下一回合中，hgcnxn 出于最优计划，会走向一个未被搜查过的节点，如果该节点里面有 Drifry ，游戏就结束了。否则对于 Drifty 来说：

走到小根。此时轮到 hgcnxn，他立刻回到小根，游戏结束。
原地静止，hgcnxn 会依个搜查每一个叶子节点。总会有一次找到 Drifty，游戏结束。

故 Drifty 在这种情况下必败。

称与小根距离为 1 的叶子节点为危险节点。Drifty 肯定不希望自己走到危险节点（就算 hgcnxn 离 Drifty 很远，Drifty 也肯定不会待在危险节点等待被抓）。故在后续中，可以忽视所有的危险节点。

进一步，若把这些危险节点忽视后，至多只有 2 个儿子，那么该情况就是一条局部的链。由推论 1，该图不是牵制地点。

总结推论 1 和推论 2，一棵树的子图牵制地点的必要条件是：

该子图拥有至少一个小根。
该子图的某一个小根中，至少有三个儿子不是叶子节点。

根据上面的结论，得出最小单位的牵制地点如下（其中橙色为小根）。接下来证明该图是牵制地点即可。

由推论 2，不妨设 Drifty 在黄色点，hgcnxn 在小根。由于 Drifty 知道全部的抓捕计划，故他会待在 hgcnxn 下一回合不会抓捕的黄色点。
出于最优的抓捕计划，hgcnxn 必须要走到黄色地点（否则 Drifty 就可以一直待在黄色点）。

又由于 Drifty 知道全部的抓捕计划，故他知道 hgcnxn 在哪一回合走到黄色点。

不妨那一回合下，hgcnxn 的抓捕方案为 X \to 1 \to A \to 1 \to X \to 2 \to B \to 2 \to X。

那么，Drifty 就有方案 B \to 2 \to X \to 3 \to C \to 3 \to X \to 1 \to A。不会被抓住。

此操作相当于每次 Drifty 都会躲在 hgcnxn 这次和下次均不会到达的黄点。 证毕。

证明了最小单位的牵制地点，难道就完了吗？不！

Drifty 必须比 hgcnxn 更先到小根，且 Drifty 到小根时，hgcnxn 与他距离至少为 2（想一想为什么）。

代码还是比较容易实现的，每组数据先进行 dfs 操作，得出两人到每个点的距离。一棵树中可能存在多个牵制地点，对于这些点，我们可以用 O(n) 的方法判断出图中的小根，然后枚举每一个小根，判断距离就行了。

AC Code

以下是 Drifty 给出的实现。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 7;
constexpr int hgcnxn = 1, Drifty = 0;
vector <int> g[N];
bitset <N> tag;
int d[2][N];
auto clear_g = [](size_t n) {
    for (int i=0; i<=n; i++) g[i].clear();
    tag = 0;
    memset (d, 0, sizeof(d));
};
auto get_struct = [](int n) {
    for (int i=1; i<=n; i++) {
        int siz = g[i].size();
        if (siz >= 3) {
            int tot = 0;
            for (int v : g[i])
                if (g[v].size() > 1) tot ++;
            if (tot >= 3) tag[i] = 1;
        }
    }
};
void dfs(int u, int fa, int s, const int k) {
    d[k][u] = s;
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs (v, u, s + 1, k);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T; cin >> T;
    for (int n, p, q; T--; ) {
        cin >> n >> p >> q;
        clear_g (n);
        for (int i=1, u, v; i<n; i++) 
            cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
        get_struct (n);
        dfs (q, 0, 0, Drifty), dfs (p, 0, 0, hgcnxn);
        if (d[Drifty][p] < 2) {cout << "hgcnxn\n"; continue;}
        bool f = false;
        for (int i=1; i<=n; i++) 
            if (tag[i]) {
                int ans = INT_MAX;
                for (int v : g[i]) ans = min(ans, d[hgcnxn][v]);
                if (ans > d[Drifty][i]) {f=true; break;}
            } 
        if (f) cout << "Drifty\n";
        else cout << "hgcnxn\n";
    }
    return 0;
}

T4

Author: Pentatonic_Vi0lin.

Solution

首先，很容易观察到，对于一个点执行 2 次同一操作是无意义的，从而对一个点执行操作的情况有：是否执行操作一与是否执行操作二的共 4 种组合。

其次，一个点受到的影响，仅来自其子树的操作二的个数的奇偶性，与这个点本身的操作。同时对自身子树有影响的操作一是翻转整颗子树，说明这棵子树本身必须全黑或全白，因而存在局部最优解。

从而，我们考虑树形 dp，从叶子节点向上转移状态，记录为 f(u,c,t)，其中 u 为节点编号，c 为其子树所染成的颜色，1 为全黑，0 为全白，t 为其子树中总共进行的操作二次数的奇偶性，1 为奇数，0 为偶数，f(u,c,t) 即为这个点的子树达到这一状态所需操作次数。

令 u 节点颜色为 color_u。

对叶子节点状态初始化：

f[u][color[u]][0] = 0;（不用操作）

f[u][!color[u]][0] = 1;（操作一）

f[u][!color[u]][1] = 1;（操作二）

f[u][color[u]][1] = 2;（操作一和二）

接下来考虑状态转移，由于一个点有多个子节点，我们要将这些点合并为一些可以代替f数组意义的量，同样有颜色和奇偶性两个标度，假定已经知道一些当前点子节点的子树全变成同一颜色，且用了某一奇偶性的操作的最小操作次数，设为 g_{c,u}，而要再加入一个子节点，则（令转移后为 t_{c,u}）转移来自同一种颜色，奇偶性相同或相反:

t[0][0] = min(g[0][0] + f[v][0][0], g[0][1] + f[v][0][1]);

t[0][1] = min(g[0][1] + f[v][0][0], g[0][0] + f[v][0][1]);

t[1][0] = min(g[1][0] + f[v][1][0], g[1][1] + f[v][1][1]);

t[1][1] = min(g[1][1] + f[v][1][0], g[1][0] + f[v][1][1]);

最后，由子节点的转移为：

f[u][color[u]] [0] = min(g[color[u]][0]//不操作, g[color[u]][1] + 1//只用操作二);

f[u][!color[u]][0] = min(g[color[u]][0] + 1//只用操作一, g[color[u]][1] + 2//用操作一、二);

f[u][!color[u]][1] = min(g[!color[u]][0] + 1//只用操作二, g[!color[u]][1]//不操作);

f[u][color[u]] [1] = min(g[!color[u]][0] + 2//用操作一、二, g[!color[u]][1] + 1//只用操作一);

通过递归实现上述过程即可。

AC Code

以下是 Pentatonic_Vi0lin 给出的实现。

#include <bits/stdc++.h>
using namespace std;
constexpr unsigned inf = INT_MAX >> 1;
constexpr unsigned SIZ = 2e5 + 7;
vector<int> son[SIZ];
bitset<SIZ> color;
int f[SIZ][2][2], n;
void dp_on_the_tree(int u, int fa) {
    f[u][0][0] = f[u][0][1] = f[u][1][0] = f[u][1][1] = inf;
    if (son[u][0] == fa && son[u].size() == 1) {
        f[u][color[u]][0] = 0;
        f[u][!color[u]][0] = 1;
        f[u][!color[u]][1] = 1;
        f[u][color[u]][1] = 2;
        return ;
    }
    int g[2][2]= {{0, inf}, {0, inf}}, t[2][2] = {};
    for (auto v : son[u]) {
        if (v == fa) continue;
        dp_on_the_tree(v, u);
        t[0][0] = min(g[0][0] + f[v][0][0], g[0][1] + f[v][0][1]);
        t[0][1] = min(g[0][1] + f[v][0][0], g[0][0] + f[v][0][1]);
        t[1][0] = min(g[1][0] + f[v][1][0], g[1][1] + f[v][1][1]);
        t[1][1] = min(g[1][1] + f[v][1][0], g[1][0] + f[v][1][1]);
        memcpy(g, t, sizeof(t));
    }
    f[u][color[u]] [0] = min(g[color[u]][0], g[color[u]][1] + 1);
    f[u][!color[u]][0] = min(g[color[u]][0] + 1, g[color[u]][1] + 2);
    f[u][!color[u]][1] = min(g[!color[u]][0] + 1, g[!color[u]][1]);
    f[u][color[u]] [1] = min(g[!color[u]][0] + 2, g[!color[u]][1] + 1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i=1, c; i<=n; i++) cin >> c, color[i] = c;
    for (int i=1, x, y; i<n; i++) 
        cin >> x >> y, son[x].push_back(y), son[y].push_back(x);
    dp_on_the_tree(1, 1);
    cout << min({f[1][1][0], f[1][1][1], f[1][0][1] + 1, f[1][0][0] + 1}) << '\n';
    return 0;
}