开题。T1 秒了。 T2 以为会，推了 4 个小时式子，然后不会了。 于是似了。 嗯，对，英改师。

# 题解：P13118 [GCJ 2019 #2] Contransmutation ## Solution 注意到一个强连通分量内的所有元素都可以集中到任意一个节点上，即强连通分量中的每一个点都等价，容易想到先跑缩点。 于是我们得到了一个 DAG，因此要使一个节点（强连通分量）达到最大值，应该让所有能到达它的点都“分…

在文章《CSP：追忆》发表评论：

已严肃完成今日追忆大学习

我常常追忆追忆。 不为人知的是，面对新一轮的 CSP-S，我早已做足了功课。 在上一届的省选联考中，“追忆”无疑是最（？）有含金量的一道题。作为一名训练有素的选手，我没有理由不相信出题人会在今年的 CSP-S 里放 4 道甚至 3 道的追忆。 考前的每一天，我每天坚持默写追忆 114514 遍，就为了能 AK CSP-…

在文章《曝光队✌@__FL__CSP2025游击》发表评论：

什么鬼

坐标 SD 游记也要有头图。  CSP RP++! # CSP-S 2025 游记 ## Day -? 初赛。因为失明改错答案： $$AK\to 98.5$$ 有点不适。不过```You hav…

在文章《【欢迎投稿】OI 教学研究当前的若干具体问题：行动起来！》发表评论：

qpzc

# AT_abc428_d [ABC428D] 183184 小清新思维题。 ## Solution 看到这个题一般都会想到去枚举完全平方数，然而 $f(C,C+x)$ 最大可以达到 $2\times 10^{18}$ 量级，不可行。 我们不妨换一个思路，注意到在钦定了 $C+x$ 的位数 $k$ 的前提下，$f(C,…

# AT_abc428_f [ABC428F] Pyramid Alignment ## Problem 有 $N$ 个滑块叠成一摞，从上往下第 $i$ 个滑块的长为 $w_i$，且上面滑块的长度总是严格小于下面滑块的长度。初始时，每个滑块的左端点都为 $0$。 现在有 $Q$ 组询问，对询问 $1$ 和 $2$，需将…

## Solution ### Task 1 对于一个人 $i$ 的最好名次，我们需要让他比其他人先跑的时间尽量长。显然对于人 $(i,j)$，人 $i$ 领先人 $j$ 的时间至多为 $|i-j|$，发现仅将 $i$ 道的喇叭打开恰好满足，故这样必定最优。 如果 $i>j$，则 $j$ 领先 $i$ 的条件为 $$a…

## Solution 什么是冒泡排序？ 众所周知，在每一次遍历中，我们比较相邻的两个元素，并把更大的放到后面，这样可以保证每一次都将剩下元素中最大的一个扔到最后，所以保证了时间复杂度是 $O(n^2)$。 这意味着，如果对于一个已经进行了 $i$ 轮冒泡排序的序列来说，它的前 $i$ 大元素会在最后，剩下的则在前面。…

在讨论《梦熊月亮赛 作弊名单》回复：

qp

在文章《题解：P11321 [NOISG 2020 Qualification] Relay Marathon》发表评论：

题解写错了\kk，时间复杂度部分应该是：“时间复杂度瓶颈在 Dijkstra，为 O((n+m)logn)。”

在讨论《『Fwb』Round 2 赛后总结帖》回复：

火钳流明。 666还在喷。

在讨论《『Fwb』Round 2 赛后总结帖》回复：

