AGC VP 记录
为了防止上一个内容太多比较卡,故新开了一个。
AGC041~AGC060
AGC060
[AGC060A] No Majority
skip。Submission #69562933 - AtCoder Grand Contest 060
[AGC060B] Unique XOR Path
给定一个 \(n\times m\) 的网格和 \(k\),和一条从 \((1,1)\) 到 \((n,m)\) 的由向下和向右构成的路径,判断能否给每个格子填一个 \([0,2^k-1]\) 的数,满足在所有从 \((1,1)\) 到 \((n,m)\) 的由向下和向右的路径中,给定的路径是唯一一条异或为 \(0\) 的路径。
\(T\le 100,n,m,k\le 30\)
一个初步的想法是,给 \((1,1)\) 填上 \(2^k-1\),然后给每个拐点处填上某个 \(2^p\),于是条件就是拐点数 \(\le k\)。但是这不是充分的,我们考虑,一条路径在每个拐点处都可以换一种拐弯方式,形成一个只和原路径只差一格的路径。设有 \(x\) 个拐点,如果拐点间是独立的,那么相当于是 \(x\) 个数的线性基能否凑出 \(0\),需要有 \(x\le k\)。
但是如果有连续两个拐弯,那么这两个拐弯不是独立的,可以发现连续 \(x\) 个拐弯只需要 \(\lceil\frac x 2\rceil\) 个数即可,所以我们统计出 \(\sum \lceil\frac x 2\rceil\) 即可。最后构造的话,我们将这条路径上的数放 \(0\),拐点处放某个 \(2^p\),然后一直向左下或右上延伸到边缘。
Submission #69563120 - AtCoder Grand Contest 060
[AGC060C] Large Heap
称一个 \(1\sim 2^n-1\) 的排列 \(p\) 是好的,当且仅当 \(\forall 1\le i< 2^{n-1}\),有 \(p_i < p_{2i}\) 且 \(p_i < p_{2i+1}\)。给定 \(a,b\),令 \(u = 2^a,v = 2^{b+1}-1\),求在所有好的排列中任意选一个,\(p_u < p_v\) 的概率是多少。对 \(998244353\) 取模。
\(n\le 5000\)
将 \(p\) 看成一个深度为 \(0\sim n-1\) 的满二叉树,那么条件就相当于一个节点的权值要小于两个儿子的权值,\(u\) 是根节点一直往左走的深度为 \(a\) 的点,\(v\) 是根节点一直往右走的深度为 \(b\) 的点。于是可以将排列看成拓扑序,即在所有拓扑序中任选一个,求 \(u\) 比 \(v\) 先枚举到的概率。
可以发现我们只用关心拓扑时,根节点一直往左走能走到哪,和一直往右走能走到哪,因为拓扑一个其他点对 \(u,v\) 的先后顺序是没有影响的。设 \(f_{x,y}\) 表示根节点往左能走到深度为 \(x\) 的点,往右能走到深度为 \(y\) 的点的状态的概率,然后看下一步会先走哪个子树内的点。
因为是拓扑序,所以下一步会走哪个子树的概率是与子树大小成正比的,两个点的子树大小分别为 \(2^{n-x-1},2^{n-y-1}\),设为 \(p,q\),于是转移为 \(f_{i+1,j}\larr f_{i,j}\frac{p-1}{p-1+q-1},f_{i,j+1}\larr f_{i,j}\frac{q-1}{p-1+q-1}\)。最后答案为 \(\sum\limits_{i=0}^{b-1} f_{a,i}\),复杂度 \(\mathcal{O}(n^2\log n)\)。
Submission #69563199 - AtCoder Grand Contest 060
[AGC060D] Same Descent Set
求有多少个 \(1\sim n\) 的排列对 \((p,q)\) 满足:
- \(\forall 1\le i < n\),\(p_i > p_{i+1}\and q_i > q_{i+1}\) 或 \(p_i < p_{i+1}\and q_i < q_{i+1}\) 中有一个成立。
答案对 \(998244353\) qu'mo
AGC059
[AGC059A] My Last ABC Problem
skip。Submission #69582718 - AtCoder Grand Contest 059
[AGC059B] Arrange Your Balls
skip。Submission #69583068 - AtCoder Grand Contest 059
[AGC059D] Distinct Elements on Subsegments
给定 \(n,k\) 和一个长度为 \(n\) 的序列 \(b\),构造一个长为 \(n+k-1\) 的正整数序列 \(a\),满足 \(\forall 1\le i\le n\),\(b_i\) 等于 \(a_i,a_{i+1},\ldots,a_{i+k-1}\) 中不同的数的个数,或者报告无解。
\(n,k\le 2\times 10^5\)
首先需要满足 \(|b_i-b_{i+1}|\le 1\),我们考虑 \(b_i,b_{i+1}\) 之间的变化代表什么。设 \(l_i\) 表示 \(a_{i-k+1\sim i-1}\) 中是否所有数都和 \(a_i\) 不同,\(r_i\) 表示 \(a_{i+1\sim i+k-1}\) 中是否所有数都和 \(a_i\) 不同,那么有 \(b_i+l_{i+k}-r_i = b_{i+1}\)。所以如果 \(b_i\ne b_{i+1}\),我们就可以确定出 \(r_i,l_{i+k}\) 的值,否则只能确定 \(r_i,l_{i+k}\)。并且还有 \(\sum\limits_{i=1}^k l_i = b_1\),\(\sum\limits_{i=n-k+1}^n r_i = b_n\)。
考虑什么样的序列 \(l,r\) 是合法的,即存在至少一个 \(a\) 对应 \(l,r\)。我们求出 \(nex_i,pre_i\) 表示 \(a_i\) 的前驱、后继,发现知道了前驱后继就可以确定 \(l,r\),我们相当于知道了每个数前驱后继离自己的距离是否 \(<k\)。而因为前驱后继是一一对应的,所以如果某个 \(r_i = 0\),那么 \(l_{nex_i} = 0\),反之同理。所以 \(l\) 中的每个 \(0\) 和 \(r\) 中的 \(0\) 是一一对应的,并且假设 \(l_i\) 对应了 \(r_j\),则需要满足 \(1\le i-j < k\)。
所以我们一一对应的方式一定是 \(l\) 的第 \(i\) 个 \(0\) 匹配 \(r\) 的第 \(i\) 个 \(0\),否则交换了一定更优。设 \(pl_i,pr_i\) 表示 \(l,r\) 中第 \(i\) 个 \(0\) 的位置,则一组 \(l,r\) 合法的条件为 \(l,r\) 中 \(0\) 的个数相等,且 \(1\le pl_i-pr_i < k\)。因为限制条件都是两个值相等,所以 \(l,r\) 中 \(0\) 的个数是否相等是已经确定好了的。接下来我们要设置还没确定的位置使得尽可能满足条件。
假设对于某个 \(i\) 有 \(r_i = l_{i+k}\),如果 \(b_i = b_{i+1} = k\),那么一定有 \(r_i = l_{i+k} = 1\)。否则,将 \(r_i,l_{i+k}\) 全都设置为 \(0\) 一定不劣,因为此时中间至少有两个数相同,即至少一个 \(l\) 和 \(r\) 为 \(0\)。我们开始先将所有 \(0\) 都匹配上,那么将 \(r_i,l_{i+k}\) 设为 \(0\) 就是调整中间的一些匹配,原来满足条件的现在依然是满足条件的,而如果原来中间有不能匹配的现在就可能可以匹配了,所以这样做一定不劣。
于是我们直接将所有这样的 \(l_{i+k},r_i\) 设为 \(0\),而对于 \(b_1\),一定是将 \(1\sim b_1\) 设为 \(1\),因为这些位置前面的数不足 \(k\) 个,所以 \(0\) 越靠近中间越好,\(b_n\) 同理。设置完之后判断一下即可,最后构造就是从前往后枚举,如果有匹配的前驱就设为前驱,否则就设为一个新的数。复杂度 \(\mathcal{O}(n)\)。
Submission #69589075 - AtCoder Grand Contest 059
[AGC059E] Grid 3-coloring
有一个 \(n\times n\) 的矩阵,共有三种颜色,给定了最外面一层的颜色,求是否存在一种染色方案,使得相邻格子颜色不同。
\(n\le 2\times 10^5\)
神仙题。
矩阵存在一种染色方案,设 \(c_{i,j}\) 表示颜色,则我们一定能给每个格子赋一个整数权值 \(d_{i,j}\),满足 \(c_{i,j}\equiv d_{i,j}\pmod 3\),并且相邻两个格子权值相差 \(1\)。考虑证明,我们发现对于一种染色方案,只要确定了某个格子的权值,就能确定整个矩阵的权值。并且对于每个 \(2\times 2\) 的子矩阵,根据左上角的权值算出来的另外三个权值一定都满足限制,即如果左下角颜色等于右上角颜色,则右下角权值一定同时符合条件;如果左下角不等于右上角,则右下角权值一定等于左下角权值,且也符合条件。
于是问题就变成了是否存在一个合法的赋权值方案满足条件,我们首先设 \(d_{1,1}=c_{1,1}\),然后就可以算出整个外层的权值,先判断这个环的头尾的权值是否满足条件。接下来我们继续找必要条件,发现对于任意两个点 \((i,j),(i',j')\),这两个点的权值之差一定不超过它们的曼哈顿距离,即 \(|d_{i,j}-d_{i',j'}|\le |i-i'|+|j-j'|\)。而如果有这样的两个两个点不满足条件,一定是正方形的两条对边上,假设是左边和右边,我们将右边的点的横坐标设为左边点的横坐标,此时这个两个点依然不合法,所以只需要判断所有相对的两个点即可。
如果所有点都满足条件,那么一定有解,我们可以构造 \(d_{i,j} = \max\{d_{i,1}-(j-1),d_{i,n}-(n-j),d_{1,j}-(i-1),d_{n,j}-(n-i)\}\)。这样子最外层的点一定都满足条件,并且相邻两个点差不超过 \(1\),而且每个值的奇偶性都和 \(i+j\) 相同,所以一定有相邻两个格子权值差为 \(1\)。
Submission #69586467 - AtCoder Grand Contest 059