负担集训-Test16
负担集训-Test18

负担集训-Test17

YYY posted @ 2017年8月16日 00:50 in ACM with tags 懒得写了 , 204 阅读
---------------------------------
今天没有做多校,说是因为出题人是中学生哈哈哈哈哈
整个机房喵成一片
 

 
--------------------------------
C:
题意是说,现在有n个商店,有m个要买的物品,每个商店对于每个物品都要一个价格,而且每个商店去一次都要交一次门票钱,问买齐这些物品最少要多少钱。
n<=100,m<=16
 
首先预处理一下c[s]表示在同一个商店买齐s这些物品(s是一个二进制串)最少花的钱。
然后dp一下,f[s]表示买齐s这些物品(s是一个二进制串)最少花的钱,每次枚举s的子集来转移,这个时间复杂度是O(3^m)的
---------------------------------
D:
给你一串n个数,问有多少对(i,j)使得a[i]|a[j] (i!=j)
n<=200000,a[i]<=2000000
 
枚举一下1~2000000内每个数的倍数,看一下出现次数,然后把a中每个数的倍数的出现次数加起来再减n(除去自己)就可以了
---------------------------------
E:
给你一堆n个石子,现在两个人甲乙玩游戏,甲每次可以拿p的任意正整数倍个,但是如果不足p个,就必须添上p个,乙每次可以拿q的任意正整数倍个,但是如果不足q个,就必须添上q个,先把石子拿完的获胜。
 
首先求gcd(p,q),如果n不整除这个数的话显然无解,然后让p、q、n都除以他们的gcd。
现在不断地+p、+q直到当前的先手可以拿石子了为止,如果他是乙的话就交换甲乙的地位。
容易知道如果p<=q且n>=p的话先手就赢了,因为每次p拿完之后q必须加上去,而p,q互质,因此每次p拿完之后剩的石子数是不一样的,因此总有一天p能把他拿到0个。
如果p>q,那么先手肯定要给乙留下必须加石子的局面,否则就像上面说的那样,乙必胜了,设p拿完之后剩下的石子数是k,那么之后一定是加q个,拿p个...因此可以检查k mod (p-q)如果为0的话就是甲胜,否则总有一天乙可以达成上述的必胜情况。
---------------------------------
F:
给你一个n*m的地面,有一些2*2的障碍物,让你规划一条欧拉回路。
n,m都是偶数且<=1000,任意两个障碍物的中心距离不超过6,任意一个障碍物距离边界不超过3
 
首先按一路向右,然后向上,再折向下,再折向上...这样的路线来规划一个没有障碍物时可行的路径,然后考虑障碍物,根据题面条件,任意两个障碍物是不会相互影响的,障碍物和边界也不会互相影响。然后我们只需要讨论障碍物的左下格子的列数为奇数、为偶数且距离下边界的距离恰好为3、为偶数且距离下边界的距离不为3这三种情况就行了。
---------------------------------
LOL

登录 *


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