Northeastern European Regional Contest 2014¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 36/274 | 5 | 8 | 11 |
A¶
solved by JLK
题意¶
一个\(n \times m\)的棋盘，初始是黑白相间。每次可以选择一个矩形，让里面所有格子颜色取反。求让所有格子颜色相同，并且操作最少的方案。
\(1 \le n,m \le 50\)
题解¶
最优策略是从第二行开始，每隔一行把一整行反色。列同理。
这样总操作数为\(\lfloor \frac n2 \rfloor+\lfloor \frac m2 \rfloor\)
B¶
solved by JLK
题意¶
贪心水题，略
题解¶
C¶
upsolved by
题意¶
题解¶
D¶
upsolved by
题意¶
题解¶
E¶
solved by YZW
题意¶
题解¶
F¶
solved by TYB
题意¶
不好描述，但读懂题就会了。
题解¶
不想写。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by TYB
题意¶
给出一棵\(n\)个点以下列方式生成的树：每次随机两个点，若不在一个连通块内则连接这两点，边有边权，问等概率随机选择一条奇数条边的路径，边权中位数的期望是多少。
\(n\le 30000\)
题解¶
中位数的题常见套路是枚举中位数，将其边权设为\(0\)，大于它的边权设为\(+1\)，小于它的边权设为\(-1\)，问题转化为统计包含\(0\)这条边且和为\(0\)的路径有多少条。随机生成的树最大深度\(d\)不会太大，考虑如何利用这个性质。从小到大枚举边权，每次只会有两条边的权值发生变化，设\(f_{i,j}\)表示以\(i\)为起点，其子树中某点为终点的路径中，边权和为\(j\)的有多少条，那么我们可以暴力跳父亲维护这个东西，复杂度\(O(nd^2)\)，但打表发现这个\(d\)不是想象中的\(\log n\)，而是\(\sqrt n\)，那么将无法通过。但我们通过精细化实现方式，可以将复杂度变为\(\sum_{i=1}^ndep_i\times mx_i\)，其中\(mx_i\)为\(i\)到子树中某点的最大距离，有个神奇的结论是这个东西是\(O(n\sqrt n)\)的，可以通过本题。
I¶
upsolved by JLK
题意¶
给定\(n\)的一个排列\(p\)，对于每个点有\(p_{i-1},p_i\)连边。现在要求边只有包含和在端点相交的关系。每次可以移动一个点，插入到任意位置。求最多能保留多少个点。
\(1 \le n \le 2\times 10^5\)
题解¶
结论是：最后保留的点一定是一个LIS加上一个LDS。
考虑最后保留的点的序列。对于一连串递增或递减的子序列，他们肯定都被上一级的最后一条边覆盖。同理，这一串里最后的一条边也要覆盖后面的所有区间。
那么肯定能找到一个分界线，使得左边都是递增的左端点，右边都是递减的右端点。要保留的点最多，那么就是LIS加上LDS。简单维护一下即可。
\(O(nlogn)\)
J¶
solved by YZW
题意¶
题解¶
K¶
solved by YZW
题意¶
题解¶
记录¶
开局跟榜AJK，J一起想了一会没有特别好的方法，YZW抄Dacing Links板子过了(0:40)。
JLK发现B有人过了，感觉是大水题，直接莽过(0:48)。
TYB写F，由于题面过长导致理解出了偏差，一段时间后AC(1:23)。
榜上很多人过了I，但是一直没有想到特别好的办法。
YZW开了H，觉得可做。但想题的时候自动把随机生成的树看做树高log了。JLK写了个暴力线段树，然后TLE/MLE。自己随机了一下发现这样生成的树高是根号级别的。于是放弃。
YZW写E，WA1后AC(3:45)。
随后JLK想到I的一个树套树写法，但是感觉时间空间都有问题，没有写。
TYB想到H不用数据结构的写法。
总结¶
JLK:看到随机数据不能想当然，有些时候还是需要随机模拟几次看看结果。
Dirt¶
E(-1)