2025年10月

🉑乐题解

参考题解：题解 P6824 【「EZEC-4」可乐】

题目分析

  • 有 n 瓶可乐，每瓶可乐有一个口味值 a[i]（非负整数）。
  • 你可以选择一个整数 x（非负整数），对于每瓶可乐：
    • 如果 (a[i] XOR x) <= k，那么你能喝到这瓶可乐。
  • 目标：选择合适的 x，使得能喝到的可乐瓶数最多，输出这个最大值。

解题思路

暴力做法

最直接的想法是枚举所有可能的 x，然后对每个 x 统计有多少瓶可乐满足 (a[i] XOR x) <= k。

但是 x 的范围是多少呢？ 因为 2^a[i] < 2^21，所以 a[i] 最大可能接近 2^21，但 x 的值其实可以限制在 [0, 2^21)，因为更大的 x 只是高位不同，对比较结果影响不大，而且 k 最大也是 2^21 级别，所以枚举到 2^21 就足够了。

优化思路

我们知道，从暴力法求解主要需要两个步骤：

  • 枚举可能的x
  • 对于给定的 x，计算有多少 a[i] 满足 (a[i] XOR x) <= k

我们打算使用 Trie 树（二进制 Trie，这样就只用跑）来存储所有 a[i]，并在 Trie 上沿着 x XOR k 的路径走，同时统计满足条件的节点数量。

查询

在Trie上，我们从高位到低位枚举，

记：k的第i位为1，x的第i位为c，假设前面判断的每一位都相等：

  1. 如果k的这一位是1，那么a[i] XOR x在这一位为0的所有情况都满足条件。

    因为高位相等，当前位0 < 1，所以整个子树都满足(a[i] XOR x) < k

            if (t == 1) {  
            // 如果k的这一位是1，那么a[i] XOR x在这一位为0的所有情况都满足条件
            // 因为高位相等，当前位0 < 1，所以整个子树都满足(a[i] XOR x) < k
            ret += sz[trie[p][!(c ^ t)]];
        }

  2. k的当前位为0：

    此时：(a[i] XOR x) 的当前位必须是 0

    • 如果是 1：那么 (a[i] XOR x) > k，不满足条件
    • 如果是 0：继续判断低位

    代码实现：只能沿着c ^ t方向继续走。

            if (!trie[p][c ^ t]) {
            flag = 1;  // 标记提前结束
            break;
        }
        p = trie[p][c ^ t];  // 移动到下一个节点

注意：如果没有提前结束（即最后一个节点亦可），记得加上最后相等的情况。

if (!flag) ret += sz[p];

统计 (a[i] XOR x) == k 的情况。

Open Source: The Hacker's Utopia

Hello everyone, it's a great honor to stand here and share my topic with you. Firstly, I'd like to ask you all to guess what I'll be talking about today.

(In English)

Initially, I intended to address the issue of wasteful electricity consumption and its environmental impact. However, assuming this topic might not resonate with everyone, I've decided to pivot to an alternative subject.

Lately I have been deeply attracted by open-source software. I think it has some characteristics of communism.Generally speaking, my speech today has four parts.

Let's begin!

First: The Hook: "The $0 Operating System That Powers the World"

Have you ever used a phone?

Have you ever surfed the internet?

Did you know that ALMOST 90% of the servers you rely on are running on the FREE, OPEN-SOURCE operating system, Linux?

The system of almost every phone is Android, which is based on the Linux kernel.

Furthermore, did you know that ALMOST 70% of the servers you rely on are running on the FREE, OPEN-SOURCE operating system, Linux?

What is Linux? A free, open-source, and community-driven operating system that powers the world.

The Core Idea: Freedom

  • Open Source: Anyone can view, use, and contribute to its code.
  • Free: Most distributions are free of cost.

Where is it