@[wanglongye](luogu://user/1080857)

在讨论《『Fwb』Round 2 赛后总结帖》回复：

码了一点字，但想了想还是： ```火钳刘明。```

在讨论《红题CE求条……》回复：

@[zhouzihang3](luogu://user/615166) 显然 $x$ 可能大于 $10^k$。

？这题 2300？ ## Solution 一个显然的观察是，每个 $x_i$ 向 $i$ 连边，会形成一个森林。我们先给每个 $b_i$ 减去 $a_i$，表示每种元素剩余或缺多少。贪心地，如果一棵子树缺少一些元素，其他元素一定会从根节点流过来；否则它的元素会往根流回去。因此对于一个节点 $u$，如果它子树的 $b_…

## Solution 考虑如果不能选有包含关系的线段时应该怎么做。显然有 dp 转移： $$f_{i}=\max_{r_j #define int long long using namespace std; const int N = 3005; int t,n,dp[N],f[N vec; struct seg…

## 题意 将题目抽象成这个问题：构造一个由 $1,2,3,4$ 组成的序列，使得存在 $1\le x\le 4$，任意两个相邻的 $x$ 的距离 $\le h$，且 $x$ 第一次出现的位置 $\le h$，最后一次出现的位置 $\ge n-h+1$。求方案数。 ## Solution 考虑指定 $x$ 是一个数时怎…

## Solution 考虑每个人 $i$ 向自己的 $P_i$ 连边，由于 $P$ 是一个排列，所以每个点入度为 $1$，出度为 $1$，也就是说图由若干个环组成。进一步地，每个环在变换它的大小的次数后会恢复原样，因此对于一个排列 $P$ 连成的图，$S(P)$ 等于所有环的大小的 $\operatorname{lc…

## Solution 直接根据原题意做是困难的，我们需要将其简化。 发现可以考虑哪些边只用走一次。考虑将关键点之间一一断开，每个关键点把自己的块走完。转化一下，就是：每个关键点向外延伸一条路径，路径不能相交，求最大路径长度和，最终答案就是 $2(n-k)-M$，$M$ 是最大路径长度和。 考虑 dp。对于一个点是否出…

## Solution 楼梯的形状是一个矩形的残缺，我们不妨考虑它完整的那一个角。考虑当一个方格作为楼梯的**左下角**时，它的最大格子数量是确定且好求的。显然，从下往上每一行都尽量往右拓展，得到的值是最大的。 考虑单调栈维护。设 $sum_{i,j}$ 表示方格 $(i,j)$ 往右最多能拓展多少个 $1$；枚举每一…

> 贪心是一种美学。 ## 题意 有一棵有 $2k$ 个结点的树，任意将它们分成 $k$ 对，定义这棵树的路径和为每对结点之间的路径长度之和，分别求路径和的最小值和最大值。 ## Solution 先考虑最小值。考虑每条边的贡献，当一条边两边的结点数为奇数时，显然这条边必定要走至少一次。事实上将每条这样的边加入答案一次…

## Solution 先考虑子任务 $3$ 怎么做。首先路径 $1\to 2$ 必选，只需要考虑剩下的关键点中选择哪两个。 对剩下的关键点跑多源最短路。由超级源点对关键点连边权为 $0$ 的边，跑 dijkstra。于是我们就能得到每个点 $u$ 离最近关键点的距离 $dis_u$，也能得到每个点的最近关键点 $b_…

## Solution 观察题目，$K$ 的取值显然具有单调性，容易想到二分。 考虑设计判断函数。有一种显然的贪心思路：对于前几个洒水器，我们希望它们第一个不能覆盖到的花越往右越好。但是有一种额外的情况，即两个洒水器组合在一起，左边的朝右，右边的朝左，这种情况我们单独考虑。 设计 $\operatorname{dp}$…

## Solution ### Question 1 可以先考虑 Special Jugde 是怎么写的。容易想到对于一个颜色序列，可以维护一个蓝栈和红栈，如果颜色是绿色，两个栈都弹出/压入一个，否则对应颜色栈弹出/压入一个。中途没有弹空栈，最后栈为空即合法。 如果我们得到了一个合法的 $01$ 序列，其中元素为 $1…

## Solution 显然当其他墙解锁后可以移动到最长的墙后面，所以我们考虑最长的墙的位置。 不妨设 $f_{i,j}$ 表示对于前 $i$ 列，未被阻挡的激光为 $j$ 束时的最小代价（**钦定第 $i$ 列未被阻挡**），显然有转移： $$f_{i,j}=\min_{k #define int long long…

尝试开启输入输出流同步（即删去```ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);```），我也不知道为什么。

在讨论《有谁打表吗？给我看一下有几行代码》回复：

@[zhuzhu0307](luogu://user/1386428) 打表会代码过长交不上去