2018-2019 ICPC Southwestern European Regional Programming Contest (SWERC 2018)¶
2021 BUAA Spring Training 7¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 1/14 | 10 | 11 | 11 |
A.City of Lights¶
solved by JLK
题意¶
\(N\)个点排成序列，初值为0，\(K\)个操作，每次把给定\(x\)的倍数位置异或1，问同时为1的最多点数。
\(1\le N \le 10^6,1 \le K \le 100,1 \le x \le N\)
题解¶
模拟即可，\(O(nK)\)
B.Blurred Pictures¶
solved by JLK
题意¶
有一个\(N\times N\)的方格，每一行有且仅有一段连续的1，其列数为\([a_i,b_i]\)，且相邻两行一定有一列同时为1。求内部及边界全部为1的矩阵最大边长。
\(0 \lt N \le 10^5，0 \le a_i \le b_i \lt N\)
题解¶
答案显然满足单调性，二分答案\(mid\)，每次在\([0,n-mid]\)枚举上边界，只要\([i,i+mid-1]\)里\(\min\{b_i\}-\max\{a_i\}+1\ge mid\)，就能保证答案\(\ge mid\)。如果用ST表，就可以做到\(O(1)\)查询，总复杂度\(O(NlogN)\)
C.Crosswords¶
solved by Snakes
题意¶
给定 \(N\times M\) 的方格，\(A\) 个词长为 \(N\) 的纵向单词表，\(B\) 个词长为 \(M\) 的横向单词表，要求每列从上往下读均在纵向单词表中，每行从左往右读均在横向单词表中，求合法填方格的方案数。保证所给单词来自词典。
\(2\leq N,M\leq 4, 1\leq A\times B\leq 1008016\)
题解¶
由于单词来源字典，方案数不会很多，爆搜+剪枝即可。
D.Monument Tour¶
solved by JLK
题意¶
有一个\(X\times Y\)的网格，只能走网格边。有\(N\)个给定点。要选一行作为主干道，从左走到右，要求在每一列都要离开主干道，经过给定点，然后回到主干道才能继续向右走。求最短路程。
\(1 \le X,Y \le 10^5,1 \le N \le 10^5,0 \le x_i \lt X,0 \le y_i \lt Y\)
题解¶
Sol.1¶
每一列的点只需要记录最上和最下。假设主干道为第\(p\)行，那么（1）当\(p \le up\)时贡献为\(2*(dn-p)\)，（2）当\(p \ge dn\)时贡献为\(2*(p-up)\)，（3）在中间时贡献为\(2*(dn-up)\)。可以从上往下扫\(p\)，一开始处理出\(p=0\)的路程，然后每一列的贡献可以看做是差分，\(p\)在上面的时候每移动一次贡献-2，在下面的时候+2，用差分数组维护一下贡献即可。
\(O(X)\)
Sol.2¶
题解给了一个求中位数的做法。只需把每列的最小值最大值都拎出来求中位数即为最优的选择。
赛时想了中位数，不过否掉了。
直观理解就是，在中位数的位置，（3）的区间会导致中位数左边和右边各有一个点，是平衡的。而去掉这些点后，由于是中位数，左边的(2)和右边的(1)区间个数也相等，也是平衡的。可以用数学里的绝对值不等式理解一下。
E.Rounding¶
solved by TYB
题意¶
一项调查人数为\(10000\)的调查，每人选择\(P\)个选项之一，给出\(P\)个选项四舍五入后的选择人数百分比，求每个选项四舍五入前的百分比最大最小值。
\(1\le P\le 10000\)
题解¶
注意到总人数固定，可将百分比转化为人数以避免误差。随后求出每个选项选择人数的上下限，简单判断即可。
F.Paris by Night¶
**solved by JLK **
题意¶
有\(N\)个点，选两个点，将两者连线后将整个平面分成两个区域，对每个区域的点求权值和，然后求两个区域的差值的绝对值，输出这个值的最小值。没有三点共线。
\(2 \le N \le 4000,0 \le X,Y \le 10^9,1 \le val \le 10^9\)
题解¶
极角排序裸题。枚举一个点，将其他点按极角排序，然后按圆周扫过去统计权值即可。
\(O(n^2logn)\)
G.Strings¶
solved by JLK
题意¶
给定一个字符串\(S(0)\)，有\(N-1\)次操作：
1、\(SUB \ \ x\ \ lo\ \ hi\)表示\(S(i)\)为\(S(x)[lo,hi)\)
2、\(APP\ \ x\ \ y\)表示\(S(i)=S(x)+S(y)\)
求\(S(N-1)\)所有字符的ASCII码之和。
\(1 \le N \le 2500 ,1 \le len(S(0)) \le 1000,len(S(i))\le 2^{63}-1\)
题解¶
Sol.1¶
我的解法是，先正着求出每个字符串的长度，然后从后往前推。\((l,r,x)\)表示要求\([l,r]\)的所有字符ASCII码乘以\(x\)。对于1操作，直接推到\((l+lo,r+lo,x)\)即可。对于2操作，有可能直接推过去，也有可能会在中间切开分到两个字符串里。为了保证复杂度，只让询问被切一次，那么对于每个字符串把询问区间重构，碰到一个区间端点就切开。例如\([a,c]\)和\([b,d]\)，变成\([a,b-1],[b,c],[c+1,d]\)。这样每次2操作其实本质上只会加一个区间，每次的询问个数是\(O(N)\)级别的。最后根据推到\(S(0)\)的询问求即可。
\(O(N^2)\)
Sol.2¶
将\(S(0)\)的每个子串当做树的叶子结点，每次操作可以在树上新建节点，最后是一个二叉树（可以有重复的儿子）。每次暴力找儿子连边。
2操作，直接把\(x,y\)当成两个儿子即可。
1操作，递归下去，如果要被切开，就新建一个节点，然后递归左右儿子。由于切开之后一定是前后缀，再切的时候必定会有一个是完整的区间。于是一次最多加\(O(N)\)个节点。
最后点数\(O(N^2)\)，深度\(O(N)\)。
总复杂度也是\(O(N^2)\)。
Sol.3¶
记忆化搜索，复杂度类似Sol.2。
H.Travel Guide¶
solved by Snakes
题意¶
给一张无向图，有三个特殊点 \(0,1,2\)，点 \(u\) 到三个特殊点的最短距离不妨记为 \((d_{0,u},d_{1,u},d_{2,u})\)。
定义 \((a,b,c)<(d,e,f)\) 当且仅当 \(a\leq d,b\leq e,c\leq f\) 均成立且 \(a<d,b<e,c<f\) 至少成立其一。
求满足不存在 \(v\) 使得 \((d_{0,v},d_{1,v},d_{2,v})<(d_{0,u},d_{1,u},d_{2,u})\) 的点 \(u\) 的数量。
\(4\leq N\leq 10^5, E\leq 5\times 10^5, 1\leq w\leq 100\)
题解¶
三次堆优化 Dijkstra 最短路 + cdq 分治套树状数组做三维偏序。
\(O(3E\log E+N\log ^2 N)\)
I.Mason's Mark¶
solved by TYB
题意¶
给出一个\(N\times M\)的\(01\)矩阵和图形\(A\)、\(B\)、\(C\)的定义，且将周围八连通都是\(0\)的\(1\)视为噪点，求去除噪点后矩阵中每个字母的数量。
\(N,M\le 1000\)
题解¶
先去除噪点，然后求出矩阵前缀和，对每个\(1\)的四连通连通块暴力判断是否为三个字母之一即可。
J.Mona Lisa¶
upsolved by Snakes
题意¶
给定四个 64 位随机生成器的种子，以及目标位数 \(N\)，求 \(a,b,c,d\) 使得四个随机生成器依次生成第 \(a,b,c,d\) 个随机数的异或和最低 \(N\) 位为零。
\(1\leq N\leq 50\)
题解¶
一个简单的想法是取两个生成器，第一个生成 \(A\) 个数，第二个生成 \(B\) 个数，meet-in-the-middle 尝试碰撞得到异或和为零（或者特定值）的 pair，得到解的概率是 \(1-(1-A/2^N)^B\sim 1-(1-AB/2^N)=AB/2^N\)，取 \(A=B\sim 2^{N/2}\) 概率较大。此时时空复杂度 \(O(2^{N/2})\)（事实上 hash 常数较大），无法通过。
利用另外两个生成器，碰撞出两组（生成器 1,2 与生成器 3,4）异或和后 \(N/3\) 位为零的 pair，再在两组之间碰撞出异或和为零的四元组。
第二次碰撞得到一组解的概率是 \(1-(1-A/2^{2N/3})^A\sim A^2/2^{2N/3}\)，需要 \(A\sim 2^{N/3}\)。
第一次碰撞得到一组解的概率是 \(1-(1-B/2^{N/3})^B\sim B^2/2^{N/3}\)，得到一组解需要 \(B\sim 2^{N/6}\)，得到 \(2^{N/3}\) 组解需要 \(B\sim 2^{N/6}\times 2^{N/6}=2^{N/3}\)。
时间复杂度 \(O(2^{N/3})\)。
K.Dishonest Driver¶
solved by Snakes
题意¶
给定长为 \(N\) 的串，可以任意将其按循环节压缩多次（e.g. \(\text{abcabcabc}\to(\text{abc})^3\)，\(\text{aaabbaaabb}\to((\text{a})^3(\text{b})^2)^2\)），求压缩后字符串中字母最少个数。
题解¶
简单的区间 DP，由于时限较长（6s），枚举子串长度的因数暴力判断子串循环节也可 AC。
\(O(n^3\log n)\) （跑不满）
KMP 可以去掉复杂度的 \(\log\)。
记录¶
2min:JLK AC A
9min:YZW AC K
17min:JLK WA B(-1)（ST表写烂了+某个循环没写等于）
24min:JLK AC B
34min:TYB AC E，YZW开始写H
57min:JLK AC D（打断H*1）
1h45min:JLK AC F（打断H*2）
1h51min:YZW AC H
2h39min:TYB WA I(-1)（没有去除噪点）
2h43min:TYB AC I
3h29min:JLK WA G(-1)（没有处理结果模出负数的情况）
3h53min:JLK AC G
3h59min:YZW AC C
4h~5h:J TLE+MLE(-9)
总结¶
本场题目较为良心，前期手速也比较快，罚时很低。
为了开简单题而打断码农题是明智的。
对于某些没有头绪的题目可以大力出奇迹。
注意题目带有的《随机》等条件，如《字典》中选取单词代表一定程度是随机的（没有构造数据）。（TYB：我应该去读一遍题发现这个条件，而不是一直空想）
Dirt¶
B(-1)
G(-1)
I(-1)