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:

• 想说的都被说了。
• 最后一个小时临危受命去搞 L，和 D 互抢机时，最后还是没搞出来。结束后一看代码发现一个地方变量名写错了，等重现赛出了看看是不是赛后 5 min 补题。
• 一起等圣诞节开奖。
• upd: 赛后 5 min 补题成功了。真是 wdnmd。

Weaver_zhu:

Problem A

Solved by Kilo_5723. 03:59 (+3)

题意：每张卡牌有名字，花色和能量，从 $n$ 张卡牌里选出五张名字不同的卡牌组成一套牌，一套牌的能量等于这套牌里卡牌的总能量乘上奖励系数。有五个奖励名字和一种奖励花色，奖励系数初始为 $1$，每有一个奖励名字奖励系数 $+0.1$，每有一个奖励花色奖励系数 $+0.2$，求最大总能量（下取整）。

题解：$dp_{i,j,k}$ 代表已选 $i$ 张牌，已有 $j$ 个奖励名字和 $k$ 个奖励花色情况下不加上奖励系数的最高总能量，dp 过程就是组合背包问题。最后取 $\lfloor \frac{(10+j+2\cdot k) \cdot dp_{5,j,k}}{10}\rfloor$ 的最大值。注意下取整要先乘后除。

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 倍数的莫比乌斯反演，脑抽了以为 $10^5$ 就不管复杂度直接上 $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 (+)

题意：一个序列，初始全为 $1$。每次操作可以把一个区间的数乘上一个 $[2,10]$ 以内的数或询问一个区间里所有数由质因数的幂次构成的约数的质因数的最大幂次是多少。

题解：题意像绕口令，对 $2,3,5,7$ 分别统计区间最大幂次，每次询问取最大值，线段树维护。

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

Upsolved by Kilo_5723. 05:35 (-2)

题意：连连看，连接两个字符串的收益由相同的位数确定，求最高收益。

题解：等场上最后一发 WA 出来之后发现有个地方变量名写错了，改完之后把代码存了下来，重现赛过了。

状压 dp 加优化，保存每个字符串上下左右拓展的最大空间，判断是否能相连时判断扩展空间是否相交即可。

Problem M

Unsolved.

Problem N

Solved by Xiejiadong. 00:02 (+)

纯输出题。