2016.09.15noi模拟考

Problem A

题意

定义矩阵中元素是鞍点仅当它是行和列中严格最大的元素.现在你有一个列的的矩阵,其中的元素都是中的整数.求出至少有一个鞍点的矩阵数对的值.

感想

根本不会做,写个暴力都还要打表才能拿分,果断弃疗.

思路

如果直接一行一行的确定鞍点来递推的话,是根本不好转移的.
看到题目中鞍点的定义,可知一个鞍点,它所在行和列中的其它元素都小于它.那么如果我们将鞍点从小的往大的放,就不必考虑之前的鞍点的限制了,并且肯定是可以不重不漏的.那我们已经知道怎么去考虑了,现在的任务就是求出只有个鞍点,个鞍点,个鞍点...个鞍点的矩阵数量.
设状态表示目前有个鞍点,其中最大的鞍点值为的方案数.则转移方程为:

但是这是的,不能接受.但是发现其实我们只要改变一下状态,令表示目前有个鞍点,其中最大的鞍点值的方案数,每次考虑从转移到就行了,依然是不重不漏的,复杂度为.

但是怎么统计答案呢?不能直接将加起来,因为我们转移是相当于慢慢地去将矩阵填满,而我们状态仅仅只填了和当前所填的鞍点有关联的行和列,也就是说还有一些格子没有填.直接填的话,可能又会和其它的状态有所重复.
表示鞍点数正好为的方案数.要大于.设.它们之间的关系是:

我们要求,变化一下式子可得:

发现是可以由大的往小的递推出来的,那么已经可以算出答案了.
但其实是可以算出答案的.数学中有一个恒等式:

我们想要的答案是,那么:

2016.09.16noip模拟考

Problem A

题意

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

感想

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

思路

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

Problem B

题意

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

感想

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

思路

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

Problem C

题意

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

感想

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

思路

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

C++ 线性筛法

for(int i=2;i<=mx;++i){
    if(!inp[i])prm[++cnt]=i;
    for(int j=1;j<=cnt&&(t=prm[j]*i)<=mx;++j){
        inp[t]=1;
        if(!(i%prm[j]))break;
    }
}

保证线性的关键在那个if语句,现在解释一下.
看得出来,使得if语句执行的prm[j]一定是i的最小质因子.
那么设.
若我们继续枚举,那么我们会筛掉,即.此处,那么.
换一种写法,即.发现.
那么我们可以在枚举更大的i的时候筛掉t.好吧那我们就不必在此继续了,break.
那么每个数都只会被它最大的因子×最小质因子筛掉,因此只会被筛掉一次.所以线性由此而来.