负担集训-Test13
负担集训-Test15(多校联合训练-6)

负担集训-Test14(多校联合训练-5)

YYY posted @ 2017年8月09日 16:17 in ACM with tags 懒得写了 , 169 阅读
--------------------------------------------------------------
全程摸鱼...我觉得我大一开学就能开个鱼塘了...
 

--------------------------------------------------------------
1008:
题意就是说给你一个多重正整数集合所有的子集和,请你还原这个集合。
集合大小$\leq 50$,子集和$\leq 10^4$
 
从小到大枚举一下集合元素大小,依次还原。
假设我们已经还原了所有$\leq k$的元素了,那么我们只需要知道已经得到的元素拼出$k$有多少种方案,再用和为$k$的子集个数减一下就可以得到大小为$k$的元素个数。
为了得到用已有元素拼出$k$的方案数,我们可以维护一个数组$f[i]$表示已经得到的元素拼出$i$有多少种方案,然后每次得到一个元素后就更新一下这个数组。
 
--------------------------------------------------------------
1001:
题意就是说给你一个长度为$n$的数组$a$,一个长度为$b$的数组$b$,以及$q$个询问,每个询问给出一个$k$,询问使得$a[i]\ mod\ b[j] = k$的二元组$(i,j)$的个数。答案模$2$输出。
$n,m,q\leq 50000,a,b$中的元素没有相同的。
 
首先$a[i]\ mod\ b[j] = k$相当于$a[i] = k + nb[j]$
那么我们把$a$放到桶里面,再把$b$每个元素的每个倍数放到桶里面,桶里面的出现次数都模$2$,这样就得到了一个$01$串,然后每得到一个$k$,就把$a$右移$k$位和$b$做与运算,再把结果统计一下$1$的个数就好了。
当然这样是错的,因为有一种情况没有考虑到,就是当$k$大于$b$的情况,这种情况下满足$a[i]=k(mod\ b[j])$但是不满足$a[i] = k + nb[j]$,于是我们就把询问排序,再把$b$排序,然后倒着加,每次加一个$k$的时候就把比他大的$b$加进去,然后再来询问,这样就可以避免上述情况了。
-----------------------------------------------------
记录:
一开始我们看了看题,刷了下榜,发现11题有人A了,于是就跑去把11题写了,然后继续看题+刷榜,最后发现06、08都是比较可做的题,然后gmr和ljz就去想06,yyy就跑去想08,然后ljz过了一会儿说会写了,然后就写写写,然后就调调调,然后就调不出来,然后yyy发现1008会做了,然后就去写写写,写到一半lzj突然知道1006哪里错了,然后就改改改,然后就A了,然后过了一会儿1008也A了。这个时候我们看了下榜,发现整个复旦都是3题,然后我们就震惊了,然后我们看了下榜,决定重点想01、02,然后yyy使用了多次上厕所大法之后终于会做1001了,写写写发现这个思路是错的,过不了样例(mdzz),然后yyy又上了多次厕所之后终于会做了,然后写写写,然后就A了,然后我们就一直在想02,ljz觉得应该是一个ac自动机有关的dp,gmr拍着胸脯说“这题是ac自动机我直播剁**”。结果我们就一直没想出来。最后讲题的时候我们发现这道题应该用ac自动机。
-----------------------------------------------------
总结:
这一次我们a了4道题之后就再也没动过了,但是其实这次很多我们看都没看的题都是可做的,比如说1009,但是我们一直是盯着榜上ac人数最多的题在做,所以很多题都没去想,这样虽然有一定便利,但是我觉得在整个队都卡住没有可做的题的时候还是可以尝试一下ac人数比较少的题的。
-----------------------------------------------------
 
LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter