2018-2019 ACM-ICPC, Asia Shenyang Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 40/549 | 6 | 12 | 13 |
A¶
upsolved by JJLeo
题意¶
一些账号，有的是大号，有的是小号，一个大号能和小号匹配当且仅当它们一个是另一个的前缀，一个大号可以匹配不超过 \(2\) 个小号，一个小号可以匹配不超过 \(1\) 个大号，求匹配可能的方案数。
题解¶
把 Trie 建出来，则两个点能匹配当且仅当它们有祖先关系，设 \(f_{i,j,k}\) 为以 \(i\) 为根的子树中有 \(j\) 个小号没被匹配，还需要 \(k\) 个祖先的小号被匹配，树形背包即可，需要上下界优化。
B¶
upsolved by JJLeo
题意¶
长度为 \(n\) 的文本串和长度为 \(m\) 的模式串，文本串每个位置最多可能是 \(10\) 个字符，给定每个的出现概率，问文本串每个位置和模式串匹配上的概率是多少，要求绝对误差不超过 \(10^{-9}\)。(\(1 \le m \le n \le 3 \times 10^5\))
题解¶
要求绝对误差，因此先默认每个位置是概率最大的那个数，然后枚举匹配起点，不断用 SA 求 LCP 往后跳到第一个失配位置，那么概率最多乘上一个 \(\dfrac{1}{2}\)，从而最多跳 \(O\left(\log 10^{9}\right)\) 次就可以输出 \(0\) 了，时间复杂度为 \(O(n \log n)\)。
C¶
solved by JJLeo
题意¶
忘了
题解¶
寄！
D¶
upsolved by 2sozx
题意¶
一个棵树，边权每秒增加 \(1\) ，\(m\) 次询问，每次询问问时刻 \(t\) 树的直径。\(n\le 2 \times 10^5, m \le 2 \times 10^5, t \le 10^9\)
题解¶
考虑边分治，这样能保证每次合并最多只合并两个链，然后只需要做一个闵可夫斯基和即可。
E¶
solved by JJLeo
题意¶
\(n\) 个忍者，每个忍者有一个二维坐标和一个门派，有三种操作：
- 更改一个忍者的坐标。
- 更改一个忍者的门派。
- 问一个区间，这个区间中门派不同忍者两两之间曼哈顿距离的最大值。
题解¶
经典曼哈顿距离，线段树维护 \(\pm x \pm y\) 每个的最大值和与最大值门派不同的次大值，就没了。
印象里我开了一堆 vector 属于是自暴自弃了。
F¶
upsolved by JJLeo
题意¶
关键词：插值做 dp，得到值，把多项式插回来。
题解¶
有时间再来。
G¶
solved by 2sozx
题意¶
一个二维平面，四种操作：
- \((x,y)\) 添加权值为 \(w\) 的点
- 删除点 \((x,y)\)
- 询问以点 \((x, y)\) 为圆心，半径为 \(\sqrt{k}\) 的圆周上的点的权值和
- 以点 \((x, y)\) 为圆心，半径为 \(\sqrt{k}\) 的圆周上的点的权值增加 \(w\)
强制在线，\(1 \le x, y \le 6000, k \le 10^7\)
题解¶
显然每个 \(k\) 对应的圆周上整点不多，因此可以预处理每个 \(k\) 所能对应的点数，操作时暴力即可，复杂度 \(O(k)\)
H¶
upsolved by
题意¶
彩虹图，Polya，不会，爬。
题解¶
I¶
upsolved by JJLeo
题意¶
当成数位 dp 了，其实不是，就枚举一下就好了。
题解¶
K¶
solved by Bazoka13
题意¶
约瑟夫环问题，崔佬求带。
题解¶
L¶
solved by Bazoka13
题意¶
大几何，崔佬求带。
题解¶
M¶
upsolved by JJLeo
题意¶
可逆 01 背包以及可逆完全背包，把 dp 方程逆过来即可，相当于求对应多项式的逆。
题解¶
记录¶
总结¶
0min：分题，ZYF冲J
10min：ZYF AC ，MJX 把 C 喂给ZYF，一起讨论式子，CSK冲L
82min：C WA2 后AC,MJX 冲 G
121min：CSK WA5 后 AC，马上MJX AC WA3RE1 后 AC，CSK 冲 K，MJX ZYF 看 E
169min：CSK T1 后 AC，冲E
266min：疯狂T+WA后AC，看I
after end：3min写完I，第一次赛后秒过题真刺激
Dirt¶
C(+2):式子推错了
E(+5):传参一定不要传vector，要传只能传指针，TLE后一定要测一下极限数据，pair
G(+4):情况讨论太粗糙了
K(+1):m=1时候需要特判
L(+5):