Northern Eurasia Finals Online 2020¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 114/587 | 7 | 8 | 15 |
A¶
solved by JJLeo Bazoka13
题意¶
让你构造一个 \(A\) 个权值为 \(1\) 的点， \(B\) 个权值为 \(2\) 的点的 \(almost balanced\) 的二叉树。
定义一个 \(almost balanced\) 二叉树为对于二叉树的每个节点都有左、右子树的权值差的绝对值小于等于 \(1\)。
\(1 \le A + B \le 10^5\)
题解¶
考虑一种构造形式，从根节点开始，如果我们此时能用 \(2\) 那么就用 \(2\)，否则用 \(1\)。
如果到一个状态时根节点赋值过后有奇数个 \(2\) 并且没有 \(1\)，则无解。
B¶
upsolved by solution
题意¶
给你一堆字符串，以及两个基准串 \(S,T\)，问这些字符串有多少个能于这两个基准串构成一个唯一解的等式，即 \(\overline{S} + \overline{T} = \overline{P}\)
唯一解的条件为：
- 每个字母表示不同的数字（不出现的字母不用管）
- 没有前导0
\(n = 279496\)
题解¶
扔 trie 上瞎搞搞暴力就能过，离谱。
C¶
solved by JJLeo 2sozx
题意¶
给定一颗有根树，除了根节点颜色为红色外其余点的颜色均为绿色。
每次可以选择改变一个点的颜色（需要保证根节点颜色为红色），保证所有红色点构成一个联通块，问整棵树有多少种染色方式，并且给出染色方案。
\(n \le 20\)
题解¶
首先我们会发现答案一定不会超过 \(2^{n}\)。太大了输出都要超时（x
考虑构造出这样一个答案，对于一个结点来说他所有子树的最优操作我们都知道了，考虑合并两个操作。我们可以先做第一个子树的操作，然后做第二个子树的操作，然后做第一个子树的逆操作，再做第二个子树的逆操作即可得到最优方案。
当然如果当前点不是根节点的话在操作子树之前要把这个点的颜色变成红色。
D¶
upsolved by 2sozx
题意¶
给定一个 \(n \times 8\) 的字符矩阵，矩阵只包含 \(W, R\) 两种字符。对于两行 \(i, j(i < j)\) 有一条 \(i \to j\) 的边，当且仅当 \(j - i \le same(i, j)\)，其中 \(same(i, j)\) 表示第 \(i, j\) 行对应位置相同元素的个数。
对于前 \(i\) 行，有两个人进行移动，如果移动不了即为输，问是否能先手必胜。
\(n \le 3 \times 10 ^ 5\)
题解¶
显然会发现每个点只会与相邻的 \(8\) 个点连出边，因此我们可以预处理这样一个状态 \(f_{i, 255}\) 表示对于第 \(i\) 个点所连的 \(8\) 条出边分别是先手必胜或者必败的状态时从 \(1\) 开始是必胜还是必败。
定义 \(e_i\) 表示点 \(i\) 连出的边的二进制表示，因此我们可以得到如下转移：
因此我们对于每次增加的一行判断最后 \(8\) 行的必胜太即可，复杂度为 \(O(256n)\)
F¶
upsolved by
题意¶
题解¶
G¶
solved by JJLeo 2sozx
题意¶
一个二维平面，\((x, y)\) 点的值 \(v_{x, y}\) 为：
再给定一个三角形，问三角形所包含的点权值和是多少。
\(|x|, |y| \le 10^6\)
题解¶
2sozx 和 JJLeo 争论如何将坐标旋转 \(45^{\circ}\)
将坐标旋转 \(45^{\circ}\) 会发现这道题变得简单无比（
枚举 \(y\) ，然后 \(O(1)\) 找到三角形在 \(y\) 上的左右区间，预处理组合树后可以 \(O(1)\) 计算出这一段的区间和，就没了。
复杂度 \(O(C)\)
H¶
upsolved by
题意¶
题解¶
I¶
upsolved by
题意¶
题解¶
J¶
upsolved by
题意¶
题解¶
L¶
solved by JJLeo
题意¶
给定一棵 BST，操作如图：
\(q\) 次询问，每次询问一个区间 \([l, r]\)，问会调用多少次 \(lookup\)（包括最开始调用的一次）。
\(n, q \le 2 \times 10 ^ 5\)
题解¶
对于每个点记录子树最大值最小值 \([L_i, R_i]\)，对于答案有贡献的点当且仅当 \([L_i, R_i] \cap [l, r] \not = \empty\) 并且 \([L_i, R_i] \cap [l, r] \not = [L_i, R_i]\)，每个交会对答案产生 \(2\) 的贡献。
因此我们将询问离线后记录线段交的个数即可。
N¶
upsolved by Bazoka13
题意¶
给一个凸包和线段，问线段在凸包内旋转平移和初始位置的最大夹角
题解¶
一个猜想是线段会先卡到某个地方，"卡"指两端都在多边形边上，然后旋转，卡，旋转，卡，以此类推，那么就考虑模拟这个过程就好了，我写了个多源bfs，然后注意一些corner case就是线段初始可能没有卡好，需要考虑这种情况，以及常见的精度问题。
std的做法待研究。
O¶
upsolved by
题意¶
题解¶
记录¶
-1h：困死（
0h：开局仨签到，EKM一人一到，挂机（。把题都过了一遍，感觉 A 不太可做，但是好多人过了，换道题，MJX 看 D 感觉很简单，和 ZYF 对了一下，感觉挺对的。
1h：交了，WA 6，研究了一下题意可能是另一种题意，改了一下 WA3，换题。CSK 猜一个 A 的做法，感觉挺靠谱的，ZYF 写，写完过了，想别的题，CSK 给 MJX 讲 N 后开始冲 N。
2h：MJX YY 个 C 做法，样例是对的，本质上也是对的，给 ZYF 讲，感觉没毛病 ZYF 就冲了，写完过了，挂机（。
3h：MJX 看 G 发现范围不大，可以暴力算每一行的值，给 ZYF 讲了做法，顺便讨论了一下转 45° 应该咋写，感觉很对准备写。ZYF 突发奇想 L 就是线段交，MJX 感觉很对，ZYF 准备写。CSK N 又寄了 ZYF 先写 L。
4h：ZYF 过了开始冲 G，写完 WA6 以为是精度问题，改了还是 WA，后来发现不能先取整，要先除 2，改完还是 WA。ZYF de 了以下发现只改了一半，没改全，改完过了。