"Many people think of Linux as a niche technical tool, but the reality is, it's the invisible foundation of our digital world. It's everywhere, powering everything from the vast internet to the devices in our pockets. Let me show you what I mean."

  1. 🌐 The Internet:

    • "Look at the internet. Over 70% of all web servers run on Linux. What this means is that virtually every website you visit is most likely delivered to you by a machine running Linux. It's the bedrock of the online experience."

  2. 📱 Android:

    • "Now, think about your phone. Android is the world's most popular mobile OS, and it's built directly on top of the Linux kernel. So, if you use an Android phone, you are using a Linux-based system every single day. "

  3. 💻 The Cloud:

    • "Moving to the cloud. Linux powers the vast majority of cloud infrastructure. Whether it's Amazon AWS, Google Cloud, or Microsoft Azure, the cloud, quite literally, runs on Linux. It's the engine of the modern digital economy."

  4. 🖥️ Supercomputers:

    • "For the most demanding tasks. When scientists need to tackle the world's biggest problems—like climate modeling or genetic research—they turn to supercomputers. And nearly all of them run on Linux, proving its unmatched power and reliability ."

  5. 🔧 Your Car & Smart Devices:

    • "And it's even closer to home. Linux is embedded in the technology all around us: in our cars, our home routers, and our smart gadgets. This shows its incredible versatility and adaptability ."

"So, from the global scale of the internet and the cloud, down to the personal devices we interact with constantly, Linux is the silent, stable, and powerful force that makes it all work. It truly is the unsung hero of our connected world."

So for the normal person, what is the meaning of Open-Source?

  • Security: The source code is open for inspection by anyone, which allows vulnerabilities to be found and fixed quickly by the global community.
  • Reliability & Quality: Peer review by a large number of developers often leads to more stable, efficient, and high-quality software.
  • Flexibility & Customization: Users have the freedom to modify the code to fit their specific needs and requirements.
  • Active Community Support: Vibrant communities provide free support, documentation, tutorials, and continuous improvement.

Well, there are always some disadvantage, such as:

  • Lack of Official Support: While community support is available, there may be no formal support service or guaranteed response time, which can be a risk for businesses.
  • Complexity & Usability: Some open-source software may have a steeper learning curve and less polished user interface compared to commercial products.
  • Potential Security Risks: While transparency aids security, it also means hackers can equally study the code to find vulnerabilities before they are patched.

But honestly, these downsides aren't a big deal. That's because we have a global community of dedicated open-source developers who are driven by passion and a spirit of collaboration.

But generally speaking, the most compelling aspect of the open-source model is its profound spirit of contribution. Countless developers, driven by pure passion and altruism, dedicate their talents and valuable time without monetary reward. They collaborate to build powerful software, motivated not by profit, but by the belief that through selfless sharing, they can make the world of technology better for everyone.

What is Open Source? Beyond "Free as in Beer"

Open-source software is the closest thing we have to the communist ideal in the digital age.

Abolition of Private Property: Source code is the "means of production," rendered public property by its license.

From Each According to Ability: Developers contribute voluntarily, following their own interests and skills.

To Each According to Need: Any open-source software is free for any person to use for any need.

You can see them commit their latest changes, as recently as 2 days ago, not for profit, but for passion.

You can see thousands of individuals, bound by a shared passion, converge into a single force.

Finally, I'd like to end with an emphatic sentence: It is their dedication and selfless sharing that makes the open-source truly strong, has allowed me to truly appreciate the charm of open source.

终端使用帮助

在Linux下，终端是一定需要掌握的工具。它可以直接与任何安装在系统上的软件进行交互（包括系统底层（直接或通过软件）），并可以执行许多在图形化界面不能完成的操作，因为Linux最初就只有一个终端（绝大多数来电脑皆是这样的，包括Windows的老祖宗）

常用命令一览

sudo - 提升权限

Pay Attantion!!!!!

We trust you have received the usual lecture from the local System Administrator. It usually boils down to these three things:

#1) Respect the privacy of others.
#2) Think before you type.
#3) With great power comes great responsibility.

[sudo] password for [用户名]:

这是第一次运行sudo时的提示。很抱歉这一次被我使用掉了。但是你们也必须知道这一点。sudo是提升用户权限为管理员的指令，使用后的10min用户都可以显式地获得临时的管理员权限（如用于安装软件等）。
注意：sudo命令后的输入密码环节**密码不回显！**即没有*提示（可以配置但是没有必要）

上面那段话的翻译：

我们相信您已从当地系统那里听到了常规的训诫 管理员。通常归结为以下三点： #1) 尊重他人的隐私。 #2）三思而后行。 #3) 力量越大，责任越大。 [sudo] 用户名 的密码：

chmod：权限管理之一

常用参数：

  • -x：添加执行权限。

  • 同样的也有-x：取消执行权限

    例如：

    djy@DianJiaoYuan:~/Temp$ cat temp.sh 
#!/usr/bin/bash
echo "HelloWorld"

