2019.3 月赛题解

Xiejiadong edited 5 年，8 月前

花絮

月赛参赛人数重回一千。撒花。

牛逼网友 oxx1108 又来出月赛了，但愿不是惨案。事实证明就是惨案。

下个月你们还能做到牛逼网友 oxx1108 出的题目，题目非常“友好”。（疯狂暗示）

Xiejiadong ：好像每次我主导的月赛题解都特别长啊？可能是我废话比较多。

kblack ：你们这出的 Div1 啊？

oxx1108 ：感觉我就是一股清流， A 和 C 怎么都几乎没人跟我做法一样。

#	Tag	Idea	Developer	Tester
A	构造	Xiejiadong	Xiejiadong	oxx1108 Kilo_5723
B	贪心	Xiejiadong	Xiejiadong	oxx1108 Weaver_zhu
C	暴力剪枝	Xiejiadong	Xiejiadong	oxx1108 Weaver_zhu
D	数学	Kilo_5723	Kilo_5723	Xiejiadong Weaver_zhu
E	树形dp	oxx1108	Kilo_5723	Xiejiadong Kilo_5723

Problem A

First Solved：DeaphetS

构造题。解法非常多。

首先无解是唬你的，不存在无解的情况，可以很容易的证明，这里省去。

解法1

随机。

我们首先按照顺序三个三个分组，发现其中有一些是不满足要求的，于是考虑随机交换。

每次随机选择一组的第二个和另一组的第三个进行交换。

但是我把我自己卡掉了。

大家有更好的随机策略可以在评论区交流。

解法2

by oxx1108

从钝角出发，很直接的就想到构造两条短边和一条长边，只要使得短边的和与长边的差值很小就行。

又是 $3n$ 个，又是三角形，最直接想法就是分成三堆（最小的 $n$ 个一堆，中间的 $n$ 个一堆，最大的 $n$ 个一堆），从最小堆里取一个，中间堆里取一个，最大堆里取一个，但是既要是钝角又要是三角形行不通，那么就改变一下想法。从最小堆里取一个偶数，中间堆里取两个；最小堆里取一个奇数，最大堆里取两个。比如 $n = 4$ 的时候分组就为 ${2, 3, 4, 5},{6, 7, 8, 9},{10, 11, 12, 13}$ 那么结果就是 ${2, 7, 8}, {4, 6, 9}, {3, 11, 12}, {5, 10, 13}$。奇数的时候要注意多加一组 ${n + 1, 2n + 1, 3n + 1}$ 即可。证明显然。

详细思路与证明可见评论区 10175101159 的分享。

解法3

通过解法1，我们发现对于每一组的第一个默认为 $2$ 、 $3$ 、$\cdots$ 、$n$ 、$n+1$ ，是一定存在这样的解的。

于是我们默认每一组的第一个数，来构造后面两个数。

首先，如果长度为 $a$ 、 $b$ 、 $c$ ( $a<b<c$ )的能够构成钝角三角形，显然 $a$ 、 $b+x$ 、 $c+x$ ( $x\ge 0$ ) 也能构成钝角三角形。

我们考虑从 $n$ 的解，通过变换得到 $2n+1$ 的解：我们对 $n$ 的解，每一组的第二条和第三条边分别进行 $+n$ 操作，由上得，显然满足钝角三角形。

这样一来，空出了 $(n+2)\cdots (2n+1)$ 和 $(4n+2)\cdots (6n+1)$ ，前面一部分有 $n$ 个数，后面一部分有 $2n$ 个数，而且正好 $x+2$ 、 $4x+2$ 、 $5x+2$ ( $x\ge 1$ ) 能构成钝角三角形，于是，我们可以从 $n$ 推到 $2n$ 。

而对于 $n$ 推到 $2n+1$ 的情况，无非是多出了三个数，组成一组即可，其他情况和推到 $2n$ 的情况类似。

解法4

同样我们默认每组的第一个是 $2$ 、 $3$ 、$\cdots$ 、$n$ 、$n+1$ ，考虑从最后一组开始。

第二数选择当前没有被选择的数中最小的一个数，然后在剩下的数中二分寻找一个满足要求的最小数。

可以证明，这样的构造方法是满足要求的。

Comments

oxx1108 ：套路的构造题，但是好像大家都觉得有点难？可能更适合放数学竞赛里吧……

Problem B

First Solved：dreamoon

签到题。

考虑最旁边的两个数，如果相等，直接略过他们，因为他们本身已经是回文了；

