ACM-ICPC 2018 Qingdao Online Contest
ECNU Foreigners
ultmaster: 题目比较。。正常的比赛。
Problem A
Solved by zerol. 00:12 (+)
温暖的签到。
Problem B
Solved by ultmaster. 02:14 (+)
题意：给一棵黑白树，定义白节点代价为 0，黑节点代价为到最近的白节点祖先的距离。每次询问一个点集，允许修改一个黑节点为白节点，求点集中代价最大的东西的最小值。
题解：二分答案，然后求超过答案的部分的 LCA。然后将这个点染白，检查超过答案的部分是不是被卡进答案范围内了。
Problem C
Solved by zerol. 00:35 (+)
题意：给一些指令，问是否有限步内结束。
题解：状态数很少，直接模拟，如果遇到重复状态就不停机了。
Problem D
Solved by kblack. 04:10 (+4)
题意：$n \times m$ 的棋盘上，水彩笔涂了 $k$ 条不相交的线，求前 $i$ 行的黑块和黑联通块数量。
题解：将每条线记在左上角处，每对交点会在 “较低” 的线计算，可以证明这样交点数量是 $O(N)$ 的。这样就只需要记录上一行的横线和能影响到这两行的竖线，然后大力讨论接上的情况。讨论有点烦，不是特别好写，贡献不少罚时，浪费不少机时。
Problem E
Problem F
Unsolved. 04:59 (-5)
补完了。不能交了。
Problem G
Solved by zerol. 02:50 (+)
题意：给一个数列，每次删除其中一个数，求出每一段的逆序对数量的最大值。强制在线。
题解：考虑新分裂出的两段，短的那段暴力计算，长的那段把短的那段以及删除掉的数的贡献从中扣除，复杂度 $O(n \log^2 n)$。
zerol: 自闭了近两小时，两度做成另一道题，所以根本过不了样例。背锅
Problem H
Solved by ultmaster. 00:55 (+)
题意：直线上红绿灯每秒变换，求所有点对的旅行代价。
题解：应该瞎 DP 一下就好了。奇偶搞错了自闭了好一会儿。
Problem I
Problem J
Solved by kblack. 01:04 (+)
题意：周期性按按钮，求亮着的情况按下的次数。
题解：周期 $a \times c$，周期只有 $a+c$ 个关键点，周期内乘系数再加上最后一段。
Problem K
Solved by kblack. 00:14 (+)
温暖的签到。
One,Two,Three,AK
Problem A
Solved by oxx1108. 00:10(+)
题意：签到
题解：签到
Problem B
Unsolved.
Problem C
Solved by Xiejiadong. 00:53(+1)
题解：给一个程序，判断是否是死循环。
题解：死循环就是回到原来一个语句，且这个变量的值已经出现过。
直接暴力模拟。复杂度$O(n*256)$。
Problem D
Unsolved.
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Solved by Xiejiadong. 03:21(+2)
题意：每次删除一个数，把序列分开，求每次删除以后每一段序列里面逆序对最多的数量是多少。
题解：每次都暴力的做。
用主席树预处理权值线段树。
枚举短的一段，暴力计算跨区间的逆序对数量，从这一段中分成两段，并减去。
口胡还是很轻松的。写起来巨恶心。还卡读入。
Problem H
Solved by dreamcloud. 00:48(+)
Problem I
Unsolved.
Problem J
Solved by oxx1108 && dreamcloud. 02:00(+5)
题意：周期性按按钮，求亮着的情况按下的次数。
题解：周期 $a \times c$，周期只有 $a+c$ 个关键点，周期内乘系数再加上最后一段。边界没考虑清楚写自闭了……
Problem K
Solved by Xiejiadong. 00:15(+)
题意：签到。
题解：把二进制下位数相同的分为一组即可。统计组里最大的数量。