2018.4 月赛题解 (Past)

oxx1108 edited 5 年,11 月前

This is a past version of blog 2018.4 月赛题解

A ultmaster 的小迷妹们

直接判断gcd(x, y)能否整除$n$即可。
证明:考虑小正方形所在列,一定不能被gcd整除,小正方形所不在列,一定能被gcd整除,所以一定不能拼成大正方形。
如果能被gcd整除,则由扩展欧几里得一定存在$ax-by=n$,因此可以构成n*n在中间,四个ax*by在周围的正方形。
ps:原来想出最小能够拼成的正方形,后来发现好像证明不了(两种情况一种都证不了,或许有反例?)。

B 代码查重

直接unordered_map >存所有同义关系即可。
注意两个坑点:1.长度可能不同。2.自反性意味着两个完全相同的同义。

C 神奇的魔术

两种做法,一是分治求出左右分别有哪些数,不用优化就严格$n 2^n$(野鸡出题人的写法,貌似比较好写?)。
二是先求出第一个数是几,然后二分找到每个数位置,极限可能会达到$(n + 1) 2 ^ n$,因此可能需要一些优化,比如不可能的就不查询了,或者rp足够好?
这题貌似很好想但是不好写?

D 夜游 ECNU

排个序后裸的dp+离散化+线段树/树状数组优化。

E 小迷妹在哪儿

尽可能先找到性价比高的小迷妹,所以按性价比排个序,然后就是个裸的背包。
证明:交换任意两个小迷妹的顺序可以列不等式证明性价比高的先找更优。
ps:野鸡出题人原来想研究cf赛制应该先做难题还是简单题。

F 修路

首先并查集分每个联通块(底图联通),那么每个联通块至少n-1条边,如果有环则n条边。
构造的话无环按拓扑序连一下边就好,有环连个哈密尔顿环就ok了。