Replacement Contest 1¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 28/59 | 5 | 5 | 12 |
A¶
upsolved by
题意¶
题解¶
B¶
solved by JLK&TYB
题意¶
给定\(n\)个数\(a_i\)和\(m\)个数\(b_i\)，用这两个序列构造出一个矩阵，其中第\(i\)行第\(j\)列的数为\(LCM(a_i,b_j)\)。
求有多少对数列\(c,d\)也能生成同样的矩阵。
\(1 \le n,m \le 10^5，1 \le a_i,b_i \le 10^9\)
题解¶
显然这个矩阵和\(a_i,b_i\)数列内数的顺序无关，可以任意排序。相当于给个映射。
首先可以对每个质因子分开考虑。用因子\(p\)构造出一个矩阵，其中第\(i\)行第\(j\)列为\(a_i,b_j\)中\(p\)的指数的最大值。只要\(c,d\)和\(a,b\)在每个质因子下生成的矩阵都相同即可。答案是对每个质因子的方案相乘。
那么考虑\(p\)的贡献。得到\(f_i,g_i\)分别为\(a_i,b_i\)的\(p\)的指数。然后把\(f_i,g_i\)各自升序排序，然后看生成的矩阵。实际上只有最左上角的一块矩阵是可以有不同方案的。其它的矩阵的格子一定能限制到\(f_i\)和\(g_i\)。
然后左上角这一块矩阵的值为\(M=\max\{a_1,b_1\}\)。不同方案的数量为\((M+1)^x+(M+1)^y-1\)。因为如果上面有一个数不是\(M\)，那么就限制了左边一定要全部为\(M\)，左边同理，减去所有都为\(M\)的情况。
而实际上不需要枚举所有因子，如果\(M=1\)，那么是对答案没贡献的。只有\(a_i\)的gcd以及\(b_i\)的gcd各自的质因子会有贡献。只枚举这些质因子就跑的很快了。
\(O(n\log a_i)\)
C¶
upsolved by
题意¶
题解¶
D¶
upsolved by
题意¶
题解¶
E¶
solved by TYB
题意¶
\(n\times m\)的方格矩阵，其中一些格子是炸弹，一些是水晶，每个炸弹可以选择引爆其所在的行或列，若引爆了其它炸弹，则该炸弹也选择一个方向引爆，一开始选择其中一个炸弹引爆，求最多引爆多少水晶。
\(n,m\le3000\)
题解¶
考虑每个炸弹向它上下左右的第一个炸弹连边，这样就连出了若干个连通块，这样我们可以单独考虑每个连通块，因为它们之间不会引爆。若一个连通块有环，那么只要引爆环中的一个炸弹，就可以把这个连通块涉及到的所有行列都引爆，获得这些行列上的所有水晶；若没有环，那么最优解一定是选择某个左右/上下没有其它炸弹的炸弹，将它竖着/横着引爆（可以画个图感受一下其正确性），对比上一种情况，这样只会损失掉某一行或某一列的水晶，减去这些即可。
时间复杂度\(\mathcal{O}(nm)\)，有点卡空间，实现的时候需要精细一点。
F¶
solved by YZW
题意¶
题解¶
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
K¶
solved by JLK
题意¶
有\(n\)个数，对于两个相邻的数，如果有\(a_i+a_{i+1}\le K\)，则可以交换\(a_i,a_{i+1}\)。问最后能得到多少不同的数列。（相同的数看做一样）
\(1 \le n \le 10^5,0 \le K \le 2\times 10^9\)
题解¶
从小到大考虑移动每个数。对于数\(x\)，可以移动的区间肯定是一块一块的。假设\(x\)可以在\(L_i,R_i\)移动，并且\([L_i,R_i]\)里有\(y\)个\(x\)，那么\(x\)自由移动的方案数是\(C_{R_i-L_i+1}^y\)。
直接这样算显然会重复。但是考虑大的数的时候可以直接忽视小的数。即在算完\(x\)之后就把所有\(x\)全部删去。
因为大的数的移动区间一定是小的数的区间的子集，大的数和小的数的关系可以看做实际上在小的数移动的时候已经确定了。例如，1 2移动，可以看成1在两个位置移动，2只能在一个位置移动，也就是不动。
用BIT维护一下信息即可。\(O(nlogn)\)
L¶
solved by JLK
题意¶
给定一个长度为\(n\)的01串，一次操作可以把任意一个字符移动到结尾，问最少多少次操作可以构成一个回文串。
\(1 \le n \le 300\)
题解¶
实际上一种操作方案可以看做是从原序列中取出若干0/1，然后任意排列放到原序列的最后。
考虑这样的一个DP：\(dp_{i,j,k}\)表示考虑了前\(i\)个位置，取出了/还需要取出\(j\)个0，\(k\)个1的最小操作次数。这里的一个合法状态是指已经在序列最后插入了一些数，使得前\(i\)个位置中，没有被取走的元素和序列最后的数可以构成回文。“还需要取出”就相当于是先欠着，等到\(i\)到后面的时候再取出对应的数。
转移就是对\(s_i\)分类讨论，要满足回文，就要取出\(s_i\)或者插入一个和\(s_i\)相同的数到后面。
然后对于每个\(dp_{i,j,k}\)，考虑操作结束时的情况。因为在这样对称的DP考虑中，只能DP到中点之前的位置。最后剩下中间的一串需要另外处理。
一种情况是，原序列剩下的长度小于等于\(\lfloor\frac n2\rfloor\)。这种情况下取出的数更多，把原序列剩下的数匹配完之后，还需要在最中间构成一个回文串。例如：01111，取出011，匹配完之后是11x11，0一个数字构成回文串并放在中间。
这种情况要求\(j,k\ge 0\)。只需要判断最后剩下的0/1数量能否构成回文串即可。
另一种情况是，原序列剩下的长度大于\(\lfloor\frac n2\rfloor\)。这种情况下就是要判断\(s[i+1,n]\)中取出了若干0/1之后能否构成一个回文串。这种情况要求\(j,k\le 0\)，也就是还需要在\(s[i+1,n]\)取出一些0和1。
考虑预处理一个四维的数组\(f_{i,j,k,l}\)表示\(s[i,j]\)取出\(k\)个0，\(l\)个1的情况下能否构成一个回文串。这样为\(O(n^4)\)。但是可以把一维下标放到值域里。\(f_{i,j,k}\)表示\(s[i,j]\)取出\(k\)个0，最少需要取出多少1才能构成一个回文串。因为如果取出\(l\)个1能回文，那么\(l+2t\)也可以。只需要对\(l\)的奇偶分别处理一下即可。
\(O(n^3)\)，注意空间大小，需要滚动。
记录¶
YZW写F，WA一次后AC(0:11)。
然后YZW试了一下H，WA一次后觉得不太可做，扔了。(0:52)
JLK过K(1:23)，然后和TYB讨论后过了B(2:02)。
剩下CEGL，两个IQ题都不太会，最后JLK尝试L，TYB和YZW讨论E。
L WA两次后对拍改过了(4:13)。
TYB冲E，MLE一次WA一次后AC(4:53)。
总结¶
Dirt¶
E(-2)
F(-1)
L(-2)