mayoi_Akira ✌️🦌➗ LV 5 @ 2025-10-28 19:07:07

预期难度排序

题目	思维难度	代码难度	综合难度
A	⭐	⭐	easy
I		⭐⭐
M		⭐⭐⭐
K	⭐⭐	⭐	medium
B	⭐⭐	⭐
F	⭐⭐⭐	⭐
J	⭐⭐	⭐⭐⭐	medium-hard
H	⭐⭐⭐	⭐⭐
C	⭐⭐⭐	⭐⭐
E	⭐⭐⭐⭐	⭐	hard
G	⭐⭐⭐	⭐⭐⭐
D	⭐⭐⭐⭐	⭐⭐⭐⭐
L	⭐⭐⭐⭐	⭐⭐⭐⭐⭐	very hard

A. 学长的困扰（一）

知识点：循环求和、大小比较、输入输出

签到题，给出 $n$ 个数和一个整数 $m$ ，只需要判断这 $n$ 个数求和的结果 $\rm sum$ 与 $m$ 的大小关系即可，若 $\rm sum \leq$ $m$ 则输出 "Yes"，否则输出 "No" 。观察新生代码发现常见错误包括：

数组开太小（ $n$ 的最大值为 $10^6$ ）
求和时 $\rm sum$ 没有初始化为 $0$
反复为一个变量输入赋值而没有计数
判断 $\rm sum$ 与 $m$ 大小关系时大于小于写反

对自己的代码还有疑问的新生可以先按上面几个常见错误排查。

正解代码：

#include <stdio.h>
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    int sum = 0, tmp;
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &tmp);
        sum += tmp;
    }
    if(sum <= m)
        printf("YES");
    else printf("NO");
}

I. 刷题笑传之 check check board

知识点：结构体、排序、模拟

对每个用户开一个结构体，储存用户名、积分、三道题的通过情况。每次交题时检查该用户对应题目的通过情况，若未通过且本次通过则更新通过情况并增加积分。每次查看榜单时对用户数组按积分降序排序后输出。

代码：

#include<stdio.h>
#include<string.h>
typedef struct user{
    char name[30];
    int sc;
    char p[3];
}user;
int main(){
    int n, m;
    //每天三道题的分数
    int sc[3];
    scanf("%d %d", &n, &m);
    for(int i = 0; i < 3; ++i)
        scanf("%d", &sc[i]);
    user u[n];
    // 用户数组初始化
    for(int i = 0; i < n; ++i)
    {
        scanf("%s %d", u[i].name, &u[i].sc);
        for(int j = 0; j < 3; ++j)
            u[i].p[j] = 'N';
    }
    while(m--)
    {
        int op;
        scanf("%d", &op);
        if(op == 1)
        {
            //按分数排序后输出榜单
            for(int i = 0; i < n; ++i)
            {
                for(int j = i + 1; j < n; ++j)
                {
                    if(u[j].sc > u[i].sc)
                    {
                        user temp = u[i];
                        u[i] = u[j];
                        u[j] = temp;
                    }
                }
            }
            for(int i = 0; i < n; ++i)
            {
                printf("%d %s %d %c %c %c\n", i + 1, u[i].name, u[i].sc, u[i].p[0], u[i].p[1], u[i].p[2]);
            }
        }
        else if(op == 2)
        {
            char name[30];
            int t;
            char tt;
            //按题目输入
            scanf("%s %d %c", name, &t, &tt);
            //如果没通过直接跳过
            if(tt == 'N')
                continue;
            for(int i = 0; i < n; ++i)
            {
                if(strcmp(u[i].name, name) == 0)
                {
                    //如果已经通过该题，跳过
                    if(u[i].p[t - 1] == 'Y')
                        break;
                    //更新分数和状态
                    u[i].sc += sc[t - 1];
                    u[i].p[t - 1] = 'Y';
                    break;
                }
            }
        }

    }
}

M.printf("DLNU");

知识点：模拟、输出

按题意输出即可。而且 $n$ 的范围是 $1$ 至 $5$ ，实在做不出也可以打表枚举所有情况输出答案。代码略。

K. 区间和和

知识点：数学推导、前缀和

题目分析

\sum_{i=1}^{n} \sum_{j=i}^{n} \sum_{k=i}^{j} a_k

