2019.3 月赛题解

Xiejiadong edited 6 年前

花絮

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

牛逼网友 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

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

又是 $3 n$ 个，又是三角形，最直接想法就是分成三堆（最小的 $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, 2 n + 1, 3 n + 1$ 即可。证明显然。

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

解法3

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

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

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

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

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

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

解法4

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

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

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

Comments

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

Problem B

First Solved：dreamoon

签到题。

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

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

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

Problem C

First Solved：applese

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

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

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

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

一些剪枝是必要的。

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

比如 $r \geq l i m, l i m = 2 \cdot 10^{9}$ 时，直接 return ；

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

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

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

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

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

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

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

花絮

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

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

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

Comments

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

Problem D

First Solved：BanFcc

签到题。

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

结论是：如果 $| x 1 - x 2 | + | y 1 - y 2 |$ 是奇数，先手必胜，否则，后手必胜。

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

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

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

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

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

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

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

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

Comments

ultmaster ：牛逼啊？

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

Problem E

First Solved：applese

给出 dp 实现的伪代码：

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

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

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

Comments

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

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

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

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

29 0

10175101159

6 年前

[已删除]

oxx1108

6 年前

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

回复 1 0

10175101159

6 年前

谢谢！！！重新整了一下

我尝试对特例 $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$
$X X X X O O$
$X X X O X O$
$X X O X X O$
$X O X X X O$
$O X X X X O$
$\dots$
下一步就是把这么多行并成一行，容易发现可以把第一行嵌入第三行，再嵌入第五行，以此类推
同理把第二行嵌入第四行，再嵌入第六行，以此类推（但这里多留了个空隙，待会会被更好的方案否决）
这样一种初步方案就被构造出来了：
$02, X X, X X, X X, X X, X X, X X, 09, 10, X X, X X, X X, X X, X X, X X$
$X X, X X, 04, X X, X X, X X, 08, X X, X X, 11, X X, X X, X X, X X, X X$
$X X, X X, X X, X X, 06, 07, X X, X X, X X, X X, 12, X X, X X, X X, X X$
$X X, 03, X X, X X, X X, X X, X X, X X, X X, X X, X X, X X, 14, 15, X X$
$X X, X X, X X, 05, X X, X X, X X, X X, X X, X X, X X, 13, X X, X X, 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 + 2 i)^{2} + (m - i)^{2} < (m + 1 + i)^{2}, 2 + 2 i < m - i]]$
展开，只要证 $\forall m > 2, \forall 0 < i < \frac{m - 2}{3}, 4 i + 8 - 2 m + i \leq i + 2 m + 2$ 即 $i \leq 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 + 2 i)^{2} + (m - i)^{2} < (m + 1 + i)^{2}, 3 + 2 i < m - i]]$
展开，只要证 $\forall m > 3, \forall 0 < i < \frac{m - 3}{3}, 4 i + 12 - 2 m + i \leq i + 2 m + 2$ 即 $i \leq m - \frac{5}{2}$
而这在 $0 < i < \frac{m - 3}{3}, m > 3$ 的条件下恒成立；
这表明只要证奇数偶数的第一行，即 $2, m, m + 1 (m \geq 4)$ 和 $3, m, m + 1 (m \geq 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

Ostrichcrab

6 年前

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

回复 0 0

oxx1108

6 年前

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

回复 0 0

kangzenan111

6 年前

%%%

回复 0 0

huhst-张嘉鑫

6 年前

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

回复 0 0

Xiejiadong

6 年前

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

回复 0 0

huhst-张嘉鑫

6 年前

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

回复 0 0

10175101189

6 年前

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

回复 0 0

Xiejiadong

6 年前

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

回复 0 0

seanPan

6 年前

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

回复 0 0

oxx1108

6 年前

没开long long

回复 2 0

seanPan

6 年前

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

回复 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

服务

开源

关于我们