这名用户暂未设置签名。
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
在讨论《真没看懂这题为什么要撤题解》回复：
是啊
建议添加 SPJ。 首先，每个点上的箭头都是固定的，那么这幅图就会构成一棵以第 $m$ 列为根的树，以及若干个环。有用的点只有树上的点。考虑将所有叶子节点按照 dfs 序重新编号，那么每个树上的点能够覆盖的就是一段连续的区间。令 $dp_{i,j}$ 表示考虑完前 $i$ 个叶子，用恰好 $j$ 个点是否可以完全覆盖。…
一道非常有思维难度的贪心题。 先考虑一个特殊性质：设从 $i$ 开始挑战的精灵有 $vis_{i}$ 个，保证 $\sum_{i}^n vis_{i}\le n-i+1$，那么这个环就成了一条链。于是我们开一个 set，每次将点 $i$ 处的精灵加入 set，如果点 $i$ 的矮人没有精灵可以战胜，就把战斗力最弱的精灵…
在文章《CSP游记&反思》发表评论：
更新：T1死因找到，数组开小
CSP 寄寄了，278->172，非常伤感，不免对未来感到迷茫。我去问了教练，幸运的是还能参加 NOIP。我迷茫的时候吗，教练的话点醒了我：“如果你只是因为这一次没考好就这么灰心丧气，那你学什么 OI 呢”。这让我意识到，CSP 的失利已经过去了，关键的考试还有 NOIP。我必须重整旗鼓，去面对接下来更为重要的考试。…
在讨论《建议增加这个题的加强版本，题目难度为紫》回复：
@Lain_yc 这个题是必须从左往右救，你怎么 sort
在文章《题解：P14097 [POCamp 2022] 救火 / Brinnande träd》发表评论：
@CatFromMars 过奖了，我不是很强
在讨论《建议增加这个题的加强版本，题目难度为紫》回复：
@mediocre_ 发这干嘛
在讨论《建议增加这个题的加强版本，题目难度为紫》回复：
@Starrykiller 管理员麻烦看一下。
在讨论《建议增加这个题的加强版本，题目难度为紫》回复：
@Starrykiller
在文章《题解：P14097 [POCamp 2022] 救火 / Brinnande träd》发表评论：
@swate114514，是的，但是平衡树优化 dp 可以解决 Xi 不单调的问题
# 前言 质量非常非常高的平衡树优化 DP。（平衡树调了好久） 下面来讲讲我的思考过程，也算是巩固平衡树优化 DP 了。 这是我做的第一道平衡树优化 DP 的题，经过和 xks 同学很久的讨论最终做出。 # 设计 DP 这道题很容易想到 $n^2$ 的 DP。 我们令 $dp_{i,j}$ 表示考虑完前 $i$ 棵树，…
我们很容易发现，一个数 $a_{i}$ 和一个数 $a_{j}$ 可以交换，当且仅当 $i a_{j}$。我们可以对于整个序列进行分块，算出块内的 $ans$。然后对于算块 $i$ 的答案，设之前数的最大值为 $mx$，那么答案就是块 $i$ 中最大的 $a_{j} #define ll long long #defi…
一道和学长单挑时随到的 2400 的题。 考虑一下这道题的难点所在：有些位置的字符可以相同。设 $a_{i}$ 表示后缀 $i$ 的排名。我们经过思考发现 $s_{i}=s_{j}$，当且仅当 $a_{i}$ 和 $a_{j}$ 的大小关系与 $a_{i+1}$ 和 $a_{j+1}$ 一样，即 $a_{i} a_{j…
第一眼看上去，这道题似乎并不可做。我们看看部分分（是一个找到正解的好方法）。咦，$n \le 2000$，这似乎提示着我们，做法的复杂度和 $m$ 无关。 来观察一下题目给出的图，我们发现，任意一次操作后，两只兔子的相对位置不会变化。通俗地说，兔子的位置和操作的顺序无关。我们考虑对于兔子 $i$，经过点 $(x_{i}…
在讨论《MatrixGroup's Unknown Round 赛时答疑帖》回复：
@MatrixGroup，而且你 spj 的1e18判挂了，题上说的是 $\le 1e18$
在讨论《MatrixGroup's Unknown Round 赛时答疑帖》回复：
@MatrixGroup，T1的数据是不是锅了，测试点里有n=2e18的
一道非常好的数据结构优化 dp 的题。 考虑 $dp_{i}$ 表示结尾的值是 $i$，$f$ 的值最大是多少。 考虑从小到大枚举 $i$，那么我们用并查集和 $set$ 维护点 $j$ 向左最远到哪里，$x$ 和 $y$ 联通当且仅当 $x-y\le D(x>y)$。 然后用线段树维护区间最大值即可。 下面是 AC…
第一次写 ```bitset``` 优化动态规划。 不难发现，如果当前取完了前 $i$ 张牌，那么总贡献就是 $(\sum_{j=1}^i a_{j})-i+1$。考虑设计 $dp_{i}$ 表示能否恰好取完前 $i$ 张牌。若 $dp_{j}=1$，则 $dp_{j+a_{j}}=1$。使用 ```bitset```…
考虑将这道题题意转化：共有 $n$ 个点，每个点的坐标为 $(x_{i},y_{i})$，点权 $t_{i}$。给了你 $m$ 次询问，每次询问给出 $a,b$，请最小化 $\mid a-x_{i} \mid+\mid b-y_{i}\mid+t_{i}$。 于是，这道题就转化到了平面上，分类讨论 $a$ 和 $x_{…
有一个很显然的贪心结论：如果选上 $a_{i}$ 仍然不会组成 $x$，就把它选上。 这启示我们，枚举区间的左端点 $l$，然后暴力扩展右端点 $r$。设 $cnt_{i}$ 表示 $x$ 的因数 $i$ 是否可以被组成。因为 $x \le 10^5$，所以 $x$ 的因数有限，大概在 130 以内。若 $a_{i}$…
在讨论《样例过了但全WA》回复：
@Union_Qwind ```cpp #include #define ll long long #define maxn 1000005 #define mod 1145141 using namespace std; ll n,Q,a[maxn],sum[maxn],l,r,ans; ll cal(ll x,ll…
在讨论《样例过了但全WA》回复：
@Union_Qwind，逆元指的是 $x$ 的 $P-2$ 次方
考虑每次询问 $k$ 的长度，那么最终剩下 $n \bmod k$ 个位置没有被问到。因为 $m$ 和 $k$ 都是偶数，所以我们可以把剩下的位置分为 $L$ 和 $R$ 长度相等的两部分。设 $L$ 和 $R$ 的长度为 $s$，找到最后一个长度为 $k$ 的询问，设它后 $k-s$ 位为 $T$。 最后询问 $T…
思考一下这道题的一个结论：若 $s_{i}$ 可选，那么 $s_{i+1}$ 到 $s_{n}$ 中不存在 $s_{j} > s_{i}$ 且 $j$ 已被选中。因此，我们可以维护一个 $mx_{i}$，表示字母 $i$ 最后出现的位置。 对于每一个 $t_{i}$，找到第一个可以选中的位置，并更新 $mx$。如果没有…
考虑 $(x,y+1)$ 对比 $(x,y)$ 贡献的不同点：多了一列，少了最外层的一个平行于对角线的列（后面简称对角线）。因此维护行、列、对角线的前缀和即可。注意一下边界情况，很容易写挂。 下面是我的 AC 代码。 ```cpp #include #define ll long long #define maxn 2…
Easy Varsion 给了我们根号分治的启发，Hard Varsion 相比也与它有关。 考虑 Easy Varsion 中的做法：从 $k$ 出发，暴力标记前 $10^3$ 个点，然后每一次跳 $10^3$ 格，直到跳回标记的点。但是我们发现，我们似乎没有用到“$n$ 是排列”的条件。 不妨先随机跳 $m$ 次，…