oxx1108 edited 6 年，7 月前
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了。
A ultmaster 的小迷妹们
直接判断$gcd(x, y)$能否整除$n$即可。
证明：考虑小正方形所在列，一定不能被gcd整除，小正方形所不在列，一定能被gcd整除，所以一定不能拼成大正方形。
如果能被gcd整除，则由扩展欧几里得一定存在$ax - by = n$，因此可以构成$n \times n$在中间，四个$ax \times by$在周围的正方形。
ps：原来想出最小能够拼成的正方形，分两种情况，后来发现好像证明不了（两种情况一种都证不了，或许有反例？）。
B 代码查重
直接unordered_map套set存所有同义关系即可。
注意两个坑点：1.长度可能不同(因为题意被坑的深感歉意)。2.自反性意味着两个完全相同的同义。
ps：某G的面试题第一问，强行加个签到（貌似比A还简单？）。
C 神奇的魔术
两种做法，一是分治求出左右分别有哪些数，不用优化就严格$n \times 2^n$（野鸡出题人的写法，貌似比较好写？）。
二是先求出第一个数是几，然后二分找到每个数位置，理论会达到$(n + 1) \times 2 ^ n$，因此可能需要一些优化，比如最后一次二分时如果有一位已经被占用那直接就可以确定放在另一位，这样至少可以减少64次。或者随机rp足够好？
ps：这题貌似很好想但是不好写？好像比后面的题还难？
D 夜游 ECNU
这个题题目有些问题，路线应该是可以非整点……
如果是整点貌似不太好做……
排个序后裸的dp+离散化+线段树/树状数组优化。
ps：原来觉得太裸想把这题删了，但是ultmaster好像觉得还不错？
E 小迷妹在哪儿
尽可能先找到性价比高的小迷妹，所以按性价比排个序，然后就是个裸的背包。
证明：交换任意两个小迷妹的顺序可以列不等式证明性价比高的先找更优。
ps：原来想研究cf赛制应该先做难题还是简单题。
F 修路
首先并查集分每个联通块（底图联通），那么每个联通块至少$n - 1$条边，如果有环则$n$条边。
构造的话无环按拓扑序依次连一下边就好，有环连个哈密尔顿环就ok了。
ps：某场cf div2把无向图读成有向图结果想了好久没想出来……