依旧是很明显啊，我们可以暴力的使用for循环去暴力的遍历所有区间来求取答案，但是由于n最大会取到1e7,三重循环就是O(n^3),计算次数达到了1e21，题目要求1秒内完成，显然不太可能（一秒一般情况下只能进行1e8次计算）。

我们考虑去优化它。

核心思路：考虑每个元素 a[i] 在所有区间中出现的次数。

它出现在所有左端点 l 且右端点 r 的区间中
左端点的选择有 i 种（从 1 到 i）
右端点的选择有 (n - i + 1) 种（从 i 到 n）

因此，元素 a[i] 在所有区间中出现的总次数为：

count[i]=i×(n−i+1)

最终答案ans为：

$$\text{ans} = \sum_{i=1}^{n} a[i] \cdot i \cdot (n - i + 1)$$

详细代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
   long long a[n+1];
    long long ans=0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ans+=a[i]*i*(n-i+1);
    }


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

B. 学长的困扰（二）

知识点：组合数学、快速幂

把每一道题看成一次选择：从这 $m$ 个知识点中选一个子集（表示这道题涉及的知识点集合）。所有可能的子集总数是 $2^m$ （每个知识点选或不选）。但题目要求：

不能选空集（不涉及任何知识点），去掉 1 种；
不能选全集（涉及全部 $m$ 个知识点），再去掉 1 种。

因此，每一道题可选的集合数为： $2^m - 2$

各题之间选择相互独立（每道题可以独立地选择一个满足条件的子集），所以总方案数就是把每道题的选择数连乘 $n$ 次：

\boxed{(2^m - 2)^n}

注意结果对 $10^9+7$ 取模。取模的原因是结果数值过大，计算机无法存下。因此不能强行计算结果并在最后取模，应当在计算过程中进行取模。

这里的乘方运算需要用到“快速幂”算法，请自行学习。

正解代码：

#include <stdio.h>
const int mod = 1e9 + 7;
// 快速幂
long long ksm(long long a, long long b)
{
    long long res = 1;
    while(b)
    {
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main(){
    int t;
    scanf("%d", &t);
    while(t--)
    {
        long long a, b;
        scanf("%lld %lld", &a, &b);
        long long c = ksm(2, b) - 2;
        long long d = ksm(c, a);
        printf("%lld\n", d % mod);
    }
}

F. 八月、某处、月明

知识点：数学、数论

小学时我们学过如何判断一个数是否为 $3$ 的倍数——将这个数的所有数位的数相加，如果结果是 $3$ 的倍数，那么这个数就是 $3$ 的倍数。

其实，判断 $9$ 的倍数也可以这样。所以，判断 $f(l,r)$ 是否是 $9$ 的倍数只需要将 $l$ 至 $r$ 的所有数加到一起判断是否为 $9$ 的倍数。

注意到，若 $l+r$ 是 $9$ 的倍数，则 $(l + 1) + (r - 1)$ 是 $9$ 的倍数...以此类推，序列 $l,\,l+1,\,l+2,...,r-2,r-1,r$ 求和一定是 $9$ 的倍数，符合条件。

因此目的改为找出一对整数 $(l,r)$ 满足 $l + r$ 是 $9$ 的倍数。

方法一

已知 $l +k = r$ 则 $l + r = l + l + k = 2 * l + k$

而 $2 * l + k \bmod 9$ 的结果在 $9$ 个数之内一定会出现循环

代码：

#include <stdio.h>
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        int k;
        scanf("%d", &k);
        for(int l = 0; l < 9; ++l){
            if((2 * l + k) % 9 == 0){
                printf("%d %d\n", l, l + k);
            }
        }
    }
return 0;
}

方法二

已知 $l + k = r$ 则 $l + r = 2r - k$ ，若要 $l + r$ 是 $9$ 的倍数，则 $2r - k$ 必须是 $9$ 的倍数，即 $2r \equiv k \pmod{9}$ 。

由于 $2$ 和 $9$ 互质，因此 $2$ 在模 $9$ 意义下有逆元 $5$ ，即 $2 * 5 \bmod 9 = 1$ 。

因此 $r \equiv 5 * k \pmod{9}$

