2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)

Problem A

Solved by bingoier. 01:34 (+)

将每一位参赛选手的 $Rank$ 之和分为两部分，第一部分为其得分总和所在层的代价，第二部分为其自身的特殊代价。 对于每一层（代表不同得分）用 $K_i*w+B_i$ 表示当前这一层每位参赛选手第一部分的得分总和，每位选手的特殊代价使用数组记录即可。 我们会发现当有一名选手的得分增加时，只有之前与之得分相同的选手（即在同一层的选手）会受到影响。 因此我们可以通过代换将这一层的 $K_i,B_i$ 变化到对应值，再修改当前次操作对于这名选手的特殊代价即可完成一次修改操作。

Problem B

Unsolved.

Problem C

Solved by yanghong. 00:48 (+1)

简单贪心

Problem D

Unsolved.

Problem E

Solved by yanghong. 00:22 (+2)

判断一下答案在中间还是两段即可

Problem F

Solved by bingoier. 00:32 (+)

并查集签到题。

Problem G

Solved by yanghong. 01:54 (+3)

枚举一下被加入其它怪的概率的区间， 然后组合数计算。 注意精度问题

Problem H

Solved by bingoier. 03:54 (+3)

将每一个顶点的坐标进行代换 $(x,y)$ -> $(x,y-k*x)$ 后排序。

易知最优解的线段一定有一个端点是在题目中的顶点处。

所以考虑每一个顶点，那么最优解即是在纵坐标大于他的所有点里面选择一个横坐标最大的值或者在纵坐标小于他的所有点里面选择一个横坐标最小的值。

对于排序后的坐标数组做个前（后）缀最小（大）值维护即可。

Problem I

Solved by bingoier. 00:19 (+)

签到题，注意特判。

Problem J

Solved by yanghong. 03:46 (+4)

枚举账号的数量， 维护一个链表， 以O(1)计算在账号数+1后需要举报的次数。

Problem K

Unsolved.