负担集训-Test5
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------
A：（赛后通过）
题意就是现在你有一个无向图，通过这些边需要一些时间，现在你有P个一定要去的点，这每一个点也有一个要停留的时间，现在你要从0出发，把这些点全部走一遍再回到出发点，然后还有一种操作，可以花费一定的时间直接从一个点飞到任意一个点，但是只能飞一次，问如果不飞，能否在规定时间内完成，如果不能，那么如果飞能不能。
首先跑个最短路，求出任意两个要去的点之间的最短距离，然后DP一下，设f[i][j][k]表示当前在第i个一定要去的点，已经去过的点是j（j是一个二进制串），是否飞过，最小花费时间。用前面的预处理出来的距离转移一下就可以了。
------------------------------------------------
D:(赛后通过)
题意就是你有一个n*m的地板以及c个砖头，问你用这些砖头能不能平铺这个地板
n,m<=100,c<=7
首先全排列一下放砖头的顺序，然后2^c枚举一下每个砖头是横着放还是竖着放，然后从头到尾枚举每个砖头放的位置，放的位置是这样枚举的：第一个砖头放在(1,1)这个位置，然后后面的就从第一个砖头开始，枚举他右边一列和下面一行的位置，能放就放，如果一个砖头没有地方放，地板也还没有铺满，那么就直接退出枚举下一种情况。
但是这样显然是过不了的，于是有几个剪枝：
一个砖头的右边一列和下面一行的位置，如果这一个砖头没能放进去，那么下一个也不去枚举了
如果不存在i使得前i个砖头的大小加起来等于地板的大小，那么就直接跳过，枚举下一种情况
然后就过了
------------------------------------------------
F:（赛中通过）
给你一个数，问约数个数
pollard-rho即可
------------------------------------------------
G:（赛中通过）
给你一个序列，问是否有序
暴力即可
------------------------------------------------
I：（赛中通过）
给你若干个作品，每个作品用x个整数来表示，第i个表示这个作品的位置i高度
有一个y，表示作品的最大高度
又有若干个操作，每个操作用x个整数来表示，第i个si表示把作品对应位置高于y-si的部分削去
现在对每个作品做每个操作，问每个作品最后长什么样
x<=100,y<=100,作品数、操作数<=10000
只需要把同一个位置的操作合并一下，只留下最大的si，然后模拟即可。
------------------------------------------------
评论 (0)