则 $l \equiv 5 * k - k \equiv 4 * k \pmod{9}$ 。

代码：

#include <stdio.h>
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        long long k;
        scanf("%lld", &k);
        printf("%lld %lld\n", k * 4, k * 5);
    }
    return 0;
}

J. 龙之国的魔法棋盘

知识点：BFS, 并查集

方法一：

对于单次询问,使用 bfs 即可找到该询问的答案，但是该题询问次数不允许每次询问都跑一次 bfs 查找答案，考虑预处理所有的格子，对于每个还没走过的格子，bfs 结束时将答案存到本次走过的格子上，最后询问的时直接输出预存好的答案即可。

预处理时间复杂度 $O(n ^ 2)$ ，处理询问时间复杂度 $O(1)$

示例代码：

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<vector<int>> vis(n, vector<int>(n, -1));
    vector<string> g(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> g[i];
    }
    map<int, int> mp;
    auto bfs = [&](int a, int b, int mark) {
        queue<tuple<int,int,int>> q;
        q.emplace(a, b, 1);
        int cnt = 1;
        vis[a][b] = mark;
        while (q.size())
        {
            auto [x, y, z] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int xx = x + dx[i], yy = y + dy[i];
                if (xx < 0 || xx >= n || yy < 0 || yy >= n || g[xx][yy] == g[x][y] || vis[xx][yy] != -1)
                    continue;
                q.push({xx, yy, z + 1});
                cnt++;
                vis[xx][yy] = mark;
            }
        }
        return cnt;
    };

    int idx = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (vis[i][j] == -1)
            {
                mp[idx] = bfs(i, j, idx);
                idx++;
            }
        }
    }

    while (q--)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        int t = vis[a][b];

        cout << mp[t] << '\n';
    }
}

方法二：

该问题本质是将相邻的颜色不同的格子并为同一连通块，最后查询某一连通块中的元素数量，使用记录元素数量的并查集即可做到这一点，实现时注意二维点编号即可。

示例代码：

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(n + 1, -1));
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= n; ++j)
        {
            a[i][j] = s[j - 1] - '0';
        }
    }
    DSU g(n * n);
    auto id = [&](int x, int y)
    {
        return (x - 1) * n + y;
    };
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if ((a[i][j] ^ a[i - 1][j]) == 1)
            {
                g.merge(id(i, j), id(i - 1, j));
            }
            if ((a[i][j] ^ a[i][j - 1]) == 1)
            {
                g.merge(id(i, j), id(i, j - 1));
            }
        }
    }

    while (m--)
    {
        int x, y;
        cin >> x >> y;
        cout << g.size(id(x, y)) << endl;
    }
}

H 这是什么数

知识点：位运算

考虑 $x$ $\rm or$ $(x + 1)$ 是一个怎样的数。可以发现， $x + 1$ 的二进制表示和 $x$ 相比，其实就是把 $x$ 从最低位开始的连续 1 都变成 0，然后把下一位变成 1，更高位都不变。

可以发现， $x$ $\rm or$ $(x + 1)$ 的本质是把二进制最右边的 0 置为 1。其中最小的 $x$ 其实就是把 $n$ 的二进制中最右边的 0 的右边的 1 置为 0。

$x$ $\rm or$ $(x + 1)$ 一定是一个奇数，最低位一定是 1， $n = 2$ 的情况无解，答案为 −1。

示例代码：

void solve()
{
    using ll = long long;
    ll n;
    cin >> n;
    if (n == 2)
    {
        cout << -1;
        return;
    }
    ll t = ~n;
    // lowbit(t)
    n ^= (t & -t) >> 1;

    cout << n;
}

C.涂色

知识点：思维、排序

题解思路

由题目给出的两个涂色条件得出：如果某个格子 $(x,y)$ 是黑色，那么它左上区域 $(i, j)(1 \leq i \leq x,1 \leq j \leq y)$ 都必须为黑色。

可以转化为：不能出现一个白格子在某个黑格子的左上方（包括正上方或正左方）。

等价条件

设黑格子为 $(x_1, y_1)$ ，白格子为 $(x_2, y_2)$ 。如果 $x_2 \leq x_1$ 且 $y_2 \leq y_1$ ，则白格子在黑格子的左上区域，这是不允许的。

