2018 ACM-ICPC China Shanghai Metropolitan Invitational Contest

From EOJ Wiki
Jump to: navigation, search

Problem A

Solved by zerol. 01:21 (+)

题意:求一条直线,至少经过 N 个点中的 N * k 个点,$(0.1 \leq k \leq 0.9)$。

题解:随机挑两个点,如果有解,那么有 $\frac{1}{k^2}$(最坏情况要随机几百次) 的概率恰好落在答案所在的直线上。当然这是不考虑点重复的情况,事实上这样就能 AC。但是比如 n = 10000,k = 0.1,有 998 个点在同一个点上,另外恰好有一组 1000 个点共线,那么概率会很低。所以如果随机到的两个点一样的话,必须重新在剩下的点里随机,即便这样命中率也只有约 $0.1 \times 0.1 \times 0.0002$。

另解:更好的做法是随机一个点,统计其他点的斜率,这样就不会有点重复的问题了,随机次数最多也只需要几十次。

Problem B

Solved by ultmaster. 00:10 (+)

求完美数分解,温暖的签到。

Problem C

Upsolved by ultmaster.

EOJ 3407。样例都没改。

ultmaster:因为做过,所以判断在现场不能做。

重现赛:上了两个板子过了。

Problem D

Solved by kblack. 00:36 (+1)

裸几何规律,温暖的签到。

Problem E

Upsolved by ultmaster.

题意:有一种循环回文子串:把字符串的某一个后缀移到前面若构成的新字符串是一个回文串,就称循环回文串。求原字符串在修改最多两个字符的情况下的最长循环回文子串,要求长度为奇数。

题解:以一个点为中心,用二分 + hash 的方法,可以求出以该点为中心,修改最多 0 个、1 个或 2 个的最长回文子串。然后把这个信息转化成以 $i$ 结尾的修改 0 个、1 个或 2 个的最长回文奇数串;以 $i+1$ 为开头的修改 0 个、1 个或 2 个的最长回文偶数串。可以发现循环回文串就是前面一个奇数和后面一个偶数拼起来。所以枚举前后的修改次数,两边拼起来就可以。奇偶可以互换,所以还要倒过来再做一遍(偶数回文串如果结果偏左或者偏右的话,倒过来的时候还要偏移)。注意也有可能只有一个奇数,如果姿势不好可能要特判。

ultmaster:这题我要背大锅。kblack 的 hash 敲了半天终于差不多敲对了已经意识模糊了。然后我贡献了一个假得不行的做法,还提出了一个其实完全用不到的 API 需求。然后比赛的剩余时间在就要丢掉奖杯的绝望和轮换调试 API 和假做法中度过。其实如果 kblack 的意识还在线的话,或许是有希望的。但是或许时间也不大够了。赛后进行了对拍,花了一个半小时修复了若干个 bug,才艰难地通过随机数据。

本题以加入 EOJ 豪华午餐:3626。(事后发现这道题其实是原题的一个加强版,原因是题目有歧义。。。)

重现赛:所以是切掉一段剩下来的组成回文串咯?我真是艹了。辣鸡 kuangbin 还我下午!

补充:就算改了这题还是假的,比如 zywvucdeedcaaaaaaaaaaaaaaraaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaa 正确答案是 57(删左边 5 个),但是 AC 代码输出 51(对 cdeedc 视而不见)。

Problem F

Solved by ultmaster. 01:06 (+1)

题意:有一个网格,然后有若干个圆去覆盖。求没有被覆盖到的点的数量。

题解:由于询问数量少、行列数量也不大,直接枚举行,然后在列上标记覆盖范围就好了。ultmaster 一开始想上线段树,然后经过 zerol 的提醒,发现线段树也不要。只要一个扫描线就好了。然后扫描线也调不出来(到底是有多惨?),甚至还打印了,最后发现 $n$ 和 $m$ 搞错了。然后修 bug 修了一半(初始化没修),WA1。

Problem G

Unsolved.

Seems similar to EOJ 2842.

Problem H

Solved by kblack. 03:01 (+1)

题意:区间平方膜 2018,区间求和。

题解:一个数不断平方膜 2018,最多 4 次后就会进入长度是 6 的约数的循环节,于是将序列分为两类数分别考虑。 对于循环内的数,直接记录当前即平方5次内的所有和,平方操作即是对数列的位移操作,可以懒标记维护。 对于循环外的数,暴力递归到叶子节点,手动平方,一旦进入循环就删掉特殊标记,转化为上一种维护方式。

Problem I

Solved by zerol. 03:34 (+1)

题意:给一个矩阵,每次可以对一个数 +1 或 -1(不能为负),问最少几次使得每行之和相等,每列之和相等。

题解:枚举每行的和,然后建图,每行以及每列是一个点,行(列)如果不够和就连源(汇),超过则连汇(源),行列之间的双向边费用均为 1,有一个方向(代表 -1)有容量限制(因为元素不能为负)。对每行的和的所有可能值进行三分跑费用流。

zerol: 鉴于数据范围很小,kblack 给出了指导性意见——网络流,在 ultmaster 读错题的情况下给出了正确的建图方法,然后蜜汁 TLE,然后加了个三分就过了。然而还有更加简单的做法。

Problem J

Solved by ultmaster. 02:05 (+)

题意:求 $n$ 以内能被各位数字之和整数的数的数量。

题解:枚举各位数字之和 $p$,然后维护两个量:一个是当前数模 $p$,还有一个是当前各位数字之和。最后可行条件是当前数为 0 且各位数字之和等于 $p$。

ultmaster: 惊!全队居然没有一个人会数位 DP。kblack 说数位 DP 复杂度不对,大家都信以为真。在没有题可以上的情况下,ultmaster 上机打了个暴搜,发现答案多得一批。绝望。然后经过 zerol 提醒,发现好像不同测试数据之间的计算是可以重用的!然后写得倒是很快。通过跟表手动对拍发现了一个 bug,避免了一个 WA。

Problem K

Solved by kblack. 00:24 (+)

裸矩阵乘法,温暖的签到。

Problem L

Upsolved by ultmaster.

题意:求 $b_i = \sum_{j=0}^{N-1} (a_j (4^i \cdot p + q)^j)) \bmod 200003$。

题解:跟 kblack 一致卡在了最后一步。然后厚颜无耻地问邝老师要了标程。

所有的奥妙大概可以用下面的式子全部涵盖:

  • $ans_{i} = \sum_{k=0}^{N-1} (p \cdot 4^i)^k / k! \cdot c_{k}$.
  • $c_{k} = \sum_{j=k}^{N-1} j! a_{j} \frac{q^{j-k}}{(j - k)!}$.
  • $t1_{k} = p^k c_{k} 2^{k^2} / k!$; $t2_{k} = 1 / (2^{k^2})$.
  • $ans_{i} = \sum_{k=0}^{n-1} t1_k t2_{i-k}$.

特别说明一下最后一步:由于要用到「负」的东西($i-k$ 可以是负的),把负的东西存在最后就好了,由于这好像是一个循环的(具体原理也没怎么搞清楚)。

有一个略有点恶心的事情是要上一个任意模 NTT 的板子。感谢邝老师,以收入模板库。

本题以收入 EOJ 3627。