如果不相等，那么一定是较小的一个要向内合并，合并完以后继续比较当前最旁边的两个数。

显然这样的策略是最优的，最坏的情况就是，所有的数合并成一个数，一个数显然满足回文。

Problem C

First Solved：applese

一种解法是显然的，我们的线段树建法，决定了线段树要么左右孩子等大，要么左孩子比右孩子大 $1$ 。

对于一个线段树上的结点 $[l,r] (len=r-l+1)$ ，他的父亲只有四种情况：

当前结点为左孩子，左右孩子等大，父亲为 $[l,r+len]$ ；
当前结点为左孩子，左孩子更大，父亲为 $[l,r+len-1]$ ；
当前结点为右孩子，左右孩子等大，父亲为 $[l-len,r]$ ；
当前结点为右孩子，左孩子更大，父亲为 $[l-len-1,r]$ 。

这样一来，我们就可以直接暴力了。这样的暴力还不足以通过这道题目。

一些剪枝是必要的。

比如可行性剪枝 $r\ge ans$ （ $r$ 是当前的做区间， $ans$ 是当前已经得到的可能最小答案）时，直接 return ；

比如 $r\ge lim,lim=2\cdot 10^9$ 时，直接 return ；

比如特判 $l=r$ 的情况。

当然验题人 oxx1108 提出了一种更加精妙（手动划去）愚蠢的解法：

本质就是枚举所有可行的 $n$ ，一个个 check 。

首先，可以明确的是如果 $l \neq 1$ 的时候，该段一定在线段树的右半棵子树上，即 $l > \frac{n}{2}$，因为如果在左半棵子树上的话，那么直接可以把右边丢了，那么将会是一个更小的解。这也意味着要是直接枚举 $n$ 的话，也至多枚举 $l$ 次。但是显然这样是行不通的，那我们来研究下线段树的性质来进行剪枝，以下两种枚举均可，方法一效果更优，方法二在个别 $len$ 小的时候会效果比方法一更好。

方法一：显然在该层线段个数一定为二的次幂，而每个线段长度一定为 $len - 1, len, len + 1$ 之一，因此暴力枚举 $2^k(len - 1) \sim 2^k(len + 1)$ 即可，实验证明无论如何取值（即去掉限制条件），枚举次数上限约为 $5 \times 10^4$。在有限制条件的情况下，可以严格计算出不会超过 $5 \times 10^4$ 次。实际结果跑得飞快，最终大约20 ms。

方法二：由于在该层，每个线段长度必为 $len - 1, len, len + 1$ 之一，因此我们只需枚举 $l + i(len - 1) \sim l + i(len + 1)$ 即可，由于题目的限制条件，因此可以保证枚举次数不会很多。最终大约120 ms。

利用类似性质应该有很多方法能过此题。

花絮

由于出题人本身技艺不佳，原本的题目是限制了 $\frac{l}{r-l+1}$ 的大小的，这样的话，直接暴力就能过了。

牛逼网友 oxx1108 在验题中的代码速度经过优化，甚至跑得比 std 快近 $1000$ 倍，经过斟酌，我们取消了限制条件。

验题人一致认为本场月赛难度太高，又无法严格证明，于是，限制条件又加上了。

Comments

oxx1108 ：递归暴力过不去，只能想野鸡做法了，结果野鸡做法比std跑得还快。如果有会证明野鸡做法正确性的可以交流一下，想了好久不知道为什么可以跑那么快。

Problem D

First Solved：BanFcc

签到题。

要想清楚还是比较麻烦的，大力猜测结论与奇偶性相关，就稳了。

结论是：如果 $|x1-x2|+|y1-y2|$ 是奇数，先手必胜，否则，后手必胜。

下面我们定义距离为两个玩家棋子间的曼哈顿距离，我们发现，每个玩家每个回合开始时距离的奇偶性是保持不变的，因为每个玩家移动时，距离的奇偶性都会发生改变，而到下个玩家移动时，奇偶性就会变回来。由于只有回合开始时距离为 $1$ 时才是必胜态，所以回合开始时距离为偶数的玩家是一定赢不了的。

接着，证明不存在平局情况：

因为一方不可能输，所以想要赢，只要不断拉近距离即可。先来简单证明双方距离不会变大：

无论守方如何移动，双方的距离都最多增加 $1$，而攻方总能找到一个移动方向，使双方距离 $-1$。

因此，想要平局，守方只能保证距离不变。为了不拉近距离，守方肯定会选择远离一方的方向移动。双方之间的位置关系有两种可能：第一种，不在同一行也不在同一列；第二种，在同一行或同一列。

