负担集训-Test5

------------------------------------------------
垫底_(:з」∠)_ 
复旦怎么会收我这么菜的学生啊...
------------------------------------------------

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,然后模拟即可。
------------------------------------------------