负担集训-Test17
负担集训-9.9(icpc乌鲁木齐站-网络赛)

负担集训-Test18

YYY posted @ 2017年8月16日 20:35 in ACM with tags 懒得写了 , 636 阅读
_THIS_IS_START_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比赛是不是像这样,有很多理解错了就会让题意差之千里的单词或者短语,然后导致水题变神题什么的...
-----------------------------------------------------
 

 

-----------------------------------------------------

_THIS_IS_END_OF_ARTICLE_

登录 *


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