2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 50/? | 9 | 9 | 11 |
A¶
solved by JLK
题意¶
一场比赛，有\(n\)个人，\(w\)天，开始都是0分，第\(k\)天会有\(c_k\)个人得到一分，按分数从高到低排名，相同分数并列。求每个人在\(w\)天内的平均排名。
\(1 \le n,w \le 3\times 10^5,\sum c_k \le 10^6\)
题解¶
考虑一个人得到一分的影响。假设他的分数为\(x\)，即将变为\(x+1\)，那么在这个变化前后，只有分数恰好为\(x\)的人会受到影响，他们的排名会+1。那么可以把每个得分时间看做\((x_i,t_i)\)，表示在\(t_i\)时刻，\(x_i\)分的人排名会+1。
对于每个人考虑，每个人的分数对于时间是一段一段的，假设在一段\([l,r]\)内，分数均为\(x\)，首先有一个初始排名\(rank\)，贡献为\(rank \times (r-l+1)\)。对于初始排名，可以枚举时间用BIT预处理出来。
然后对于\(l \le t_i \le r,x=x_i\)的\((x_i,t_i)\)，都会有\((r-t_i+1)\)的贡献。这可以通过预处理\(t_i\)的前缀和来解决。可以对相同\(x_i\)维护一个vector，预处理之后在vector上二分找到对应区间即可。
\(O((w+\sum c_k)\log n)\)
B¶
upsolved by
题意¶
题解¶
C¶
solved by JLK
题意¶
有\(n\)块长方形的布，在晾衣绳上是若干个区间，不重叠，只会在边上相交。要用夹子夹住，可以在边上同时夹住两个。要求每个布恰好被两个夹子夹住，给定\(p\)个夹子，求出最少还需要多少夹子。
布的长度可以看做远大于夹子的宽度。
\(1 \le n \le 10^3, 0 \le p \le 2\times 10^3\)
题解¶
如果给定的夹子已经让一些布上面有三个，那么无解。否则贪心考虑，从左到右，对于每块小于2的布，如果后面紧挨着一块布并且也小于2，那么就放在右边界，否则在内部随意放。
用set维护比较方便。
\(O(n\log n)\)
D¶
solved by YZW
题意¶
题解¶
E¶
solved by TYB
题意¶
签到。
题解¶
略。
F¶
solved by TYB
题意¶
签到。
题解¶
略。
G¶
solved by TYB
题意¶
签到。
题解¶
略。
H¶
solved by JLK
题意¶
给定一个折线图，每个点是\((i,h_i),0 \le i \le n\)，\(k\)次询问，每次要求找最长的区间\([l,r]\)（不一定是整点），使得\(l\)到\(r\)的平均增长率至少是\(g\%\)。
\(2 \le n \le 10^5,1 \le k \le 50,0 \le h_i \le 10^9,-100 \le g \le 100\)，\(g\)只有一位小数。
题解¶
可以把\(g\)乘10转化为整数，然后在单位换算下就是图像上的增长率。
原问题为\(\frac{h_r-h_l}{r-l}\ge g\)。
令\(h'_i=h_i-g\times i\)，问题转化成\(h'_r\ge h'_l\)。
按\(h'_i\)把折线图划分成若干段，对于每一段来说，只有最左和最右的能覆盖这一段的线段有用。可以用线段树预处理出来。每一段找到最左和最右之后分类讨论，得到这一段上的区间最大值。然后考虑不同段之间的影响。再做一个左端点的前缀最小值，把每一段的右端点最大值和前缀左端点最小值相减，就得到了以当前段为右端点的最大值。所有取max即为答案。
如果答案为0，则是无解。
还要特殊处理一下\(h'_i\)是水平线的情况。考虑相同高度水平线的最左最右，不同高度之间的可以放到前面的前缀方法里面处理。注意有全部都是水平线的情况。
\(O(nk\log n)\)
I¶
solved by YZW
题意¶
题解¶
J¶
solved by TYB
题意¶
给一个长度为\(n\)的序列\(a\)，要求通过下列两种操作使得该序列满足\(\forall i\in[1,n),a_i\times a_{i+1}<0\)：
1：删除序列中的一个数，花费为\(r\)。
2：对于所有\(a_i\)，将其变为\(a_i-1,a_i,a_i+1\)之一，每个数的变化可以不同，花费为\(c\)。
求最小花费。
\(n\le5\times10^5\)
题解¶
考虑操作\(2\)用的次数，只有\(\mathcal{O}(n)\)种取值，即恰好把某个数的符号反转所用的次数。枚举这个次数，那么所有反转符号所需\(2\)操作次数小于等于枚举次数的都可以忽略，因为我们可以让其变成任意符号。对于剩下的数，则必须通过删除它或者它前面的数来满足条件。不妨假设奇数位置的数是正数，偶数位置的数是负数，按照这个标准可以将剩下的数分成两类，一种是需要改变符号的，一种是不需要改变符号的。把这些数拉出来，并将需要变号的设为\(1\)，否则设为\(0\)，我们就得到了一个\(01\)序列。问题转化为，删除一个数，并让其后面所有\(01\)反转，最后令这个序列没有\(1\)的最小删除次数。可以发现，当开头为\(1\)时，答案为\(01\)的段数，否则为段数\(-1\)。但注意到我们现在默认的是第一个数是整数，如果第一个数是负数，那么\(01\)可以反转。因此答案为段数\(-1\)。用一个set维护即可。
K¶
upsolved by
题意¶
题解¶
记录¶
TYB写E，WA一次后换YZW写I。
YZW过了I(0:17)，然后TYB又WA了一次，换JLK写C，TYB和YZW看E。
C WA了一次，一起看E，TYB先写F，E又WA了一次后AC(0:49)。
TYB过F(0:51)。
然后一起看C，改了之后AC(0:58)。
TYB过G(1:32)。
JLK过A(2:07)。
剩下DHJ可做，先讨论出了D的一个半平面交的做法，不敢直接写，然后看H。
JLK写H，RE一次后AC(3:36)。期间TYB和YZW讨论出了J。
TYB写J，WA三次后换YZW写D。
YZW过D(4:24)，然后TYB改过了J(4:25)。
总结¶
JLK：开局有点乱，不过根本原因是被小数转整数坑了，吃一堑长一智。
TYB：这套题涉及到很多小数，总结一下遇到的问题：1、对于输入都是恰好x位小数的题，可以考虑直接转为整数提高精度。2、转整数的过程中由于计算机中小数的表示方法问题，一定要用lround。3、对于涉及到乘积的大数，考虑取对数。
Dirt¶
C(-1)
E(-3)
H(-1)
J(-3)