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 |
构造题。解法非常多。
首先无解是唬你的,不存在无解的情况,可以很容易的证明,这里省去。
随机。
我们首先按照顺序三个三个分组,发现其中有一些是不满足要求的,于是考虑随机交换。
每次随机选择一组的第二个和另一组的第三个进行交换。
但是我把我自己卡掉了。
大家有更好的随机策略可以在评论区交流。
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 的分享。
通过解法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$ 的情况类似。
同样我们默认每组的第一个是 $2$ 、 $3$ 、$\cdots$ 、$n$ 、$n+1$ ,考虑从最后一组开始。
第二数选择当前没有被选择的数中最小的一个数,然后在剩下的数中二分寻找一个满足要求的最小数。
可以证明,这样的构造方法是满足要求的。
oxx1108 :套路的构造题,但是好像大家都觉得有点难?可能更适合放数学竞赛里吧……
签到题。
考虑最旁边的两个数,如果相等,直接略过他们,因为他们本身已经是回文了;
如果不相等,那么一定是较小的一个要向内合并,合并完以后继续比较当前最旁边的两个数。
显然这样的策略是最优的,最坏的情况就是,所有的数合并成一个数,一个数显然满足回文。
一种解法是显然的,我们的线段树建法,决定了线段树要么左右孩子等大,要么左孩子比右孩子大 $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$ 倍,经过斟酌,我们取消了限制条件。
验题人一致认为本场月赛难度太高,又无法严格证明,于是,限制条件又加上了。
oxx1108 :递归暴力过不去,只能想野鸡做法了,结果野鸡做法比std跑得还快。如果有会证明野鸡做法正确性的可以交流一下,想了好久不知道为什么可以跑那么快。
签到题。
要想清楚还是比较麻烦的,大力猜测结论与奇偶性相关,就稳了。
结论是:如果 $|x1-x2|+|y1-y2|$ 是奇数,先手必胜,否则,后手必胜。
下面我们定义距离为两个玩家棋子间的曼哈顿距离,我们发现,每个玩家每个回合开始时距离的奇偶性是保持不变的,因为每个玩家移动时,距离的奇偶性都会发生改变,而到下个玩家移动时,奇偶性就会变回来。由于只有回合开始时距离为 $1$ 时才是必胜态,所以回合开始时距离为偶数的玩家是一定赢不了的。
接着,证明不存在平局情况:
因为一方不可能输,所以想要赢,只要不断拉近距离即可。先来简单证明双方距离不会变大:
无论守方如何移动,双方的距离都最多增加 $1$,而攻方总能找到一个移动方向,使双方距离 $-1$。
因此,想要平局,守方只能保证距离不变。为了不拉近距离,守方肯定会选择远离一方的方向移动。双方之间的位置关系有两种可能:第一种,不在同一行也不在同一列;第二种,在同一行或同一列。
先来讨论第一种情况,我们假设守方在攻方的左上方,那守方只能向左或向上走,否则就会主动拉近距离。此时,攻方只要重复守方的移动即可。因为守方在攻方的左上方,因此如果守方一直向左或向上,肯定比攻方先碰到边界,最终被逼到边角,不得不向右或下方移动,不可能保证距离一直不变。
接着讨论第二种情况,我们假设守方在攻方的正上方,如果守方向左或向右,那攻方只要向上走,就会在不增加距离的情况下变成第一种情况,因此守方只能向上走,但这么走也早晚会碰到边界,最后不得不将情况变成第一种情况。
于是,我们知道两个棋子之间的距离只可能减小。因此,不存在平局情况,回合开始时距离为奇数的一方必胜。
ultmaster :牛逼啊?
Xiejiadong :由于楼上不信,现学了博弈搜索,莽了一发。
给出 dp 实现的伪代码:
其中第五第六行为背包过程,由于只需要输出答案,因此保留 max 值即可。
F 的含义是不包含子树根结点,其祖先已取的集合为 A 时最大取值,G 的含义是包含子树根结点。
由于一定是祖先中最近的结点最优,因此可以用最近的祖先/距离来代替集合 A,注意空集时候的问题,最终复杂度 $O(n^2k^2)$。
Xiejiadong :这个树形 dp 也太难了。想出来了也写不出来。何况我也想不出来。
oxx1108 :这是从某篇正在研究的paper里提取出来的问题,原本还需要套一个虚树,但是太胖了虚树部分就扔掉了(原来计划放校赛里卡 Xiejiadong ,现在校赛里应该是一堆“友好”的题了)。如果有更好的解法或者推广(到 DAG ,改成无根树等)欢迎交流。
Kilo_5723 :这题两个星期前就给我了,终于在比赛当天中午验出来了。
解法四似乎会超时(本人TLE11好几发了),对于最坏1e6的情况,剩余数组里有2e6规模的数字,二分需要20次的查找到(最坏),而解法二的用时最低的是0.235s,乘上这20次的二分查找次数就有4s多了,而且看了其他AC的代码,也没有用解法四AC的
非常感谢你分享自己的做法,其实你的构造方式和解法二(我的构造方式)是一样的,主要逻辑也是一致的。只是由于我写的过于简略,可能大家都没看懂。
也很感谢你够花那么长时间来思考月赛题目,其实每一场都会有一些题有很多的思路解法,如果感兴趣深入探究都可以发现出一些很奇妙的方法。
很欣赏你思考问题的精神!
谢谢!!!重新整了一下
我尝试对特例$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$会比反过来更容易定界: