Northern Eurasia Finals Online 2020¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 84/? | 7 | 8 | 15 |
A¶
solved by JLK
题意¶
有\(A\)个权值为\(1\)的结点，\(B\)个权值为\(2\)的结点。要求用这些点构造一棵平衡二叉树（左右子树权值和之差至多为1）。
\(1 \le A+B \le 10^5\)
题解¶
一种构造方法：
因为\(1\)比较灵活，所以尽可能让\(2\)在两边是平衡的。
如果\(B\)为奇数，那么让当前的根节点为\(2\)，然后均分到子树里，解决子问题。
如果\(B\)为偶数，那么让当前的根节点为\(1\)，然后均分到子树里，解决子问题。
如果\(A=0\)且\(B\)不为奇数，就无解。
B¶
**upsolved by **
题意¶
题解¶
C¶
solved by JLK
题意¶
一棵以\(1\)为根的树，初始除了根都是绿色，根是红色。每次要选一个点反色，反色后满足所有红色点是包含根的一个连通块，并且这个状态之前没有出现过。求最多操作多少次和方案。
\(1 \le n \le 20\)
题解¶
其实次数就是状态数。也就是每个合法状态都能被转移到。
对于每个子树，可以先解决所有儿子的子树的子问题，然后考虑合并。
如果有两个子树\(A,B\)，得到了子树里的子问题的解，要合并的话，可以在\(A\)的每个操作中间（以及开始的时候）插入所有\(B\)的操作（第一次正着，第二次倒着，以此类推）。这样就可以把\(A\)和\(B\)的所有状态都遍历到。
有多个的话也可以类似合并，每次注意一下正着还是倒着即可。
\(O(n2^n)\)
D¶
solved by TYB
题意¶
有一个高度为\(n\)的颜色方格，每一行有\(8\)个字符，其中\(W\)代表白色，\(R\)代表红色。
现在要求你输出\(n\)个数，其中第\(k\)个数代表\([1,k]\)为被激活的行的游戏结果。
游戏规则如下：
最初一个手帕放在第\(1\)行，你可以将其按照下列法则向下移动：
对于每一行\(i\in[1,n]\)，你可以移动到\(j\in[i+1,\min(i+8,n)]\)当且仅当第\(i\)行和第\(j\)行的相同颜色方块个数\(num\)满足：\(j−i\le num\)。
且只能移动到被激活的行，如果某个玩家无法移动，则输。
双人均采用对其最优策略的。输出中\(1\)代表先手必胜，\(2\)代表后手必胜。
（上网抄的，懒得概括了）
题解¶
显然暴力是\(\mathcal{O}(n^2)\)的，考虑优化。
暴力做法的问题是对于每次询问，都必须从当前行倒着往上递推到第一行，无法利用之前DP得到的信息，考虑优化。
一个很重要的性质是，每一行的胜负状态只与其下面最多\(8\)行的胜负状态有关，因此可以设\(f_{i,S}\)表示第\(i\)行往上\(8\)行的胜负状态为\(S\)的情况下，先手必胜还是必败。直接递推即可。
优化可以考虑记忆化搜索，因为很多状态都是不可能到达的。但直接跑也很快，也就无所谓了。
E¶
solved by YZW
题意¶
题解¶
F¶
**upsolved by **
题意¶
题解¶
G¶
upsolved by JLK
题意¶
有一个杨辉三角倒着放在平面直角坐标系内，给一个三角形，问框柱的数的和是多少。
坐标范围\([-10^6,10^6]\)
题解¶
枚举行，然后和三角形交一下，用杨辉三角某一行的前缀和的递推技巧处理出区间和即可。参考这场的B题最后
更简单的方法是转一下，放到第一象限内，这样实际上求的东西更简单。
H¶
**upsolved by **
题意¶
题解¶
I¶
**upsolved by **
题意¶
题解¶
J¶
**upsolved by **
题意¶
题解¶
K¶
solved by TYB
题意¶
签到，略。
题解¶
略。
L¶
solved by JLK
题意¶
有一个\(n\)个点的二叉搜索树，\(q\)次查询某个区间内的点的个数。给了一个程序，求出这个dfs运行的次数。
\(1 \le n,q \le 2\times 10^5\)
题解¶
如果能找到左右端点分别到达的最深的地方，那么答案就是\((dep_x+dep_y-dep_{lca})\times 2+1\)。（考虑经过的每个点的儿子都要访问）
对于这个最深的地方，如果\(L\)这个数存在，那么可以找到这个点，然后往上找，找到第一个\([min,max]\)不是\([L,R]\)子集的点即可。
如果不存在，就是找最深的\([min,max]\)包含\(L\)的点。
线段树+倍增搞搞即可。
\(O(q\log n)\)
M¶
solved by JLK
题意¶
签到，略
题解¶
N¶
**upsolved by **
题意¶
题解¶
O¶
upsolved by
题意¶
题解¶
记录¶
TYB过K(0:08)，YZW过E(0:14)。
JLK过M(0:18)，A(0:31)，C(1:10)，L WA一次后AC(2:09)。
TYB过D(2:42)。
然后围观昆明去了。
发现G可做，但是一直WA。
总结¶
JLK：注意哪些地方该加eps哪些地方不该加。
Dirt¶
L(-1)