注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

HNOI2012 全题解(Day1)  

2012-04-29 14:01:59|  分类: HNOI |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
双十字:
首先预处理出每个点向左向右最多能拓展多少个1。然后枚举双十字的竖线底端的位置。对于每一列都统计下答案,然后加起来。对每一列统计答案的方法是,引一条扫描线,从上往下扫,有一个数组v,和一个高度top。v一开始为空,top一开始为-1。如果碰到0就清空数组,top=-1;碰到1并且top=-1就让top等于当前高度,碰到拓展值大于0的就把这个位置往v里丢。
每碰到一个1,就统计一下答案。方法是枚举v中所有不相邻的两行l1、l2,算出双十字的两横线是l1和l2的方案数(l1<l2)。记l1、l2的拓展值分别是w1、w2,那么方案数delta为:start = max(1, w2 - w1),delta = ((start + w2 - 1) * (w2 - start) / 2) * (l1 - top)。所以我们得到了暴力算法。
我们可以发现,算delta很多时候我们都在算一些重复的东西,如果某段时间扫描线遇到的一直是拓展值为0的方块,那么delta值都是相等的!
所以我们记一个数add,每找到一个拓展值大于0的方块,就用刚才的公式更新add。要统计方案时,就直接把结果加上add即可。
可是这样时间复杂度依然很高,进一步优化的余地在哪里?
整个算法中,最耗时间的部分是算add,即已知top和w2,求所有满足一定要求的w1带入公式后的值之和。我们需要一个数据结构,能支持不断询问,不断插入新的w1,那么它是什么呢?

首先再来看看公式,里面有个min实在太讨厌了,于是把公式裂为两个:
delta = (2 * w2 - w1 - 1) * w1 * (l1 - top) / 2        (w2 - w1 > 1)
delta = w2 * (w2 - 1) * (l1 - top) / 2                     (w2 - w1 <= 1)

那么也就是说,事实上我们需要三个值:
w1 * (l1 - top)
w1 * (w1 + 1) * (l1 - top) / 2
l1 - top
把这三个值放在三个数组的下标为w的位置上,于是原问题变为了:我们需要一个数据结构,能支持不断查询下标大于某个值的值之和,下标小于等于某个值的值之和,不断在某位置加入新的值。

读者看到这里,也就知道这个数据结构是啥了吧……本蒟蒻就不点名了。

与非:
首先想到,为什么有些数是不能表示出来?那就是因为某些二进制位没体现它的特殊性。何为特殊性?我们一起来看看下面的例子:
两个二进制数:110和001,多自己折腾一下发现,无论你怎么折腾与非运算,结果的前两位总是相同的!这就是因为这两个二进制数的前两位,一个是11,一个是00,无论怎么运算,这两个位都不可能不同,它们的结果总是作为一个整体出现,体现不出自己的特殊性!
那么我们得到了一个必要条件,即若把所有题目中给的二进制数以二进制形式排成n行,那么若有两列完全相同,则所有运算结果的这两位肯定相同。
既然如此,这是否是充分必要条件呢?即若把所有题目中给的二进制数以二进制形式排成n行,得到一些限制,这些限制要求,结果的某两位是相同的。那么所有满足所有限制的二进制数都是可以通过若干次nand算出的结果。
好像是对的耶?怎么证?

首先讨论只有两个数的情况。
那么列一下真值表:
 aa nand b a nand b nand a a nand b nand b (a nand a) nand (b nand b)
 0 0 1 1 1 0
 0 1 1  1 0 1
 1 0  1  0 1 1
 1 1  0  1 1 1
通过真值表我们可以发现,若现在有两个数,根据上面说的结论,如果某两位一定相同,我们就把这两位分为一组,那么我们一定可以通过某种方式使得某一组的值为0,其它全为1。
可否让某两组的值变为0呢?我们只需要一个与运算就可以了!可是我们只有与非啊……
可以用nand构造出and:a and b = (a nand b) nand (a nand b)
于是我们一定可以通过某种方式使得某两组的值为0,其它全为1。
同样的方法,我们一定可以通过某种方式使得某三组的值为0,其它全为1。我们一定可以通过某种方式使得所有组的值为0。
至此,我们证明了,在只有两个数时,所有满足所有限制的二进制数都是可以通过若干次nand算出的结果。

这个结论可否推广到n个数的情况?答案是肯定的。读者用脚丫子想也可以轻易地证明之。

于是原问题变成了:给你一些限制,求满足限制的在区间[l, r]范围内的数有多少个。
这就是个非常简单的数位统计问题了。

排队:
这道题是唯一一道我在考场上AC了的题……大牛勿鄙视。
我首先的想法是:先让男生排好顺序,接着往缝里丢女生,再放老师。结果我发现老师把站在一条缝里的女生隔开了的这种情况很难讨论……
于是我换种思路:先让男生排好顺序,接着往缝里丢老师,再放女生。
首先男生排好顺序是n!,接下来分类讨论:
1.老师放在了一条缝里:那么肯定有一个女生站在老师中间,所以是A(1, n + 1) * 2! * m * A(m - 1, n + 2)
2.老师不在同一条缝里:A(2, n + 1) * A(m, n + 3)
接下来就是高精度的事了。

矿场搭建:
首先……如果去掉一个点……那么剩下的每一个联通块中都必须至少有一个出口。那么枚举删掉的点,可以得到一大堆限制,即某些点中至少有一个出口。
一个显然的事:如果某个限制是:A、B、C中有一个出口,另一个限制是A、B中有一个出口,那显然前者是个废的,可以直接忽略。推广之就是,如果一个限制包含另一个限制,那么前者是无用的。
我在考场上得出一个我不会证的结论:这些限制若某两个有交集,那么它们肯定会各包含另一个小限制。也就是说,按照上面的结论删去无用的限制以后,最后剩下的限制肯定没有交集。
所以算法就是,首先去掉每个点,算出所有限制,去掉废条件。那么第一问答案就是剩下的限制数,第二问答案就是剩下的每个限制包含的节点数之积。
于是我就这样写了……80分入手,剩下的那两个点WA了。

问题出在哪里呢?我们来看看这个结论怎么证:
HNOI2012 全题解(Day1) - vfleaking - vfleaking的博客
如果说现在有个点a,去掉它后图变为了三个联通块A、B、C。考虑联通块B中的一个节点b。
1.如果b不是割点,那么由去掉b得到的限制肯定是:原图中不包含b的点中要有一个出口,显然包含了一个小的限制A(或C),是个废条件。
2.如果b是割点,那么去掉b后,图顶多是B分为了好几块,B的某一小块与a、A、C成为一个联通块。显然B分成的好几块被B包含,B变成了废条件;B的某一小块与a、A、C成为的联通块,显然包含了A,于是这是一个废条件。
证明完毕。

那么既然证明都给出来了,问题究竟出来哪呢?原来,在刚才的讨论中,我们先假设了一个割点a,才得出了刚才的结论。我们能假设一个割点a的前提条件是,图中有一个割点!(我真是傻×…………考试时居然没想到……不然就AC了……)
所以说,我们只要特判图中没割点的情况即可。图中没割点,那么第一问答案是2,第二问答案是n * (n - 1) / 2(n是节点数)
  评论这张
 
阅读(1784)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017