在文章《【附代码】NOIP2025的组题确有问题？由 S->NOIP 的成绩散点图统计分析》发表评论：

成功找到自己（

```cpp #define int long long ``` 对吧！ 要计算组合数。 ```cpp int C[maxn][maxn]; ``` 对吧！ 要对 $2n$ 个元素排序。 ```cpp const int maxn=10010; ``` 对吧！ 我还会 T4，还拼了 T3 暴力。 对吧！ 我文操没写错吧…

好像一个没有任何难度的做法。 直接支配对启动。对于右端点 $i$，维护 $[i-pr,i-pl]$ 的前缀最小值，可以从大往小扫右端点，队列维护，前面删后面加之类的。 然后对于这个过程中的一个左端点区间 $[l,r]$，$a_l$ 是最小值，会在右端点属于 $[l+pr,r+pl]$ 时存在，st 表找到区间内最大值，…

[P11115](https://www.luogu.com.cn/problem/P11115) 一坨。 询问是跟 X 轴相关的信息，扫描线 X 轴。数据结构维护 Y 轴信息，在 $i$ 处计算所有 $x2$ 为 $i$ 的 $(x1,x2)$ 对。 修改在矩形 X 轴边界进行。对 Y 轴维护当前被覆盖了几次，以及当…

[P14316](https://www.luogu.com.cn/problem/P14316) 平衡！设 $n,q,a_i$ 同阶。 尝试找到支配对，形如一些最小的 $(l,r,x)$ 使得包含 $[l,r]$ 的询问 $x$ 可以存在。 对于右端点 $i$，考虑哪些 $j$ 和 $i$ 形成支配对。 若 $a_j…

在讨论《有没有懂图论的大手子证一下》回复：

直接手玩K4

[P12547](https://www.luogu.com.cn/problem/P12547) 感觉非常神秘啊。 首先需要一个有前途的 $O(n^2)$ 做法，然后可以猜到后面就是用线段树维护一下区间信息。 首先区间内所有的 $1$ 都可以选。现在要在 $1$ 的间隔中选一些 $-1$，满足前后缀和都非负。 有一堆…

[P14250](https://www.luogu.com.cn/problem/P14250) 一个全部顶满的做法。 ### Solution 记 $a$ 的最大、次大、第三大值为 $mx$，$se$，$th$（可以相等）。 先问 $1\sim n$ 的链得到 $\sum a_i$。由于查询操作是离线的，尝试一下发…

在文章《题解：CF1209H Moving Walkways》发表评论：

膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜膜拜

厉害题。根本想不到。 ### Solution 先考虑完美匹配怎么做。 考虑 hall 定理判定，要求 $\forall S,|S|\le|N(S)|$。记 $w(S)=|S|-|N(S)|$。考虑容斥掉不合法的，对于 $\exist S,w(S)>0$ 的图，选取一个代表元，使得 $w(S)$ 最大，存在相等时令 $…

[P11834](https://www.luogu.com.cn/problem/P11834) 为了方便，用 ```+-``` 来表示集合的加减。 记 $num_s$ 表示 $s$ 内部的边数，$cross(s,t)$ 表示 $s$ 指向 $t$ 的边数，因为最开始是无向边，有 $corss(s,t)=\frac{…

在文章《题解：P14099 [POCamp 2022] 一安在？2 / Where's Waldo?》发表评论：

好像只加 r-l+1=2 那个就够了

在文章《题解：P14099 [POCamp 2022] 一安在？2 / Where's Waldo?》发表评论：

我怀疑 3 是负面效果

[CF2115E](https://www.luogu.com.cn/problem/CF2115E) ### 思路 对于完全背包问题，在 $V$ 极大的时候，会选很多性价比最高的物品。令 $mx$ 为 $\frac{w_{mx}}{c_{mx}}$ 最大的物品，非性价比最高的物品至多选 $c_{mx}$ 件，因为如果…

#### [CF2097F](https://www.luogu.com.cn/problem/CF2097F) ### 思路 考虑网络流。对第 $i$ 天的第 $j$ 个机场建点 $id_{i,j}$。$S$ 向 $id_{0,j}$ 连边权为 $s_j$。$id_{i-1,j}$ 向 $id_{i,j-1}$ 连…

[CF2135E](https://www.luogu.com.cn/problem/CF2135E2) ### 思路 令 $0$ 为 $-1$，$1$ 为 $1$，求前缀和。$f(s)$ 一定是前缀是 $0$，后缀是 $1$，并且 $f(s)$ 前面有 $|\min s_i|$ 个 $0$。因为 $rev(s)$ 的…

[P11893](https://www.luogu.com.cn/problem/P11893) ### 思路 枚举 $0/1$ 和 $3/4$ 分别几个， $0/1$ 不能放在开头，还要留至少一个 $2$。 $$ans=\sum_{i=2}^{n-3}\binom{n-1}{i}(i-1)(\sum_{j=2}^{…

[abc363g](https://www.luogu.com.cn/problem/AT_abc363_g) ### 思路 如果没有修改，可以费用流：建一排点表示每天的选择，$S$ 向 $d_i$ 天连流量 $1$ 费用 $p_i$；$i$ 天向 $i-1$ 天连流量 $+\infty$ 费用 $0$；$i$ 天向…

[P13574](https://www.luogu.com.cn/problem/P13574) ### 思路 最后的情况形如 $s_i=L$ 且 $s_{i+1}=R$。设 $[1,i-1]$ 的子弹不到达 $i$ 的概率为 $f_i$， $[i+1,n]$ 的子弹不到达 $i$ 的概率为 $g_i$，则 $ans…

[P11224](https://www.luogu.com.cn/problem/P11224) > 如果您觉得这个任务在比赛中很难，那是因为它确实很难。事实上，这个任务的创意最初是作为2017/2018赛季HONI比赛的提案提出的。这个任务的唯一问题是作者自己也无法解决它。然而，一些比作者更聪明的人也尝试解决这个任…

[P13045](https://www.luogu.com.cn/problem/P13045) ### 思路 也是很唐的题。跟 Ad-hoc 爆了。 先手确实很劣，但如果先手连 $(1,1)$ 不就变成后手了吗！ 模仿人机操作。如果它连 $(i,j)$，那你就连 $(j,i)$，多得一分；否则它连 $(i,i)$，…

[P12427](https://www.luogu.com.cn/problem/P12427) ### 思路 对原来的边建点。若 $i$ 边能接到 $j$ 边，连边 $i\to j$。$m^2$ 条边，$O(m^2)$ dfs 找环。需要减少边数。 对原来的点建虚点。连边 $i\to y_i$，$x_i\to i$…

[arc196c](https://www.luogu.com.cn/problem/AT_arc196_c) ### 思路 容斥。 钦定有 $k$ 个分解线，$k+1$ 段中后面的不能连向前面的，每段中可能还有更小的段，系数为 $(-1)^k$。 规定一个段以白点结尾。可以合法的前缀中每个黑点都要被前缀中的白点匹配，…

[P13042](https://www.luogu.com.cn/problem/P13042) ### 思路 博弈是在线段树上，按照深度，$g_{nd}=\max(g_{ls},g_{rs})$ 或 $g_{nd}=\min(g_{ls},g_{rs})$。 转 $0/1$。枚举 $v\in[1,m]$，设 $f_…

[P13028](https://www.luogu.com.cn/problem/P13028) ### 思路 唯一能决定你在一道题的回答的只有其他 $n$ 个人在该题答案是否相同。 #### $n=1$ 如果得分大于一半，就回答相同的答案；否则回答相反的答案。 #### $n=2$ 设有 $num$ 个问题两人答案…

[P12996](https://www.luogu.com.cn/problem/P12996) ### 思路 不会载球跨过原点，数轴两边分开考虑。按距离排序。 $O(n^2)$ 可以设 $dp_{i,j}$ 表示 $0$ 型已经取掉了前 $i$ 个，$1$ 型取掉了前 $j$ 个。两个相交的同类型匹配不优，可以规定…

[P12730](https://www.luogu.com.cn/problem/P12730) ### 思路 物品 $i$、$j$ 能同时选要求 $dis(p_i,p_j)\ge d_i+d_j+1$。设 $dp_u$ 表示所选物品只覆盖到 $u$ 子树内的最大价值。将物品挂在 $p$ 的 $d$ 级祖先上。若没有…

线性！ ### 思路 记前缀和 $sum_i$ 表示 $i$ 及之前左括号减右括号的数量。判断 $[l,r]$ 是合法的括号序列，等价于 $sum_{l-1}=sum_r$ 且 $\min_{i=l}^r sum_i\ge sum_{l-1}$。 枚举答案在 $A$ 上的左端点 $l$，计算 $A$ 从 $l$ 开始的…

[P6846](https://www.luogu.com.cn/problem/P6846) ### 思路 对于一个 DAG，把所有边反向后也是 DAG。即 $x$ 步做出一个 DAG，就可以 $m-x$ 步做出对应的另一个。所以答案为 DAG 数乘 $\frac{m}{2}$。 状压 $dp_S$ 表示 $S$ 的…

[P9165](https://www.luogu.com.cn/problem/P9165) ### 思路 限制 $len\le 750$。 如果用 $x$ 位传一个数，即在 $[i\times x,(i+1)\times x)$ 位全填 $val$。可以认为被随机打乱的数两两都不会相同，那只要一个数出现 $\ge…