上海大学ACM集训队选拔赛题解

Problem I. Triangle War

  • 做法:勾股定理判断直角三角形即可。
  • 复杂度:$O(1)$
  • 通过人数:53/97
  • 最快通过:顾淑洁(3:39)

Problem F. Number Theory Problem

  • 做法:考虑到$7$的二进制表示为$111$,而$2^k−1$的二进制表示为$k$个$1$。不管你打表找规律还是动一下脑筋就知道,每三个里面有一个是$7$的倍数。所以直接输出$⌊n/3⌋$即可。
  • 复杂度:$O(1)$
  • 通过人数:49/108
  • 最快通过:黄坤(5:17)

Problem E. Lonelam’s Problem Set

  • 做法:将所有题目按难度排序之后,遍历一遍判断即可。
  • 复杂度:$O(n \log⁡ n)$
  • 通过人数:48/173
  • 最快通过:苗伟华(7:46)

Problem H. QAQ

  • 做法:由于数据范围很小,我们可以直接枚举三个下标的位置进行判断即可通过。
  • 复杂度:$O(n^3)$
  • 通过人数:46/89
  • 最快通过:顾淑洁(10:41)

可以遍历A的位置,利用前缀和可以得到它前面和它后面Q的数量,可以做到$O(n)$的复杂度。

Problem K. WeChat Group

  • 做法:答案为$\sum \limits_{k=1} ^ n \binom{n}{k} = 2 ^ n - 1$。直接快速幂即可。
  • 复杂度:$O(\log⁡ n)$
  • 通过人数:39/67
  • 最快通过:顾斌(22:59)

Problem C. Counting Star

  • 做法:当$m>n$时答案显然为$0$。否则我们令$dp[i]=\sum _ {j = i - m + 1} ^ i l_j$,即第$i$个点及其前$m$个点亮度之和,那么有递推关系式$dp[i]=dp[i−1]−l_{i−m}+l_i$。然后统计个数即可。
  • 复杂度:$O(n)$
  • 通过人数:33/180
  • 最快通过:苗伟华(7:46)

Problem J. XOR Game

  • 做法:显然游戏的胜负与$(i,j)$对的奇偶性有关,所以我们枚举$(i,j)$对进行判断即可。对于查找是否在这$2n$个数中,可以开一个数组,或者使用平衡树来维护。如果用数组,需要注意的是两个数异或后的答案会越界。
  • 复杂度:$O(n^2)$
  • 通过人数:19/733
  • 最快通过:任悦(1:41:50)

由于异或的性质,$(i,j)$对的数量一定为偶数个,所以直接输出CSL即可。

Problem L. Word Construction

  • 做法:考虑用一个$26$位二进制数来表示一个单词中的各字母是否出现。如果两个单词对应的数按位与的结果不为$0$则说明有相同字母。然后进行DFS即可。由于给出的均是常用的英文单词,所以可以保证单词中必然会有元音,这样一个强大的剪枝会使得递归约为$5$层。
  • 复杂度:$O(n^5)$
  • 通过人数:7/37
  • 最快通过:俞硕文(1:28:24)

Problem A. A+B Problem

  • 做法:统计每个数出现的个数,存在数组对应的下标中(由于有负数,所以要有$500$个单位的地址偏移)。那么加和为$k$的选取方法数为:$$\sum _ {i + j = k} c[i] * c[j] - \sum _ {2a_i = k} 1$$然后遍历一遍原数组,统计对答案的贡献即可。需要注意在统计答案的时候还有$0$的存在需要特别对待,具体细节留给大家思考。
  • 复杂度:$O(|a_i|^2+n)$
  • 通过人数:4/57
  • 最快通过:柯春旺(3:34:54)

Problem O. Yet Another Simple Problem

  • 做法:由威尔逊定理:当且仅当p为素数时$(p−1)!≡−1\pmod p$ 。所以这题只需要判断$3k+7$是不是素数即可。使用欧拉筛可以做到线性复杂度。
  • 复杂度:$O(n)$
  • 通过人数:4/7
  • 最快通过:许立雄(2:49:25)

Problem M. World Cup

  • 做法:暴力枚举六场比赛的胜平负关系得到每支队伍的积分,用四维数组记录即可。
  • 复杂度:$O(1)$
  • 通过人数:2/5
  • 最快通过:黄坤(4:29:49)

Problem B. After EC-Final

  • 做法:买的东西越多,单价就会越贵。我们发现答案具有单调性,所以考虑二分答案。
    每次计算各个物品的价格并排序,选择最便宜的$k$件物品购买。
  • 复杂度:$O(n \log^2 n)$
  • 通过人数:1/12
  • 最快通过:苗伟华(3:07:09)

Problem N. Wow! Such String!

  • 做法:我们只需要令长度为$4$的子串都不同,就满足了题意。知道了这个,就可以乱搞了。
    长度为$4$,最多有$26 ^ 4$种情况,最长链为$26 ^ 4 + 3$。
    如何构造呢?如果我们视为字母的三元组为一个点,字母的四元组为一个边。那么,如果存在最长链,意思是:我们构造的图,存在欧拉路径。当然,这里有$26 ^ 3$个点,每个点的出入度都是$26$,自然是有欧拉路径的。
  • 复杂度:$O(n)$
  • 通过人数:1/5
  • 最快通过:俞硕文(4:11:21)

Problem G. Oneday’s Codeforces

  • 做法:设使用$k$个小号,根据题目要求可以得到贪心策略:
    • 对于自己做得快的题,让这道题的通过率变低,价值变高,即这$k$个小号都没做对;
    • 对于自己做得慢的题,让这道题的通过率变高,价值变低,即这$k$个小号都做对;
    • 对于你自己都没做对的题,这$k$个小号也没法做对。
  • 当总人数超过现有人数$32$倍的时候,再增加人数也对得分没有影响了。所以可以从$1$个小号开始暴力枚举,复杂度可以接受。
  • 复杂度::$O(n)$
  • 通过人数:1/2
  • 最快通过:苗伟华(2:06:44)

注意:本题的答案是不具有二分性质的!

Problem D. CSL’s School Card

  • 做法:可以想到使用BFS进行搜索。主要难在状态表示,用$d[state][x_1][y_1][x_2][y_2]$表示两个人坐标分别位于$(x_1, y_1)$$(x_2, y_2)$,地图上每个格子的访问状态为$state$($n×m$位二进制状态压缩)
  • 复杂度::$O(2^{nm}nm)$
  • 通过人数:0/9

标程与数据

捐助作者
0%