djy@DianJiaoYuan:~/Temp$ ll temp.sh 
-rw-rw-r-- 1 djy djy 35 10月  4 22:10 temp.sh
djy@DianJiaoYuan:~/Temp$ ./temp.sh 
bash: ./temp.sh: 权限不够
djy@DianJiaoYuan:~/Temp$ chmod +x temp.sh
djy@DianJiaoYuan:~/Temp$ ./temp.sh 
HelloWorld
djy@DianJiaoYuan:~/Temp$ ll temp.sh 
-rwxrwxr-x 1 djy djy 35 10月  4 22:10 temp.sh*
djy@DianJiaoYuan:~/Temp$ chmod -x temp.sh 
djy@DianJiaoYuan:~/Temp$ ./temp.sh 
bash: ./temp.sh: 权限不够
djy@DianJiaoYuan:~/Temp$ ll temp.sh 
-rw-rw-r-- 1 djy djy 35 10月  4 22:10 temp.sh
djy@DianJiaoYuan:~/Temp$

mkdir touch

mkdir: 创建目录

touch: 创建文件

echo

输出

$ echo "Hello, World!"
"Hello, World!"
$

ls

ls命令用于列出目录中的所有文件及子目录。有几个常用的参数：

  • -a：列出隐藏文件，默认有缩写la
  • -l：列出详细信息，默认有缩写ll

cat

输出文件内容

例如：

$ cat temp.txt
Exemple File

pwd

pwd输出当前工作目录即所在目录

cd

进入某目录 例：

djy@DianJiaoYuan:~$ cd 下载
djy@DianJiaoYuan:~/下载$ pwd
/home/djy/下载

rm 删除文件/目录

rm <filename>删除文件

djy@DianJiaoYuan:~/Temp$ touch temp.txt
djy@DianJiaoYuan:~/Temp$ ls
temp.txt
djy@DianJiaoYuan:~/Temp$ rm temp.txt 
djy@DianJiaoYuan:~/Temp$ ls
djy@DianJiaoYuan:~/Temp$

辅助字符（部分常用的）

&&

连续执行（在前者执行成功之后） 如

djy@DianJiaoYuan:~$ mkdir Temp && cd Temp
djy@DianJiaoYuan:~/Temp$ pwd
/home/djy/Temp

> / >>

