湖南网站建设公司排名,网站设计制作ihanshi,百度博客网站模板,y-m-d WordPressMy OI Blog A R C 155 F \mathbb{ARC \ 155 \ F} ARC 155 F E, F 先咕着#xff0c;做一些多项式题#xff0c;这篇题解是我人工翻译的 [1] Double Counting 双重计数 考虑从叶子节点开始#xff0c;用唯一的方式#xff08;如果有的话#xff09;来构造出一棵满足条件的树…My OI Blog A R C 155 F \mathbb{ARC \ 155 \ F} ARC 155 F E, F 先咕着做一些多项式题这篇题解是我人工翻译的 [1] Double Counting 双重计数 考虑从叶子节点开始用唯一的方式如果有的话来构造出一棵满足条件的树。因此我们可以对一棵每个节点度为 D i D_i Di 的有向有标号树来代替无向树进行计数。
常用的对有标号树计数的方式是双重计数设 A A A 是原问题的答案 B B B 是这棵有根树的数量其中
树根是 N N N 个节点中任意一个。从节点 i i i 连出的 D i D_i Di 条边用 1 1 1 到 D i D_i Di 标号。
那么 B A × N × ∏ i 1 N D i ! BA \times N \times \prod_{i1}^{N}D_i! BA×N×∏i1NDi! 。
[2] Construction of the rooted trees 有根树的构造有根树可以按照一下方法构造此外对于所有的树按以下方式都有唯一构造。
确定与根相连的节点集合 S S S 。对于 S S S 中的节点从 D i D_i Di 中选择一条指向根并给其他的边选择指向的节点。确定其他边的终点。
考虑在完成了第一步和第二步之后执行第三步的方式有多少让我们按节点编号的升序边的升序来开始考虑可以选择没有父节点且与当前起点不在一个连通块里的点作为终点。在一开始有 n − ∣ S ∣ n - \mid S \mid n−∣S∣ 个节点没有父节点所以有 ( n − ∣ S ∣ − 1 ) ! (n - \mid S \mid - 1)! (n−∣S∣−1)! 种方式特别地这一步的方案数和上一步无关。
接下来来计算第二步的方案数。这里有 ∏ i ∈ S D i \prod_{i \in S} D_i ∏i∈SDi 种方式选择指向根的边对于其他边的终点的方案数观察可以得到这个方案数等于 N N N 个节点 ∣ S ∣ \mid S \mid ∣S∣ 条边组成森林的方案数。
现在我们把选出来的 S S S 忽略掉从 N N N 个节点和 0 0 0 条边开始重复以下操作 ∣ S ∣ \mid S \mid ∣S∣ 次形成一个有根森林。将一个节点 u u u 与另一个在其连通块之外的没有父节点的 v v v 连接。这里有 ∏ i 1 ∣ S ∣ N × ( N − i ) N ∣ S ∣ × ( N − 1 ) ! ( N − ∣ S ∣ − 1 ) ! \prod_{i 1}^{\mid S \mid} N \times (N - i) N^{\mid S \mid} \times \frac{(N - 1)!}{(N - \mid S \mid - 1)!} ∏i1∣S∣N×(N−i)N∣S∣×(N−∣S∣−1)!(N−1)! 来选择 u u u 和 v v v 然后消序得到 N ∣ S ∣ × ( N − 1 ) ! ∣ S ∣ ! ( N − ∣ S ∣ − 1 ) ! N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!} N∣S∣×∣S∣!(N−∣S∣−1)!(N−1)! 种方案。对称地来看其中一共有 N ∣ S ∣ × ( N − 1 ) ! ∣ S ∣ ! ( N − ∣ S ∣ − 1 ) ! × 1 N C ∣ S ∣ N ∣ S ∣ ( N − ∣ S ∣ ) N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!} \times \frac{1}{N^C \mid S \mid} N^{\mid S \mid}(N - \mid S \mid) N∣S∣×∣S∣!(N−∣S∣−1)!(N−1)!×NC∣S∣1N∣S∣(N−∣S∣) 种方案满足所选出来的父节点集合为 S S S 。
因此在第一步钦定了 S S S 之后这里有 N ∣ S ∣ − 1 × ( N − ∣ S ∣ ) ! × ∏ i ∈ S D i N^{\mid S \mid - 1} \times (N - \mid S \mid) !\times \prod_{i \in S} D_i N∣S∣−1×(N−∣S∣)!×∏i∈SDi 棵满足条件的有根树可以被构造出来。
[3] Using convolution 使用卷积 故而我们定义 f ( x ) ∏ i N ( 1 D i x ) f(x) \prod_{i}^{N}(1 D_ix) f(x)∏iN(1Dix)我们有 B ∑ k 0 N − 1 N k − 1 ( N − k ) [ x k ] f ( x ) B \sum_{k 0}^{N - 1}N^{k - 1} (N - k)[x^k]f(x) B∑k0N−1Nk−1(N−k)[xk]f(x) 。于是就可以用多项式直接做了。 A G C 043 D \mathbb{AGC \ 043 \ D} AGC 043 D
需要手玩如果画成柱状图大概是 发现分布很有规律有连续的单调的段长度 l e n ∈ [ 1 , 3 ] len \in [1,3] len∈[1,3]并且每段的开头放在一起单调不降长度为 2 2 2 的段数量永远小于长度为 1 1 1 的段。 考虑为啥会出现这种情况对于原序列一段 A 1 , A 2 , A 3 A_1, A_2, A_3 A1,A2,A3如果 A 1 A 2 A_1 A_2 A1A2 或者 A 2 A 3 A_2 A_3 A2A3那么这三个数会有两个连续被取出如果 A 1 A 2 A_1 A_2 A1A2 并且 A 1 A 3 A_1 A_3 A1A3这三个数会一起取出。 上述一起取出来的数一定会被扔进一个单调的块里面因为大小为 2 2 2 的块和大小为 1 1 1 的块都会成对出现所以大小为 2 2 2 的块的个数一定小于等于大小为 1 1 1 的块的个数。 于是定义 d p i , j dp_{i, j} dpi,j 表示现在长度为 i i i大小为 1 1 1 的块的个数减大小为 2 2 2 的块的个数为 j j j 的方案数可以直接转移。 A R C 163 C \mathbb{ARC \ 163 \ C} ARC 163 C
我是肯尼迪我脑洞非常大。 这题是真抽象但是我想到了就更抽象。 有个东西叫裂项相消就是说 1 ∑ i 2 n ( − 1 i 1 i ) 1 1 \sum_{i 2}^{n} \left(-\frac{1}{i} \frac{1}{i}\right) 1 1∑i2n(−i1i1)1换个写法 1 2 ∑ i 2 n − 1 ( 1 i − 1 i 1 ) 1 n 1 \frac{1}{2} \sum_{i 2}^{n - 1} \left(\frac{1}{i} - \frac{1}{i 1}\right) \frac{1}{n} 1 21∑i2n−1(i1−i11)n11于是这道题就会做了。 然后这样就会WA对于 n 6 n 6 n6 会得到如下方案 2 , 6 , 12 , 20 , 6 2, 6, 12, 20, 6 2,6,12,20,6出现了两个 6 6 6。显然不对。 如何避免呢对于 n ( i 1 ) i n (i 1)i n(i1)i 的形式可以先拆一个 2 2 2 出来然后再裂项一下凑出剩下的 1 2 \frac{1}{2} 21。 A R C 163 D \mathbb{ARC \ 163 \ D} ARC 163 D
不会竞赛图性质GG。 现在会了这里指 将一个竞赛图缩点之后形成的 DAG 是一条单链证明方式考虑依次加点进图即可。 然后还是不会计数听说是套路但是真的不会。 难点在于去计算所有强连通块个数的和。考虑换一种方式去描述强连通块个数 结合到性质发现对于一张固定的图对它缩点劈开这条单链使其成为两个非空集合的方案数等于强连通个数减一。 更具体地来说如果缩点后图变成 s c c 1 → s c c 2 → s c c 3 → ⋯ → s c c n scc_1 \to scc_2 \to scc_3 \to \dots \to scc_n scc1→scc2→scc3→⋯→sccn将其划分成 A , B A,B A,B 两个集合满足 A ∪ B s c c , A ∩ B ∅ , ∀ u ∈ A , v ∈ B , ∃ e u → v A \cup B scc, A \cap B \varnothing, \forall u \in A, v \in B, \exists e u \to v A∪Bscc,A∩B∅,∀u∈A,v∈B,∃eu→v。 于是达到了切换主体的目的定义 d p i , j , k dp_{i, j, k} dpi,j,k 表示考虑了前 i i i 个点 ∣ A ∣ j \mid A \mid j ∣A∣j有 k k k 条小连大的边 Θ ( n 4 ) \Theta(n^4) Θ(n4) 转移即可。
dp[0][0][0] 1;
for (int i 0; i n; i) {for (int j 0; j i; j) {for (int k 0; k m; k) {if (!dp[i][j][k]) continue;for (int l 0; l j; l) dp[i 1][j 1][k l] (dp[i 1][j 1][k l] (dp[i][j][k] * binom(j, l) % Mod)) % Mod;for (int l 0; l (i - j); l) dp[i 1][j][k j l] (dp[i 1][j][k j l] (dp[i][j][k] * binom(i - j, l) % Mod)) % Mod;}}
}A R C 164 D \mathbb{ARC \ 164 \ D} ARC 164 D
发现这个东西和括号匹配很像但是一开始想偏了想成把 看成左括号把 - 看成右括号了。 其实这样非常不对比如 ---。 正确的想法是要把每个球的移动方向看成左右括号。考虑算贡献本来这个非常套路但是当时降智了以为要去枚举匹配的两个点计算其实这个贡献非常好拆一对匹配的点 ( x , y ) (x, y) (x,y) 的贡献为 y − x y - x y−x拆成单点如果方向往左贡献为正方向往右贡献为负。 因为左边的序列定了右边的序列也能定所以枚举左边有多少个 ? 变成了 以此来判断当前小球的移动方向即可计算贡献了。 A R C 159 D \mathbb{ARC \ 159 \ D} ARC 159 D
哈哈我是傻逼。 首先观察得到性质如果选了一个区间 [ l i , r i ] [l_i, r_i] [li,ri] 中的 x x x那么一定会去选 [ x , r i ] [x, r_i] [x,ri]证明非常显然但是我没想到。 于是分类讨论即可记 d p i dp_i dpi 表示以第 i i i 个区间结尾 LIS 的最大长度。 如果 r j l i r_j l_i rjli d p i max { d p j } ( r i − l i 1 ) dp_i \max\{ dp_j \} (r_i - l_i 1) dpimax{dpj}(ri−li1)如果 r j ≥ l i r_j \ge l_i rj≥li d p i max { d p j − r j } r i dp_{i} \max\{ dp_j - r_j \} r_i dpimax{dpj−rj}ri。 A R C 159 C \mathbb{ARC \ 159 \ C} ARC 159 C
哈哈我是傻逼。 比较厉害的一点在于如何把对所有元素的操作通过叠加使其变成对两个元素的操作。 首先做一遍 1 , 2 , 3 , … , n 1, 2, 3, \dots, n 1,2,3,…,n 然后再做 n , n − 1 , n − 2 , … , 1 n, n - 1, n - 2, \dots, 1 n,n−1,n−2,…,1 相当于啥都没做于是在第二次操作时交换相邻两个数那就实现了一个数加一一个数减一这样就能构造答案了。 A G C 001 D \mathbb{AGC \ 001 \ D} AGC 001 D
比较有意思的构造题值得思考的点在于转换这个问题。 算是积累一个技巧看到回文的限制注意到可以把对应的两个点之间建立边一类的联系。 这道题就充分体现了这个玩意。因为大条件是 ∑ a i ∑ b i n \sum{a_i} \sum{b_i} n ∑ai∑bin需要做的是在把 a a a 这边的限制刻画完之后把 b b b 拼上去。 然后我来偷两张图/bx command_block。 这个构造非常自然一个是 a i a_i ai 为奇数一个是 a i a_i ai 为偶数的情况。但是也注意到了如果 a a a 中出现了大于两个奇数这个是 Impossible 的。 然后按图模拟即可注意特判 m 1 m 1 m1 的情况。 A G C 001 E \mathbb{AGC \ 001 \ E} AGC 001 E
我先猜一手这道题应该从 a i , b i a_i, b_i ai,bi 的值域大小出发并转组合意义去做。 注意到 ( a i a j b i b j a i a j ) \binom{a_i a_j b_i b_j}{a_i a_j} (aiajaiajbibj) 的组合意义是从 ( 0 , 0 ) (0, 0) (0,0) 出发走到 a i a j b i b j a_i a_j b_i b_j aiajbibj 的方案数。 但是这样有点问题我需要去记录每种情况的 a i a j b i b j a_i a_j b_i b_j aiajbibj 是多少相当于这个组合意义并没有起到作用。思考这样做的问题在于组合意义是对于 ( a i , b i ) , ( a j , b j ) (a_i, b_i), (a_j, b_j) (ai,bi),(aj,bj) 这两个点对而言的复杂度与 ( a i , b i ) , ( a j , b j ) (a_i, b_i), (a_j, b_j) (ai,bi),(aj,bj) 这样的点对数量有关如果要降复杂度需要拆单点贡献。 修改一下组合意义把起点从 ( 0 , 0 ) (0, 0) (0,0) 挪到 ( − a i , − b i ) (-a_i, -b_i) (−ai,−bi) 上去。于是转化为求两两点对之间的路径数这样复杂度非常对因为这样做的复杂度与 a i , b i a_i, b_i ai,bi 的值域相关总的复杂度是 Θ ( a b n ) \Theta(ab n) Θ(abn)需要注意减去 i j i j ij 的情况后答案应该除以 2 2 2。
吐了 atcoder 模数居然不是 998244353 998244353 998244353。 /tuu A G C 001 F \mathbb{AGC \ 001 \ F} AGC 001 F
先放一波我的错误思路。 看起来不是很好处理先变形一下这个限制 i , j i, j i,j 能够交换必须满足 ∣ i − j ∣ ≥ n k , ∣ a i − a j ∣ n \mid i - j \mid \ge nk, \mid a_i - a_j \mid n ∣i−j∣≥nk,∣ai−aj∣n 那么 i i i 和 j j j 能够换。 发现上面这个转化不是等价的只是一个必要条件。 怎么办这说明了从条件出发并不是一个好的方向。那从问题出发要是字典序最小不难想到有这样一种方式去交换。 p 1 p 2 p 3 p1 p2 p3 p1p2p3且 p 1 , p 2 p1, p2 p1,p2 之间距离大于等于 k k k p 2 , p 3 p2, p3 p2,p3 之间距离小于 k k k a p 2 a p 1 1 a p 3 2 a_{p2} a_{p1} 1 a_{p3} 2 ap2ap11ap32。 那么我做 swap(p1, p2) 后接一个 swap(p2, p3) 就变成了 p 3 , p 1 , p 2 p3, p1, p2 p3,p1,p2 这样就非常优秀。 能不能推广能不能月下无限连 不能。
问题在于我需要去刻画三个点的关系并且在不断弱化的我限制这样是非常不优秀的。 并且值得注意的是在这种有限制的交换关系求方案思路重点一般在限制上但是我从一开始弱化了这个限制导致不可做。
这道题解法就很牛逼了题目着重刻画的是下标和值的关系正解是把这两个玩意儿反过来。 这显然不是人类能够想出来的东西但是也有其合理性。 记反过来之后的排列是 q q q i , j i, j i,j 能交换的条件是 i , j i,j i,j 相邻且 ∣ q i − q j ∣ ≥ k \mid q_i - q_j \mid \ge k ∣qi−qj∣≥k。为什么这样会更好下手下标相邻这样的限制是非常强的它是由 ∣ a i − a j ∣ 1 \mid a_i - a_j \mid 1 ∣ai−aj∣1 这个限制转化过来的。这就提示在有对偶姑且称之为的两个限制下尽量把强限制等于放在更好刻画的位置下标把若限制偏序关系放在比较能用某些结构刻画的位置值域。
下一步继续用更强的限制刻画偏序关系当 ∣ q i − q j ∣ k \mid q_i - q_j \mid k ∣qi−qj∣k 时他们的相对顺序不会发生改变因为交换是相邻的当存在交换使 i , j i, j i,j 相邻时他们会因为值的限制卡住动不了。
然后对这样的点对 i → j i \rightarrow j i→j 建边。
最后把这个边建回原图对于 p i , p j p_i, p_j pi,pj 如果 ∣ i − j ∣ k \mid i - j \mid k ∣i−j∣k则要求他们的大小关系不变如果要求 p i p j p_i p_j pipj 就建边 i → j i \rightarrow j i→j。 运用一下拓扑字典序原理解决这个问题注意不能直接贪心应该建反图后从大往小贪典中典。
然后想了一下发现我剩下的几步还是不会纯纯废物了。 考虑 i i i 能向 { j : ∣ i − j ∣ k , p j p i } \{ j : \mid i - j \mid k, p_j p_i \} {j:∣i−j∣k,pjpi} 这个集合里面的点连边 i i i 的入度为 0 0 0 的充要条件是 p i p_i pi 是 [ i − k , i k ] [i - k, i k] [i−k,ik] 这个区间里面的最大值。那么用一个大根堆去维护目前出度为 0 0 0 的点即可然后用线段树维护区间最大值在删除 i i i 时查看 [ i − k , i ) , ( i , i k ] [i - k, i), (i, i k] [i−k,i),(i,ik] 中最大值编号如果入度为 0 0 0 就塞进大根堆。 A G C 002 D \mathbb{AGC \ 002 \ D} AGC 002 D
忘了整体二分怎么做了完蛋啦哈哈。 没啥好说的直接整体二分拿并查集连连就好然后我调了 2h原因是我是唐在写可撤销并查集时路径压缩了。 A G C 002 F \mathbb{AGC \ 002 \ F} AGC 002 F
换个方式去刻画题目考虑到所有颜色都是等价的把涂白的球记为 0 0 0那么题目变成要求第 i i i 种颜色的球出现在第 i i i 个白球之后最后的方案总数乘 n ! n! n! 即可。发现可以把白球出现这个事件拎出来以此对整个过程分段。定义 d p i , j dp_{i, j} dpi,j 表示放了前 i i i 个白球前 j j j 种彩球都放了 k − 1 k - 1 k−1 的方案数。 千万不能把每种彩球分开处理原因很简单分开处理后需要记录每种彩球出现了多少个而这种开销是无法接受的。相反把每种彩球都分在一起可以更有效地去计数。 转移分成两种
放一个白球这样一定合法方程是 d p i 1 , j d p i 1 , j d p i , j dp_{i 1, j} dp_{i 1, j} dp_{i, j} dpi1,jdpi1,jdpi,j放一种彩球满足的要求是 j 1 ≤ i j 1 \le i j1≤i注意到要先放一个在最靠前的空位上于是剩下了 k − 2 k - 2 k−2 个球有 ( n k − i − ( k − 1 ) j − 1 k − 2 ) \binom{nk - i - (k - 1)j - 1}{k - 2} (k−2nk−i−(k−1)j−1) 种放法于是方程是 d p i , j 1 d p i , j 1 d p i , j × ( n k − i − ( k − 1 ) j − 1 k − 2 ) dp_{i, j 1} dp_{i, j 1} dp_{i, j} \times \binom{nk - i - (k - 1)j - 1}{k - 2} dpi,j1dpi,j1dpi,j×(k−2nk−i−(k−1)j−1)。
需要特判 k 1 k 1 k1。 A G C 003 D \mathbb{AGC \ 003 \ D} AGC 003 D
从考察一个数是否是完全立方数出发一个数如果是完全立方数当且仅当它的所有质因子的次数都能被 3 3 3 整除。 一个很 naive 的思路是分解每个质因数按模 3 3 3 的余数分类一个类和恰好另一个类对应乘积是完全立方数。 但是这个数据范围着实分解不了质因数。首先把 ( 1 , s 1 3 ] (1, s^{\frac{1}{3}}] (1,s31] 内的质数除掉这样剩下的性质就只能是 p , p 2 , p 1 p 2 p, p^2, p_1p_2 p,p2,p1p2注意到 p 2 p^2 p2 需要再补上 p 3 k 1 p^{3k 1} p3k1 才会变成完全立方数因为已经超过了 s 1 3 s^{\frac{1}{3}} s31所以补上的一定是 p p p而 p 1 p 2 , p p_1p_2, p p1p2,p 必须补上 p 2 , p 1 p 2 p^2, p_1p_2 p2,p1p2 才行。 于是我们调了一下上界获得了和暴力一样的做法。 A G C 003 E \mathbb{AGC \ 003 \ E} AGC 003 E
神仙东西。 首先去除一堆没用的 n i n_i ni得到的序列是严格递增的。这个操作是在干嘛 是把原序列复制几遍并接上一个前缀记 P i P_i Pi 为操作了 i i i 次之后的序列 d p i , j dp_{i, j} dpi,j 表示 j j j 在 P i P_i Pi 中出现的次数。 令 t ⌊ n i n i − 1 ⌋ t \lfloor \frac{n_i}{n_{i - 1}} \rfloor t⌊ni−1ni⌋那么 P i P_i Pi 就由 t t t 个 P i − 1 P_{i - 1} Pi−1 和 P i − 1 P_{i - 1} Pi−1 的前 n i m o d n i − 1 n_i \mod n_{i - 1} nimodni−1 个字符组成于是先将 d p i , j dp_{i, j} dpi,j 初始化为 d p i − 1 , j dp_{i - 1, j} dpi−1,j。 然后前缀怎么办
现在重新想一下上面的思考是怎么来的首先淡化 P i P_i Pi 和 P i − 1 P_{i - 1} Pi−1 之间的转移。改成 P i P_i Pi 从 P p r e P_{pre} Ppre 转移过来。 那么有 P i ⌊ n i n p r e ⌋ P p r e P p r e [ 1 , n i m o d n p r e ] \begin{aligned} P_i \lfloor \frac{n_i}{n_{pre}} \rfloor P_{pre} P_{pre}[1, n_i \ \mathrm{mod} \ n_{pre}] \end{aligned} Pi⌊npreni⌋PprePpre[1,ni mod npre] p r e pre pre 的寻找自然是最后一个小于 n i n_i ni 的 n p r e n_{pre} npre然后抛弃掉 n n n 个表示把 n i m o d n p r e n_i \ \mathrm{mod} \ n_{pre} ni mod npre 和 n n n 放在同一位置那么这就是个子问题递归下去处理即可。 复杂度反而不是重点。 反思为什么想不到这种方法因为一般的题目强调的都是两两状态之间的转移在想题的时候就陷入了如何从 P i − 1 P_{i - 1} Pi−1 到 P i P_i Pi 的陷阱里面。要想到泛化泛化泛化。 A G C 003 F \mathbb{AGC \ 003 \ F} AGC 003 F
你说得对但是连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数做完了。
没有注意可以直接矩阵乘法加速。 A G C 004 E \mathbb{AGC \ 004 \ E} AGC 004 E
物理原理相对移动。 固定机器人不动就变成了挪动出口去救机器人假设把出口挪动了 ( p x , p y ) (p_x, p_y) (px,py)那么以 ( x 0 , y 0 ) (x_0, y_0) (x0,y0) 为左下角到以 ( x 0 p x , y 0 p y ) (x_0 p_x, y_0 p_y) (x0px,y0py) 为右上角的这个矩阵里的所有机器人可以被救。 于是直接 Θ ( n 4 ) \Theta(n^4) Θ(n4) 定义 d p w , s , a , d dp_{w, s, a, d} dpw,s,a,d 含义看键盘可知暴力转移即可。 A G C 004 F \mathbb{AGC \ 004 \ F} AGC 004 F
大分类讨论题。 非常神了看到 m ∈ [ n − 1 , n ] m \in [n - 1, n] m∈[n−1,n]不难想到分成树和基环树的情况讨论。
首先讨论树的情况每一次都会改变两个点的颜色一个点必须被改变奇数次所以当总点数为奇数时直接判无解。 那么偶数时怎么计算最小步数呢能不能形象一点改变颜色一类的题目要想到把改变颜色变成移动颜色之类的更好计算的方式。 因为树是二分图于是把整棵树都黑白染色现在改变一下操作变成颜色不同的两个点可以互换颜色不难发现一个点被操作奇数次的结果是颜色反色。于是把黑色看成有棋子在上面把白色看成空操作就是移动棋子使得每个棋子最终落在一开始没有棋子的地方。 也容易发现当棋子和空白点数不同时是无解的。 对于一个节点 u u u假设子树内有 x x x 个棋子总共点数有 s i z u siz_u sizu 个可以猜想到经过 u u u 这个节点的棋子数目下界是 x − ( s i z u − x ) x - (siz_u - x) x−(sizu−x) 步意思是能够内部消化的就内部消化不能内部消化的都要经过 u u u 离开这颗子树于是所有点被经过的次数就是需要移动的总步数注意一下取绝对值多单位移动的步数问题可以转化为考虑每一个节点被经过的次数问题。
然后是基环树的情况次数需要讨论环的奇偶性。 当环是偶环时先抠出来一条边变成树是否无解和树的情况一致考虑多出来的这条边能给我们带来什么 显然某些情况下直接通过这条边要比在环上绕一大圈更优于是现在单独考虑这条边要被经过多少次。 把环上的点拉出来为 p 1 , … , p l p_1, \dots, p_l p1,…,pl这条边连接了 p 1 , p l p_1, p_l p1,pl记棋子为 1 1 1空格为 − 1 -1 −1子树和为 a i a_i ai如果这条边被经过了 x x x 次那么最后的答案是 ∑ i ∈ l e f t ∣ a i − x ∣ ∑ i ∈ r i g h t ∣ − a i − x ∣ ∣ − x ∣ \sum_{i \in left} \mid a_i - x \mid \sum_{i \in right} \mid -a_i - x \mid \mid -x \mid ∑i∈left∣ai−x∣∑i∈right∣−ai−x∣∣−x∣。初一数学问题。 最后是奇环情况此时这个环两边的点是同色的操作一次增加或减少 2 2 2 个棋子。 那么断开这条边只要黑白点数的差是偶数就可以利用这条边调整至有解于是先调整有解然后跑树的做法就可以了。 A G C 005 D \mathbb{AGC \ 005 \ D} AGC 005 D
我一眼秒了然后看题解发现推错了一步题解是wgy在两年前写的。 第一步先容斥记 f ( i ) f(i) f(i) 表示至少 i i i 个地方填冲突的方案数于是得到 r e s ∑ i 0 n ( − 1 ) i ( n − i ) ! f ( i ) \begin{aligned} res \sum_{i 0}^{n} (-1)^{i} (n - i)! f(i) \end{aligned} resi0∑n(−1)i(n−i)!f(i)
考虑怎么算这个 f ( i ) f(i) f(i)因为我组合数学撇所以先建图建出来 k k k 条链相当于在这 k k k 条链上选出来 i i i 条边有一个 Θ ( n 2 ) \Theta(n^2) Θ(n2) 的 dp 可以直接做。 A G C 005 E \mathbb{AGC \ 005 \ E} AGC 005 E
感觉很神奇趁还没被题解定式思维先写一下我自己的想法。 可以观察到答案一定是偶数最后一步一定是 B 去抓住 AA 不可能自己撞上去因为他选择停一步会更优。 所以应该是从最后结束或是结束不了的情况入手分析两个人的策略。 首先排除掉无解的情况即是 B 永远抓不到 A利用样例 4看到这种情况下 A 可以反复横跳即是说对于 A 树里面直接相连的 i → j → k i \rightarrow j \rightarrow k i→j→k如果 B 树中直接连接 i , j , k i, j, k i,j,k 的只有 1 1 1 条边那么 A 可以利用这个链一直跳。 那么反过来如果不存在这种情况 B 的策略就应该是一直朝着有 A 的子树里面走A 跑到离 B 最远的点等死就好了
看了题解题解的描述更具体如果一条红边连接了在蓝树上两个距离大于 2 2 2 的点那么只要 A 跑到了这两个点任意一个游戏就不会停止。否则就很好想了此时不存在一条红边连接了蓝树上距离大于 2 2 2 的点根据最先的观察A 最理想的情况一定是跑到蓝树上离 B 的初始点最远的点然后等 B 来找他。
于是这是一个对于先手的单手游戏了对于先手一定需要保持在第 i i i 步走到的节点 p i p_i pi 满足 d i s ( p i , B ) i dis(p_i, B) i dis(pi,B)i 才能保证不被抓住这样 Θ ( n ) \Theta(n) Θ(n) 就能做了。
很牛逼啊为啥最后做法这么简单因为无解的情况自带性质如果有解那么必定使无解的条件不成立。提示是从无解情况出发用无解的性质当条件做题。 A G C 005 F \mathbb{AGC \ 005 \ F} AGC 005 F 这是什么套路我完全不会。 看起来很 dp所以用湘妹儿思考法我来切换主体。 考虑一个点 u u u 对询问 i i i 能造成啥贡献 枚举块的大小得到下面的式子 f u ∑ i 1 n ( ( n i ) − ∑ v ∈ s o n u ( s i z v i ) ) \begin{aligned} f_u \sum_{i 1}^{n} \left( \binom{n}{i} - \sum_{v \in son_u} \binom{siz_v}{i} \right) \\ \end{aligned} fui1∑n((in)−v∈sonu∑(isizv))
哈哈我就会这个 Θ ( n 2 ) \Theta(n^2) Θ(n2) 的暴力。 哈哈切换主体之后换不回来了。 重新定义 f f f 把 f i f_i fi 的下标改成连通块大小。 f i ∑ u 1 n ( ( n i ) − ∑ v ∈ s o n u ( s i z v i ) ) n ( n i ) − ∑ u 1 n ∑ v ∈ s o n u ( s i z v i ) \begin{aligned} f_i \sum_{u 1}^{n} \left( \binom{n}{i} - \sum_{v \in son_u} \binom{siz_v}{i} \right) \\ n\binom{n}{i} - \sum_{u 1}^{n} \sum_{v \in son_u} \binom{siz_v}{i} \end{aligned} fiu1∑n((in)−v∈sonu∑(isizv))n(in)−u1∑nv∈sonu∑(isizv)
然后把 s i z siz siz 相同的子树视为一个整体。记子树大小为 i i i 的子树个数为 c n t i cnt_i cnti改写上面的式子 f i n ( n i ) − ∑ s i z 1 n c n t s i z ( s i z i ) n ( n i ) − ∑ s i z 1 n c n t s i z s i z ! i ! ( s i z − i ) ! n ( n i ) − 1 i ! ∑ s i z 1 n c n t s i z ⋅ s i z ! ( s i z − i ) ! \begin{aligned} f_i n \binom{n}{i} - \sum_{siz 1}^{n} cnt_{siz} \binom{siz}{i} \\ n \binom{n}{i} - \sum_{siz 1}^{n} \frac{cnt_{siz} siz!}{i!(siz - i)!} \\ n \binom{n}{i} - \frac{1}{i!} \sum_{siz 1}^{n} cnt_{siz} \cdot \frac{siz!}{(siz - i)!} \\ \end{aligned} fin(in)−siz1∑ncntsiz(isiz)n(in)−siz1∑ni!(siz−i)!cntsizsiz!n(in)−i!1siz1∑ncntsiz⋅(siz−i)!siz!
记 F ∑ c n t s i z s i z ! , G ∑ 1 ( s i z − i ) ! F \sum cnt_{siz} siz!, G \sum \frac{1}{(siz - i)!} F∑cntsizsiz!,G∑(siz−i)!1 反转一下 G G G 的下标 发后面一坨是具有 juanable 的性质。
现在写完了我觉得说得对没什么困难的地方。 扯淡。那为啥我做不来。 A G C 006 C \mathbb{AGC \ 006 \ C} AGC 006 C
真聪明置换快速幂。 这个期望一眼吧。。。 难点在于需要很快找到换了 k k k 次之后的位置然后发现这个映射和次幂有着相同优美的性质。 于是可以 Θ ( n log k ) \Theta(n \log k) Θ(nlogk) 做了。 A G C 006 E \mathbb{AGC \ 006 \ E} AGC 006 E
这个东西是魔方不让我求步数那我是不是真的可以当魔方做 好复杂先放了。 A G C 006 F \mathbb{AGC \ 006 \ F} AGC 006 F
既视感过于强烈以至于我觉得这就是道傻逼题。 没有手玩能力的我什么时候才会做这种题 《手玩一下》发现可以三染色。 为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手 当 x 1 ≡ y ( m o d 3 ) x 1 \equiv y \pmod 3 x1≡y(mod3) 时 x , y x,y x,y 之间会有连边于是三染色如果染色失败就说明这张图会变成任意两点之间会有连边贡献是 2 s i z 2^{siz} 2siz。 如果只有两种颜色那啥也干不了。 否则记每种颜色点数为 c 0 , c 1 , c 2 c_0, c_1, c_2 c0,c1,c2 贡献是 c 0 c 1 c 1 c 2 c 0 c 2 c_0c_1 c_1c_2 c_0c_2 c0c1c1c2c0c2。 A G C 007 E \mathbb{AGC \ 007 \ E} AGC 007 E
首先二分答案出 m i d mid mid转成判定问题判定能不能使所有叶子之间的路径权值都小于 m i d mid mid。 结合到题目给出的树的特定的形态思考路径有哪些性质对于 u , v u, v u,v 是兄弟节点在访问了其中一个之后一定会马上访问另一个因为每条边只能经过两次更进一步地发现这是在模拟深搜的过程。 考虑把 d f n dfn dfn 序拉出来记 d f n dfn dfn 的反序列为 p p p只保留叶子的信息为 p 1 → p 2 → ⋯ → p k p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_k p1→p2→⋯→pk。 在二分出 m i d mid mid 的情况下这个序列合法当且仅当 ∀ i ∈ [ 1 , k ) , d i s t ( p i , p i 1 ) ≤ m i d \forall i \in [1, k), \mathrm{dist}(p_i, p_{i 1}) \le mid ∀i∈[1,k),dist(pi,pi1)≤mid考察这个序列的生成方式如果叶子节点存在兄弟节点那么这一对将会连续加入序列否则单独加进去。那么对于以 u u u 为根的子树内一定会存在一条跨过左右子树的路径思考这条路径怎么去计算令 s o n 0 , s o n 1 son_0, son_1 son0,son1 分别为 u u u 的两个儿子 l e a f 0 , l e a f 1 leaf_0, leaf_1 leaf0,leaf1 分别为左子树内最后访问的叶子节点和右子树里最先访问的叶子节点那么这条路径 l d i s t ( l e a f 0 , s o n 0 ) d i s t ( s o n 0 , u ) d i s t ( u , s o n 1 ) d i s t ( s o n 1 , l e a f 1 ) l \mathrm{dist}(leaf_0, son_0) \mathrm{dist}(son_0, u) \mathrm{dist}(u, son_1) \mathrm{dist}(son_1, leaf_1) ldist(leaf0,son0)dist(son0,u)dist(u,son1)dist(son1,leaf1)。拆一下中间的 d i s t ( s o n 0 , u ) d i s t ( u , s o n 1 ) \mathrm{dist}(son_0, u) \mathrm{dist}(u, son_1) dist(son0,u)dist(u,son1) 是定值所以决定这条路径的是 d i s t ( l e a f 0 , s o n 0 ) d i s t ( s o n 1 , l e a f 1 ) \mathrm{dist}(leaf_0, son_0) \mathrm{dist}(son_1, leaf_1) dist(leaf0,son0)dist(son1,leaf1)所以现在可以有一个初步的状态为 d p u , l , r dp_{u, l, r} dpu,l,r 表示对于以 u u u 为根的子树内第一个访问到 l l l最后一个访问到 r r r 的过程中路径的最大值转一下 d p u , l , r min { max { d p s o n 0 , l , k 1 , d p s o n 1 , k 2 , r , d i s t ( u , k 1 ) d i s t ( u , k 2 ) } } \begin{aligned} dp_{u, l, r} \min\{ \max\{dp_{son_0, l, k_1},dp_{son_1, k_2, r}, \mathrm{dist}(u, k_1) \mathrm{dist}(u, k_2)\} \} \end{aligned} dpu,l,rmin{max{dpson0,l,k1,dpson1,k2,r,dist(u,k1)dist(u,k2)}}
然后写成判定形式 d p u , l , r d p s o n 0 , l , k 1 d p s o n 1 , k 2 , r [ d i s t ( u , k 1 ) d i s t ( u , k 2 ) ≤ m i d ] \begin{aligned} dp_{u, l, r} dp_{son_0, l, k_1} \ dp_{son_1, k_2, r} \ [\mathrm{dist}(u, k_1) \mathrm{dist}(u, k_2) \le mid] \end{aligned} dpu,l,rdpson0,l,k1dpson1,k2,r[dist(u,k1)dist(u,k2)≤mid]
发现这个状态很蠢。怎么优化不会了。 问题在哪里在于我的状态后两维记录的是叶子节点的编号导致我很难看出关键之处换一下把叶子节点编号直接改成到该叶子节点的距离。 d p u , l , r d p s o n 0 , l , k 1 d p s o n 1 , k 2 , r [ k 1 k 2 ≤ m i d ] \begin{aligned} dp_{u, l, r} dp_{son_0, l, k_1} \ dp_{son_1, k_2, r} \ [ k_1 k_2 \le mid] \end{aligned} dpu,l,rdpson0,l,k1dpson1,k2,r[k1k2≤mid]
突破口在状态本身减少状态数的最直接方法是去掉不必要的状态。也就是说如果存在 l 1 l 2 , r 1 r 2 l_1 l_2, r_1 r_2 l1l2,r1r2那么对于 d p u , l 1 , r 1 dp_{u, l_1, r_1} dpu,l1,r1 来说 d p u , l 2 , r 2 dp_{u, l_2, r_2} dpu,l2,r2 这个状态是没有意义的。 这部就有单调性了吗对于 l l l 升序排那么对应的 r r r 必定是降序。对于 d p x , l , r dp_{x, l, r} dpx,l,r 来说在另一棵子树内能和它合并的状态一定是一个前缀直接双指针就能做到 Θ ( n log 2 n ) \Theta(n \log^2n) Θ(nlog2n)状态数不难分析得到。 A G C 007 F \mathbb{AGC \ 007 \ F} AGC 007 F 拿到这种题完全没有思路。。。开始不了啊。。。 注意可以从特殊情况开始思考首先判掉 S T S T ST。 算是长脑子记住这种生成序列一类的题可以从被生成序列和原序列之间点对点、区间对区间的关系入手。 这题最重要的性质在于将被生成元素和原元素之间连边后所有的边都不相交且一定是一个字符对应一个区间这是由这道题特殊的生成方式决定的重点在于要动手多玩。
得到一个初步的策略对于一个点先尽量往右走走到需要被覆盖的左端点处然后一路复制下来最后一步覆盖掉整个区间。 说得非常抽象具体操作
看了一圈题解感觉抽象。放个代码。
int up n - 1, down n - 1;
while (down 0) {while (down t[down - 1] t[down]) down--;while (up 0 (up down || s[up] ! t[down])) up--;if (up 0) return printf(-1), 0;while (!que.empty() que.front() - (int)que.size() down) que.pop();if (up ! down) que.push(up);res Max(res, (int)que.size() 1);down--;
}A G C 007 D \mathbb{AGC \ 007 \ D} AGC 007 D
n 只小熊我好害怕被小熊打手板
首先观察到一点假设之前给了 i i i 号位上的小熊一颗糖在走到 j j j 之后回头到 i i i 如果能够捡起金币那么再往 j j j 的途中所有的小熊给出的金币都能收集到。所以他的路线应该是走过去折回来走过去折回来一直到终点所有点要么经过一次要么经过三次。然后我会 Θ ( n 2 ) \Theta(n^2) Θ(n2) 大力 dp 了。定义 d p i dp_i dpi 表示 [ 1 , i ] [1, i] [1,i] 中的所有金币都被捡起到达 x i x_i xi 的最小时间那么枚举上一次的转移点 j j j 则 d p i min { d p j c a l ( j 1 , i ) } dp_{i} \min\{dp_{j} cal(j 1, i)\} dpimin{dpjcal(j1,i)}其中 c a l ( j 1 , i ) cal(j 1, i) cal(j1,i) 表示搞定 ( j , i ] (j, i] (j,i] 中间这一段小熊的耗时。~~我搞定很多小熊的耗时。~~耗时为 x i − x j 1 max { 2 ( x i − x j 1 ) , T } x_i - x_{j 1} \max \{ 2(x_i - x_{j 1}), T \} xi−xj1max{2(xi−xj1),T}。然后我不会了。愚蠢啊啊啊 x i − x j 1 x_i - x_{j 1} xi−xj1 全部加起来就是 E E E所以可以忽略去掉这一坨看起来更厉害。 d p i min { d p j max { 2 ( x i − x j 1 ) , T } dp_{i} \min \{ dp_j \max \{ 2(x_i - x_{j 1}), T \} dpimin{dpjmax{2(xi−xj1),T}里面有 max \max max 看起来很不舒服拆一下。要分类讨论。 2 ( x i − x j 1 ) T 2(x_i - x_{j 1}) T 2(xi−xj1)T 则转移是 d p i min { d p j 2 ( x i − x j 1 ) } dp_{i} \min \{ dp_j 2(x_i - x_{j 1}) \} dpimin{dpj2(xi−xj1)} 2 ( x i − x j 1 ) T 2(x_i - x_{j 1}) T 2(xi−xj1)T 则转移是 d p i min { d p j T } dp_{i} \min \{ dp_j T \} dpimin{dpjT}
转移是一次的啊啊啊啊啊啊这个范围直接线段树就行了更牛逼的能单调队列做到 Θ ( n ) \Theta(n) Θ(n)。 A G C 008 E \mathbb{AGC \ 008 \ E} AGC 008 E 既视感过强。 很明显可以先连边看看性质。注意到 a a a 是序列而非排列不能直接往 a i a_i ai 连边那就连 p i → i p_i \rightarrow i pi→i考虑 p p i p_{p_i} ppi 是个啥应该连 p p i → p i p_{p_i} \rightarrow p_i ppi→pi 还是 p p i → i p_{p_i} \rightarrow i ppi→i。 显然保留 p p i → p i p_{p_i} \rightarrow p_i ppi→pi 更好这是一个置换环考虑单看这一堆环能不能发现些性质。 a i a_i ai 要么选 p i p_i pi 要么选 p p i p_{p_i} ppi在图上相当于选一条边的两个端点。 蚌埠住了。我要反向计数。 不会做了。破大放我来看题解。
我是定势思维小丑能不能学会分类讨论
思路是观察图的形态分类讨论。 又臭又长不做了。 A G C 008 F \mathbb{AGC \ 008 \ F} AGC 008 F
没有模数 这次学乖了我从不合法状态开始思考。 什么情况下两个点 ( u , d u ) , ( v , d b ) (u, d_u), (v, d_b) (u,du),(v,db) 染色情况会相同首先这两个点的染色区域一定能互相覆盖考虑到 l c a lca lca 处交汇则还应该满足 d u − d i s t ( l c a , u ) d v − d i s t ( l c a , v ) d_u - \mathrm{dist}(lca, u) d_v - \mathrm{dist}(lca, v) du−dist(lca,u)dv−dist(lca,v)这个条件满足了这两个点染到 l c a lca lca 后继续往上延申或者向 l c a lca lca 的其他子树染色的长度相同。 现在还需要解决从 l c a lca lca 到 u , v u, v u,v 路径上所有点子树内的染色情况一眼看出来这些子树一定被完全染色。这里就有点小问题怎么知道这些子树里距离 u u u 最远的点记 d e p ( u ) \mathrm{dep}(u) dep(u) 表示以 u u u 为根的子树深度的最大值对于从 u u u 到 l c a lca lca 这条路径上的子树内距离 u u u 最远的点可以被刻画为 d e p u − d e p x m a x d e p ( x ) − d e p x dep_{u} - dep_{x} \mathrm{maxdep}(x) - dep_{x} depu−depxmaxdep(x)−depx。记 f ( x ) max { m a x d e p ( y ) − 2 d e p y } , y ∈ s u b t r e e ( x ) f(x) \max \{ \mathrm{maxdep}(y) - 2dep_{y} \}, y \in subtree(x) f(x)max{maxdep(y)−2depy},y∈subtree(x)于是可以算出来一个点涂满这棵子树的耗时记为 t ( l c a , u ) t_{(lca, u)} t(lca,u)。 于是直接枚举 l c a lca lca 去计算不合法的点对数即可具体一点对于 l c a lca lca在其子树内深度相同的点 v , d e p v k v, dep_v k v,depvk 来说能产生的不同涂色方案的贡献是 ∑ v t ( l c a , v ) \sum_{v} t_{(lca, v)} ∑vt(lca,v)发现还是会重。 怎么弄对于 ( u , d ) (u, d) (u,d) 同构的二元组按 u u u 这一维计算不优秀于是按 d d d 来算只统计 d d d 最小时的答案这样就对了。 看了一圈题解什么鬼玩意大家的思考方式都一样是吧。。。 A G C 009 D \mathbb{AGC \ 009 \ D} AGC 009 D
这题意好神奇。这是要求给定树的点分治层数最小值 对就是这个我会求上界是 log \log log。 这 dp 不了了吧。考虑怎么去贪对这个很不熟完全不会。
以 u u u 为中心合并一些等级为 k k k 的子树然后把 u u u 赋为 k 1 k 1 k1现在的目标是最小化最大权值。对于每棵子树记录哪些权值到根的路径上没有更大的权值记为“出现”。合并子树的时候看一下同时有两个出现的最大权值 k k k 是多少然后当前点取 k 1 k 1 k1空间随便开。 A G C 009 E \mathbb{AGC \ 009 \ E} AGC 009 E
注意到它保证了 n m − 1 n m - 1 nm−1 能被 k − 1 k - 1 k−1 整除。这是啥啊 好的一点不会我去看题解了。 这个是人类解法要是下次再看到这种东西我还不会我就吃。
转成 n n n 个叶子节点的 k k k 叉树其中 n n n 个上写着 0 0 0 m m m 个上写着 1 1 1非叶子节点上写着它的 k k k 个儿子的节点的权值的平均值发现最后的权值只和所有标上 1 1 1 的叶子节点的深度有关。 如果一个标上 1 1 1 的叶子节点的深度为 d d d那么到最后它会被除 d d d 次每次都除以 k k k所以贡献是 ( 1 k ) d (\frac{1}{k})^d (k1)d总的贡献是 ∑ i 1 m ( 1 k ) d i \sum_{i 1}^{m} (\frac{1}{k})^{d_i} ∑i1m(k1)di。 所以现在只要能构造出合法的 k k k 叉树就可以了怎么保证合法如果所有的叶子节点上都是 1 1 1那么根节点也是 1 1 1所以只要满足 ∑ i 1 m n ( 1 k ) d i 1 \sum_{i 1}^{m n} (\frac{1}{k})^{d_i} 1 ∑i1mn(k1)di1 即可注意这里的 d d d 是针对所有叶子节点不管上面是否是 0 / 1 0/1 0/1。 然后就可以转换问题了变成有多少个 v a l val val 满足能被写成 ∑ i 1 m ( 1 k ) x i \sum_{i 1}^{m}{(\frac{1}{k})^{x_i}} ∑i1m(k1)xi且 1 − v a l 1 - val 1−val 能被写成 ∑ i 1 n ( 1 k ) y i \sum_{i 1}^{n}(\frac{1}{k})^{y_i} ∑i1n(k1)yi。 这里记 h ( n m − 1 ) / ( k − 1 ) h (n m - 1) / (k - 1) h(nm−1)/(k−1) 即树的高度我这下懂了题目里面的条件是在干嘛了但是直接去枚举每一层的 1 1 1 的个数会算重因为一层里面的 k k k 个 1 1 1 会等价于上一层的一个 1 1 1。 于是去枚举进行了多少次把一层的 k k k 个 1 1 1 换成上一层的 1 1 1 个 1 1 1 的操作记为 X X X。 注意到此时的树高变成了 h − X h - X h−X 1 1 1 的个数少掉了 k − 1 k - 1 k−1 个所以此时保证每一层的 1 1 1 的个数不超过 k − 1 k - 1 k−1 就行了根据先前的思考可以知道最后的答案是一个由 m − k 1 m - k 1 m−k1 个 1 1 1 拼出来的 k k k 进制数。于是 Θ ( n 2 ) \Theta(n^2) Θ(n2) 计算即可。 A G C 010 D \mathbb{AGC \ 010 \ D} AGC 010 D
从最后的状态开始想形式大概是一堆相同的数 x x x 外带一个 x 1 x 1 x1现在不管谁对 x 1 x 1 x1 操作一下剩下的那个人就输了。 感觉这个除以公倍数的操作很难受 A G C 010 E \mathbb{AGC \ 010 \ E} AGC 010 E
思考了 5min 想起来了上周我的做法。 这种东西正着一般不好入手反着想如果两个数不互质那么他们的相对顺序就不会改变。 然后数据范围是 2000 2000 2000 可以直接 Θ ( n 2 ) \Theta(n^2) Θ(n2) 把这样的数对拎出来这样的关系是有传递性的考虑直接建边。最后连出来的图由多个 DAG 组成。 存在博弈的限制先手为了使字典序小在放置原始数列的时候会让每个 DAG 上的点从小往大排列对于后手跑拓扑排序时用优先队列维护即可。 A G C 010 F \mathbb{AGC \ 010 \ F} AGC 010 F
连猜带做蒙过去一个做法但是想了很久不知道怎么证明。
inline bool dfs(int u, int fath) {for (int v : G[u]) if (a[u] a[v] !dfs(v, u)) return true;return false;
}比较直觉如果当前点周围存在一个比他的石子数少并且会使先手失败的点那么我先占据这个点在操作后往这个会失败的点挪如果后手不往回挪他就输掉如果他往回挪我就和他反复横跳因为这时一定是他先耗完。非常对等我把证明看懂了回来补一下。 A G C 012 D \mathbb{AGC \ 012 \ D} AGC 012 D
比较显然的是这个交换的性质是有传递性的。 但是这样只能有一个 Θ ( n 2 ) \Theta(n^2) Θ(n2) 的做法。
往往这种时候一些比较容易的观察可以成为突破口。从不合法的状态入手看看 颜色不同时如果一种颜色中最小的球都无法移动那么这种颜色就被 fix 了可以直接去掉颜色相同时如果某个球和同色最小的球都无法交换或者与其他颜色中最小的球无法交换那么这个球就被 fix 了可以直接去掉。 剩下的球都可以随便移动组合数算算即可。 A G C 012 C \mathbb{AGC \ 012 \ C} AGC 012 C
构造题创思我。 先放前 100 100 100 位为 1 → 100 1 \to 100 1→100现在就变成构造后面一段使得后面一段的上升子序列数为 n n n。 然后考虑从大往小放数字放在前面增加 1 1 1 个放在后面增加一倍做一个二进制拆分就好了。 A G C 013 D \mathbb{AGC \ 013 \ D} AGC 013 D
这道题点出了数形结合的重要性。 虽然不画图也能做但是画图能做到秒杀。 首先发现球的总数不变一个显然的想法是定义 d p i , j dp_{i, j} dpi,j 表示进行了 i i i 次操作现在手头有 j j j 个白球。 转移非常 ez分四种情况按拿出的顺序为 白白黑黑白黑黑白 分类。 问题在于会算重如果把白球个数画成折线图大概是这样。 在上述的计算过程中绿色蓝色和红色代表了三种不同的方案然后这三条线对于的拿出球的序列是一致的不难想到钦定白球在计算过程中降到 0 0 0只统计这一部分的答案。 于是状态多一维表示白球的个数是否降至过 0 0 0但是这样的转移不优美。记没有去重的方案数为 f n , m f_{n, m} fn,m那么最后的答案是 f n , m − f n − 1 , m f_{n, m} - f_{n - 1, m} fn,m−fn−1,m。 非常奇妙其实很好想因为 f n , m f_{n, m} fn,m 比 f n − 1 , m f_{n - 1, m} fn−1,m 多出来的部分即是需要统计的经过了 0 0 0 的折线条数代码也很 ez。 A G C 014 D \mathbb{AGC \ 014 \ D} AGC 014 D
题面写得比较绕意思是问最后能不能存在有白点使得没有黑点和它相连。 树上问题从叶子开始思考套路化地找出后手输掉的情况。存在 u u u 与它相连的有两个叶子节点 v 1 , v 2 v_1, v_2 v1,v2先手先涂掉 u u u后手必须去涂 v 1 v_1 v1 或者 v 2 v_2 v2否则先手可以在下一步就涂掉叶子获胜而在此时后手涂掉了 v 1 v_1 v1 或 v 2 v_2 v2先手涂掉剩下的那个就可以获胜。这是先手必胜的情况启示很大我们直接从这样的情况开始思考每次都删除叶节点和父节点如果过程中出现了孤立的节点则先手获胜。 A G C 015 D \mathbb{AGC \ 015 \ D} AGC 015 D
手玩 很多性质必须搞硬搞感受搞题时的那股劲。
首先干掉 l , r l, r l,r 的相同的前缀因为这一段不管怎么弄都不会变现在我们最高的不同位在 r r r 上是 1 1 1在 l l l 上是 0 0 0然后引入一个数 z z z形式是和 l , r l, r l,r 有着相同的前缀并且在 l , r l, r l,r 最高位不同时该位为 1 1 1后面的低位上全是 0 0 0。 于是把 [ l , r ) [l, r) [l,r) 拆成 [ l , z ) [l, z) [l,z) 和 [ z , r ) [z, r) [z,r)。 容易看出 [ l , r ) [l, r) [l,r) 中的数互相计算的范围还是在 [ l , r ) [l, r) [l,r) 中考虑 [ z , r ) [z, r) [z,r) 怎么算范围 其实也比较容易看出来找到 r r r 中最高不同位下的第一个一令 p p p 为 r r r 从最高不同位往下第一个一后面全部替换成一的值这就是上限。跨区间的范围是 [ l ∣ z , z ∣ ( z − 1 ) ] [l | z, z | (z - 1)] [l∣z,z∣(z−1)]。 A G C 015 E \mathbb{AGC \ 015 \ E} AGC 015 E
脑动模拟一下这个过程一个黑点往右移动然后碰到了一个白点然后使它成为黑点它也开始能染色其他点。这是一个连锁反应似乎很像是 DAG 上拓扑排序但是不一样这道题只需要前面任何一个点是黑点就可以了。
首先假设我已经拿到了这张图如果能做我就思考把这张图建出来否则需要另择其道了。
想了一想发现这张图很大
对于一个点 u u u考虑将能和它相遇的点按相遇的时间排序如果 u u u 能被染色要么它自己本身是黑点要么存在一个点 v v v 在与 u u u 相遇之前就是黑点。
于是我们把每对能相遇的点和相遇时间写成三元组 ( u , v , t ) (u, v, t) (u,v,t)并按 t t t 排序这个感觉不是很好把它放在坐标系里面如果 ( x 1 , v 1 ) (x_1, v_1) (x1,v1) 和 ( x 2 , v 2 ) (x_2, v_2) (x2,v2) 能相遇并且是 x 2 x_2 x2 超过 x 1 x_1 x1 的话则有 x 2 x 1 x_2 x_1 x2x1, v 2 v 1 v_2 v_1 v2v1我们需要按时间排序那么 t x 1 − x 2 v 2 − v 1 t \frac{x_1 - x_2}{v_2 - v_1} tv2−v1x1−x2但是这样看起来不爽令 t ′ x 1 − x 2 v 1 − v 2 t \frac{x_1 - x_2}{v_1 - v_2} t′v1−v2x1−x2于是 t t t 的正序转化为 t ′ t t′ 的逆序斜率越小越先相遇。这就变成了一张图每个点和它左上角区域的点都有连边。所以有一个很厉害的性质对于 ( x , v ) (x, v) (x,v) 是黑点它左上角、右下角、左下角的所有点都能黑。于是题目转化为了给定一堆点选择其中一些能够以覆盖左上角、右下角、左下角的方式覆盖所有点。
怎么弄呢把右上角抠出来只要选出来集合中的点的右上角区域的交越过了所有点的最右端和最高端即可。于是我们直接去计算不合法的方案数即可去钦定最右点和最高点记为 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 和 ( x 2 , y 2 ) (x_2, y_2) (x2,y2)在 ( x 1 , y 2 ) (x_1, y_2) (x1,y2) 范围内的点随便选于是经典套路排一维序另一位用数据结构维护。 于是对 x x x 轴排序依次加入点当前点一定是我们的最右点对于每个不合法高度在更右的点中比该高度还要高维护该高度以内有多少点即可需要离散化。
似乎是全网唯一解因为我这个复杂度不太牛。
update: 哈哈和洛谷第一篇题解前面的步骤一样的但是他发现这个具有可二分性于是上了 dp我做的确实有点小丑了。 A G C 016 D \mathbb{AGC \ 016 \ D} AGC 016 D
看起来好困难。把其中一个变成整个序列的异或未免过于抽象。 让我来手玩一下“把其中一个变成”换一下“把其中异或上其他所有值”。 假设第一次操作了 x 2 x_2 x2 变成 ⨂ i 1 n x i \bigotimes_{i 1}^{n} x_i ⨂i1nxi第二次操作 x 1 x_1 x1 就应该是变成 ⨂ i 1 n x i ⨂ x 1 ⨂ i 3 n x i x 2 \bigotimes_{i 1}^{n} x_i \bigotimes x_1 \bigotimes_{i 3}^{n}x_i x_2 ⨂i1nxi⨂x1⨂i3nxix2。那如果我再操作一次 x 2 x_2 x2 呢 ⨂ i 1 n x i ⨂ x 2 ⨂ i 3 n x i x 1 \bigotimes_{i 1}^{n} x_i \bigotimes x_2 \bigotimes_{i 3}^{n}x_i x_1 ⨂i1nxi⨂x2⨂i3nxix1。
有点牛啊我这样就可以在三步以内做到交换两个位置了所以现在的问题是要使得 A , B A, B A,B 两个序列元素相同。 直觉是我找到 A A A 中和 B B B 不相同的元素那么一定有整个序列异或出来能补上一个没有的元素于是反复操作即可反之无解。 然后发现更牛逼的东西是我可以直接建一个虚的 n 1 n 1 n1 号位这一位就放最开始的异或和所以现在的操作就变成了每次拿一个位置跟 n 1 n 1 n1 换。
然后不是很会建这个图题解的建图比较厉害。 从 b i b_i bi 向 a i a_i ai 连边相同数值对于一个点然后尝试从 ⨂ i 1 n x i \bigotimes_{i 1}^{n} x_i ⨂i1nxi 开始遍历每一条边如果图是一个包含 a l l all all 的连通块则一定可以找到一条欧拉路径不一定是回路覆盖所有边。如果图不连通或 a l l all all 是孤立点则答案就是边数再加上连通块数再减去 1 1 1 如果 a l l all all 是孤立点就不用减 1 1 1。 A G C 017 C \mathbb{AGC \ 017 \ C} AGC 017 C
你确定这个是蓝题 总之这个性质很难。看了兔队的博客大概有点懂了。 在数轴每个位置上挂一根绳子对于每个点 A i k A_i k Aik那就在 k k k 这个位置上加 1 1 1 的长度挂完之后往左拉直如果能覆盖完 [ 0 , n ] [0, n] [0,n]那就没问题否则需要改变的次数是没有被覆盖的位置个数。 A G C 018 D \mathbb{AGC \ 018 \ D} AGC 018 D
感觉和之前的一道题很像啊。这里指 A G C 007 G \mathbb{AGC \ 007 \ G} AGC 007 G。 不一样的点在于这里是哈密顿路径不需要回到起点那么我是不是需要去找一条哈密顿回路然后删一条边 直觉告诉我需要找最长的回路然后去掉最短的边。感觉很对
思考无果去看题解发现结论猜对了但是不会构造。
首先证明这个结论以只有一个重心的情况为例。如果一条哈密顿回路使得重心的每条邻边被经过的次数都取到了最大值那么可以发现其他每条边被经过的次数也取到了最大值也就是说这条哈密顿回路一定是最长的哈密顿回路。 那么一条不是最长的哈密顿回路至少有一条重心的邻边被经过的次数没有取到最大值也就是说它至少比最长的哈密顿回路少了这条边的边权的两倍——那就比我们找到的哈密顿路径短了再去掉一条边只会更短所以我们找到的哈密顿路径一定是最优的。
然后这个证明里有一个《经典结论》取重心外一点做起点以重心做终点存在遍历整个图的方案使得步步跨过重心。
那么唯一一条不会被统计进去的边就是起点到重心于是计算这条边的最小值就好了。 A G C 018 E \mathbb{AGC \ 018 \ E} AGC 018 E / unfinished
看起来非常组合数学往容斥方面想想 给了三个矩形我猜复杂度和中间那个矩形的边长有关应该是要去枚举。 那我就来枚举从 X 3 → X 4 X_3 \to X_4 X3→X4 这个范围。
尝试失败。做过这题的 ly 给我讲这题是要用组合意义继续尝试。
我先想想如何确定唯一路径直接枚举每个矩形里面的三个点显然不对手玩一会发现具体在中间这个矩形里怎么走和在这个矩形里面走的步数有比较强联系再搞一搞发现我只需要知道进入这个矩形的入口和离开这个矩形的出口我就能计算了。 不能一对一枚举出入口但是发现出入口有很强的对称性考虑单独拉出来然后拼一下首先不考虑出入口怎么拼先去计算一下在知道出入口时到另外两个矩阵的方案数这个玩意儿也是对称的来画个图理解一下。 我现在在左下角我要走到右上角蓝色区域我的方案数是 我来想想固定左下角 ( 1 , 1 ) (1, 1) (1,1)右上角在矩形内 ( n , m ) (n, m) (n,m) 我随便走的方案数推推式子枚举停下来的那个点。 ∑ i 1 n ∑ j 1 m ( i j i ) \begin{aligned} \sum_{i 1}^{n} \sum_{j 1}^{m} \binom{i j}{i} \end{aligned} i1∑nj1∑m(iij)
