2018.4 月赛题解

oxx1108 edited 6 年，12 月前

A ultmaster 的小迷妹们

直接判断 $g c d (x, y)$ 能否整除 $n$ 即可。
证明：考虑小正方形所在列，一定不能被gcd整除，小正方形所不在列，一定能被gcd整除，所以一定不能拼成大正方形。
如果能被gcd整除，则由扩展欧几里得一定存在 $a x - b y = n$ ，因此可以构成 $n \times n$ 在中间，四个 $a x \times b y$ 在周围的正方形。
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把无向图读成有向图结果想了好久没想出来……

13 1

hnust_wangchun

6 年，12 月前

D题
3
0 1
0 2
0 3

横纵坐标在0的，答案只有一种。。。。不是求和。

回复 1 0

signalK

6 年，12 月前

B是如果n!=m的话直接输出no吗？

回复 1 0

Uniontake

6 年，12 月前

是!第21个样例
QAQ

回复 0 0

maggch

6 年，12 月前

D题到达一个景点的坐标时能选择跳过这个景点?
4
0 1
1 1
0 2
1 2

答案是多少呢

回复 1 0

Lytning

6 年，12 月前

·······

一直以为这才是这道题的难点orz

回复 1 0

cubercsl

6 年，12 月前

我也是被这个给hack了不敢写了……

回复 1 0

oxx1108

6 年，12 月前

可以。好像是题面没说清楚……
1 2 2 6

回复 1 0

oxx1108

6 年，12 月前

是题目问题，应该路线非整点。
没考虑到这个情况，如果是整点貌似不太好做……

回复 0 0

maggch

6 年，12 月前

oj会考虑跟手机通知栏一样加一个清除所有消息吗,网页上面的消息一条一条×太多了

回复 0 0

ultmaster

6 年，12 月前

已加入 Possible feature list.

回复 0 0

Master X

6 年，12 月前

第一题想到欧几里得实现还是崩了，果然还是太菜了……

回复 0 0

10175101159

6 年，12 月前

弱弱问下， $E$ 的性价比可以用什么式子表示 $q w q$

回复 0 0

oxx1108

6 年，12 月前

ai * tj < aj * ti

回复 0 0

neoming

6 年，4 月前

B 第二十个样例一直过不去

回复 0 0

A ultmaster 的小迷妹们

B 代码查重

C 神奇的魔术

D 夜游 ECNU

E 小迷妹在哪儿

F 修路

Past Versions

Comments

服务

开源

关于我们