负担集训-Test14（多校联合训练-5）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------
全程摸鱼...我觉得我大一开学就能开个鱼塘了...
--------------------------------------------------------------
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人数比较少的题的。
-----------------------------------------------------
评论 (0)
