Polaris 能干什么？
command_block
·
·
科技·工程
什么是 Polaris？为 OI 设计的教学 Agent：Polaris
以下内容在 Polaris 内部测试版本中完成，我们以文字/截图的形式将其转录在此。
由于底层模型更新等原因，正式版本的表现可能和测试版本有差异，或有部分功能尚未移植。我们最终会保证两者的一致性。
题解助手
写题解是个很有用的训练方式，可以锻炼思维严谨性，缺点是时间成本较高。
Polaris 提供题解助手功能：把口胡整理为题解，同时适当追问，确保作者充分理解了做法细节。节省精力的同时，不减弱训练效果。
以下是一个使用题解助手的例子，题目是 P10222 [省选联考 2024] 最长待机（D2T3）。
:::info[用户：给出题面]
一个 Sleep++ 程序由 n 个函数构成，每个函数有一个 flag e 和调用列表 Q，在调用某个函数时：
- 若 e=0，令 r=1；
若 e=1，输入变量 r。（每次调用都重新输入）
- 若 Q 为空：等待 r 秒。
若 Q 不为空：重复以下操作 r 次：
- 按顺序调用函数 Q_1,Q_2,\dots,Q_m。（设 Q 的长度为 m）
保证调用关系构成一棵有根树。
我们认为除了“等待 r 秒“之外的操作（包括输入，调用函数等）都不消耗任何时间。这可能导致同一时刻内输入多个数。
可以证明，调用任意一个 Sleep++ 程序的任意一个函数，无论如何设定输入，消耗的时间总是有限的。
“最长待机”的游戏规则如下：
-
小 \omega 和 小 \aleph 准备好各自的 Sleep++ 程序并选择各自程序中的一个函数。它们互相知晓对方程序的结构以及选择的函数。
-
在时刻 0，小 \omega 和 小 \aleph 同时调用自己选择的函数，游戏开始。
-
在时刻 t（t \ge 0），双方可以看到对方在时刻 0\sim (t - 1) 输入的所有数字，并相应调整自己在时刻 t 输入的数字，但双方无法得知对方在时刻 t 输入的数字。
-
函数调用先结束的一方输掉游戏，另一方胜利。两个调用同时结束算作平局。
小 \omega 和 小 \aleph 都是绝顶聪明的，在它们眼中，如果有一方存在必胜策略，那么这局游戏是不公平的。换言之，双方都不存在必胜策略的游戏是公平的。
小 \omega 写了一个 n 个函数的 Sleep++ 程序并进行了 m 次操作，操作有以下两种：
- 操作一：给出 k，将 e_k 修改为 (1 - e_k)；
- 操作二：给出 k，与小 \aleph 玩一局“最长待机”，开始时小 \omega 会调用自己的函数 k。
小 \aleph 信奉极简主义，它希望对于每一局游戏设计出函数个数最少的程序，使得选择其中某个函数能让这局游戏是公平的。你能帮它求出最少所需的函数个数吗？
可以证明，小 \aleph 总是能设计一个程序并选择其中一个函数，使得游戏是公平的。
（帮我总结简要题意）
:::
:::success[Polaris：简要题意]
**简要题意**
给定一棵以函数为节点的有根树，每个函数 $i$ 有一个类型 $e_i \in \{0,1\}$ 和一个子函数列表 $Q_i$（可能为空）。调用函数 $i$ 时：
- 若 $e_i=0$，令 $r=1$；若 $e_i=1$，则从外界输入一个正整数 $r$。
- 若 $Q_i$ 为空，则等待 $r$ 秒；否则重复 $r$ 次：按顺序调用 $Q_i$ 中的所有子函数。
两人各准备一个这样的程序，并各自选定一个起始函数，在时刻 $0$ 同时开始调用。在任意时刻 $t$，双方可以看到对方在 $[0,t-1]$ 内输入的所有数字，并据此决定自己在时刻 $t$ 输入的数字（但不知道对方同一时刻的输入）。先结束调用的一方输，同时结束则平局。若双方均不存在必胜策略，则称游戏公平。
现在小 $\omega$ 有一个 $n$ 个函数的程序，进行 $m$ 次操作：
- 操作一：翻转 $e_k$。
- 操作二：给定 $k$，小 $\omega$ 将调用自己的函数 $k$。小 $\aleph$ 需要设计一个函数个数最少的程序，使得游戏公平。求这个最少函数个数。
$n \le 5\times 10^5$，$m \le 2\times 10^5$。
:::
:::info[用户：口胡做法]
对于函数 A 和 B，若 A 对 B 不能必胜，则称 A <= B，若互不能必胜则称 A = B。
- 如果 A' 是 A 的子集（删掉某些节点，剩下的节点接到自己仍存的祖先），A' <= A
- 如果又有 A' >= A，那么 A' = A 且节点数更少。
- 思路：找满足 A' >= A 的子集 A'，将 A 化简为 A'
设根节点为 u
- 所有除了 u 之外的 e=0 点都可以删掉。
- 如果 u 的 e=1，那么除了 e=1 最多的链 L（链指根节点向下的一条链，把 e=0 缩合起来，只剩一条纯 e=1 链，后面类似），其他的部分都没用，因为即使一开始没有，也可以通过填写 L 造出来。显然 L 就是最小的，长度不一样一定会不公平。
- 如果 u 的 e=0，它向下连接着若干个 e=1 的子树，先把这些子树化简为 e=1 链。设对于两条 e=1 链，如果前面的比后面的长，可以抛弃掉后面的，理由类似。化简后 e=1 链的长度单调不降，显然这是最简的，如果这个“长度序列”不一致，一定会在最后一个不等处产生不公平。
考虑怎么维护，为了方便可以加 e=0 点将树三度化。
对每个节点维护子树化简后的结果，将长度序列相邻相等的元素压缩成一个，产生自然根号，合并的代价是子树大小的根号。
类似 DDP，写个全局平衡二叉树维护，分析得（子树规模倍增求和）复杂度还是根号。
:::
:::warning[Polaris：必要追问]
题意和核心思路我理解了。你从偏序关系出发，把问题归约成“找最小等价子集”，然后分 $e_u=0/1$ 讨论化简结果，这个方向很清晰。
目前文章里有几个地方我想确认一下，避免后续整理时出现歧义：
1. **“A' 是 A 的子集”的精确定义**：是指从原函数树中删去若干节点，并把被删节点的子节点重新挂到被删节点的父节点上吗？还是允许更一般的操作？
2. **$e_u=0$ 时的化简结果**：你说“化简后 $e=1$ 链的长度单调不降”，这个单调性是化简过程中自然产生的，还是需要显式排序？另外，最终保留的“长度序列”是否就是这些链的长度按某一顺序排列？
3. **复杂度部分**：“自然根号”和“子树规模的根号”目前描述比较简略，后面整理时需要补一下势能分析或简要推导。
如果你现在就想让我把已有内容整理成更完整的题解草稿，我可以先搭一个框架；如果还想继续讨论细节，我们就先把上面几点对齐。
:::
:::info[用户：解释疑点]
1. 你可以理解为节点是一个个删除的，把子节点接到父节点上，一口气看来就是“剩下的节点接到仍存的祖先”，对了，根不许删除
2. 剩余的长度自然单调了，没有任何交换
3. 一次修改的复杂度是 sqrt(n)+sqrt(n/2)+sqrt(n/4)+...=O(sqrt(n))
:::
:::warning[Polaris：必要追问 2]
好，三点都清楚了。根不可删、链长自然单调、复杂度是根号级求和，这些都没问题。
现在文章里还缺一个关键点：**为什么“长度序列不一致就一定不公平”**。你刚才说“一定会在最后一个不等处产生不公平”，这个论证需要展开一下——具体是构造性的（比如长的那方可以模拟短的那方），还是基于某个归纳？如果现在想补，可以简单说一下你的想法；如果暂时不想展开，我也可以先标一个 TODO，后面再填。
:::
:::info[用户：解释疑点 2]
考虑有两个程序 A,B
1. 如果 B 的链长序列是 A 的严格后缀，那么 A 更强
2. 如果链长最后一个不等处 A 是 c，B 是 c'，且 c>c'
那么 A 通过给 c 的第一层填充分大的数，将其展开，再取子集，就能变成 B，且左侧有额外东西，根据 (1)，这比 B 强
:::
:::success[Polaris：最终确认]
这个论证很漂亮，两条规则把“长度序列不一致一定不公平”说清楚了。我确认一下逻辑链：
1. 规则 (1) 处理了“后缀关系”的情况——B 是 A 的严格后缀，则 A 更强。
2. 规则 (2) 处理了“最后一个不等处”的情况——A 在不等处更长，则 A 可以通过在那一层填大数把自己展开成 B 的形态，且左侧多出东西，根据 (1) 就比 B 强。
这样两条合起来，确实覆盖了任意两个不同长度序列的比较。我按这个逻辑帮你把文章里那一段补完整。
:::
:::info[用户：开工吧]
既然没有疑问了，把整个题解重新整理好吧
:::
:::success[Polaris：完成题解]
> 好的，我把整篇题解按现在的讨论结果重新整理一遍，结构上拆成题意、偏序与化简、核心结论、维护方法几个部分，并把之前确认的论证细节补进去。
**偏序与化简**
对于两个程序 $A$ 和 $B$，若 $A$ 对 $B$ 不存在必胜策略，则记 $A \le B$；若 $A \le B$ 且 $B \le A$，则记 $A = B$。
考虑对程序进行化简。称 $A'$ 是 $A$ 的**子集**，当且仅当 $A'$ 可以通过从 $A$ 中删除若干节点（根节点不可删除），并将被删节点的子节点重新挂到被删节点的仍存祖先上得到。
容易看出，若 $A'$ 是 $A$ 的子集，则 $A' \le A$。这是因为 $A'$ 的调用结构是 $A$ 的“删减版”，$A$ 总可以通过在对应位置填充分大的数来模拟 $A'$ 的行为，从而不会输给 $A'$。
因此，若存在 $A$ 的一个真子集 $A'$ 满足 $A' \ge A$，则 $A' = A$，且 $A'$ 的节点数更少。我们的目标就是找到 $A$ 的极小等价子集。
---
**核心结论**
设当前考虑的子树根节点为 $u$。
**情况一：$e_u = 1$**
将子树内所有 $e=0$ 的节点缩合（即删除 $e=0$ 节点，将其子节点上移），得到若干条纯 $e=1$ 的链。保留其中最长的一条链 $L$，其余部分均可删除。
理由：即使初始时没有那些较短的链，也可以通过在 $L$ 上填充分大的数来“造出”它们的行为，因此较短链的存在不会改变程序的等价类。显然 $L$ 就是该子树的最简形式。
若两条链长度不同，则它们一定不公平。具体地，设链长序列分别为 $A$ 和 $B$：
1. 若 $B$ 的链长序列是 $A$ 的严格后缀，则 $A$ 更强。
2. 若在最后一个不等处 $A$ 的长度为 $c$，$B$ 的长度为 $c'$，且 $c > c'$，则 $A$ 可以通过在 $c$ 的第一层填充分大的数，将自己展开成 $B$ 的形态，且左侧多出额外部分。根据 (1)，$A$ 比 $B$ 强。
综上，任意两个不同的长度序列必然在最后一个不等处产生不公平，因此长度序列唯一确定了等价类。
**情况二：$e_u = 0$**
根节点 $u$ 向下连接着若干个子树。先将每个子树按上述规则化简为 $e=1$ 链，得到若干条链。对于这些链，若前面的链比后面的链长，则后面的链可以抛弃（理由同情况一：较短的链可以被较长的链模拟）。
化简后，剩余的 $e=1$ 链长度单调不降。这个长度序列就是该子树的最简表示。若两个子树的长度序列不一致，同样会在最后一个不等处产生不公平。
---
**动态维护**
为了方便维护，可以添加 $e=0$ 的虚节点将树三度化。
对每个节点维护其子树化简后的结果。将长度序列中相邻相等的元素压缩成一个，这样序列长度是 $O(\sqrt{\text{子树大小}})$ 级别的（自然根号）。
合并两个子树的代价为 $O(\sqrt{\text{子树大小}})$。采用类似动态 DP 的全局平衡二叉树进行维护，每次修改的复杂度为：
$$\sqrt{n} + \sqrt{n/2} + \sqrt{n/4} + \cdots = O(\sqrt{n})$$
总复杂度 $O((n+m)\sqrt{n})$，可以通过。
:::
最终产生的题解在简单人工修改后发布为 [题解：P10222 [省选联考 2024] 最长待机](https://www.luogu.com.cn/article/oln09v0l)。
以上测试完成于 2026 年 6 月 4 日。
# 题目搜寻
### 原题识别机
目标：认出《小Z的礼物》。
### 相似题搜寻
目标：这道题太妙了，但我有点没消化，有没有很像的题？
### 类型题搜寻
目标：完全图+最小生成树。
### 前置题搜寻
目标：想做 NOIP T4，但不会科技，先刷一些前置题目。
### 题单挑选
目标：我想练网络流了。
Polaris 会根据你的刷题记录动态推荐题单。
:::info[给一名提高选手的题单]
:::
:::info[给一名省选选手的题单]
:::
# 知识问题
Polaris 会根据站内优秀文章回答知识问题，并引导到对应文段。
# 内容库基建
### 题目标注与可视化
我们利用 LLM 为题目自动标注了难度和相关性。人工测试支持该标注的可靠性。
一则相关题目图谱，中心题为 [CF1205E Expected Value Again](https://www.luogu.com.cn/problem/CF1205E)：
另一则相关题目图谱，中心题为 [CF888G Xor-MST](https://www.luogu.com.cn/problem/CF888G)：
> 节点和边由内容库自主生成，色块和注释为人工添加，便于理解。