The 2020 ICPC Asia Shenyang Regional Programming Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 17/285 | 7 | 8 | 13 |
A¶
**solved/upsolved by **
题意¶
题解¶
B¶
**solved/upsolved by **
题意¶
题解¶
C¶
**solved/upsolved by **
题意¶
题解¶
D¶
solved by TYB&YZW
题意¶
给定\(n\)，构造长度为\(n\)的\(01\)序列，满足区间异或和为\(1\)的子串数量尽量多，按字典序从小到大输出，若多于\(100\)个输出前\(100\)个。
\(n\le 10^5\)
题解¶
考虑原序列的异或前缀和序列，他们是一一对应的。该序列第\(0\)个位置为\(0\)，后面\(1\)到\(n\)任意填\(01\)，原要求即为\(01\)配对的数量最多，显然是各占一半最优（奇偶分开讨论）。考虑异或前缀和序列，它对应的原串字典序最小，就要求相邻两个不同的地方越晚出现越好。通过观察或者思考可以发现，最优的形如\(000...01...111\)这样的串，次优的是把第一个\(1\)的位置左移，然后把若干个\(0\)插入后面的一堆\(1\)中。这个方案数是组合数，增长地很快，由于有\(100\)的限制，可以分段讨论：1、\(n\le20\)，暴力枚举\(01\)串判断是否合法；2、\(20<n\le200\)，枚举第一个\(1\)往后移动多少位（至多\(3\)位），然后把\(0\)插进去，将所有得到的串直接排序；3、\(200<n\)，此时\(1\)只会移一位，把一个\(0\)往后放即可。
E¶
**solved/upsolved by **
题意¶
题解¶
F¶
**solved by JLK **
题意¶
签到
题解¶
签到
G¶
solved by TYB
题意¶
签到
题解¶
签到
H¶
solved by JLK
题意¶
有\(n\)张租车卡，每张卡有\(d_i\)的有效期长度，\(t_i\)次租车次数，需要\(c_i\)元。卡到期作废，已经有卡时买新卡，原来的作废。也可以不买卡，每次花\(r\)块钱租一次。现在有一个租车记录，\(p_i\)表示日期，\(q_i\)表示这一天的租车次数。求最少花费。
\(1 \le n \le 500,1 \le m \le 10^5,0 \le \sum q_i \le 3\times 10^5\)，其余均为\(10^9\)
题解¶
由于给出\(\sum q\)很小，尝试表示在dp状态里。
不买卡的情况也可以当成一张卡。
\(dp[i]\)表示前\(i\)次都租完了的最小花费。由于限制条件比较好，可以把一次卡当做覆盖一段连续次数区间。那么只需要枚举卡的种类，找到下一个状态更新dp即可。
注意可能有\(q=0\)的情况。
\(O(n\sum q)\)
I¶
solved by YZW&TYB
题意¶
一天有 \(H\) 小时，每小时 \(M\) 分钟，有一块时针分针均匀速转动的表。
给出 \(A\)，求一天内时针与分针夹角不超过 \(\alpha={2\pi A\over HM}\) 的分钟数。
题解¶
推式子。容易写出：
分针角度：\(mH\cdot{2\pi \over MH}\)
时针角度：\((hM+m)\cdot{2\pi \over MH}\)
即得：\(|m(H-1)-hM|\leq A\) 或 \(|m(H-1)-hM|\geq HM-A\)
一种较为繁琐的方法是采用类欧几里得算法。
另一种简单的做法是将其改写为模意义下的不等式，即要求 \(m(H-1)-hM \bmod HM\) 的取值在 \([0,A]\) 或在 \([HM-A,HM-1]\)（也即 \([-A,A]\)）。由 Bezout 定理，存在 \((m',h')\) 使得 \(m'(H-1)-h'M=\gcd(H-1,M)\)，并且有 \(\gcd(H-1,M)|HM\)，因此可知所有能取得的 \(m(H-1)-hM \bmod HM\) 的取值 \(x\) 均满足 \(\gcd(H-1,M)|x\)，并且取得 \(x\) 的 \((h,m)\) 二元组对数恰为 \(\gcd(H-1,M)\)。
由对称性，当 \(2A\neq HM\) 时可得答案为 \(\left(\left\lfloor{2A\over \gcd(H-1,M)}\right\rfloor+1\right)\gcd(H-1,M)\)；当 \(2A=HM\) 时答案即为 \(HM\)。
J¶
upsolved by TYB
题意¶
长度为\(n\)的序列，初始所有位置为\(0\)，两种操作：1、把区间中的\(x\)变为\(x+1\)；2、询问区间最大值。
\(n,q\le5\times10^5\)，时限6s
题解¶
考虑分块，对每块维护最大值、块中某个数最后一次出现的位置、每个位置对应和哪个位置相等。
具体来说，\(lst_{i,j}\)表示第\(i\)个块中\(j\)这个数最后一次出现位置，\(nxt_{i}\)表示\(i\)位置和\(nxt_i\)位置上的数相等。
询问比较简单，不再赘述。
最大值的维护十分简单，只需要判断当前块的最大值是否为\(x\)即可。
对于另外两个，散块直接rebuild，重新求；整块看\(x\)和\(x+1\)是否存在来维护，也比较显然。
注意空间限制，尽管给了1G，但貌似\(lst\)还是要short int才行。
复杂度\(O(n\sqrt n)\)。感觉这个现场仅逆十字AC的题没有想象中难……
还有一种\(\log^2\)的做法，留坑待填。
K¶
solved by JLK
题意¶
题意十分巨大长，略
题解¶
对\(\theta\)分段算TPR和FPR，然后排序做前缀最大值，然后算积分。
L¶
**solved/upsolved by **
题意¶
题解¶
M¶
solved by YZW
题意¶
有 \(m\) 个回答仅为 AB 其一的问题，收集 \(n\) 组答案，求有多少非空问题子集满足有至少 \(k\) 对不同的问题子集的答案。
\(1\leq n\leq 2\times 10^5\)，\(1\leq m\leq 20\)，\(1\leq k\leq {n(n-1)\over 2}\)
题解¶
将一组答案对应为二进制，FWT xor 卷积一次即可求出：答案恰在某个问题子集下互不相同的答案对的数量。
再利用高维前缀和（换言之，FWT or？）即可求出答案在某个问题子集下存在不同的答案对的数量。
时间复杂度 \(O(nm+m2^m)\)。
记录¶
开场tyb签G，然后yzw口胡了一个E做法并WA了，JLK改正后AC(0:20)
看到逆十字过了M，于是跟榜，yzw想到FWT并WA了。JLK尝试对拍未果，检查代码发现没加1LL，改后AC(1:23)
此时卡在D和I。看到K过的人越来越多，于是JLK开始尝试理解题意并AC(2:29)
tyb与yzw大力分类讨论D，与此同时JLK发现一道可做题H，等机位。
D过了(3:45)之后敲H，WA了。仔细读题后发现没处理好\(q_i=0\)的情况，随后AC(4:09)
最后开I，yzw/tyb分析类欧板子并多次调试后有惊无险地在4:51AC
总结¶
开局不是很好，好在最后阶段翻盘回来了。
还是有一些低级错误，需要尽量避免。
存在一些题目题面长但实际简单，可以通过跟榜并及时发现解决。
总体来说还是比较满意的，在Au中部，以后再接再厉吧。
TYB：加强Case讨论能力和对模板熟悉程度，不要再抄错板子了。
Dirt¶
E(-1)
G(-1)
M(-1)