UOJ Logo jiry_2的博客

博客

UOJ Easy Round #5 题解

2015-11-01 21:41:58 By jiry_2

大家好,这里是第二次参与造比赛工作的jiry_2..

承蒙大家的厚爱,在UOJ一周年零一个礼拜之际,参赛人数创历史新高啦owo

这次的UER好像又造的有点偏难了?不过讲道理这已经比上一场UER简单了很多了吧..

因为有很大一部分内容是JRY熬夜意识模糊下的产物,所以出现了什么纰漏也请大家多多包涵QAQ

[upd]因为A题题解写的比较仓促所以题解写错啦QAQ现在已经更正

[upd]感谢数学迷 nneztlk 提供C题等式的组合解释owo

[upd]A题题解的公式一个变量打错啦..现在已经更正。

[upd]A题中点数为 $300860$ 的数据已由 lll6924 构造出。

QAQ

万圣节的南瓜灯

By Picks

算法一

原问题相当于判断删除一些格子后的网格是否是一棵树。所以我们可以直接把图建出来然后用并查集来判断。

时间复杂度 $O(nm \alpha(nm))$,期望得分50分(多良心)。

算法二

可以发现当 $nm$ 很大的时候,这个网格一定不是一棵树。因为树满足点数恰好比边数大1,所以就存在不等式:

$$ nm-K > 2nm-m-4K $$

即 $nm < 3K+m$,所以在 $nm > 4 \times 10^5$ 的时候就可以直接输出 No 了,否则就用算法一来暴力判断。

注:$nm=3 \times 10^5$ 的 Yes 数据可以用如下方式构造:$n=10^5,m=3,K=10^5$,所有满足 $x \equiv y \pmod{3}$ 的格子 $(x,y)$ 被破坏了。$nm=3 \times 10^5 +1$的数据已经由 bzoj构造出,如果能早出更大的数据请直接联系我,我会把它添加到题解以及extra test中,谢谢。

万圣节的数列

妹红多萌啊!

大家好这里是扔了一堆错误数据给 jiry_2BillXu2000

算法一

暴力枚举所有的置换,取等差子序列最少的就行啦!

如果用dfs的话时间复杂度是$O((n+1)!)$的。可以拿到$20$分哦!

算法二

我们先来打个表……诶好像长度为$\leq 10$的排列最优解没有长度$\geq 3$的等差子序列!

我们只要打个表,然后把所有数值相等的数放在一起就好啦!

时间复杂度是O(n)的。可以拿到另外的$20$分哦。

算法三

这题这么sxbk一定有结论!诶好像排列都没有长度$\geq 3$的等差子序列!

我来试着构造一下……你看只要分治就好啦!我们先将原序列排序,设$ans_{i}$为排序后答案第$i$位的数值。

对于一个区间$[l,r]$,我们先分治处理$[l,\lceil \frac{l+r}{2}\rceil ]$与$[\lceil \frac{l+r}{2}\rceil +1,r]$。

然后将左区间内的数$\times 2$,右区间内的数$\times 2-1$就可以啦。

为啥这样是对的呢?因为长度为三的等差数列的首项与末项必定同奇偶,然而在我们递归的过程中保证了不会出现这种情况!

时间复杂度是$O(nlogn)$的。又拿到$20$分啦!

算法四

我觉得吧……既然你会做算法三,推广一下就可以啦!

结论是不可能出现公差不为零的长度$\geq 3$的等差子序列。

对于一个区间$[l,r]$,我们只要把奇数全都丢到这个区间的左边,偶数全都丢到右边,所有数右移一位,递归处理就好啦!

时间复杂度是$O(nlogn)$的。AC啦!

吐槽

Q:这题时间复杂度是$O(nlogn)$的,为啥数据范围只有$500$?

因为出题人想了解一些其他靠谱算法哦!