先来讨论第一种情况，我们假设守方在攻方的左上方，那守方只能向左或向上走，否则就会主动拉近距离。此时，攻方只要重复守方的移动即可。因为守方在攻方的左上方，因此如果守方一直向左或向上，肯定比攻方先碰到边界，最终被逼到边角，不得不向右或下方移动，不可能保证距离一直不变。

接着讨论第二种情况，我们假设守方在攻方的正上方，如果守方向左或向右，那攻方只要向上走，就会在不增加距离的情况下变成第一种情况，因此守方只能向上走，但这么走也早晚会碰到边界，最后不得不将情况变成第一种情况。

于是，我们知道两个棋子之间的距离只可能减小。因此，不存在平局情况，回合开始时距离为奇数的一方必胜。

Comments

ultmaster ：牛逼啊？

Xiejiadong ：由于楼上不信，现学了博弈搜索，莽了一发。

Problem E

First Solved：applese

给出 dp 实现的伪代码：

其中第五第六行为背包过程，由于只需要输出答案，因此保留 max 值即可。

F 的含义是不包含子树根结点，其祖先已取的集合为 A 时最大取值，G 的含义是包含子树根结点。

由于一定是祖先中最近的结点最优，因此可以用最近的祖先/距离来代替集合 A，注意空集时候的问题，最终复杂度 $O(n^2k^2)$。

Comments

Xiejiadong ：这个树形 dp 也太难了。想出来了也写不出来。何况我也想不出来。

oxx1108 ：这是从某篇正在研究的paper里提取出来的问题，原本还需要套一个虚树，但是太胖了虚树部分就扔掉了（原来计划放校赛里卡 Xiejiadong ，现在校赛里应该是一堆“友好”的题了）。如果有更好的解法或者推广（到 DAG ，改成无根树等）欢迎交流。

Kilo_5723 ：这题两个星期前就给我了，终于在比赛当天中午验出来了。

恭喜 applese ， caribou ， lanpang 冠亚季军。

29 0

10175101159

5 年，8 月前

[已删除]

oxx1108

5 年，8 月前

非常感谢你分享自己的做法，其实你的构造方式和解法二（我的构造方式）是一样的，主要逻辑也是一致的。只是由于我写的过于简略，可能大家都没看懂。
也很感谢你够花那么长时间来思考月赛题目，其实每一场都会有一些题有很多的思路解法，如果感兴趣深入探究都可以发现出一些很奇妙的方法。
很欣赏你思考问题的精神！

回复 1 0

10175101159

5 年，8 月前

谢谢！！！重新整了一下

我尝试对特例$2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$构造找规律
试了三四种策略发现$a^{2}+b^{2}< c^{2}(1)$容易满足，但$a+b>c(2)$比较困难
于是考虑先满足$(2)$，枚举注意到$2$比较特殊，它所在的组另两数必相邻
前面尝试还发现，如果较小的两个数取的太小，最后一组三个数很容易相邻，难以保证$(1)$
很自然地想到让最小的$n$个数分属$n$组，每组另外两个数恰好满足$(2)$（尽可能间隔拉大）
也就是说$2$所在的组另两数相差$1$，$3$所在的组另两数相差$2$，以此类推
那么每组较大的两个数的相对位置关系形如下图中每行的两个$O$
$XXXXOO$
$XXXOXO$
$XXOXXO$
$XOXXXO$
$OXXXXO$
$…$
下一步就是把这么多行并成一行，容易发现可以把第一行嵌入第三行，再嵌入第五行，以此类推
同理把第二行嵌入第四行，再嵌入第六行，以此类推（但这里多留了个空隙，待会会被更好的方案否决）
这样一种初步方案就被构造出来了：
$02,XX,XX,XX,XX,XX,XX,09,10,XX,XX,XX,XX,XX,XX$
$XX,XX,04,XX,XX,XX,08,XX,XX,11,XX,XX,XX,XX,XX$
$XX,XX,XX,XX,06,07,XX,XX,XX,XX,12,XX,XX,XX,XX$
$XX,03,XX,XX,XX,XX,XX,XX,XX,XX,XX,XX,14,15,XX$
$XX,XX,XX,05,XX,XX,XX,XX,XX,XX,XX,13,XX,XX,16$
其中奇数部分为了去掉前述空隙，采用了偶数部分的图案就解决了
稍微试了一下，貌似可行
但这样构造马上让我思考，偶数的$6$个数放前面（$5+6+4$）呢还是把奇数的$4$个数放前面（$5+4+6$）
想到对第一个奇偶数（$2,3$）而言，因为$n$增大时，$n^{2}$和$(n+1)^{2}$的距离不断变大
所以贪心地只需要把满足$2^{2}=4$的较小要求放在前面，所以先配偶数$2,4,6$，再配奇数$3,5$
到此为止，我们就只需要说明这种构造的正确性了，证明是显然的
偶数部分证明$\forall m[2^{2}+m^{2}<(m+1)^{2},m>2 \Rightarrow \forall i>0[(2+2i)^{2}+(m-i)^{2}<(m+1+i)^{2},2+2i< m-i]]$
展开，只要证$\forall m>2,\forall 0< i<\frac{m-2}{3},4i+8-2m+i\le i+2m+2$即$i\le m-\frac{3}{2}$
而这在$0< i< \frac{m-2}{3},m>2$的条件下恒成立；
奇数部分证明$\forall m[3^{2}+m^{2}<(m+1)^{2},m>2 \Rightarrow \forall i>0[(3+2i)^{2}+(m-i)^{2}<(m+1+i)^{2},3+2i< m-i]]$
展开，只要证$\forall m>3,\forall 0< i<\frac{m-3}{3},4i+12-2m+i\le i+2m+2$即$i\le m-\frac{5}{2}$
而这在$0< i< \frac{m-3}{3},m>3$的条件下恒成立；
这表明只要证奇数偶数的第一行，即$2,m,m+1(m\ge 4)$和$3,m,m+1(m\ge 6)$满足
而相邻两个自然数平方差随着数的增加而增大，只要验证$2,4,5$和$3,6,7$即可
最后单独计算说明只有偶数没有奇数的情况（$2,3,4$）就完成了证明
然后确定一下前$n$个数中奇数偶数分别有多少就能确定边界了
实际操作中发现从$n+1$输出到$2$会比反过来更容易定界：

