NOI2025福建省队集训部分题解

Union_Find · 2025-07-03 17:04:03 · 个人记录

D1T1

题意

交互题，有一颗高度为 h 的满二叉树，有 n 个点，每个点有一个点权 f_i，你不知道 f 序列。现在你需要得到 \sum_{i=1}^n f_i。保证 f 是正整数。

你可以通过询问与一个点距离为 d 的所有点的点权值和，其中 d > 0，如果没有距离为 d 的点，返回 0。注意，这里你不知道每个点在树上的位置，因为每个点已经重新编号了。

要求在 2n+3 次询问内得到答案，且单个点的询问次数不超过 4。交互库自适应。

分析

首先容易想到我们先对每个点都询问以下距离为 1 的值，全部加起来，设这个值为 S，那么我们发现，S 包括了 3 倍的中间结点权值和，2 倍的根节点权值，1 倍的叶子节点权值和。如果我们可以让所有权值都是 3 倍的话，我们就可以直接除 3 解决了。

首先想到求根节点是哪个。不难想到可以直接对每个点查询距离为 h 的。因为根节点距离最远的点是 h - 1 的，所以只有根节点是 0。

那么现在可以直接对根节点查询距离为 h - 1 的权值和，这个值就是叶子节点权值和。此时我们只剩下求根节点权值了。

不难想到对根节点两个儿子查询距离为 1，加起来，此时发现这个值包括了 2 倍的根节点权值和第 3 层的权值和。我们要减去第 3 层的权值和，所以对根节点查询距离为 2。

而至于找到根节点的两个儿子，可以查询距离 h + 1 的所有点，如果是 0 且不是根节点，那么就是这两个儿子。

现在我们就有一个可以 O(n) 求出答案的方法，计算一下发现用了 3n+4 次。精细实现一下。

首先在求根节点两个儿子用了 n 次，但实际上我们可以换一下顺序，就是先求出所有 h+1 的值是 0 的点，容易知道只有 3 个。然后对于这 3 个点再查询 h 求出根节点，这样子就只用了 n+3 次。

当然这个还可以再优化，因为我们知道一定有恰好 3 个点距离 h+1 值为 0。这样子我们可以只用查询前 n - 1 个点，如果只有 2 个点，说明最后一个一定也是距离 h+1 值为 0 的点。

虽然说在 3 个点中找根节点也可以这样优化，但是我们后面还要用到两个儿子距离为 h 的权值和，所以先不优化。

现在我们用了 2n+6 次。但是注意到查询两个儿子距离为 1 的权值和在之前已经查询过了，所以我们可以存下来，此时变成 2n+4。

最后我们来优化求叶子节点，我们不用从根节点查询距离 h-1，我们可以变成查询两个儿子距离为 h 的和。因为我们前面在找根节点时已经查询过了，所以不用再查询，此时只用了 2n+3 次，且询问次数最多的根节点恰好询问了 4 次。

#include "tree.h"
#include <bits/stdc++.h>
using  namespace std;
#define ll long long
ll res[1000005], point[4], val[3];
ll solve(int subtask, int h){
    int n = (1 << h) - 1;
    ll ans = 0, sum = 0, cnt = 0, root = 0, prt = 0;
    if (h == 2){
        for (int i = 1; i <= n; i++) for (int j = 1; j <= h + h - 2; j++) ans += ask(i, j);
        return ans / (n - 1); 
    }
    for (int i = 1; i <= n; i++) sum += (res[i] = ask(i, 1));
    for (int i = 1; i < n; i++) if (!ask(i, h + 1)) point[++cnt] = i;
    if (cnt == 2) point[++cnt] = n; 
    for (int i = 1; i <= 3; i++){
        val[i] = ask(point[i], h);
        if (!val[i]) root = point[i];
    }
    for (int i = 1; i <= 3; i++) if (point[i] != root) prt += res[point[i]];
    prt -= ask(root, 2), prt /= 2;
    ans = sum + prt + (val[1] + val[2] + val[3]) * 2;
    return ans / 3;
}

D2T1

题意

给定一个序列 a，你可以进行若干次操作，每次操作可以选择一个区间，将每个数依次进行 +1,-1,0,+1,-1,0,\cdots 的操作，问至少几次操作后，可以让 a 中所有元素都变成 0。无解输出 -1。

分析

