House_of_Fan

P15352 [COCI 2025/2026 #4] 魔术 / Magija 思路 倍增并查集，以下描述忽略反阿克曼函数 $\alpha(n)$。 首先考虑直接 $O(nq)$ 的维护，显然简单，用并查集维护哪些点可以相互到达，合并时压缩路径并统计答案，数据比较水所以甚至有 $73$ 分。 ▶ [73 pts Code] 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<bits/stdc++.h>#define fir first#define sec second //#define int long long#define pii pair<int,int>#defin...

CF2225D Exceptional Segments 题解 思路 定义 $f(i)=1\oplus 2\oplus\dots\oplus i$，有经典结论： $$ f(i)= \begin{cases} i &\text{if } i\bmod 4=0\ 1 &\text{if } i\bmod 4=1\ i+1 &\text{if } i\bmod 4=2\ 0 &\text{if } i\bmod 4=3 \end{cases} $$ 证明可以通过数学归纳或观察二进制规律得到。 那么区间 $[l,r]$ 的异或和可以写成： $$ l\oplus (l+1)\oplus\dots\oplus r=f®\oplus f(l-1) $$ 因为 $f®=f(l-1)\oplus (l\oplus\dots\oplus r)$。 所以区间异或为 $0$ 等价于： $$ f®=f(l-1) $$ 令 $L=l-1$，$R=r$，则条件变为： $0\le L\le x-1$ $x\le R\le n$ $f(L)=f®$ 我们需要统计满足上述条件的 ...

P15301 [ROI 2012 Day 2] army 汗国军队 思路 首先直接做是不太好做的，因为要同时满足两个限制： 最长的 LIS 长度为 $k$； 给定的长度为 $k$ 的 $g$ 数组必须在序列里按顺序排列。 考虑拆分这两个问题。 首先忽略第二部分，考虑第一部分。 我们发现，从大到小地在数组任意位置插入所有数就可以构成所有排列。 那模拟这个插入的过程。 容易发现 LIS 数组的每个位置相比上一个位置最多增加 $1$，这是显然的，不然你每次都只加了一个数还能多更多不成。 那就考虑对整个 LIS 数组进行一个差分，这样每一位都是 $1$ 或是 $0$，整个数组可以用状压表示。 因为此时插入的数比已有的其它数都要大，所以它后面的数无法接在它自己后面使得 LIS 变长，而它一定可以接在它前面的任意数后面使得 LIS 变长 $1$。 插入的过程就相当于在插入的位置加上一个 $1$，然后删掉后面最近的一个 $1$（在本位多一，后面自然就要少一，但是原本的 $0$ 可以继承本位，所以不变），这一步可以通过位运算轻易地得出。 考虑一个 $f_{i,j}$，$i$ 表示要插入的数，...

CF2225B Alternating String 简化题意 给定一段 01 数组 $a$。 选择一段区间 $[l,r]$，将其翻转，可以将其取反，问能否实现一次操作后数组中每个 $a_i\ne a_{i-1}$。 思路 最后若能得到合法数组，有两种情况： $a_i=i \bmod 2$； $a_i=1-i\bmod 2$。 那么我们只需要将初始值全部取反，就可以使第二种与第一种处理方法相同。 而要翻转的区间端点一定是在原数组中不合法的点。 考虑若翻转多奇数个合法点，则可以通过取反操作使其与翻转不合法点等价。 而多翻转偶数个合法点本身就与翻转不合法点等价。 所以遍历一遍整个数组，记录最左和最右的不合法点 $l,r$。 然后若 $[l,r]$ 内存在两个相邻点相等，那我也没招了，不管对整个区间取几次反都不能成功，这种情况直接不成立，排除掉。 其他情况一定可以通过取反成立，不再赘述。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535...

CF2225C Red-Black Pairs 思路 只有两行，所以是简单 DP。 考虑只能通过竖着的一对或横着且左右端点相同的两对矩形组成最后的大矩形，否则会产生一个一格的缺口，一定填不满。 那么设 $f_i$ 表示要填第 $i$ 列时的最小代价，算出本次转移代价再向 $f_{i+1}$ 和 $f_{i+2}$ 转移即可。 最后取 $f_{n+1}$ 为答案（要填 $n+1$，已经填完 $n$）。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i&g...

P12675 「LAOI-8」Boundary 思路 首先考虑如何使得整个区间变为 $-10^9$，显然一定有一次修改左端点为 $1$，有一次修改右端点为 $n$，因为无法通过增加 $1$ 使得某个数变为一个极小值（当然不考虑上溢出）。 那么就得到了一种比较普通的方法，取 $1<l<r<n$，那么答案即为 $|a_1-a_l|+l+|a_n-a_r|+(n-r+1)+(r-l+1)$。 化简式子可得 $|a_1-a_l|+|a_n-a_r|+n+2$，可以发现与 $l,r$ 的位置无关，只与 $a_1,a_l$ 与 $a_n,a_r$ 的大小有关。 考虑两个 DP 数组 $f,g$，$f_i$ 表示 $x\in(1,i],\min |a_1-a_x|$，$g_i$ 表示 $x\in[i,n),\min |a_n-a_x|$，这两个数组也是好做的，代码大概是： 123f[1]=inf;g[n]=inf;rep(i,2,n)f[i]=min(f[i-1],abs(a[1]-a[i]));per(i,n-1,1)g[i]=min(g[i+1],abs(a[n]-a[i...

P15093 [UOI 2025 II Stage] Odd Rows 思路 首先考虑求答案的 subtask。 我们考虑维护四个值：$jmx,jmi,omx,omi$ 分别表示奇数和偶数的最大最小可能取到的值，$cnt$ 表示本次要填入多少个 $1$，发现 $jmx+omi=n,jmi+omx=n$，所以更新时只需要更新两个最大值。 对于 $jmx$ 有三种情况： $omi\ge cnt$：此时一定是将所有 $cnt$ 个 $1$ 都放在原先是偶数的位置最多，即更新为 $jmx+cnt$ 个。 $omx\le cnt$：此时无论怎么选，都一定会有一部分奇数被转为偶数，而所有偶数都被转为奇数，所以新的奇数最大值就是总数减去被转换的奇数数量，要使得这个东西最大，只需使得被转换的奇数最少，即偶数最多，取 $omx$，更新为 $omx+jmi-(cnt-omx)$。 $omi\le cnt\le omx$：这是最重要的一种情况，同时需要用到本题的关键结论：一种数一定可以取到上下界之间所有与上界（下界）奇偶性相同的所有数，也就是 $o\in [omi,omx],o\equiv omi(...

P15939 [JOI Final 2026] 传奇团子吃家 题解 思路 考虑前缀和 $P_i$ 表示前 $i$ 段甜减辣的净甜度。则对于固定的左端点，贪心策略为：每口都恰好吃到净甜度增加量 $\ge K$ 的最早位置。这等价于在模 $K$ 意义下推进状态。 我们离线处理询问，按右端点扫描。维护一棵模 $K$ 的权值线段树，存储每个余数状态对应的答案，并利用并查集合并等价状态。遇到奇数段（甜）时执行区间加操作；遇到偶数段（辣）时执行区间合并与删除。 动态开点线段树维护区间加法与单点查询，下标域 $[0, K-1]$。 用 set 维护当前仍有效的模余数集合。 带权并查集维护状态间的差值关系。 扫描 $i$： 若 $i$ 为奇数，计算甜团子带来的增量，执行线段树区间加，并尝试与已有代表合并。 若 $i$ 为偶数，将受辣团子影响的一段余数全部合并到新余数上，并从集合中删除旧余数。 回答所有右端点为 $i$ 的询问。 时间复杂度 $O((N+Q)\log K)$，空间 $O(N\log K)$，可以通过本题。 代码 ...

CF2220B OIE Excursion 思路 首先每个时间点都可以在原地停留，向左或向右。 先考虑 $m=2$ 的情况。 对于 $i$ 号位置，若可以到达，则可能可以通过一些调整使其在除 $a_i$ 之外的其他时间到达。 考虑什么时候做不到调整，即 $a_i=a_{i+1}$ 时，不论怎样通过这一段都需要至少 $3$ 秒的空档期，无法通过。 那么对这个东西进行推广，若有 $i\in[l,r]$，所有 $a_i$ 相等，则至少要 $(r-l+1)+1$ 的时间才可以通过，而我们拥有 $m$ 秒的时间，进行比大小即可。 所以线性地扫描一遍，判断每段连续的区间长度加一与 $m$ 的大小关系即可。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<bits/stdc++.h>#define fir first#define sec second #define int long ...

P16308 [ICPC 2023 Jinan R] 很多很多头 思路 首先题目中提到两种括号的朝向可以任意，所以实际上同种类型的括号等价。 然后考虑合法（唯一）且仅存在 [A] 这种结构的括号序列（将其称为“简单括号序列”）长啥样。 发现一定是 [([(A)])] 状物或是 ([(A)]) 状物。 也就是两种括号必须交替出现。 若有一段出现了 [[A]]，则可以被替换为 []A[]，圆角括号也是一样，此时不是唯一构造。 然后考虑 AB 结构。 若 A 与 B 的最外层是同一种，如 [A][B]，则可以替换为 [A[]B]，此时也不是唯一构造。 而如果存在三段及以上的“简单括号序列”，则根据抽屉原理一定存在两段的最外层相同，不是唯一构造。 所以得出结论：只能存在形如 [A] 的子结构，且最多有两个字结构，最外层还必须不同。 那么一个合法的序列就是 [A](B) 这样，转化一下变成 [A[(B(，然后 A 内部两种交替出现，B 内部两种交替出现，只有 A 和 B 最内层会出现连续且类型相同的括号，所以只需统计有多少组连续相同的括号，判断是否少于两种即可。 代码 1234567891...