负担集训-Test17
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
---------------------------------
今天没有做多校，说是因为出题人是中学生哈哈哈哈哈
整个机房喵成一片
--------------------------------
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这三种情况就行了。
---------------------------------
评论 (0)
