[collapse status="false" title="感想"]ARC D 都不会了，水平再创新低！希望早日恢复水平。。[/collapse]题意有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。$n,m \leq 2500$。题解比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题，就是一个边可以指定它连接的一个点，将这个点和其相邻的边删去。考虑一个联通块怎么做：一定可以找出一个联通块的生成树，然后我们自底向上每次删去叶子就好了。我们发现这样我们最后只会删不了根。也就是说，我们要决策根是一个行优还是一个列优。暴力的做法是都做一遍取最大值，但是我们其实可以考虑一下，如果一个行/列作为根会损失多少：如果全选行为根，损失的就是这一行上没有红色的列的个数；列同理。所以我们统计没有红色的行的个数 $r_1$，和没有红色的列的个数 $r_2$。如果 $r_1 < r_2$，说明选列为根的代价小，就每次选择一个列开始 bfs 就可以。否则就选行。bfs 的过程就是，我们将每个边（也就是对应原图中的一个红色位置）对应到操作它的叶子代表的行/列。最后加入答案的时候要倒着加即可。总结：遇到行列问题还是要多思考二分图。代码#include <bits/stdc++.h> #define fi first #define se second #define DB double #define U unsigned #define P std::pair #define LL long long #define LD long double #define pb emplace_back #define MP std::make_pair #define SZ(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2500 + 5; std::vector<int> G[MAXN<<1]; int n,m; char str[MAXN][MAXN]; int pre[MAXN<<1]; bool vis[MAXN<<1]; int main(){ scanf("%d%d",&n,&m); FOR(i,1,n) scanf("%s",str[i]+1); FOR(i,1,n) FOR(j,1,m) if(str[i][j] == 'R') G[i].pb(n+j),G[n+j].pb(i); int r1 = 0,r2 = 0; // r1: 空行的个数 = 废弃一个列的个数 // r2: 空列的个数 = 废弃一个行的个数 FOR(i,1,n){ int c = 0; FOR(j,1,m) c += (str[i][j] == 'R'); if(!c) ++r1; } FOR(i,1,m){ int c = 0; FOR(j,1,n) c += (str[j][i] == 'R'); if(!c) ++r2; } std::vector<int> ans; auto bfs = [&](int s){ if(vis[s]) return; std::vector<int> tmp; std::queue<int> q;q.push(s);vis[s] = 1; while(!q.empty()){ int v = q.front();q.pop(); for(auto x:G[v]){ if(!vis[x]){ tmp.pb(x);pre[x] = v; q.push(x);vis[x] = 1; } } } std::reverse(all(tmp)); for(auto x:tmp) ans.pb(x); }; if(r1 < r2) FOR(i,n+1,n+m) bfs(i); else FOR(i,1,n) bfs(i); printf("%d\n",SZ(ans)); for(auto x:ans){ if(x <= n){ printf("X %d %d\n",x,pre[x]-n); } else{ printf("Y %d %d\n",pre[x],x-n); } } return 0; }
由于是恢复训练，所以会把所有题目解法都写写。A显然是少的每一堆就放一个，大的尽量均摊，设 $r < b$，那么就是判断 $\lceil \frac{b}{r} \rceil -1\leq d$。B模拟一下发现这东西无论什么路径权值都是 $nm-1$。证明可以考虑对 $n+m$ 归纳：首先 $n=m=1$ 是对的，考虑到达 $(n,m)$ 最后一步是怎么走的，如果是从 $(n-1,m)$ 走过来，代价是 $(n-1)m-1 + m = nm-1$；如果从 $(n,m-1)$ 走过来，代价是 $n(m-1)-1 + n = nm-1$。所以判断是否 $k=nm-1$ 即可。C对于每个大学计算他的贡献，设这个大学有 $m$ 个人，发现 $k$ 确定后我们只会取前 $\lfloor \frac{m}{k} \rfloor k$ 大，所以从大到小排序处理前缀和然后对于每个大学暴力枚举 $k$ 计算贡献就好了。D直接暴力。重点是预处理 $f_{l,r}$ 表示 $a[l,r]$ 反转后和 $b[l,r]$ 不反转点乘的值，直接区间 dp。E考虑这实际上是个匹配问题：每个点有两个值 $v_1,v_2$，两个点能匹配当且仅当他们的值有交集。根据之前惨痛的教训：看到两个值问题考虑将两个值之间连边。那么问题其实就是对边之间做一些匹配，一对边能匹配当且仅当它们在同一个点上相连。设边的个数为 $m$，对于一个联通块，答案的一个界是 $\lfloor \frac{m}{2}\rfloor$ ，事实证明我们永远可以达到这个界。先考虑树怎么做：我们发现如果一个子树内有没有匹配上的边，它一定可以移动到根往上的边，所以我们就可以归纳证明了：每次先递归做子树，然后把子树剩下的边在这个点匹配。如果是图的话，就是多了一些返祖边，直接把返祖边挂在深度比较低的点上也可以类似归纳。F这个题比较神仙。不过如果能把限制写出来观察一下应该也会做。先考虑如何判断 Bob 是否能获胜：发现这其实就是一个 Bob 选箱子，然后花费是和这些箱子有关联的锁。所以锁和箱子连边，我们可以枚举箱子的集合 $S \subseteq [n]$，Bob 不可以获胜，当且仅当对于所有集合 $S$，都有：$$ \sum_{i \in S} a_i \leq \sum_{i \in \Gamma(S)} b_i $$其中 $\Gamma(S)$ 表示 $S$ 的子集。发现这个非常想 Hall 定理！！1，所以我们考虑拆点，第 $i$ 个盒子拆出 $a_i$ 个点，第 $j$ 个锁拆出 $b_j$ 个点，那么这个条件等价于原图有包含左边所有点的完美匹配。现在问题就是说，如果盒子 $i$ 的某个点与箱子 $j$ 的某个点有连边，那么就会有代价 $c_{i,j}$，要求求完美匹配的代价，那么就可以 dp 了。dp 一开始一个 naive 的想法是记录右边的每个点有没有被选，这样状态是 $O(2^{nb})$ 的，无法通过。但是我们发现同一个锁拆出来的点本质上是一样的，所以我们只需要记录每个锁拆出来的点还剩几个，状态数就是 $O(b^n)$ 了。转移的时候枚举 $a$ 拆出的点每个匹配的谁，总复杂度大概是 $O(n 5^n \binom{n+3}{3})$ 之类的东西？反正可以快速通过。
A先将其压成二进制数，考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数，也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下，发现两个数不同，当且仅当一个是 $1$ 一个是 $0$，我们只考虑这些不同的位置，发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ 和偶数个 $1$ 的数量，乘起来就好了。B$C_{i,j} = A_i + B_j$。我们考虑第 $i$ 行，就是 $B$ 序列整体加上了一个 $A_i$，于是差分一下就可以算出 $B$ 序列的差分序列。考虑列也可以算出 $A$ 序列的差分序列。首先如果通过不同的行/列算出的差分序列不同一定是无解的。现在关键在于决定 $A_1,B_1$ 是啥，知道这个之后就可以推出来了。首先我们有 $A_1+B_1 = C_{1,1}$，然后由于这个题要求非负整数，根据差分数组的前缀和的最小值，我们还有两个限制 $A_1 \geq l_1,B_1 \geq l_2$。随便找出一组可行解那么它一定满足限制。C我们考虑估一个答案的下界：$\lfloor \log_2 n \rfloor$。因为所有形如 $2^x$ 的数字组成了一个团。那么我们考虑如何构造能让如果 $x|y$，那么 $a_x \neq a_y$：可以想到如果 $x$ 整除 $y$，那么 $x$ 唯一分解后 $\sum e_i$ 一定是小于 $y$ 的，所以我们构造这个序列即可。注意特判 $1$，所以其实整体都是要加一的，那个下界也应该是 $\lfloor \log_2 n \rfloor + 1$。另一种做法：考虑将 $n$ 的因数分解为若干组，每一组满足两两都是除数/被除数的关系。每一组都是一个团，所以我们只需要找到这些团的最大值然后加一就好了。简化一下：也就是找到所有因数的答案的最大值加一就好了。D欧拉回路有一个经典的结论：求出一个 dfs 树后等价于 dfs 树上若干个树环（只包含一个非树边）的异或。但是这个题需要求有 $k$ 个奇点的数量怎么办？我们求欧拉回路的时候如果有奇点一般的处理方法都是建立一个新点，连所有奇点。由于奇点一定有偶数个，所以连完之后一定变成一个欧拉图。我们考虑用类似的方法计数：首先肯定要分联通块考虑，设一个 $n$ 个点 $m$ 条边的联通块，选出恰好 $k$ 个奇度点（$k$ 是偶数）的方案是：首先我们要选出这 $k$ 个点向新点连边，这一部分方案是 $\binom{n}{k}$；然后我们要选一些新图上的树环，但是注意：由于我们钦定了奇度点，所以我们必须选择连接之后新产生的环，而原先的环的数量显然是 $m-n+1$。所以答案就是 $\binom n k 2^{m-n+1}$。多个联通块卷起来就好了。复杂度 $O(n^2)$。可以用分治+NTT之类技巧优化到 $O(n \log^2 n)$ 但是没必要。E考虑容斥。我们枚举把它划分成 $t$ 个段，每段内都要相同，那么每段内可以取的数字就是从 $1$ 到这一段的最小值，对答案的贡献是 $(-1)^{n-t}$。我们可以把 $(-1)^{n-t}$ 看成 $(-1)^n \times (-1)^t$，然后 dp：设 $f_i$ 表示当前划分了前 $i$ 个数，并且 $i$ 是最后一段的结尾的答案。转移枚举这一段的开头是啥：$$ f_i = -\sum_{j=1}^i f_{j-1} \times \min(a_{j},a_{j+1},\ldots,a_{i}) $$这样直接做是 $O(n^2)$ 的。考虑优化：这个 min 让我们想到用单调栈维护。我们维护一个递增的单调栈 $b_1,b_2,\ldots,b_m$，这里的 $b_i$ 表示在原序列的位置。不难发现在 $[b_i,b_{i+1})$ 的 $j$，都满足 $\min(a_j,a_{j+1},\ldots,a_i)$ 是 $a_{b_i}$。所以我们对于栈内的位置 $i$，维护一下 $sm_i = \sum_{k=b_i}^{b_{i+1}-1} f_{k-1}$，再维护一个整体的和 $now = \sum_{i=1}^m b_ism_i$ 即可。弹栈的时候相当于合并区间，更新一下即可。复杂度 $O(n)$。F比较神仙。。。考虑一个最显然的暴力：将第 $i$ 个点当前在哪里看成一个 $k$ 元组，每个这样的 $k$ 元组看成一个新图点，权值是所有点的和；新图中的两个点有连边当且仅当它们可以一步到达。问从 $S$ 到 $T$ 的最小瓶颈路。看到最大值最小我们会去思考二分：设二分了一个上界 $L$，我们现在只需要保留所有权值 $\leq L$ 的状态，检查 $S,T$ 是否连通即可。由于状态之间的边都是无向边，所以我们考虑转而能否让它们都走到一个确定的状态：不妨让它们都走到能到达的状态的最小值，然后判断是否是同一个点即可。如果和相同就按照编号手动标号。那么我们跳出二分看一下这个过程：相当于是有 $k$ 个球位置集合为 $\{s_i\}$ 和另外 $k$ 个球 $\{t_i\}$，每次你可以选择一个点走到一个 $h_i$ 比它小的点，走到它们完全相同位置。我们对于原图每个点预处理出所有 $h_i$ 比它小的点中代价最少的（就是路径上最大值最小的），然后每次将一个球移动到它所在的点预处理出的位置，更新一下答案。贪心选最小贡献，一直走到相同为止。走过的路径就是答案。因为这个在二分的基础上每次保证了扩大了尽量小的上界，所以这个东西求出的方案和原问题是等价的。复杂度 $O(n^2 \log n)$。
A如果 $x > k$ 那么可以随便选。$[1,k]$ 我们选择后一半，这样保证任意两个数字相加都 $> k$ 就好了。B直接枚举即可。$0,1,8$ 反转后不变，$2,5$ 反转后互换。C$\geq s$ 最小，也就是尽量靠近 $s$。于是从大到小枚举相同的前缀长度，每次暴力看一下是否有一种方案可行，如果有的话就直接贪心按照字典序放置剩下的字符。D我赛时的做法：对于 $\leq \sqrt n$ 的素数，可以直接暴力处理询问。问题就变成了单点加，求全局最小值。我们倒过来做，就变成了单点减，求全局最小值。每次更新一下就好了。这一部分复杂度是 $O(98(n+q))$ 的对于 $> \sqrt n$ 的素数，每次询问最多只会增加一个这样的素数的出现次数，所以我们可以统计一下每个素数的出现次数，如果 $\geq n$，我们把包含它的所有询问提出来，做上面的做法。由于每处理一个这样的素数，首先询问的和肯定是 $q$，所以还是 $O(q)$ 的；然后每次会花 $O(n)$ 的代价让这个素数的出现次数减掉 $n$，也就是均摊 $O(1)$ 的。总复杂度 $O(98(n+q))$。一个非常简单的做法：直接分解质因数，然后对每个质数维护 multiset 就完了。。需要额外记录一下这个质数是否每个位置都 $\geq 1$，这样 multiset 只需要存 $\geq 1$ 的数，复杂度就是 $O(n \log^2 n)$ 了。E要注意到一个非常好的性质这个题就简单了。。如果两个数字的最高位不同，答案一定是全 $1$。因为我们可以选择区间 $[0111\ldots,1000\ldots]$，就取得最大值了。否则考虑我们询问区间和变成询问两个前缀和的疑惑和，设 $s(n) = \text{Xor}_{i=0}^n i$，那么有以下规律：$$ s(n) = \begin{cases} n&n \equiv 0 \pmod 4\\ 1&n \equiv 1 \pmod 4\\ n+1&n \equiv 2 \pmod 4\\ 0&n \equiv 3 \pmod 4 \end{cases} $$发现答案至少可以取到 $r$。由于我们这里一定要取长度为奇数的区间，所以问题变成了我们从区间中选出两个奇偶性不同的数字 $x,y$，获得答案 $s(x) \text{ xor } s(y)$，那么容易发现答案最大是 $r+1$（也就是在 $r \equiv 0 \pmod 4$ 的时候有一个数 $r' \equiv 1 \bmod 4$；或者是 $r \equiv 2 \pmod 4$ 的时候有一个数 $r' \equiv 0 \pmod 4$；其他的答案都会是 $0$。这样就 $O(n)$ 完成了。要注意我们找的 $r'$ 是左端点减一的答案。F首先行列独立分开做。这个循环节看起来就和阶一样，考虑分解质因数后用求阶的方法求答案（每次试除一个质数一直到不合法位置），那么就是快速判断 $(d,n)$ 表示前 $n$ 个数中 $d$ 是否是循环节了。先把这 $n$ 个数分成 $\frac{n}{d}$ 个长度为 $d$ 的块，问题就变成了 $(1,\frac{d}{n})$。注意到题目有个很诡异的限制是「询问区间不能重复」，那么肯定先考虑重复怎么做：发现只需要询问 $(1,n-1)$ 和 $(2,n)$ 是否相同就好了。如果不能重复，但是我们可以通过让两个重复的区间同时询问第三者来看看是不是相同。如果 $n=2$，直接询问 $(1,1),(2,2)$ 是否相同；否则这之后 $n$ 是个奇数，设 $t=\lfloor \frac{n}{2}\rfloor$，先询问 $(1,t),(t+1,n-1)$，再询问 $(1,t),(t+2,n)$，如果都相同就可以推出 $(t+1,n)$ 相同，进而退出 $(1,t),(t+1,n)$ 相同，那么全都相同。算一下操作次数：首先注意到如果有 $2$ 这个质因子，每次只需要花费 $1$ 的代价就可以除二，所以最坏情况应该是形如 $3^x$，也就是操作次数为 $2\log_3(nm)$，然后算一下发现并没有超过上界。
A暴力枚举每个字母对应的括号即可。$O(2^3 n)$CodeB发现行列之间的影响只会在于四个角上，所以暴力枚举四个角是否填，然后确定上下界判断即可。$O(2^4)$。CodeC显然 $a_i,b_i > 0$ 和 $a_i,b_i < 0$ 可以分开做：我们只考虑 $a_i,b_i > 0$ 的情况。排序之后，我们枚举「推」到的最后一个位置是 $b_x$，那么我们找到 $\leq b_x$ 的 $a$ 数量，设为 $y$，我们相当于就是占据了 $[b_x-y+1,b_x]$ 的所有格子，和 $(b_x,\infty)$ 的所有已经在目标位置上的格子。前者直接二分就可以找到 $y$ 和那个区间里有几个目标格子，后者处理一个后缀和表示 $ \geq b_i$ 的位置有几个是不用动就放好的就行了。$O(n \log n)$CodeD由于要求每个人至少有两个下属，并且要求值是严格下降的，所以我们考虑从高到低去递归构造。由于题目保证有解，设我们现在正在构造 $S$ 内的点构成的树。如果不是要求父亲严格比儿子大，我们随便找出一对 $u,v \in S$，满足 $a_{u,v}$ 是当前能取到的最大值，将剩下的点 $x$ 分为三类：$a_{u,x}<mx,a_{v,x}=mx$$a_{u,x} = a_{v,x} = mx$$a_{u,x}=mx,a_{v,x}<mx$新建一个点 $r$，令 $val_r = a_{u,v}$，那么一类点一定要放在左儿子，三类点一定要放在右儿子，二类点随便安排就好了。但是要注意：如果二类点的个数 $\geq 3$，按照上面的构造方法我们会在下面也加入一个 $val_r$，所以这样不满足严格了。我们对于两个点 $(u,v)$，如果 $a_{u,v}=mx$，就连边 $u,v$。然后我们随便找出一个极大团，剩下的点 $x$ 一定和极大团中至少一个点 $y$ 满足 $a_{x,y}<mx$。那么就把它分配到 $y$ 对应的子树内就好了。同理，我们不可能出现和 $\geq 2$ 个最大团里的点 $y$ 满足 $a_{x,y}<mx$ 的情况。时间复杂度为 $O(n^3)$。可能可以优化。CodeE遇到判定回文串的问题，我们可以考虑按照长度进行奇偶分类，然后不断去每次删掉开头结尾，去寻找剩下的最短串是否可以构造出来。将 $k$ 分类讨论：$k$ 是奇数如果存在一个长度为 $k$ 的路径，那么每次我们可以删去开头和结尾，仍然是满足条件的。最后可以得到一个长度为 $3$ 的路径，大概是也就是，只要有一对点之间有双向边，就一定能构造出 $k \geq 3$，$k$ 是奇数的所有路径。可以发现这个条件和存在一条长度为 $k$ 的路径是等价的。（因为两个方向上面我们都推过了）$k$ 是偶数类似上面的思想，我们最后会缩成以下情况：也就是说只要有一对点之间有双向边并且字母相同，我们就可以构造出 $k \geq 2$，$k$ 是偶数的所有路径。也是等价的。具体维护的时候，更改某条边就看看有没有反方向的边，算算影响就好了～CodeF不难发现如果奇点数量 $\leq 2$ 的话直接找出一个欧拉路径就做完了。我们考虑什么时候我们应该切换模式，也就是考虑切换模式后的状态能清空哪些图：首先有环肯定不行（这里指的长度 $\geq 3$ 的环），因为环走一遍之后会消去一半的边，就继续走不下去了。一条 $\geq 4$ 长度的链也不行，这个手动模拟一下也能看出来。所以我们只能做：直径 $\leq 3$ 的树，发现这好像就是菊花图！！1于是我们考虑先找出一个路径，使得剩下没被经过的边恰好构成一个菊花图，并且中心是这个路径的终点。赛时有一个 naive 的想法：直接令中心为连接所有奇点的点，然后去做。发现 WA on test 19 然后比赛结束了。。。赛后想到了一种特殊情况是，删掉这个菊花图后还有两个奇点，所以我找的中心改成连接奇点的数量 $\leq odd-2$，如果只有 $odd-2$ 个考虑找一条欧拉路径并且终点是中心。然后 WA on test 38。。。。并且比赛的时候只会测前 $37$ 个点，所以一堆人 fst 了。test 38 是一个很小的数据，大概长这样：我们就会选择 $1$ 点作为中心，然后把边 $1 \to (2,3,4,5)$ 全都删了，就无法到达 $1$ 了。会判断为无解。这种问题只会和菊花图的某一个叶子有关，也就是说这个图不能长这样，否则无解（不会证，）：那么我们就枚举中心，找到所有叶子。先看看有没有直接到达中心的欧拉路径，如果没有的话，枚举某个叶子不删除然后接着找就行了。复杂度 $O(nm)$ 。由于现在 open hacking 还没有结束，随时可能被 hack。代码
A把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 200+5; char str[MAXN]; int cnt[26],n; int main(){ int T;scanf("%d",&T); while(T--){ CLR(cnt,0);scanf("%d",&n); scanf("%s",str+1); FOR(i,1,n) ++cnt[str[i]-'a']; FOR(i,1,cnt[1]) putchar('b'); FOR(i,0,25){ if(i == 1) continue; FOR(j,1,cnt[i]) putchar('a'+i); } puts(""); } return 0; }B我们证明答案一定 $\leq 1$：假设答案 $\geq 2$，考虑最后一步和倒数第二步，倒数第二步会把最后一步操作的点直接拉过来，所以最后一步的操作是无效的，可以删去。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 100+5; int n,x[MAXN],y[MAXN],k; inline void Solve(){ scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d%d",x+i,y+i); FOR(i,1,n){ int mx = 0; FOR(j,1,n) mx = std::max(mx,std::abs(x[i]-x[j])+std::abs(y[i]-y[j])); if(mx <= k){ puts("1"); return; } } puts("-1"); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }C1感觉比较难。。发现三个相邻的点 $i+j \bmod 3$ 两两不同，于是按照 $i+j \bmod 3$ 分类，找一个最小的将其全部翻转即可。C2会了 C1 稍微想想就会了。我们现在把 X 分成三类 $x_0,x_1,x_2$，把 O 分成三类 $o_1,o_2,o_3$，显然我们只需要选一对 $p \neq q$，将 $x_p$ 全都变为 O，并且将 $x_q$ 全都变为 X，可以得到这样是 $\leq \frac{1}{3}$ 的。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 300+5; char str[MAXN][MAXN];int n; int mp[MAXN][MAXN]; int cnt[2][3],ps[2]; inline void Solve(){ scanf("%d",&n);CLR(cnt,0); FOR(i,1,n){ scanf("%s",str[i]+1); FOR(j,1,n){ if(str[i][j] != '.') ++cnt[str[i][j]=='X'][(i+j)%3]; } } ps[0] = ps[1] = -1; int mn = 1e9; FOR(i,0,2){ FOR(j,0,2){ if(i == j) continue; if(mn > cnt[0][i]+cnt[1][j]){ mn = cnt[0][i] + cnt[1][j]; ps[0] = i;ps[1] = j; } } } FOR(i,1,n){ FOR(j,1,n){ if(str[i][j] == '.') putchar(str[i][j]); else{ if(str[i][j] == 'O') putchar((i+j)%3 == ps[0] ? 'X' : 'O'); else putchar((i+j)%3 == ps[1] ? 'O' : 'X'); } } puts(""); } } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }D特判 $k=1$ 和 $k=n$。考虑 $k \in [2,n-1]$ 的情况：首先最小值 $1$ 肯定要出现且仅出现一次，发现只需要出现一次的位置一定是边界，所以等价于要判断是否只有一个 $1$ 并且这个 $1$ 在边界上，然后删掉这个 $1$ 变成了一个子问题。我们就可以求出最长能凑出多少的排列了。感觉比 C 简单。。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; int n,a[MAXN]; bool vis[MAXN]; bool f[MAXN]; int cnt[MAXN]; inline void Solve(){ scanf("%d",&n);FOR(i,1,n) cnt[i] = 0; FOR(i,1,n) scanf("%d",a+i),vis[i] = 0,++cnt[a[i]]; FOR(i,1,n) vis[a[i]] = 1,f[i] = 0;f[0] = 1; int sm = 0; FOR(i,1,n) f[i] = f[i-1]&vis[i],sm += vis[i]; std::reverse(f+1,f+n+1); int l = 1,r = n,now = 1; while(l <= r){ if(a[l] != now && a[r] != now) break; --cnt[now]; if(cnt[now]) break; if(a[l] == now) ++l,++now; else if(a[r] == now) --r,++now; } --now; FOR(i,1,n-now-1) f[i] = 0; if(sm == n) f[1] = 1; if(vis[1]) f[n] = 1; FOR(i,1,n) putchar('0'+f[i]);puts(""); } int main(){ int T;scanf("%d",&T);while(T--) Solve(); return 0; }E其实是个差分约束题（首先相邻两个人一定奇偶性不同，所以如果不是二分图直接无解。考虑一条无向边 $(u,v)$，相当于有限制 $|a_u-a_v| = 1$，不妨先写成 $|a_u-a_v| \leq 1$；考虑一条有向边 $u \to v$，相当于有限制 $a_v-a_u=1$，也就是 $a_v-a_u \leq 1$ 和 $a_v-a_u \geq 1$。我们按照上面不等式建差分约束然后跑最短路，枚举一个起点，求出距离起点最远的距离，显然这个距离的最大值就是答案。首先答案一定不能超过这个值，所以我们只要构造出一组合法的解就好了。我们取能取到最大值的起点，将点 $i$ 的权值直接设为起点到 $i$ 的最短路就好了。因为这是一个二分图，所以无向边的情况不可能有 $a_u=a_v$（因为都是连的 $1$ 边，如果有这个情况说明一定不是二分图了）。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 200+5; int G[MAXN][MAXN],dis[MAXN][MAXN]; int n,m; bool flag=1; int col[MAXN]; bool vis[MAXN]; inline void dfs(int v){ vis[v] = 1; FOR(i,1,n){ if(G[v][i] == 1e8 || v == i) continue; if(vis[i]) flag &= (col[v]^col[i]); else col[i] = col[v]^1,dfs(i); } } int main(){ scanf("%d%d",&n,&m); FOR(i,1,n) FOR(j,1,n) G[i][j] = 1e8; FOR(i,1,n) G[i][i] = 0; while(m--){ int i,j,w;scanf("%d%d%d",&j,&i,&w); if(!w){ G[j][i] = std::min(G[j][i],1); G[i][j] = std::min(G[i][j],1); } else{ G[j][i] = std::min(G[j][i],1); G[i][j] = std::min(G[i][j],-1); } } dfs(1); if(!flag){ puts("NO"); return 0; } FOR(i,1,n) FOR(j,1,n) dis[i][j] = G[i][j]; int cir = 1e9; FOR(k,1,n){ FOR(i,1,k-1){ FOR(j,1,k-1){ if(i == j) continue; cir = std::min(cir,G[k][i]+G[j][k]+dis[i][j]); } } FOR(i,1,n){ FOR(j,1,n){ dis[i][j] = std::min(dis[i][j],dis[i][k]+dis[k][j]); } } } // FOR(i,1,n) FOR(j,1,n) if(G[i][j] != 1e9 && i != j) printf("%d %d %d\n",i,j,G[i][j]); if(cir < 0){ puts("NO"); return 0; } int mx = 0,ps = -1; FOR(i,1,n){ int c = -1e9; FOR(j,1,n) c = std::max(c,dis[i][j]); if(mx < c){ mx = c;ps = i; } } puts("YES"); printf("%d\n",mx); FOR(i,1,n) printf("%d%c",dis[ps][i]," \n"[i==n]); return 0; }F还是结论题，完全不会这个操作实际上就是将原排列分成尽量少的段，将这些段翻转和重排后要求相邻的值不能相同。那么我们先考虑如何判断对于一个分成了 $k+1$ 段的切割方案，是否存在一种操作方案，能重排后相邻值不相同。首先我们要保证每段内部不能有相邻相同的对，因为操作影响不到内部的点。设 $f(c)$ 表示颜色 $c$ 在端点上的出现次数，一个显然的限制是 $f(c) \leq k+2$，我们现在说明只要满足这个限制的所有切割方案都是合法的：考虑对 $k$ 归纳，如果 $k=0$ 时只有一段，命题显然成立；对于 $k \geq 1$ 的部分，考虑取最大值的 $f(x)$，找出一端是颜色 $x$ 的段，再随便找一个一端是颜色 $y(y \neq x)$ 的段，将 $x,y$ 对着拼在一起，现在相当于是一个 $k-1$ 的局面，我们发现 $f(x)-1 \leq k-1+2$，$f(z) \leq k-1 \leq k$（因为如果非最大值 $> k$ 那么和就超过 $k+2$ 了），所以这个局面是合法的，归纳得证。所以我们先将所有相邻相同的地方都分开，然后看下是否满足条件，如果满足条件直接输出 $k$，否则我们要多切出一些段来让其满足条件。设最大值为 $f(x)$，分类讨论一下发现每次切开的两边的颜色都不能是 $x$，切到满足条件为止就好了。如果全都切完了还不满足条件就无解。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int n,a[MAXN],f[MAXN]; inline void Solve(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i),f[i] = 0; int k = 0; ++f[a[1]];++f[a[n]]; FOR(i,2,n){ if(a[i] == a[i-1]){ ++k;++f[a[i]];++f[a[i-1]]; } } int mx = 0,ps = -1; FOR(i,1,n){ if(mx < f[i]-k-2){ mx = f[i]-k-2; ps = i; } } if(!mx){ printf("%d\n",k); return; } int r = 0; FOR(i,2,n) if(a[i] != a[i-1] && a[i] != ps && a[i-1] != ps) ++r; if(mx <= r){ printf("%d\n",k+mx); } else{ puts("-1"); } } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }G先咕了，等个谁写个中文题解 （H1先考虑如何求 $f(c)$：首先发现如果有相邻相同颜色的点可以都删掉，于是我们只需要考虑黑白交替的 $f(c)$ 答案是啥：不难发现是黑色点数量除二。所以我们可以用栈来搞这个东西：每次加入一个新球，如果栈顶和这个球颜色相同就一块弹出栈，否则弹出栈并让答案 $+1$。不妨考虑哪些黑色点对答案有贡献：我们如果假设第一个点是黑色点的话，第一个点有贡献当且仅当下一个黑色点也是奇数位置的点（说明有一个白色和它配对掉了），如果下一个黑色点是偶数位置的话说明它和上一个黑色点消去了，设奇数位置，偶数位置黑色点数量为 $B_1,B_2$，白色为 $W_1,W_2$，答案就是$\frac{1}{2}|B_1-B_2|$。如果枚举 $B_1,B_2$ 然后计数很麻烦，考虑 $B_2+W_2=\frac{n}{2}$，所以这个式子可以换成 $\frac{1}{2}|B_1-\frac{n}{2}+W_2|$，我们枚举 $i=B_1+W_2$，设空位置数量为 $p$ ，已经有的 $b_1+w_2=c$，方案数就是 $\binom p {i-c}$，所以答案就是：$$ \frac{1}{2^p}\sum_{i=0,i \equiv \frac{n}{2} \pmod 2}^n \binom p {i-c} |i-\frac{n}{2}| $$我们改为枚举 $i-c$，设 $d=c-\frac{n}{2}$式子化简为：$$ \frac{1}{2^p}\sum_{i=0,i \equiv d \pmod 2}^n \binom p i |i-d| $$#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; const int ha = 998244353; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } inline void add(int &x,int y){ x += y-ha;x += x>>31&ha; } int fac[MAXN],inv[MAXN]; inline void prework(){ fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha; inv[MAXN-1] = qpow(fac[MAXN-1]);ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha; } inline int C(int n,int m){ return (n < 0 || m < 0 || n < m) ? 0 : 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha; } char str[MAXN]; int n,m; int main(){ prework(); scanf("%d%d",&n,&m); scanf("%s",str+1); int B1=0,W2=0,p=0; FOR(i,1,n){ B1 += (str[i] == 'b' && (i&1)); W2 += (str[i] == 'w' && (!(i&1))); p += (str[i] == '?'); } int ans = 0; FOR(x,0,n){ int c = C(p,x),d = std::abs(x-(n/2)+B1+W2); if(d&1) continue; c = 1ll*c*d%ha; add(ans,c); } ans = 1ll*ans*qpow(qpow(2,p))%ha; printf("%d\n",ans); return 0; }H2首先要解决 $i \equiv d \pmod 2$ 的限制的问题，发现 $\binom n m = \binom {n-1}{m}+\binom{n-1}{m-1}$，所以我们将式子写开，就去掉了这个限制。现在我们考虑如何维护如下式子的值：$$ \begin{aligned} \sum_{i=0}^n \binom p i |i-d| = \sum_{i=0}^d \binom p i d-\sum_{i=0}^d \binom p i i+\sum_{i=d+1}^n \binom p i i - \sum_{i=d+1}^n \binom p i d \end{aligned} $$发现 $\binom n m m= \binom {n-1}{m-1}n$，区间求和可以拆成前缀和询问，所以我们相当于要快速维护$$ \sum_{i=0}^{lim} \binom p i $$我们发现 $lim$ 和 $i$ 的变化都是 $O(1)$ 的，所以我们只需要考虑 $lim,p$ 加减 $1$ 的变化即可。$lim$ 加一直接加上对应的项即可。$\binom {p+1}{i} = \binom p i + \binom p {i-1}$，所以 $p$ 加一只需要额外维护一下 $0\ldots lim-1$ 的求和即可。注意特判 $p=1$ 的边界。代码咕了。
题意要求构造大小为 $n$ 的排列，要求至少 $\lceil \frac{m}{2} \rceil$ 条限制：第 $i$ 条限制 $(a_i,b_i,c_i)$ 形如排列中 $b_i$ 的位置要在 $a_i$ 和 $c_i$ 之间。题解神仙题。这个题一般确定排列的方法都不能用了，我们考虑这个在两个数中间的限制：考虑用按照顺序每次将一个数放到前面或者后面的方式。因为保证有解，所以肯定能搞出来一个答案，也就肯定有一种放置顺序。我们假设我们知道了放置顺序，考虑如何去构造出答案，分类讨论一下：假设一个限制中第一个被放入的数是 $a_i$，那么如果下一个数是 $b_i$，就要和 $a_i$ 放在同侧，否则就要放在不同侧。所以我们加入一个点的时候，算出它放在左边和右边分别能满足多少限制，选择最大的那个即可。这样相当于将所有限制分成若干组，每一组至少取了一半，所以满足题目限制。现在问题在于如何找到这个放置顺序：发现如果在三元组内是 $b_i$ 先出现，那么怎么放置都不满足条件，所以我们要求出的序列形如要求 $a_i$ 或 $c_i$ 出现在 $b_i$ 之前，用类似拓扑排序的方法即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,m,a[MAXN],b[MAXN],c[MAXN]; std::vector<int> G[MAXN],lim[MAXN]; int deg[MAXN]; int dfn[MAXN],p[MAXN]; bool zt[MAXN];// left=0 right=1 bool vis[MAXN]; int main(){ #ifndef RainAir freopen("insider.in","r",stdin); freopen("insider.out","w",stdout); #endif scanf("%d%d",&n,&m); FOR(i,1,m){ scanf("%d%d%d",a+i,b+i,c+i); G[a[i]].pb(i); G[c[i]].pb(i); ++deg[b[i]]; } std::queue<int> q;int ts = 0; FOR(i,1,n) if(!deg[i]) q.push(i); while(!q.empty()){ int v = q.front();q.pop(); dfn[v] = ++ts; for(auto x:G[v]){ if(vis[x]) continue; vis[x] = 1; if(!--deg[b[x]]){ q.push(b[x]); } } } FOR(i,1,m) assert(!(dfn[b[i]] < dfn[a[i]] && dfn[b[i]] < dfn[c[i]])); FOR(i,1,n) p[dfn[i]] = i; FOR(i,1,m) if(dfn[a[i]] > dfn[c[i]]) std::swap(a[i],c[i]); FOR(i,1,m) lim[b[i]].pb(i),lim[c[i]].pb(i); FOR(i,1,n){ int cnt[2];CLR(cnt,0); int v = p[i]; for(auto x:lim[v]){ if(v == b[x]){ if(dfn[c[x]] < dfn[b[x]]) continue; cnt[zt[a[x]]]++; } if(v == c[x]){ if(dfn[b[x]] < dfn[c[x]]) continue; cnt[zt[a[x]]^1]++; } } zt[v] = cnt[0] > cnt[1] ? 0 : 1; } std::vector<int> v1,v2; FOR(i,1,n){ if(zt[p[i]]) v2.pb(p[i]); else v1.pb(p[i]); } std::reverse(all(v2)); for(auto x:v1) printf("%d ",x); for(auto x:v2) printf("%d ",x); puts(""); return 0; }
A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果是 $0$ 说明一定是 $i$ 跳到自己，如果多了 $2$ 说明 $i$ 往后跳，少了 $2$ 是往前跳。所以我们可以得出每个点往哪里跳，然后用类似括号序列的方式配对就行了：遇到往右的加入栈，往左的就随便取出一个。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,a[MAXN]; int ans[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n-1) scanf("%d",a+i); bool flag = 1; FOR(i,1,n){ flag &= !(a[i]&1); flag &= (std::abs(a[i]-a[i-1]) == 2 || a[i] == a[i-1]); } if(!flag){ puts("No"); return 0; } std::vector<int> S; FOR(i,1,n){ if(a[i] == a[i-1]+2){// 左括号 S.pb(i); } else if(a[i] == a[i-1]){ ans[i] = i; } else{ // 右括号 if(S.empty()){ puts("No"); return 0; } ans[S.back()] = i; ans[i] = S.back(); S.pop_back(); } } if(!S.empty()){ puts("No"); return 0; } puts("Yes"); FOR(i,1,n) printf("%d%c",ans[i]," \n"[i==n]); return 0; } /* 1. a[i] 都是偶数 并且正好一半往左一半往右 2. 考虑 a[i] 和 a[i+1]:如果中间不动 a[i]==a[i+1],如果中间往右 a[i+1] = a[i]+2,如果中间往左 a[i+1] = a[i]-2 往右必然要有一个往左 所以遇到往右的可以看成左括号 往左的可以看成右括号 就行了 */B. 树先把颜色相同的缩成一个树，感性理解操作肯定是每次操作同一个联通块，让他的影响不断增大。我们设第一次操作的点是 $x$ ，以 $x$ 为根建树，发现操作最大深度次就能完成。所以我们要让最大深度尽量小，就是直径的长度除以二。稍微注意下处理重边即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; int n,a[MAXN]; std::vector<int> G[MAXN],T[MAXN]; bool vis[MAXN]; int f[MAXN]; inline int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); } inline void merge(int x,int y){ x = find(x);y = find(y); if(x == y) return; f[x] = y; } inline void dfs(int v){ vis[v] = 1; for(auto x:G[v]){ if(vis[x]) continue; if(a[x] != a[v]) continue; merge(v,x); dfs(x); } } int g[MAXN][2],ans; inline void dfs2(int v,int fa=0){ for(auto x:T[v]){ if(x == fa) continue; dfs2(x,v); if(g[v][0] < g[x][0]+1){ g[v][1] = g[v][0]; g[v][0] = g[x][0]+1; } else if(g[v][1] < g[x][0]+1){ g[v][1] = g[x][0]+1; } } ans = std::max(ans,g[v][0]+g[v][1]); } std::map<P,int> S; int main(){ scanf("%d",&n);FOR(i,1,n) scanf("%d",a+i),f[i] = i; FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v);G[u].pb(v);G[v].pb(u); } FOR(i,1,n){ if(vis[i]) continue; dfs(i); } FOR(v,1,n){ for(auto x:G[v]){ if(find(x) != find(v)){ int a = find(x),b = find(v); if(a > b) std::swap(a,b); S[MP(a,b)] = 1; } } } for(auto x:S){ T[x.fi.fi].pb(x.fi.se); T[x.fi.se].pb(x.fi.fi); } dfs2(find(1)); printf("%d\n",(ans+1)/2); return 0; }C. 背包如果没有背包的限制，那么答案就是按照重量从大到小排序，求价值的 LDS。我们按照重量从大到小排序，那么位置 $i$ 我们能得出最多能选几个物品，设 $f_i$ 表示考虑了前 $i$ 个的答案，树状数组优化转移后特判一下能选几个物品的数量限制就行了。也就是 $f_i = \min(f_i,lim_i)$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; struct BIT{ #define lowbit(x) ((x)&(-(x))) int tree[MAXN]; inline void add(int pos,int x){ while(pos){ tree[pos] = std::max(tree[pos],x); pos -= lowbit(pos); } } inline int query(int pos){ int res = 0; while(pos < MAXN){ res = std::max(res,tree[pos]); pos += lowbit(pos); } return res; } }bit; int n; P a[MAXN]; int lim[MAXN],w[MAXN],m; inline void Solve(){ scanf("%d",&n);std::vector<int> S;CLR(bit.tree,0); FOR(i,1,n) scanf("%d%d",&a[i].fi,&a[i].se),S.pb(a[i].se); std::sort(all(S));S.erase(std::unique(all(S)),S.end()); FOR(i,1,n) a[i].se = std::lower_bound(all(S),a[i].se)-S.begin()+1; std::sort(a+1,a+n+1,[&](const P &x,const P &y){return x.fi > y.fi || (x.fi == y.fi && x.se > y.se);}); scanf("%d",&m); FOR(i,1,m) scanf("%d",w+i);std::sort(w+1,w+m+1);std::reverse(w+1,w+m+1); int ans = 0; FOR(i,1,n){ lim[i] = lim[i-1]; while(lim[i]+1 <= m && w[lim[i]+1] >= a[i].fi) ++lim[i]; int f = bit.query(a[i].se)+1;f = std::min(f,lim[i]); bit.add(a[i].se,f); ans = std::max(ans,f); } printf("%d\n",ans); } int main(){ // freopen("C.in","r",stdin); int T;scanf("%d",&T); while(T--) Solve(); return 0; }D. 蚂蚁先考虑不需要支持修改怎么做：假设现在有 $k$ 只蚂蚁，所在的点分别为 $v_1\ldots v_k$，设每个蚂蚁到达根的时间为 $t_i$，答案就是 $\max t_i$，我们观察一下有哪些限制：首先，每个蚂蚁的 $t_i \geq dep_{v_i}$，因为就算从开始爬也要花这些时间才能过去。然后，我们要保证不会在某时刻在同一个点，我们可以发现如果两只蚂蚁在某个时候在同一个点上，那么它们在根的时候也会在同一个点上，所以我们只需要保证 $t_i$ 互不相同就行了。所以问题变成了，每个变量有一个下界 $lim_i$，要求分配使得变量互不相同，并且最大值尽量小，这是个经典问题：考虑记 $s_i = \sum_{x=1}^k [lim_x \geq i]$，答案显然是 $\max(s_i+i-1)$，用线段树维护即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int mx[MAXN<<2],tag[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void cover(int x,int d){ mx[x] += d;tag[x] += d; } inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R){ cover(x,d); return; } int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); mx[x] = std::max(mx[lc],mx[rc]); } inline void build(int x,int l,int r){ tag[x] = 0; if(l == r){ mx[x] = l;return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); mx[x] = std::max(mx[lc],mx[rc]); } int n,m; std::vector<int> G[MAXN]; int dep[MAXN]; inline void dfs(int v,int fa=0){ dep[v] = dep[fa]+1; for(auto x:G[v]) if(x != fa) dfs(x,v); } inline int query(int x,int l,int r,int L,int R){ if(L > R) return 1; if(l == L && r == R) return mx[x]; int mid = (l + r) >> 1;pushdown(x); if(R <= mid) return query(lc,l,mid,L,R); if(L > mid) return query(rc,mid+1,r,L,R); return std::max(query(lc,l,mid,L,mid),query(rc,mid+1,r,mid+1,R)); } std::multiset<int> S; int main(){ scanf("%d%d",&n,&m); FOR(i,2,n){ int f;scanf("%d",&f); G[f].pb(i); } dfs(1);build(1,1,n); S.insert(0); FOR(i,1,m){ int opt,x;scanf("%d%d",&opt,&x); if(opt == 1){ if(x != 1){ S.insert(dep[x]); modify(1,1,n,1,dep[x],1); } } else{ if(x != 1){ S.erase(S.find(dep[x])); modify(1,1,n,1,dep[x],-1); } } int t = *S.rbegin(); printf("%d\n",query(1,1,n,1,t)-1); } return 0; }E. 划分为啥完全没有思路。。。我们考虑固定 $1$ 为根，定义每个连通块的根为连通块深度最小的点，我们枚举其中一个连通块的根为 $x \neq 1$，那么有一个连通块根一定为 $1$，我们设剩下的那个连通块的根为 $y$，分类讨论：如果 $sz_x = |A|$：如果 $y$ 不是 $x$ 的祖先，$sz_y = sz_x$ 或 $sz_y=n-2sz_x$如果 $y$ 是 $x$ 的祖先，$sz_y=2sz_x$ 或 $sz_y=n-sz_x$如果 $sz_x = |C|$：如果 $y$ 不是 $x$ 的祖先，$sz_y=\frac{n-sz_x}{2}$如果 $y$ 是 $x$ 的祖先，$sz_y = \frac{n-sz_x}{2}+sz_x = \frac{n+sz_x}{2}$相当于我们对于一个点，想要询问到根的链上是否有点的 $sz$ 是某个值，这个可以 dfs 的时候处理一个数组搞出来；还需要询问某个点子树外并且不是它的祖先的所有点中是否有点 $sz$ 是某个值，预先处理所有的点的 $sz$ 出现情况，补集转化后变成了求子树内某个值的出现次数，这个可以用类似差分计算增量的方法实现，也就是在进入子树前记录一下要查询的值，然后进入这个子树，遍历完所有的点并且加到桶里后再求一下值，做个差就能得到子树的值。详情可以看代码#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; std::vector<int> G[MAXN]; int n; int sz[MAXN]; int c1[MAXN],c2[MAXN],c3[MAXN]; // c1: 整棵树 // c2: 查询子树用 // c3: 祖先 inline void dfs1(int v,int fa=0){ sz[v] = 1; for(auto x:G[v]){ if(x == fa) continue; dfs1(x,v); sz[v] += sz[x]; } ++c1[sz[v]]; } int ans = 0; inline void dfs2(int v,int fa=0){ if(2*sz[v] <= n && c3[2*sz[v]] && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(c3[n-sz[v]] && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(!((n+sz[v])&1) && c3[(n+sz[v])>>1]) ans = std::max(ans,(n-sz[v])>>1); int p1 = c2[sz[v]],p2 = n-2*sz[v] > 0 ? c2[n-2*sz[v]] : -1e9,p3 = (n-sz[v])&1 ? -1e9 : c2[(n-sz[v])>>1]; ++c3[sz[v]];++c2[sz[v]]; for(auto x:G[v]){ if(x == fa) continue; dfs2(x,v); } p1 = c1[sz[v]]-(c2[sz[v]]-p1); if(p2 != -1e9) p2 = c1[n-2*sz[v]]-(c2[n-2*sz[v]]-p2); if(p3 != -1e9) p3 = c1[(n-sz[v])>>1]-(c2[(n-sz[v])>>1]-p3); if(p1 > 0 && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(p2 > 0 && 2*sz[v] < n) ans = std::max(ans,sz[v]); if(p3 > 0) ans = std::max(ans,(n-sz[v])>>1); --c3[sz[v]]; } int main(){ scanf("%d",&n); FOR(i,2,n){ int u,v;scanf("%d%d",&u,&v); G[u].pb(v);G[v].pb(u); } dfs1(1);dfs2(1); printf("%d\n",ans); return 0; }
A. 小星星考虑一个大家都会的暴力 dp：设 $f_{v,i,S}$ 表示确定好了 $v$ 的子树内的点映射到集合 $S$ 上，并且 $v$ 对应 $i$ 的方案数。合并子树的时候要保证 $S1$ 和 $S2$ 不交，然后根据图是否有边来判断。复杂度瓶颈显然在每次转移时的枚举子集。我们考虑我们这个第三维的作用是什么：是为了防止多个点映射到同一个点上。我们如果限定这个数的映射只能用 $S$ 然后跑上面去掉第三维后的 dp ，设得到的方案数为 $f(S)$，那么 $f(S)$ 表示 $n$ 个点，映射到的点的集合 $\subseteq S$ 的方案数，而我们要求 $g(S)$ 表示 $n$ 个点，映射到的点的集合 $=S$ 的个数。那么我们有$$ f(S) = \sum_{T \subseteq S} g(T) $$根据子集容斥，可以得到$$ g(S) = \sum_{T \subseteq S} (-1)^{|S|-|T|}f(T) $$所以我们只需要枚举子集，$O(2^n n^3)$ 才能过。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 17 + 1; int n,m; int G[MAXN][MAXN]; std::vector<int> T[MAXN]; LL f[MAXN][MAXN]; std::vector<int> lim; inline void merge(int x,int y){ for(auto i:lim){ LL s = 0; for(auto j:lim){ if(!f[y][j]) continue; if(!G[i+1][j+1]) continue; s += f[y][j]; } f[x][i] *= s; } } inline void dfs(int v,int fa=0){ for(auto i:lim) f[v][i] = 1; for(auto x:T[v]){ if(x == fa) continue; dfs(x,v); merge(v,x); } } int main(){ scanf("%d%d",&n,&m); FOR(i,1,m){ int u,v;scanf("%d%d",&u,&v); G[u][v] = G[v][u] = 1; } FOR(i,1,n-1){ int u,v;scanf("%d%d",&u,&v); T[u].pb(v);T[v].pb(u); } LL res = 0; FOR(S,1,(1<<n)-1){ if(__builtin_popcount(S) == 1) continue; LL gx = 0;lim.clear();CLR(f,0); FOR(i,0,n-1) if((S>>i)&1) lim.pb(i); dfs(1); FOR(i,0,n-1) if((S>>i)&1) gx += f[1][i]; if((n-__builtin_popcount(S))&1) gx = -gx; res += gx; } printf("%lld\n",res); return 0; }B. 魔法小程序首先可以把 $a$ 的长度缩短的 $O(\log n)$ 级别。注意需要把 $1$ 去掉。然后我们看一下给出的程序在做什么：相当于用那个递归程序写成若干个字符串后，求高维前缀和。那么我们考虑高维前缀和如何做：在第一层的时候我们设 $x=a_0$，按照 $x$ 分组，每组内都是第一位递增的，所以每组内部都 $b_i += b_{i-1}$，然后我们到下一层，那么原来的每 $x$ 组在下一层中的最低位都是一样的，设 $y=a_0a_1$，按照 $y$ 分组，也是在每一组内 $b_i += b_{i-x}$，剩下的也是类似做。。 那么高维前缀和的逆就是倒着做，每次倒着减掉就行了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e6 + 5; int a[MAXN],n,b[MAXN],m; std::vector<int> basis; int main(){ scanf("%d",&n); FOR(i,0,n-1) scanf("%d",a+i); scanf("%d",&m); FOR(i,0,m-1) scanf("%d",b+i); basis.pb(1); FOR(i,0,n-1){ if(a[i] == 1) continue; if(basis.back()*a[i] > m-1) break; basis.pb(basis.back()*a[i]); } basis.pb(m); ROF(cc,(int)basis.size()-1,1){ for(int i = 0;i < m;i += basis[cc]){ int j = std::min(m-1,i+basis[cc]-1); while(j >= i+basis[cc-1]) b[j] -= b[j-basis[cc-1]],--j; } } printf("%d\n",n); FOR(i,0,n-1) printf("%d%c",a[i]," \n"[i==n-1]); printf("%d\n",m); FOR(i,0,m-1) printf("%d%c",b[i]," \n"[i==m-1]); return 0; }C. 组合数问题卢卡斯定理拆成 $p$ 进制下的问题，我们将 $n,m$ 在 $p$ 进制下分解，如果 $\bmod p=0$ 那么就说明存在一位 $a_i < b_i$。所以可以设计数位dp：设 $f_{i,0/1,0/1,0/1,0/1}$ 表示考虑前 $i$ 位，是否已经有 $a_i<b_i$，$j$ 是否卡 $i$ 上界，$i$ 是否卡 $n$ 上界，$j$ 是否卡 $m$ 上界，枚举转移即可。复杂度 $O(q\log_p^3)$#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 60+5; const int ha = 1e9 + 7; int a[MAXN],b[MAXN],len; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } /* C(i,j) f[考虑到哪一位][是否有i<j][j是否卡i上界][i是否卡n上界][j是否卡m上界] */ int f[MAXN][2][2][2][2],k; inline int dp(int i,int ok,int b1,int b2,int b3){ // DEBUG(i); if(i > len) return ok; if(f[i][ok][b1][b2][b3] != -1) return f[i][ok][b1][b2][b3]; int &res = f[i][ok][b1][b2][b3];res = 0; int lim1 = b2?a[i]:(k-1); FOR(x,0,lim1){ int lim2 = std::min(b1?x:(k-1),b3?b[i]:(k-1)); FOR(y,0,lim2){ add(res,dp(i+1,ok|(x<y),b1&(y==x),b2&(x==a[i]),b3&(y==b[i]))); } } return res; } int main(){ int T;scanf("%d%d",&T,&k); while(T--){ LL n,m;scanf("%lld%lld",&n,&m); m = std::min(n,m);CLR(a,0);CLR(b,0); CLR(f,-1); int lena = 0,lenb = 0; while(n) a[++lena] = n%k,n /= k; while(m) b[++lenb] = m%k,m /= k; len = std::max(lena,lenb); std::reverse(a+1,a+len+1);std::reverse(b+1,b+len+1); printf("%d\n",dp(1,0,1,1,1)); } return 0; }
A考虑对串的反串建后缀树，答案就是叶子节点个数。注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。证明要考虑这个命题等价于叶子节点在值域上是连续的一段后缀，然后考虑反证：假设前缀 $x$ 不属于但是 $y$ 属于，一定能从 $y$ 属于的那个前缀找出一部分变成 $x$ 属于的。（然而我考试直接找规律）所以有个结论：后缀树的叶子节点个数，每个前缀的 border 集合的并的大小，本质不同的 $fail_i$ 的个数，$\text{max} fail_i$ 的值是相等的。不管怎么说，即使在 NOIP 赛场上遇到字符串题也要想想能否用后缀树的思想方便优化。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e6 + 5; char str[MAXN]; int n; int nxt[MAXN]; int main(){ scanf("%s",str+1);n = strlen(str+1); int j = 0;nxt[0] = -1;nxt[1] = 0;int ans = 0; FOR(i,2,n){ while(j && str[i] != str[j+1]) j = nxt[j]; if(str[i] == str[j+1]) ++j; else j = 0; nxt[i] = j; ans = std::max(ans,nxt[i]); } printf("%d\n",n-ans); return 0; }B首先一个很松的上界的是 $ans \leq n$，我们设所有三元组三个数的和的和为 $S$，三元组个数为 $k$，可以发现 $kn = S \geq 3(1+2+\ldots+k)$，可以得到 $k \leq \lfloor \frac{2n}{3}\rfloor -1$。写个剪枝搜索应该是能跑出来 $n \leq 17$ 的，于是打表可以发现规律。我们将 $n$ 按照 $n \bmod 3$ 分类，我们发现 $n \bmod 3=0$ 比较特殊，找找这种方案的规律：首先我们只需要考虑二元组 $(a_i,b_i)$ 满足和互不相同，$a_i$ 互不相同，$b_i$ 互不相同即可。我们 $a_i,b_i$ 的值域都是 $[1,ans]$，我们考虑 $a_i$ 前面全放奇数后面全放偶数，然后把 $b_i$ 最小的若干个倒着和 $a_i$ 的奇数部分匹配，剩下的倒着和 $a_i$ 的偶数部分匹配。举个 $n=12$ 的例子：1 4 3 3 5 2 7 1 2 7 4 6 6 5首先 $a_i,b_i$ 一定互不相同。然后发现这样排列上一个和下一个的和一定会相差 $1$，所以都满足条件。$n \bmod 3 = 1$ 的答案是不变的，改一下 $c_i$ 就行了。$n \bmod 3 = 2$ 的答案变了，我们让 $a_i$ 整体加一，$c_i$ 整体加一，发现 $a,c$ 都可以放 $1$ 了，然后 $b$ 放 $n-2$ 即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; int a[MAXN],b[MAXN],c[MAXN],n,ans; bool vis[3][MAXN]; inline void check(){ assert(ans == (2*n-3)/3); // DEBUG(ans); FOR(i,1,ans){ // DEBUG(i); assert(a[i]+b[i]+c[i] == n); assert(!vis[0][a[i]]); assert(!vis[1][b[i]]); assert(!vis[2][c[i]]); vis[0][a[i]] = vis[1][b[i]] = vis[2][c[i]] = 1; } } int main(){ scanf("%d",&n); if(n == 1){ puts("0"); return 0; } if(n == 2){ puts("0"); return 0; } if(n%3 == 0){ ans = 2*(n/3)-1; printf("%d\n",ans); int t = 0; for(int i = 1;i <= ans;i += 2) a[++t] = i; int t1 = t; for(int i = 2;i <= ans;i += 2) a[++t] = i; t = 0; ROF(i,t1,1) b[i] = ++t; ROF(i,ans,t1+1) b[i] = ++t; FOR(i,1,ans) c[i] = n-a[i]-b[i]; FOR(i,1,ans) printf("%d %d %d\n",a[i],b[i],c[i]); check(); return 0; } if(n%3 == 1){ --n; ans = 2*(n/3)-1; printf("%d\n",ans); int t = 0; for(int i = 1;i <= ans;i += 2) a[++t] = i; int t1 = t; for(int i = 2;i <= ans;i += 2) a[++t] = i; t = 0; ROF(i,t1,1) b[i] = ++t; ROF(i,ans,t1+1) b[i] = ++t; FOR(i,1,ans) c[i] = n-a[i]-b[i]+1; FOR(i,1,ans) printf("%d %d %d\n",a[i],b[i],c[i]); ++n; check(); return 0; } if(n%3 == 2){ n -= 2; ans = 2*(n/3)-1; int t = 0; for(int i = 1;i <= ans;i += 2) a[++t] = i; int t1 = t; for(int i = 2;i <= ans;i += 2) a[++t] = i; t = 0; ROF(i,t1,1) b[i] = ++t; ROF(i,ans,t1+1) b[i] = ++t; FOR(i,1,ans) c[i] = n-a[i]-b[i]+1; FOR(i,1,ans) a[i]++; // 第一列有1 第三列有1 ++ans; n += 2; a[ans] = 1;c[ans] = 1;b[ans] = n-2; printf("%d\n",ans); FOR(i,1,ans) printf("%d %d %d\n",a[i],b[i],c[i]); check(); return 0; } return 0; }C首先注意数字互不相同，所以能分成若干条链，限制形如某条链上相邻的两个点原序列不能相邻（注意我这里思考的链的元素是相邻关系，也就是若干个 pair ，所以选了链上一个点对应了固定了原序列两个点，选了相邻两个对应固定三个，不相连两个对应固定四个）考虑容斥，枚举有几个相邻的位置 $i$，有一对相邻的位置就可以将两个点并起来，所以排列的方案数就是 $(n-i)!$。现在只需要求出来有 $i$ 个相邻的位置的方案数就好了。链与链之间的关系是独立的，我们考虑如果只有一条链怎么做（就是样例 $1$ 的情况）。我们钦定链上一些连通块选了，那么每个连通块可以正着也可以反着，对答案有 $2$ 的贡献。于是搞个 dp：$f_{i,j,0/1}$ 考虑前 $i$ 个 pair ，选了 $j$ 个 pair ，上一个是否选。转移如果上一个是 $0$ 并且这一个是 $1$ 方案数就要 $\times 2$。不同链之间是独立的；直接背包合并是爆炸的，不如把所有链拼在一起，在分隔点打标记，每次强制断开即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5000+5; const int ha = 998244353; int n,k,a[MAXN]; namespace Subtask1{ inline bool check(){ return n <= 10; } int p[MAXN]; inline void Solve(){ FOR(i,1,n) p[i] = i; int ans = 0; do{ bool flag = 1; FOR(i,2,n) if(std::abs(a[p[i-1]]-a[p[i]]) == k) {flag = 0;break;} ans += flag; }while(std::next_permutation(p+1,p+n+1)); printf("%d\n",ans);exit(0); } } inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } namespace Subtask2{ int f[MAXN][MAXN][2],fac[MAXN]; inline bool check(){ return n <= 5000; } bool qd[MAXN]; int g[MAXN]; std::map<int,int> S; int to[MAXN],len[MAXN],tot; bool vis[MAXN]; inline void Solve(){ FOR(i,1,n) S[a[i]] = i; FOR(i,1,n){ S[a[i]] = 0; to[i] = S[a[i]+k]; } int sz = 0; FOR(i,1,n){ if(!vis[i]){ int v = i;++tot; while(v){ ++len[tot];vis[v] = 1; v = to[v]; } len[tot]--; if(!len[tot]) --tot; else sz += len[tot]; } } int sm = 0; FOR(i,1,tot){ sm += len[i]; qd[sm+1] = 1; } f[0][0][0] = 1; fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha; FOR(i,1,sz){ FOR(j,0,i){ f[i][j][0] = (f[i-1][j][0]+f[i-1][j][1])%ha; if(qd[i]){ if(j) f[i][j][1] = 2ll*(f[i-1][j-1][0]+f[i-1][j-1][1])%ha; } else{ if(j) add(f[i][j][1],f[i-1][j-1][1]); if(j) add(f[i][j][1],2ll*f[i-1][j-1][0]%ha); } } } FOR(i,0,sz) g[i] = (f[sz][i][0]+f[sz][i][1])%ha; int ans = 0; FOR(i,0,sz){// 选了几个球 int gx = 1ll*fac[n-i]*g[i]%ha; if(i&1) gx = ha-gx; add(ans,gx); } printf("%d\n",ans); } } int main(){ scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d",a+i); if(Subtask1::check()) Subtask1::Solve(); if(Subtask2::check()) Subtask2::Solve(); return 0; } /* 注意 这个题没有相同的数 所以限制只有 O(n) 对 n个球 染黑m个 连续段 */