判断方法

直接两两比较黑格子和白格子是 $O(K^2)$ 的，不可行。

我们可以按行从小到大，行相同时按列从小到大排序所有格子。这样在遍历过程中，我们保证当前格子之前的格子要么在同一行但列更小，要么在更小的行。

我们维护一个变量 mn，表示当前已遍历过的白色格子中，最小的列号。

对于当前格子：

如果是白色，更新 mn。
如果是黑色，检查 mn 是否 ≤ 当前列：如果是，说明存在一个白格子在它的左上区域（因为白格子的行 ≤ 当前行，且列 mn ≤ 当前列），这是不允许的，输出 $\text{No}$ 。

代码实现

#include<bits/stdc++.h>
using namespace std;
struct node {
	int x, y, c;
}g[200010];
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for(int i = 0; i < k; i++) {
		cin >> g[i].x >> g[i].y >> g[i].c;
	}
	sort(g, g + k, [](node a, node b) {
		if(a.x == b.x) return a.y < b.y;
		return a.x < b.x;
	});
	int mn = INT_MAX;
	for(int i = 0; i < k; i++) {
		if(g[i].c == 0) mn = min(mn, g[i].y);
		else if(mn <= g[i].y) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

E. 诗书与咖啡

知识点：博弈论、数学推导

注意到, 当 $n = m$ 时，当前回合的玩家必败，因为不管当前玩家如何操作，另一名玩家都可以通过 “镜像” 他的操作来使自己拿到最后一个;

例如： $a$ 拿第一堆的 $x$ 个，那么 $b$ 就可以拿第二堆的 $x$ 个，循环往复直到 $b$ 获胜

这样的话，我们的目标就变成了在自己拿完之后将状态置为 $n = m$ 来使对手失败。在此之前，我们考虑更一般的情况。假设当前较小堆的数量为 $x$ ，我们只从较大的堆中取卡片。

不难发现，当较大堆的数量为 $2x + 2$ 时，我们无法通过一次操作达到 $n = m$ 的目标态。不仅如此，无论我们如何操作，对手都可以采用相同的策略将我们置于必败态。

因此， $(n, m) = (x, 2x + 2)$ 也是一种必败态。这样的话，我们目标也可以是将状态转化为这种形式。继续分析可得，当较大堆的数量为 $2(2x + 2) + 2 = 4x + 6$ 时，我们又将处于必败态。

以此类推，我们可以得到必败态的递推公式：

设较小堆数量为 $x$ ，则当较大堆数量 $y$ 满足以下条件时，当前玩家必败：

$$\begin{align} y &= 2 \cdot (2 \cdot (\ldots (2 \cdot x + 2) \ldots ) + 2) + 2\\ &= 2^{k} \cdot x + 2^{k} + 2^{k-1} + \cdots + 2^2 + 2 \\ &= 2^{k} \cdot x + 2(2^{k} - 1) \\ &= 2^{k} \cdot x + 2^{k+1} - 2 \\ & (k \in \mathbb{N})\notag \end{align}$$

当较大堆数量在 $y$ 的值域内，当前玩家处于必败态；否则，当前玩家都可以将较大堆数量改为 $y$ 的值域内，以此让另一位玩家处于必败态。

现在考虑改变较小堆的数量，若当前形式为 $(n, m) = (x, 2x + 2)$ ，即使我们改变 $x$ ，对手依然可以通过改变较大堆的数量以进行 “追杀”。例如，当前我们的回合， $n = 4$ 且 $m=10$ ，符合 $m = 2^{1} \cdot n + 2 ^ {1 + 1} - 2$ ，即当前状态处于必败态，即便我们选择拿数量较小堆将 $4$ 变为 $3$ ，对手仍然可以将 $10$ 变为 $8$ 使我们依旧处于必输态。不难证得，无论我们如何操作，对手都可以实现一直使我们处于必败态，直到彻底失败。

综上所述，

两堆卡片的数量分别为 $n$ 和 $m$ ，不失一般性，不妨设 $n \leq m$ 。

先手必胜条件：

$$\forall k \in \mathbb{N},\ m \ne 2^k\cdot n + 2^{k+1} - 2$$

否则，后手必胜。

所以我们可以通过判断 $m$ 是否满足上述条件来判断先手是否必胜。

代码可以通过枚举 $k$ 的值来实现，时间复杂度大约为 $O(t \cdot \log m)$ 。

#include <stdio.h>
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        // 如果n > m，交换两个变量的值
        if (n > m) n ^= m ^= n ^= m;
        while(n < m)
            n = (n * 2) + 2;
        if(n == m)
            printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

G. 所以我放弃了音乐

知识点：二分答案、贪心、优先队列

题目问最终数组的最小长度，我们可以反过来考虑，即考虑最多可以删掉多少个数。

不难发现，假设最多能删掉 $k$ 个数，那么一定不能删大于 $k$ 个数，一定能删小于等于 $k$ 个数。

因此我们可以使用二分答案来求解这个问题。

对删掉的数的数量进行二分，假设当前二分到的值为 $mid$ ，我们需要判断是否能删掉 $mid$ 个数。

首先将两个数组排序，既然我们现在选择删掉 $mid$ 个数，那么要删掉的一定会是数组 $a$ 中最小的 $mid$ 个数和数组 $b$ 中最大的 $mid$ 个数。

但是除了这 $mid$ 个数以外，我们还有给数组 $b$ 的 $k$ 次增强的机会，但 $k$ 最大只到 $10$ ，因此这个过程我们可以使用优先队列最小堆来模拟。

二分的 $\rm check$ 具体过程如下：

判断删掉 $mid$ 个数是否可行
留下 $a$ 中最小的 $mid$ 个数，将 $b$ 中最大的 $mid$ 个数放入最小堆
不断取出最小堆的堆顶元素（即当前 $b$ 中最小的数）和 $a$ 中最小元素比较
如果堆顶元素小于 $a$ 中的数，则使用增强机会将堆顶元素加 $x$ 后重新放入堆中
否则弹出堆顶元素，抛弃掉 $a$ 中最小元素，继续与下一个 $a$ 中的数比较
若出现了当前堆顶元素小于 $a$ 中当前数且增强机会用完的情况，则删掉 $mid$ 个数不可行；若成功比较完所有 $a$ 中的数，则删掉 $mid$ 个数可行

二分出的结果则为最多能删掉的数量，使用数组长度减去该值即为最终答案。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, x;
    cin >> n >> k >> x;
    vector<int> a(n), b(n);
    for (auto& i : a) cin >> i;
    for (auto& i : b) cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    auto check = [&](int mid) {
        vector<int> aa(a.begin(), a.begin() + mid);
        priority_queue<int, vector<int>, greater<>> q(b.end() - mid, b.end());
        for (int i = 0, cnt = 0; i < mid;)
        {
            int tp = q.top();
            q.pop();
            if (tp >= aa[i])
                i++;
            else
            {
                if (cnt >= k)
                    return false;
                cnt++;
                q.push(tp + x);
            }
        }
        return true;
    };
    int l = -1, r = n + 1;
    while (l + 1 < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << n - l << '\n';
    return 0;
}

D.帽子学长的树

知识点：换根 DP

题目分析

$$R_i = \sum_{1\leq j \leq n,\,j\neq i} a[j] \times (-1) ^ {\,f(i, j)}$$

很明显公式的含义其实是：所有与根节点距离为偶数的节点的权值和减去所有与根节点距离为奇数的节点的权值和。

特殊的我们不考虑根节点本身的权值，因为j！=i

看到题目我们最朴素的想法是，暴力的将每一个节点i当作根节点，，从i出发DFS这棵树，DFS的同时维护根到当前遍历节点的距离dis，如果是dis是偶数贡献加上当前节点的权值，如果是奇数减去当前节点的权值。

但这样做，DFS一次的时间是 O( n )，n 个点各DFS 一次，总时间就是 O(n^2)，会超时。如何优化呢？

从1换到2，我们观察距离的变化量：

我们到子树2的每个点的距离都减少了dis(1,2)，

到不在子树2上的每个点的距离都增加了dis(1,2)。

所以:

$$R[2] = (-1)^{\text{dis}(1,2)} \cdot R[1] + a[1] - a[2]$$

推广这个公式，假如我们已知R[i],节点j是节点i的一个子节点那么：

$$R[j] = (-1)^{\text{dis}(i,j)} \cdot R[i] + a[i] - a[j]$$

到这里题目就已经很明朗了，这是一个很简单的换根 DP。

我们只需要先从1出发DFS,计算出R[1],然后再次从1开始再次DFS,假设j是i的孩子，那么我们就可以直接通过上面推导出的公式直接求出R[j]的值而不需要以j为根节点再次进行一次DFS。

PS:

其实我们进行第一次DFS时，可以直接将1节点的权值计算进去，第二次DFS时将孩子的节点权值也计算进去，然后在最后输出答案的时候减去对应节点的权值即可。那么我们的公式就直接会被优化为：

R[j] = (-1)^{\text{dis}(i,j)} \cdot R[i]

详细代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int mod = 1e9 + 7;

void solve()
{
    int n;
    cin >> n;

    vector<vector<pair<int, int>>> g(n+1);
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    vector<int> ans(n+1,0);
    vector<tuple<int,int,int>> st;
    st.push_back({1, -1, 0});
    while (!st.empty()) {
        auto [x, fa, depth] = st.back();
        st.pop_back();
        if (depth % 2 == 0) ans[1] += a[x];
        else ans[1] -= a[x];
        for (auto [y, v] : g[x]) {
            if (y != fa) {
                int next = (depth + v) % 2;
                st.push_back({y, x, next});
            }
        }
    }
    vector<bool> vis(n+1, false);
    vector<pair<int,int>> q;
    q.push_back({1, -1});
    vis[1] = true;
    while (!q.empty()) {
        auto [x, fa] = q.back();
        q.pop_back();
        for (auto [y, v] : g[x]) {
            if (y != fa && !vis[y]) {
                if (v % 2 == 0) ans[y] = ans[x];
                else ans[y] = -ans[x];
                q.push_back({y, x});
                vis[y] = true;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] - a[i]<< " ";
    }
}

signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

L:树学家 III

知识点：树链剖分，线段树，位运算

由于询问时询问的是树上两点间路径的信息，不难想到通过树链剖分将每条路径转化为 $log~n$ 个区间。

由于每个结点上的运算符均为二进制位运算符，运算过程中不同二进制位之间互不影响。我们可以考虑对于每一个二进制位分开来考虑其运算结果，即对于每一个二进制位都求出其为 0/1 时经过路径后的结果，最后将初始输入的每一位分别取对应的值即可。

而由于询问时两点间的路径是有向的，从 $x \rarr lca$ 的路径是向上的，从 $lca \rarr y$ 的路径是向下的。将树上移动的顺序对应到区间上移动的顺序，不难发现 $x \rarr lca$ 的路径对应的区间都是从右向左经过的， $lca \rarr y$ 的路径对应的区间都是从左向右经过的。因此我们需要对于每一个区间都求出每一个二进制位初始为 0/1 时从左向右或是从右向左经过该区间之后的值。

考虑如何维护，建立一棵线段树，每个线段树结点都记录 $l0_i, l1_i, r0_i, r1_i$ 分别表示：

二进制第 $i$ 位为 $0$ 时从左向右经过该区间后该位的值。
二进制第 $i$ 位为 $1$ 时从左向右经过该区间后该位的值。
二进制第 $i$ 位为 $0$ 时从右向左经过该区间后该位的值。
二进制第 $i$ 位为 $1$ 时从右向左经过该区间后该位的值。

每次合并两个结点 a, b 的信息时令：

ans.l0[i] = a.l0[i] && b.l1[i] || !a.l0[i] && b.l0[i]
ans.l1[i] = a.l1[i] && b.l1[i] || !a.l1[i] && b.l0[i]
ans.r0[i] = b.r0[i] && a.r1[i] || !b.r0[i] && a.r0[i]
ans.r1[i] = b.r1[i] && a.r1[i] || !b.r1[i] && a.r0[i]

即枚举某一位在经过第一个区间后的值，将其以初值代入第二个区间得到结果。

此时对于每一个询问我们将路径拆为 $log~n$ 个区间，每个区间对应 $log~n$ 个线段树结点，每次合并结点需要花费 $O(k)$ 的时间，因此此时的总时间复杂度为 $O(q \times k \times log^2n)$ ，无法通过本题，此处 $k \leq 31$ 。

我们仔细分析上面的时间复杂度，发现两个 $log~n$ 在该算法中都难以去除，因此我们考虑优化掉 $O(k)$ 的时间复杂度。容易发现 $O(k)$ 的时间复杂度来自线段数结点合并。

仔细观察我们发现对于 $k$ 位分别进行逻辑运算是非常浪费的，我们考虑将四个大小为 $k$ 的数组压为四个大小为 $2^k$ 的数字，将逻辑运算转变为二进制位运算即可。对应的四个转移变为：

ans.l0 = (a.l0 & b.l1[i]) | (~a.l0[i] & b.l0[i])
ans.l1 = (a.l1 & b.l1[i]) | (~a.l1[i] & b.l0[i])
ans.r0 = (b.r0 & a.r1[i]) | (~b.r0[i] & a.r0[i])
ans.r1 = (b.r1 & a.r1[i]) | (~b.r1[i] & a.r0[i])

因此合并结点信息的复杂度优化到 $O(1)$ ，总复杂度达到 $O(q \times log ^2n)$ ，足以通过此题。

代码上注意链条合并的方向和顺序，以及线段树只需要单点修改，不需要懒标记。

示例代码：

#include <bits/stdc++.h>

using namespace std;

using i32 = int;
using u32 = int;

struct node
{
    u32 l, r, l0, l1, r0, r1;
    node(u32 _l = 0, u32 _r = 0, u32 _l0 = 0, u32 _l1 = -1, u32 _r0 = 0, u32 _r1 = -1)
    {
        l = _l, r = _r;
        l0 = _l0, l1 = _l1;
        r0 = _r0, r1 = _r1;
    }
};

node merge(node a, node b)
{
    return node(
        a.l, b.r,
        (~a.l0 & b.l0) | (a.l0 & b.l1),
        (a.l1 & b.l1) | (~a.l1 & b.l0),
        (~b.r0 & a.r0) | (b.r0 & a.r1),
        (b.r1 & a.r1) | (~b.r1 & a.r0));
};

void setup(node &p, char op, u32 val)
{
    if (op == '&')
        p.l0 = p.r0 = 0, p.l1 = p.r1 = val;
    else if (op == '|')
        p.l0 = p.r0 = val, p.l1 = p.r1 = -1;
    else if (op == '^')
        p.l0 = p.r0 = val, p.l1 = p.r1 = ~val;
};

#define GL (k << 1)
#define GR (k << 1 | 1)

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

    u32 n, q;
    cin >> n >> q;
    vector<u32> fa(n + 1), dep(n + 1), sz(n + 1), son(n + 1), top(n + 1), dfn(n + 1), L(n + 1), R(n + 1);
    vector<vector<u32>> tree(n + 1);
    vector<char> ops(n + 1);
    vector<u32> vals(n + 1);
    vector<node> seg(4 * n + 1);
    u32 tot = 0;

    auto pushup = [&](u32 k) -> void
    {
        seg[k] = merge(seg[GL], seg[GR]);
    };

    auto build = [&](auto &&build, u32 l, u32 r, u32 k = 1) -> void
    {
        if (l == r)
        {
            seg[k].l = seg[k].r = l;
            setup(seg[k], ops[dfn[l]], vals[dfn[l]]);
            return;
        }
        u32 mid = (l + r) >> 1;
        seg[k] = node();
        seg[k].l = l, seg[k].r = r;
        build(build, l, mid, GL);
        build(build, mid + 1, r, GR);
        pushup(k);
    };

    auto modify = [&](auto &&modify, u32 pos, u32 k = 1) -> void
    {
        if (seg[k].l == seg[k].r)
        {
            setup(seg[k], ops[dfn[pos]], vals[dfn[pos]]);
            return;
        }
        u32 mid = (seg[k].l + seg[k].r) >> 1;
        if (pos <= mid)
            modify(modify, pos, GL);
        else
            modify(modify, pos, GR);
        pushup(k);
    };

    auto query = [&](auto &&query, u32 l, u32 r, u32 k = 1) -> node
    {
        if (l <= seg[k].l && seg[k].r <= r)
            return seg[k];
        u32 mid = (seg[k].l + seg[k].r) >> 1;
        if (l <= mid)
        {
            if (mid < r)
            {
                return merge(query(query, l, r, GL), query(query, l, r, GR));
            }
            else
                return query(query, l, r, GL);
        }
        else
            return query(query, l, r, GR);
    };

#undef GL
#undef GR

    auto dfs1 = [&](auto &&dfs1, u32 u) -> void
    {
        dep[u] = dep[fa[u]] + 1;
        sz[u] = 1;
        for (u32 v : tree[u])
        {
            if (v == fa[u])
                continue;
            fa[v] = u;
            dfs1(dfs1, v);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]])
                son[u] = v;
        }
    };

    auto dfs2 = [&](auto &&dfs2, u32 u, u32 up) -> void
    {
        top[u] = up;
        L[u] = ++tot;
        dfn[tot] = u;
        if (son[u])
            dfs2(dfs2, son[u], up);
        for (u32 v : tree[u])
        {
            if (v == fa[u] || v == son[u])
                continue;
            dfs2(dfs2, v, v);
        }
        R[u] = tot;
    };

    auto change = [&](u32 pos, char op, u32 x) -> void
    {
        ops[pos] = op, vals[pos] = x;
        modify(modify, L[pos]);
    };

    auto ask = [&](u32 u, u32 v, u32 val) -> u32
    {
        node lc, rc;
        while (top[u] != top[v])
        {
            if (dep[top[u]] > dep[top[v]])
            {
                lc = merge(query(query, L[top[u]], L[u]), lc);
                u = fa[top[u]];
            }
            else
            {
                rc = merge(query(query, L[top[v]], L[v]), rc);
                v = fa[top[v]];
            }
        }
        bool f = 1;
        if (dep[u] < dep[v])
        {
            f = 0;
            swap(u, v);
            swap(lc, rc);
        }
        swap(rc.l0, rc.r0);
        swap(rc.l1, rc.r1);
        node res = merge(rc, merge(query(query, L[v], L[u]), lc));
        if (f)
        {
            swap(res.l0, res.r0);
            swap(res.l1, res.r1);
        }
        return ((~val & res.l0) | (val & res.l1));
    };

    for (u32 i = 1; i <= n; i++)
        cin >> ops[i];
    for (u32 i = 1; i <= n; i++)
        cin >> vals[i];

    for (u32 i = 0; i < n - 1; i++)
    {
        u32 u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs1(dfs1, 1);
    dfs2(dfs2, 1, 1);

    build(build, 1, n);

    for (u32 i = 0; i < q; i++)
    {
        u32 op;
        cin >> op;
        if (op == 1)
        {
            u32 x, val;
            char o;
            cin >> x >> o >> val;
            change(x, o, val);
        }
        else
        {
            u32 val, x, y;
            cin >> val >> x >> y;
            cout << ask(x, y, val) << endl;
        }
    }

    return 0;
}