>: 覆写。即删除文件所有内容并写入(执行过程：若存在同名文件：覆盖；不存在：创建。所以会自动创建文件)
>>: 追加。即在文件最后追加内容(同样会自动创建文件（兼容性存疑））

djy@DianJiaoYuan:~/Temp$ touch temp.txt
djy@DianJiaoYuan:~/Temp$ ls
temp.txt
djy@DianJiaoYuan:~/Temp$ cat temp.txt
djy@DianJiaoYuan:~/Temp$ echo "Hello, world!" > temp.txt
djy@DianJiaoYuan:~/Temp$ cat temp.txt
Hello, world!
djy@DianJiaoYuan:~/Temp$ echo "Hello, Linux!" > temp.txt
djy@DianJiaoYuan:~/Temp$ cat temp.txt
Hello, Linux!
djy@DianJiaoYuan:~/Temp$ echo "Hello, Linux!" >> temp.txt
djy@DianJiaoYuan:~/Temp$ cat temp.txt
Hello, Linux!
Hello, Linux!
djy@DianJiaoYuan:~/Temp$ rm temp.txt 
djy@DianJiaoYuan:~/Temp$ ls
djy@DianJiaoYuan:~/Temp$ echo "Hello, world!" > temp.txt
djy@DianJiaoYuan:~/Temp$ ls
temp.txt
djy@DianJiaoYuan:~/Temp$ cat temp.txt 
Hello, world!
djy@DianJiaoYuan:~/Temp$ rm temp.txt 
djy@DianJiaoYuan:~/Temp$ ls
djy@DianJiaoYuan:~/Temp$ echo "Hello, World!" >> temp.txt
djy@DianJiaoYuan:~/Temp$ ls
temp.txt
djy@DianJiaoYuan:~/Temp$ cat temp.txt 
Hello, World!

|管道字符。

将前者的输出作为后者的输入执行两者（将前者的标准输出(stdout)重定向到后者的标准输入stdin）。

例如：

djy@DianJiaoYuan:~/Temp$ echo "#include <bits/stdc++.h>
int main() {
    int a;
    std::cin >> a;
    std::cout << \"a = \" << a << std::endl;
    return 0;
}" > temp.cpp
djy@DianJiaoYuan:~/Temp$ g++ -std=c++14 -O2 -o temp temp.cpp
djy@DianJiaoYuan:~/Temp$ ./temp
1
a = 1
djy@DianJiaoYuan:~/Temp$ echo "12" > ./temp
djy@DianJiaoYuan:~/Temp$ echo "#include <bits/stdc++.h>
int main() {
    int a;
    std::cin >> a;
    std::cout << \"a = \" << a << std::endl;
    return 0;
}" > temp.cpp
djy@DianJiaoYuan:~/Temp$ g++ -std=c++14 -O2 -o temp temp.cpp
djy@DianJiaoYuan:~/Temp$ echo "1" | ./temp
a = 1
djy@DianJiaoYuan:~/Temp$ echo "1" > ./temp
djy@DianJiaoYuan:~/Temp$ ./temp
./temp: 行 1: 1：未找到命令
djy@DianJiaoYuan:~/Temp$ cat ./temp
1

这个用处还是挺多的，可以直接把cat 文件作为前项，达到不用手输输入。或者这个好玩的（需要你们自己试试，我这里就放终端复制的HTML了）

djy@DianJiaoYuan:~$ ll | lolcat 
总用量 72
drwxr-xr-x 12 djy  djy  4096 10月  3 23:20 ./
drwxr-xr-x  3 root root 4096 10月  3 21:52 ../
drwxr-xr-x  2 djy  djy  4096 10月  3 22:37 下载/
drwxr-xr-x  2 djy  djy  4096 10月  3 22:44 桌面/
-rw-------  1 djy  djy    15 10月  3 21:57 .bash_history
-rw-r--r--  1 djy  djy   220 10月  3 21:52 .bash_logout
-rw-r--r--  1 djy  djy  3771 10月  3 21:52 .bashrc
drwx------ 14 djy  djy  4096 10月  4  2025 .cache/
drwxr-xr-x 12 djy  djy  4096 10月  3 22:03 .config/
drwx------  3 djy  djy  4096 10月  3 21:52 .dbus/
drwx------  3 djy  djy  4096 10月  4  2025 .gnupg/
drwx------  3 djy  djy  4096 10月  4  2025 .local/
drwx------  5 djy  djy  4096 10月  4  2025 .mozilla/
-rw-r--r--  1 djy  djy   807 10月  3 21:52 .profile
-rw-r--r--  1 djy  djy     0 10月  3 22:37 .sudo_as_admin_successful
drwxrwxr-x  2 djy  djy  4096 10月  3 23:35 Temp/
-rw-------  1 djy  djy  4138 10月  3 22:44 .viminfo
drwxr-xr-x  3 djy  djy  4096 10月  3 21:52 .vscode/

第三方常用软件

g++

这里介绍g++的常用用法

g++ "文件名" <选项> 常用的选项有：

  • -o 指定输出文件名
  • -std=指定C++标准。如C++ 14

lolcat: 彩色输出

例如：

djy@DianJiaoYuan:~$ ls | lolcat
001.cpp
下载
桌面
clash-for-linux
OI-ZhX589
temp
Temp
temp.cpp
temp.o

当然，实际上要你们自行测试才能清楚是什么样子的（或者使用typora打开时查看上面那一段HTML代码）。

Luogu P3218

题目大意：

求取被指定的多条路径覆盖的树中找出被覆盖次数最多的节点

!!INPUT：

  • 第一行

    • N: 节点
    • K: 路径数

  • 接下来N - 1行，每一行：

    • x y: 节点x与y之间有通路

  • 接下来K行：

    • s t: 路径端点

思路

考虑使用链式前向星建树。

遍历路上的节点，经过一次加1。

题中路径已知两端点，记起点为 $u$ , 终点为 $ v $ 则路径为

$$ u \to lca(u, v) \to v $$ 若直接遍历，则时间复杂度为$ O(NK)$ ，按题目数据最多遍历$ 5 \times 10^{10}$ , 这是不能接受的。

考虑使用树上差分优化。

关于前缀和 & 差分的知识，可以去OI-WiKi中学习。

如果要对结点 $x$ 和 $y$ 之间的路径上的所有点权都加 $v$，可以对它的差分序列 ${D_x}$ 做如下操作：

$$ \begin{aligned} D_x &\gets D_x + v, \ D_{\operatorname{lca}(x, y)} &\gets D_{\operatorname{lca}(x, y)} - v,\ D_y &\gets D_y + v, \ D_{\operatorname{fa}(\operatorname{lca}(x, y))} &\gets D_{\operatorname{fa}(\operatorname{lca}(x, y))} - v. \end{aligned} $$

在所有修改操作完成后，可以计算一次子树和，就能得到更新后的点权。

倍增求LCA

首先第一遍DFS预处理数组，得到二维倍增数组 $fa$ 及 深度数组 depth。fa[u][i]表示节点i往上走$2^i$步的父节点。

接下来进行LCA查询，具体步骤：跳、跳、跳……然后就到LCA了。

从最低节点出发，往上跳diff步即可。具体操作：

for (int i = 0; i <= LOG; i++)
    if (diff & (1 << i)) // 若 diff 的二进制第 i 位为 1
        u = fa[u][i];

再两个点从同一高度出发，一起蹦蹦跳跳直到两点相同。虽然使用while循环可以优化一丢丢，但是这里还是给出for循环的代码：

for (int i = 0; i <= LOG; i++)
    if (fa[u][i] != fa[v][i])
    {
        u = fa[a][i];
        v = fa[b][i];
    }

$lca(u, v)$即为此时的$u = v $的父节点即$fa_{u,0}$。

树上差分

树上差分和一维差分略有不同。树上差分是子节点**"在后续的累加过程中，要向它的父节点（以及自己）传递多少值"**。

例如对于树：

graph TD
1/0 --> 2/0
1/0 --> 3/0 
2/0 --> 4/0
2/0 --> 5/0
3/0 --> 6/0
3/0 --> 7/0

要给路径$2 \to 1 \to 7$加上 $1$ , 只需要给

$$ D_7 \leftarrow D_7 + 1 \\ D_2 \leftarrow D_2 + 1\\ D_1 \leftarrow D_1 - 1\\ $$ 如果 $$lca(u,v)$$ 不是根节点，则 $father(lca(u, v))$ 也需要自减。

因为在$D_u$和$D_v$自增的过程中，$lca(u,v)$及其以上的所有节点的值都相应地减了两个$1$，因此给$D_{lca(u,v)}$及其父节点各自减一刚好可以抵消。

在最后结束时，使用前缀和合并差分数组即可得出初始值。

注意：需要使用后序遍历（即左->右->根的顺序），因为根节点需要统计所有子节点的贡献（直接在递归子节点后加上子节点的值即可）。

**提示：**在后序遍历之前记得先初始化节点值为差分值（因为也包括它自己的贡献）

示例代码

#include <bits/stdc++.h>
using namespace std;

const int LOG = 20; 
const int MAXN = 5e4 + 10;

int fa[MAXN][LOG << 2], depth[MAXN], D[MAXN], val[MAXN];
vector<int> tree[MAXN];

void dfs(int x, int father)
{
    fa[x][0] = father;
    for (int i = 1; i <= LOG; i++)
    {
        fa[x][i] = fa[fa[x][i-1]][i-1]; // 一分为二
    }
    for (auto child: tree[x])
    {
        if (child == fa[x][0]) continue;
        depth[child] = depth[x] + 1; // 深度+1 
        dfs(child, x);
    }
}

int lca(int u, int v)
{
    if (depth[v] > depth[u]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; i <= LOG; i++)
        if (diff & (1 << i)) // 若 diff 的第 i 位为 1 
            u = fa[u][i];
    if (u == v) return u;
    if (fa[u][0] == fa[v][0]) return fa[u][0];
    for (int i = LOG; i >= 0; i--)
        if (fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    return fa[u][0];
}

void accumulate(int x, int father)
{
    val[x] = D[x];
    for (auto child: tree[x])
    {
        if (child == father) continue;
        accumulate(child, x);
        val[x] += val[child];
    }
}

signed main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int u, v; 
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    dfs(1, 0); // 根节点的爸爸是 0 
    
    for (int i = 1; i <= k; i++)
    {
        int s, t;
        cin >> s >> t;

        int l = lca(s, t);

        ++D[s];
        ++D[t];
        --D[l];

        if (fa[l][0])
            --D[fa[l][0]];
    }

    accumulate(1, 0);

    int ans = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, val[i]);
    }

    cout << ans << '\n';
    
    return 0;
}