#include<bits/stdc++.h>
using namespace std;
int n,l1,r1,l2,r2;
int i;
int main()
{
    cin>>n;
    ++n;
    l1=n+1;
    r1=n+n/2*2;
    l2=r1+1;
    r2=3*n-2;
    for(i=n;i>1;--i){
        if(i&1){
            cout<<i<<' '<<l2<<' '<<r2<<endl;
            ++l2;
            --r2;
        }
        else{
            cout<<i<<' '<<l1<<' '<<r1<<endl;
            ++l1;--r1;
        }
    }
    return 0;
}

回复 13 0

10175101189

5 年，8 月前

请问A题解法4第三个数的选区策略？单纯地选择满足条件的最小的数就可以了吗？？？

回复 0 0

Xiejiadong

5 年，8 月前

选择满足三个数组成钝角三角形的最小数。

回复 0 0

seanPan

5 年，8 月前

你好问一下 Problem B 题解有源代码参考吗？
是按照题解思路写的，大部分都可通过。测试用例66总是通不过，不清楚什么原因。

回复 0 0

oxx1108

5 年，8 月前

没开long long

回复 2 0

seanPan

5 年，8 月前

哇塞秒回。改了一下通过了，十分感谢！

回复 0 0

Ostrichcrab

5 年，8 月前

A题的解法2，从中间堆或者大堆是怎么取呢？有策略吗

回复 0 0

oxx1108

5 年，8 月前

参考评论区 10175101159 的评论，就是解法二的构造方式，他已将完整思路以及证明说的比较清楚了。题解写的比较简略深感抱歉。

回复 0 0

kangzenan111

5 年，8 月前

%%%

回复 0 0

huhst-张嘉鑫

5 年，8 月前

解法四似乎会超时（本人TLE11好几发了），对于最坏1e6的情况，剩余数组里有2e6规模的数字，二分需要20次的查找到（最坏），而解法二的用时最低的是0.235s，乘上这20次的二分查找次数就有4s多了，而且看了其他AC的代码，也没有用解法四AC的

回复 0 0

Xiejiadong

5 年，8 月前

提交记录1527719 是这个解法的实现。

回复 0 0

huhst-张嘉鑫

5 年，8 月前

好的。。是本人的能力问题。。。

回复 0 0

花絮

Problem A

First Solved：DeaphetS

解法1

解法2

解法3

解法4

Comments

Problem B

First Solved：dreamoon

Problem C

First Solved：applese

花絮

Comments

Problem D

First Solved：BanFcc

Comments

Problem E

First Solved：applese

Comments

恭喜 applese ， caribou ， lanpang 冠亚季军。

Comments

服务

开源

关于我们