2017 Multi-University Training Contest – Team 2

1001 Is Derek lying?
题意:告诉你A B两人的分数以及A B两人的答案序列,判断是否可以合法。
相同的答案有两种可能,两人都对了或者两人都错了。不同的答案有三种可能,两人都不对,或者一人对一人错。

1003 Maximum Sequence

RedPolya的博客

1004 Puzzle

从拼图游戏开始(三)_可行解的讨论

不过这题求T的时候可以O(1)求,不用模拟出来再做逆序对。😅

1006 Funny Function
RedPolya的博客

1009 TrickGCD
题意:根据给的序列生成一个序列,要求序列整体的最大公因子大于等于2,求符合这一要求的方案数。
整体最大公因子大于等于2,也就是说序列拥有一个公共的因子k,且k>=2。这样的话,可以通过枚举因子来计数。
但是在枚举因子的时候,会发现有的因子计重复了,由容斥得,每个质因子的贡献系数为:\((-1)^{k+1} , n=p_1P_2…P_k\)。这恰恰就是莫比乌斯反演的系数,可以由线性筛求得。
然后可以通过某种骚气的前缀和来加速乘的过程。
gunpowder的博客

1011 Regular polygon
题意:给平面里n个整点,求最多多少个正多边形。
根据2017国家集训队论文里的证明,这样的正多边形只能是正方形。注意斜着的情况。

WA了好几发😕。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Foreignbill