Ptz Camp 2021s Day 1: Kyoto U Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 18/90 | 8 | 8 | 13 |
A¶
solved by JLK
题意¶
签到，略
题解¶
B¶
solved by JLK
题意¶
签到，略
题解¶
C¶
solved by JLK
题意¶
提答题。构造一个\(n\times n\)的由小写字母组成的字符矩阵，要求所有行的所有子串和所有列的所有子串放在一起比较，两两都不同。
\(13 \le n \le 100\)
题解¶
显然\(n\)越小越好构造。
本质上只需要让所有长度为2的子串不相同即可。
从上到下，从左到右枚举，每次找到合法的（不会和前面的长度为2的子串重复的）字符随机一个填进去即可。这样可以直接构造出来。
D¶
solved by YZW
题意¶
题解¶
E¶
solved by TYB
题意¶
给出三个数组\(\{a_n\},\{b_n\},\{c_n\}\)，将\([1,n]\)划分为若干段\([l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\)，要求所有区间不重合且并集为\([1,n]\)，定义第\(i\)段的权值为\(\sum_{j=l_i}^{r_i}a_j+b_{l_i}+c_{r_i}\)，一种划分方案的权值为每段权值的最小值，求所有划分方案中最大权值为多少。
\(n\le2\times10^5,-10^9\le a_i,b_i,c_i\le10^9\)
题解¶
二分答案，再把前缀和略作修改，令\(s_1[i]=\sum_{j=1}^ia[j]-b[i+1],s_2[i]=\sum_{j=1}^ia[j]+c[i]\)，就可以快速求出一段区间的权值。然后扫一遍，判断每个点\(i\)作为右端点是否存在可行的划分方案，需要维护当前所有可行的右端点\(x\)中最小的\(s_1[x]\)，若\(s_2[i]-s_1[x]\ge mid\)则可行，再更新一下这个最小值即可。
F¶
solved by JLK
题意¶
一个\(H\times W\)的方格，有\(A,B,C,D\)四个数组。每个\((i,j)\)到\((i+1,j)\)有一条边权为\(A_i+B_j\)的边，到\((i,j+1)\)有一条边权为\(C_i+D_j\)的边。求最小生成树。
\(2 \le H,W \le 10^5,1 \le A,B,C,D \le 10^6\)且均单调递增。
题解¶
一个点连出去的四条边里，边权最小的边肯定是向上或者向左。那么最小生成树里也一定有这两条边之一。
考虑快速判断哪些点向上，哪些点向右。
如果选向左的，那么就是\(A_{i-1}+B_j \le C_i+D_{j-1}\)。移项，得到\(A_{i-1}-C_i\le D_{j-1}-B_j\)。
那么预处理对\(D_{j-1}-B_j\)排序。枚举\(i\)，对于每一行，二分出一个分界线，一边是全部用向左的边，一边是全部用向上的边，再前缀和维护一下即可。
\(O(HWlogW)\)
G¶
solved by JLK
题意¶
初始有一个序列\(S=\{1\}\)。进行\(n\)次操作，每次操作可以是：
在序列最后面加入一个1或加入一个\(m\)。
在已经生成的序列里，找到一个\(i\)和\(x\)，插入\(x\)，使得\(S_i \lt x \lt S_{i+1}\)或\(S_i \gt x \gt S_{i+1}\)。
问不同的操作方案有多少。
\(1 \le n \le 3000,1 \le m \le 10^8\)。
题解¶
最终得到的序列可以看做是在一堆1和\(m\)里插入一些数。而且每一段\(1\to m\)和\(m\to 1\)的所有数字都是单调的。
先考虑只有一段单调区间的操作方案数。不管这个区间是\(1\to m\)还是\(m\to1\)，方案数都是一样的。假设插入了\(i\)个数，那么就相当于是先选出\(i\)个数，再按一定顺序插入。操作方案数为\(C_{m-2}^i\times i!=\prod\limits_{j=m-1-i}^{m-2}j\)。设其为\(g_i\)。
如果有很多段单调区间，设某一段的两端下标分别为\(j,i\)，考虑这一段的贡献。这一段的起止端点肯定是最先插入的，而最终在这一段中间的数可能是在之后才插入。确定这一段的两个端点之后还需进行的总操作数是确定的，即\(n-j\)。那么可能的操作方案数就是在\(n-j\)个操作里选出\(i-j-1\)个位置进行这一段区间的操作，即\(g_{i-j-1}\times C_{n-j}^{i-j-1}\)。
这样就可以DP转移了。\(f_i\)表示前\(i\)个位置的贡献。枚举新的单调区间从哪里开始。
\(f_i=f_{i-1}+\sum\limits_{j=1}^{i-1}f_j\times g_{i-j-1}\times C_{n-j}^{i-j-1}\)。（\(f_{i-1}\)是指出现11,mm这样的序列）
\(O(n^2)\)
H¶
solved by TYB
题意¶
一个\(n\times m\)的方格图，其中一些点有一个豆子（所有豆子互不相同），一些点是障碍点不能走，每行是一个环，即\((x,1)\)向左走到\((x,m)\)，\((x,m)\)向右走到\((x,1)\)。两人玩游戏，每人轮流选择一个豆子移动，可以向左右下可以走的点移动，但不能到这个豆子到过的点，多个豆子可以同时在一个点，不能移动的人输，求谁赢。
\(n,m\le1000\)
题解¶
有一个很显然的做法，对于每个\((x,y)\)，设三种状态，只能向左走、只能向右走、两边都可以走，这样规定了一个方向，就可以处理不能到重复点的问题，然后就可以直接计算SG值了。但是这样做在某一行没有障碍点的时候会有问题，因为每行是一个环，即使规定了移动的方向，也有可能经过重复的点，如果要记录经过的区间，状态数是\(\mathcal{O}(n^3)\)的，不可承受。考虑如何计算这种情况的SG值。
可能有三种走法，向下走简单，向左和向右类似，以向左为例。若一行中第\(i\)个格子只能向左走，即可以依次经过\(i-1,i-2,\dots,1,m,m-1,\dots,i+1\)，但SG值要倒着推，也就是从\(i+1\)这个格子一路向右推过来。注意到这段路线实际上由两段连续的区间组成，且SG值\(\le3\)，我们可以通过预处理加速求SG值的过程。具体来说，预处理两个东西，\(b[u][i]\)表示如果\(i\)这个位置的SG值是\(u\)，一路向右推，\(m\)这个位置的SG值是多少；\(a[u][i]\)表示假设\(0\)的位置有一个SG值为\(u\)的，从\(1\)一路向右推到\(i\)，\(i\)的SG值是多少。预处理这些信息即可。
复杂度\(\mathcal{O}(nm)\)。
I¶
**upsolved by **
题意¶
题解¶
J¶
**upsolved by **
题意¶
题解¶
K¶
**upsolved by **
题意¶
题解¶
L¶
**upsolved by **
题意¶
题解¶
M¶
**upsolved by **
题意¶
题解¶
记录¶
开局JLK签A(0:03)B(0:10)F(0:42)。
TYB过E(0:55)。
JLK和YZW讨论C，JLK随机摸了几下然后就对了(1:16)。
YZW抄板子试了一下M，TLE。
TYB写H，调了一万年，WA两次后YZW突然会D了，于是AC(4:08)。
JLK写G，同时TYB看H代码，改了一下又WA了。
JLK过G(4:20)，TYB又WA了一发后AC(4:38)。
然后下班。
总结¶
JLK:感觉发挥还算可以，就是中间真空期有点大。
Dirt¶
H(-4)