ID: 578
时间: 1000ms
内存: 256MiB
难度: 10
标签: (无)
递交数: 3
已通过: 2
上传者: hanser_no_neko

1 条题解

预期难度排序

A. 学长的困扰（一）

I. 刷题笑传之 check check board

M.printf("DLNU");

K. 区间和和

题目分析

详细代码

B. 学长的困扰（二）

F. 八月、某处、月明

方法一

方法二

J. 龙之国的魔法棋盘

方法一：

方法二：

H 这是什么数

C.涂色

题解思路

等价条件

判断方法

代码实现

E. 诗书与咖啡

G. 所以我放弃了音乐

D.帽子学长的树

题目分析

详细代码

L:树学家 III

区间和和

信息

状态

开发

支持

关于

1 条题解

预期难度排序

A. 学长的困扰（一）

I. 刷题笑传之 check check board

M.printf("DLNU");

K. 区间和和

题目分析

详细代码

B. 学长的困扰（二）

F. 八月、某处、月明

方法一

方法二

J. 龙之国的魔法棋盘

方法一：

方法二：

H 这是什么数

C.涂色

题解思路

等价条件

判断方法

代码实现

E. 诗书与咖啡

G. 所以我放弃了音乐

D.帽子学长的树

题目分析

详细代码

L:树学家 III

区间和和

信息

状态

开发

支持

关于

还没有账户？

登录