2019 ICPC Yinchuan Onsite
Replay
Xiejiadong:
- 垃圾键盘，无数次 想打 “\n” 直接回车就下去了。
- 热身赛感觉是办给主办方的。开始时间延迟将近一小时，结束时间却没有变动。
- 这个比赛不论是 “Ningxia Competition Area” 还是 “Ningxia Railway Station” 抑或是 “44rd” 或者 “IUPC” 从里到外、从上到下都透露着一股神秘的气息。
- 从网络赛开始的各个环节，没有一个环节是好的。幸运的是，正赛没有出现任何大问题。
- 主办方人手赠送一份中宁枸杞作为伴手礼好评。
- 宾馆和比赛场地不是一般的近，第一次体会到了比赛当日八点起床的爽感。
- 十分感谢 qls 和其他技术负责人连夜检查题目、导入题目。保证了比赛的正常进行。
- 整个宁夏的承办方、志愿者都是尽心尽力在维护比赛的正常进行。
- 算是比较顺畅的一场比赛。
- 最后一个小时还是一如往常的在压抑中进行， Weaver_zhu 还是一如往常的在最后 10min 带来了 surprise .
- 去年 “徐州+桂林” 的时候，F0RE1GNERS 在徐州 rank3 出线；今年 “厦门+银川” 我们也拿到了 rank3 ，希望剧本重演。
- 静等圣诞节开奖。
Kilo_5723:
Weaver_zhu:
Problem A
Solved by Kilo_5723. 03:59 (+3)
Problem B
Solved by Xiejiadong && Kilo_5723. 00:30 (+)
题意：每次可以选择一行或者一列对所有的数加上一个一样的正整数，现在屏蔽一个数，求那个数是多少。
题解：考虑还原。每次对于每一行和每一列减去他们的 min 一定是合法的。
于是我们把 "-1" 的位置设为 “0” ，然后还原一下，把 “-1” 的位置取反输出即可。
Problem C
Unsolved.
Problem D
Solved by Weaver_zhu. 04:57 (+6)
开场感觉是傻逼题，结果差点没出来。。。
$a_i$之间都是独立的直接用gcd倍数的莫比乌斯反演，脑抽了以为1e5就不管复杂度直接上 $nlogn$，还被模数和自己的假优化骗了。。其实线性筛预处理等幂求和和 $i^n$ 就能做到 $O(m + num_{prime}log(k))$ 的复杂度，CRT处理模数
Problem E
Unsolved.
Problem F
Solved by Weaver_zhu. 02:39 (+1)
小于 $\sqrt{(n)}$ 暴力，大于的对数取值只能是1，多项式直接搞出来。
Problem G
Solved by Kilo_5723. 01:38 (+)
Problem H
Solved by Xiejiadong && Kilo_5723. 02:32 (+)
题意：求单源最短路。无向边边权都是非负的，有向边一定连接两个无向边构成的联通块，而且联通块之间的有向边构成了 DAG ，有向边的边全可能是负的。
题解：显然没有负环，可以直接用 dij 跑。
但是直接用 dij 跑会 TLE 。因为对于一个联通块，可能会不断重复的更新很多次。
于是考虑根据有向边构成的 DAG ，利用他们的拓扑排序，分别对所有的无向边联通块跑最短路。
利用并查集维护联通块信息。
Problem I
Solved by Kilo_5723. 00:18 (+)
大数进制转换。
上 python 就完事了。
Problem J
Unsolved.
Problem K
Solved by Xiejiadong. 04:01 (+)
Problem L
Unsolved. (-2)
Problem M
Unsolved.
Problem N
Solved by Xiejiadong. 00:02 (+)
纯输出题。