2016.09.16noip模拟考

Problem A

题意

个点,个操作,每次加入一条边,并询问有多少个子图满足每个点的度数都是非零偶数.

感想

考试时完全没有往正解那方面想过.一开始想法就是,看增加一条边,要怎么算它的贡献.发现即使算的出来也不好维护,想了一个半小时,实在想不出,就干脆打暴力.先是直接打了个找环,发现根本不好找,一个子图会被重复计算多次.然后就慌了,一直忘了看数据范围,后来一看,发现暴力的范围,.这就好打了,枚举边集然后看是否是一个环即可.但我以为选出的子图必须要联通才行,结果暴.

思路

考后别人告诉我,让我看看样例.:看不出有啥特点啊.:你难道没发现答案都是吗.:还真是,那这是为什么呢?
正解是这样的.做一个并查集,每次加边,若两个点不在同一集合内,并起来放着.如果在同一集合内的话,.每次输出就行了.
证明详见博客:NYHTN 's Blog

Problem B

题意

场擂台,每场擂台获胜的概率是,获胜可以获得一个地图碎片或者是一个容量为的背包,一个单位的容量可以装一个地图碎片.开始时有一个容量为的背包,至少要打赢次擂台才能退出擂台.问把所有的到的碎片全部带走的概率是多少.

感想

看一眼就知道是一道题,并且知道,那么大肯定是逗你玩的.实际上它们超过的部分是没有意义的,所以迅速设好状态表示考虑到第场擂台,赢了场,有张地图碎片,容量的背包时的概率,很好转移,于是乎的做法就出来啦!貌似有点爆空间,木有关系,滚动数组就行.好像会超时,这可怎么办?把第三维改成背包容量地图碎片应该就行了.新鲜出炉.不过...怎么只有半个小时了!不管了直接打第三题去!

思路

正解就是上面讲过的的做法.

Problem C

题意

给你数轴上的个互不重叠的区间,再给出一个,要求将个数字分类,使得在任意一个区间中,取出任意一个整数,将其后位中的任意一个数字,换成和它同一类的数字中的任意一个,得到的数字仍然在这些区间内.

感想

理解题意理解了半天,以下是原题面:
对于两个数字,如果对于这个波段内的任意一个整数,把它在十进制表示下的后位中某一位上的换成(或者换成),满足得到的整数仍然在这个波段内,那么称在该激光器中,数字等价的.我们称两两之间等价的数字组成一个等价类.
,讲的什么鬼.这是赤裸裸的恶意啊!!出题人说这是一道防题,果不其然,读错题的就有几人.
的理解是这样的:
对于每一个数字,只要将其后位中的某一位改为是可行的,那么这一类对于这个数字就是合法的.
而我是这么理解的:
对于每一个数字,若将其后位中的每一位都改为是可行的,那么这一类对于这个数字才是合法的.
结果我发现我根本没法输出.举个例子:(一个数字一个区间).在这里,照我的理解,是等价的,是等价的,却不是等价的,搞毛啊!

思路

枚举两个数字,再枚举一个,判断等价对于第位是否合法,再枚举一个区间判断对于每个区间是否合法.显然,对于一个区间,变换的范围是断断续续的几个区间,并且若是合法,这些区间肯定要被某些区间真包含.但是发现,如果,说明换了后的数字会更大,只需考虑右端点往外跳的情况.并且发现,我们只需要考虑最大的这段.因为更小的话,它一定能被自己这段区间真包含.找出它能变换到的区间,判断这个区间是否被某个区间真包含即可.然后也是同理.
然后就是极为麻烦的实现问题了.这里不赘述.