首先考虑无解情况，注意到一次操作后前缀和只会变大，所以我们计算所有前缀和，判断是否存在有大于 0 的即可。存在输出 -1。

考虑证明剩余情况一定有解。不难想到我们可以简化成每次只用 +1,-1 和 +1 这两种操作。所以一定有解。

接下来考虑求最优解。因为一次操作是对于区间的，不好做，我们转化一下。设 b_i = a_{i-2}+a_{i-1}+a_i。此时我们就有 3 种情况。

1. 结尾的操作是 +1,-1，此时就是 b_l + 1,b_{r+2}-1。
2. 结尾操作是 +1,-1,0，此时就是 b_l + 1,b_{r+1}-1。
3. 结尾操作是 +1，此时就是 b_l + 1,b_{r+1}+1,b_{r+2}+1。

我们发现只有 3 操作会对总和产生影响，而总和是固定的，所以我们可以先求出总和，此时就可以计算出 3 操作的总次数。

而对于 1,2 操作，不难发现是等价的。我们可以归为一类。

现在我们从后往前考虑计算。分类讨论。

• - $b_{i-1} < 0$，此时使用 $3$ 操作右端点修改。 - $b_{i-1} < 0$ 但是 $3$ 操作次数不够，那么只能用左端点修改。 - $b_{i-1} \ge 0$，优先使用左端点。 - $b_{i-1} \ge 0$，但左端点次数不够，那么使用 $3$ 操作右端点。

按照这个步骤就可以直接 O(n) 计算了。不要忘记开 long long。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, T, a[N], b[N], Left[3], Right;
void Main(){
    Left[0] = Left[1] = Left[2] = Right = 0;
    for (int i = 1; i <= n; i++) a[i] = rd();
    n += 2;
    int sum = 0, ans = 0;
    for (int i = 1; i <= n; i++){
        sum += a[i];
        if (sum > 0) return puts("-1"), void(0);
    }
    for (int i = 1; i <= n; i++) b[i] = (i == 1 ? 0 : a[i - 2]) + a[i - 1] + a[i], Right -= b[i];
    Right /= 3;
    for (int i = n; i >= 1; i--){
        if (b[i] >= 0) Left[i % 3] += b[i], ans += b[i];
        if (b[i - 1] < 0 && b[i] < 0 && Right){// 还可以用 3 操作，两个数都小于 0，那么一起加 
            int tmp = min(-max(b[i - 1], b[i]), Right);// 操作次数 
            Right -= tmp, b[i - 1] += tmp, b[i] += tmp, Left[(i + 1) % 3] += tmp, ans += tmp;
        }
        if ((b[i - 1] >= 0 && b[i] < 0) || (b[i - 1] < 0 && b[i] < 0 && !Right)){// 如果还小于 0，或者前面大于 0，用之前剩下的左端点 
            if (b[i] + Left[i % 3] >= 0) Left[i % 3] += b[i], b[i] = 0;
            else b[i] += Left[i % 3], Left[i % 3] = 0;
        }
        if (b[i] < 0){// 如果还小于 0，用右端点 
            int tmp = min(-b[i], Right);// 操作次数 
            Right -= tmp, b[i - 1] += tmp, b[i] += tmp, Left[(i + 1) % 3] += tmp, ans += tmp;
        }
    }
//  cout << Left[0] << " " << Left[1] << " " << Left[2] << "\n";
    printf ("%lld\n", ans);
}
signed main(){
    freopen ("trans.in", "r", stdin);
    freopen ("trans.out", "w", stdout);
    T = rd(), n = rd();
    for (; T--;) Main(), n -= 2;
    return 0;
}

D3T1

题意

有一个长度是 n + m 的序列，有 c + 1 种颜色，共有 m 个，其中第 c + 1 颜色是特殊颜色。给定义一个长度为 n + 1 的序列 w，以及对于每个颜色 1 \sim c 出现次数 a_i 和 a_i 个数 v_{i,j}。我们定义一个序列的权值如下。

• 设 x 表示第 x 个数是第一次出现的特殊颜色。
• 设最后一个颜色是 u。如果 u \not= c+1，那么设有长度为 y 的极长后缀，满足后缀所有颜色相同。
• 如果 u = c+1，那么权值就是 w_x。
• 否则权值就是 w_x\times v_{u,y}。

求对于所有可能序列的权值之和。