RainAir's Blog - 构造
type: channel
link: http://blog.aor.sd.cn/tag/构造
items: ARC119D Grid Repainting 3
items: Educational Codeforces Round 108
items: ARC 115 题解
items: CF 1493 题解
items: CF 1494 题解
items: CF1450 题解
items: gym100801I Insider's Information
items: ZR 2020普转提七连测day5
items: contest3 题解
items: 20联赛集训day4 题解

ARC119D Grid Repainting 3
type: item
date: 2021-05-17T09:21:00+08:00
description: [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…

Educational Codeforces Round 108
type: item
date: 2021-05-16T10:03:00+08:00
description: 由于是恢复训练，所以会把所有题目解法都写写。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})$ 之类的东西？反正可以快速通过。

ARC 115 题解
type: item
date: 2021-03-23T21:37:00+08:00
description: 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…

CF 1493 题解
type: item
date: 2021-03-10T11:33:00+08:00
description: 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)$，然后算一下发现并没有超过上界。

CF 1494 题解
type: item
date: 2021-03-03T10:41:00+08:00
description: 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。代码

CF1450 题解
type: item
date: 2020-12-07T21:29:00+08:00
description: 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.beg…

gym100801I Insider's Information
type: item
date: 2020-11-20T14:41:57+08:00
description: 题意要求构造大小为 $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…

ZR 2020普转提七连测day5
type: item
date: 2020-10-28T20:46:00+08:00
description: 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 co…

contest3 题解
type: item
date: 2020-10-20T21:48:46+08:00
description: 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}$，剩下的也是类似做。。 那么高维前缀和的…

20联赛集训day4 题解
type: item
date: 2020-10-15T21:23:00+08:00
description: 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(…