(其实是误导你们

((真实情况是我们只会写$O(n^{2})$的spj

扩展问题:你们可以想一想算法三的spj怎么做到$O(nlogn)$。

万圣节的糖果

大家好这里是冒充 shanquan2BillXu2000

算法一

我们可以先无视集合的顺序进行计算,然后再$\times n!$。我们之后的算法都是基于这一点来做的。

然后回溯一下就好啦!

时间复杂度是$O((\frac{n}{2}!)^{2})$。应该能拿到$20$分吧……(拿不到别打我

算法二

我们令$f[i][j][k]$表示$1~i$这$i$个糖果分成了$j$个最后一个糖果奇偶性与$i$相同,$k$个最后一个糖果奇偶性与$i$不同的集合时的方案数。

那么$f[i][j][k]=f[i-1][k+1][j-1]\times (k+1)+f[i-1][k][j-1]$。

状态$O(n^{3})$,转移$O(1)$,所以时间复杂度为$O(n^{3})$,可以拿到$50$分哦!

算法三

我有一个绝妙的解法,但是这里空白太小了,写不下。

时间复杂度为$O(n^{2}logn)$,可以拿到$70$分哦!

算法四

我们来讲故事!

正当红包在计算方案数时,BillXu2000敲开了红包家的门,高呼着“泉岭精神不朽,汉中诸球永生”的口号冲进来传教。

红包告诉了BillXu2000他正在想的问题,但是BillXu2000过于泉岭精神,并不能算出方案数。

于是,BillXu2000开始鏼划另一种划分糖果的方案,他想的方案与红包的十分类似,但是唯一不同的是BillXu2000希望每个集合中的糖果奇偶性相同。

以下为BillXu2000的思路:

设$g[i][j]$为将i个不同的数划分成$j$个集合的方案数。

$$ g[i][j]=g[i-1][j-1]+g[i-1][j]\times j $$

设$dp[i][j][k]$为bx2k的划分的方案数,定义同$f$。

$$ dp[i][j][k]=g[\lceil \frac{i}{2}\rceil][j]\times g[\lfloor \frac{i}{2}\rfloor][k] $$

“我算出来啦,是#@%!”BillXu2000逗逼地说。

“为啥我也算出来#@%?”红包并不能理解。

BillXu2000发现他不小心把自己带来的一颗糖算进了答案。

经过他们俩一番思考,他们发现$f[i][j][k]=dp[i+1][k+1][j]$。

在窗外的你偷偷地把这个解法实现,交到了uoj上。

“这样的话只要$O(n^{2})$次计算就可以出结果呢……"你趁着夜色逃了回去。

证明

这题可以用归纳法证哦!

当$i=1$时,只有$j=1,k=0$时方案数为$1$,其余方案数均为$0$。

当$i>1$时,若对于任意$j,k$,满足$f[i-1][j][k]=dp[i][k+1][j]$,则

$$ f[i][j][k]=f[i-1][k+1][j-1]\times (k+1)+f[i-1][k][j-1]=dp[i][j][k+1]\times (k+1)+dp[i][j][k]=dp[i+1][k+1][j] $$

就证好啦!

这个思路是不是很自然呢?

证明二

不自然!

比赛结束以后已经有好多人这么抱怨啦..UOJ萌萌哒的题目也被点了很多差评..

这个时候数学迷英勇地站出来拯救世界啦!

(以下是JRY从评论区贴过来的原话

对于一个分拆我们把每个集合都从大到小排序,然后一个数$x$只要不是所在集合内的最大数,就会有一个前驱(就是所在集合内最小的比它大的数)。

然后对于一个红包分拆,我们添加一个单元集$\{i+1\}$, 然后对于一个数$x$, 如果它是所在集合内最大数,就不动它;如果不是,就令它的前驱为原来的前驱加一。(我们可以从大到小枚举每一个数,这样依次定下每个数后来的位置)就得到了一个BillXu2000分拆。

这样变化之后的拆分显然有$k+1$个最大数和$i+1$奇偶相同的集合(原来的$k$个再加上$i+1$本身)和$j$个最大数和$i+1$奇偶相异的集合(即原来的$j$个),然后逆变换也很显然。

这就证明了$f[i][j][k]=dp[i+1][k+1][j]$。

这样是不是就兹瓷了许多啊..

最后还是要感谢业界良心的数学迷提出了一个这么直观的解释owo

评论

jiry_2
第一是我的!
matthew99
前排
matthew99
前排
mxh1999
中排
BillXu2000
shanquan最2啦!
RAcceleratorPlus
140142
呀,这就后排啦
r_64
http://uoj.ac/contest/20/problem/142是smg UER5不是21吗
WuHongxun
jry业界良心!
tsy
orz
Lvat_s
大后排orz
wxjlzbcd
后排Orz
shanquan2
t3好像还可以递推,参见@San_Siro_Waltz 解答
shanquan2
@BillXu2000 t2的nlogn的spj不是我以前给你讲过吗
bzoj
t1在 n*m>300000的时候也是可以yes的
Derrick_M
t1真的可以啊 这组数据呢 1 1 1000000000 1 1 2
zmx
@BillXu2000 最后一题的等式有没有组合解释?这样的解释很巧妙但是不服啊。。
nneztlk
@zmx 有呀……我们这样子构造一个红包分拆和bx2k分拆之间的对应: 对于一个分拆我们把每个集合都从大到小排序……然后一个数x只要不是所在集合内的最大数,就会有一个前驱(就是所在集合内最小的比它大的数)…… 然后对于一个红包分拆,我们添加一个单元集{i+1}, 然后对于一个数x, 如果它是所在集合内最大数,就不动它;如果不是,就令它的前驱为原来的前驱加一……(我们可以for(x=i;x>0;--x)这样依次定下每个数后来的位置)就得到了一个bx2k分拆……然后它显然有k+1个最大数和i+1奇偶相同的集合(原来的k个再加上i+1本身)和j个最大数和i+1奇偶相异的集合(原来的j个咯),然后逆变换也很显然……这就证明了f[i][j][k]=dp[i+1][k+1][j]…… @jiry_2 考虑把这个证法加到题解么[思考熊] (我是数学迷辣)
Magnificent
求教t3容斥做法
Ayer
菜鸟 问下第一题 1 10000 410000 1 1 1 答案为什么是NO

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。