负担集训-Test18
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------------------------------
这场出题人sb卡英语，没什么好说的。
---------------------------------------------------------
B:
题意就是说给你n个数a，求一个a的排列使得下式最大：
f(a) = ||...||a[1]-a[2]|-a[3]|-a[4]|...-a[n]|
n<=300,a[i]<=300
因为答案不超过300，而且似乎要控制只有某一种特定的排列使得f最大是不太容易的，因此不断随机打乱更新答案，就很容易得到最大值。
---------------------------------------------------------
G:
现在给你n个质数p1,p2...pn，求一个数x使得对于任意i存在正整数t满足t^p[i]|(x/p[i])，并且要求x最小
n<=1000,pi<=10^9
首先x肯定是p[i]的倍数，假设x=Pi(i)p[i]^a[i]，那么对于任意(i,j)就一定满足：
p[i]|a[j] (i ≠ j)
p[i]|a[j]-1 (i ＝ j)
对于i，就有a[i]=1(mod p[i]) , a[i]=0(mod p[j])(j ≠ i)
因为p都是质数，因此对于j≠i的部分肯定就是直接把诸p乘起来，假设是p'
那么就有a[i]=1(mod p[i]),a[i]=0(mod p')
只需要求最小的满足这个的a[i]
我们构造一个答案：a[i] = p'(p'^(-1) mod p[i])，这个数是小于p[i]*p'的，而根据中国剩余定理，p[i]*p'内一定有且只有一个解，因此这个解就是最小解。
---------------------------------------------------------
H:
题意是说给你一个序列，他的一个排列是合法的当且仅当存在i<j，且i第一次出现的位置在j第一次出现的位置后面
求合法的排列数
这个序列包含的不同的数的个数不超过20，每个数的重复次数不超过10^16
我们先只考虑第一次出现的数，这样的话合法的序列就是存在逆序对的序列，我们可以用所有排列减去有序的排列
所有可能的排列数是很容易用组合数求出来的。
对于有序的排列，我们现在把重复的数加进去，考虑从后向前加，假设第i个数重复次数是c[i],那么相当于把c[i]-1个小球放到(c[i+1]+c[i+2]+...+c[n]+1)个盒子中的方案数，这个也是很容易用组合数求的。
至于怎么求组合数，我们可以通过分块打表+lucas定理来求。
---------------------------------------------------------
I：
给你一个n*m的矩阵，求他的所有子矩阵的大小之和
n,m<=10^9
随便推一下公式，答案就是Sigma(i=1,n)i*(n-i+1)Sigma(j=1,m)j*(m-j+1)
随便求一下就好了。
---------------------------------------------------------
K：
说现在地上有一个大小为n的石子堆，现在有一个操作，就是选择一堆石子，把他分成两堆石子，然后答案加上这两堆的大小之积，现在给出一个数t，问能否在若干次操作后得到答案t。
n<=300,t<=10^9
首先容易发现n<=300的情况下答案最大不超过50000，因此t>50000的情况可以忽略掉。
另外可以发现答案只和最后的局面有关，和中间过程无关。
因此我们就每分出来两堆石子，我们就假设其中一堆再也不分了，这样就相当于每次从原来那堆石子里面分出来一点。
因此有一个显然的dp：f[i][j]表示一开始有i个石子，拼出j是否可行，我们可以枚举每次分出来的大小来转移。
然后用bitset优化一下，就可以过了。
-----------------------------------------------------
比赛记录：
开始大家就按照各自的顺序看题，过了一会儿gmr发现C题是个水题，写了一写过了。过了一会儿ljz觉得I题也是个水题，于是写写写，又过了。同时ljz又觉得F题可以乱搞，于是让gmr去写写写，然后血wa，这时ljz和yyy讨论了一下G，想到了一种乱搞，然后写写写，又wa了，然后gmr又回去写G，调了半天发现看错题了，然后终于A掉。这时yyy想了一会儿觉得K会做了，就写写写把K A了，然后我们就没题做了，就一直卡着，大家都在想G和B，然后过了一会儿ljz构造出了G的解，成功A掉了G（事后问了一下其他队都是exgcd做的，只有ljz是直接把解构造出来的Orz），然后大家就去想B，想了一会儿ljz觉得可以随机乱搞，大家觉得很有道理，于是写写写，然后A了，然后大家就去想H和E，一开始我们觉得这个范围应该不能用组合数，后来ljz说可以用分块打表+lucas定理强行用组合数，于是yyy就想了一种用组合数的做法，然后调了半天成功A掉了。
-----------------------------------------------------
比赛总结：
我们队罚时老是垫底，总是因为各种莫名其妙的错误，尤其是sbyyy经常一道水题交几次才A。
这一次主要坑掉我们罚时的错误有：看错题、没删调试语句、用clock()卡时间却忘了linux下clock()是以微秒为单位的、用lucas定理求C(n,m)没有判断n<m的情况。
总之应该在交代码之前仔细思考一下。
另外读题也是个大问题啊...不知道正常的acm比赛是不是像这样，有很多理解错了就会让题意差之千里的单词或者短语，然后导致水题变神题什么的...
-----------------------------------------------------
-----------------------------------------------------
评论 (0)
