第46屆ICPC 東亞洲區域賽（澳門）(正式賽）¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 3/166 | 7 | 8 | 11 |
A¶
solved by TYB
题意¶
签到。
题解¶
略。
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by JLK
题意¶
平面上有\(n\)个点，他们两两之间都有一条边。现在从\((0,0)\)开始，要求不经过任意边到达外部（无穷远处），问最少要去掉多少点。
\(1 \le n \le 10^6,-10^9 \le x,y \le 10^9\)
题解¶
不难发现能到达外部一定要满足有一个经过\((0,0)\)的半平面内是没有任何点的。极角排序+双指针扫一下即可。
注意精度。最好用叉积来极角排序。
\(O(n\log n)\)
D¶
**upsolved by **
题意¶
题解¶
E¶
solved by JLK
题意¶
\(n\)个人围成若干个圈，手上有编号和自己编号相同的球，每轮会把球给旁边的人（指定方向），\(q\)次询问\(k_i\)轮后\(\sum\limits_j i\times b_i\)（\(b_i\)为最后在\(i\)手里的球的编号）。
\(2 \le n \le 10^5,1 \le q \le 10^5,1 \le k_i \le 10^9\)
题解¶
每个环考虑，对答案的贡献肯定是以环长为周期。每个小于环长的\(k\)的贡献可以用一遍FFT求出来。具体就是人编号和球编号其中一个倒过来，另一个循环一次，然后卷积。
有可能报精度，可以直接上MTT。
得到答案之后可以按根号分块，小的直接记同一环长的每个\(k\)的总和，大的就暴力记录。
\(O(n\log n+q\sqrt n)\)
F¶
solved by JLK
题意¶
\(n\)个点，每个点有权值\(a_i\)，如果\(a_i\ge n-1\)，那么会分给其他的每个点\(1\)的权值。问最后局面或者输出循环。
\(2 \le n \le 5\times 10^5,0 \le a_i \le 10^9\)
题解¶
一个结论：每次选最大的，尽可能往外分，这样做\(n\)次后如果还没平衡，就会循环。
用线段树或者堆维护一下这个过程。
\(O(n \log n)\)
证明留坑待填。
G¶
solved by TYB
题意¶
给一个\(n\)的排列\(p\)，你可以访问这个排列的前\(k\)个数，需要按顺序访问\(1\sim n\)，如果需要访问的数不在前\(k\)个数中，可将排列向左或向右shift一格，求访问所有\(n\)个数需要shift的最少格数。
\(1\le k\le n\le 10^6\)
题解¶
策略一定是：如果需要访问的数在区间中就不动，否则就要shift，而且只有两种策略：即那个数在shift后区间的左/右端点。所以只有\(2n\)个有效状态，DP即可。
H¶
**upsolved by **
题意¶
题解¶
I¶
solved by YZW
题意¶
串串题。
题解¶
广义 SAM + parent tree 上 kruskal。
J¶
upsolved by TYB
题意¶
维护一棵树，点有颜色，边有边权。开始只有\(1\)号节点，\(q\)次操作，为下面两种之一：
\(1\)、新加入一个节点，其编号为当前节点数\(+1\)，颜色为\(c\)，父亲为\(x\)，边权为\(d\)。
\(2\)、把节点\(x\)的颜色改为\(c\)。
每次操作后输出异色点间的最远距离。
\(q\le5\times10^5\)
题解¶
考虑传统的线段树维护直径的方法：每个节点维护编号在这个区间中的点构成的虚树直径的两个端点，两个区间合并的时候只用考虑共四个端点。
这题可以魔改一下。维护\(q+1\)个二元组\((x,c)\)，表示节点\(x\)的颜色为\(c\)。一开始只有一个二元组，\(q\)次操作可以被拆解为若干个加入/删除某个二元组的操作。线段树维护区间内未被删除的二元组构成的虚树直径的两个端点。
考虑维护每种颜色到其它颜色节点距离的最大值，显然可以通过求出 该颜色的点构成的虚树直径的两个端点 和 其它颜色的点构成的虚树直径的两个端点 后，判断四种情况哪个更大。为了求出上述信息，只需要将二元组按照\(c\)排序即可，这样同样颜色的节点就在一段连续的区间，可以用上面的线段树方法求。
K¶
solved by YZW
题意¶
签到。
题解¶
略。
记录¶
YZW过K(0:15)，TYB过A(0:23)。
JLK写C，WA一次，先扔了。
F猜了个结论，JLK开始写，TLE一次。
C尝试改了下long double就过了(1:22)。
F改了下结论就过了(1:28)。
TYB嘴了E，但是怕FFT精度太差，JLK抄MTT板子，WA一次后AC(2:27)。
随后TYB开始写G，TLE一次后加上读入挂输出挂过了(3:05)。
YZW写I，一发过(3:35)。
JLK嘴了一下J，然后开始猛敲。还剩半个小时的时候发现假了。
然后三人一起看D，没构造出来。
总结¶
JLK：或许开大数据结构题应该至少留两个小时。。
Dirt¶
C(-1)
E(-1)
F(-1)
G(-1)