2019.3 月赛题解

Xiejiadong edited 5 年,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

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

又是 $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)$ ,他的父亲只有四种情况:

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

一些剪枝是必要的。

比如可行性剪枝 $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 冠亚季军。

Comments

10175101159
[已删除]
oxx1108

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

10175101159

谢谢!!!重新整了一下

我尝试对特例$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;
}
huhst-张嘉鑫

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

Xiejiadong

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

huhst-张嘉鑫

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

10175101189

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

Xiejiadong

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

seanPan

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

oxx1108

没开long long

seanPan

哇塞 秒回。改了一下通过了,十分感谢!

Ostrichcrab

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

oxx1108

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

kangzenan111

%%%