training-2016.08.15
这场训练的题目在这里2016 Multi-University Training Contest 6
代码在这里Our code
A题
题意……没啥想说的，打表找规律题，发现ans(n,m) = $ \frac{m^{n + 1} - 1}{m - 1} $
B题
题意：国际象棋的马，从(1,1)跳到(n,m)只能向右下跳（即横纵坐标都单调递增），n、m都是10^18，平面上有ｒ(r<=100)个坏点，问不经过任何一个坏点的方案数。
做法：从(x1,y1)到(x2,y2)，只有两种跳法，所以每种跳法的次数是可以解方程解出来的：
- 2x + y = x2 - x1
- x + 2y = y2 - y1
所以如果不考虑坏点的话用一个组合数就可以算出来了(Lucas定理)
然后发现直接容斥是会炸的，我们考虑用dp来做：
f[i][0]表示i是最后一个被枚举到的点，且枚举总点数为偶数的，从(1,1)走到第i个坏点的方案数×(-1)
f[i][1]表示……总点数为奇数……的方案数
我们令(n,m)为第r + 1个点，则ans为f[r+1][0]+f[r+1][1]，相当于把容斥的过程顺序来做了……
求f[i]的时候就枚举它之前的点是谁，加过来更新答案。容斥->DP
C题
题意：给你n堆石子，你每次可以从任意一堆中取走若干个(>0)，或是将一堆任意分成非空的三堆石子，取得最后一颗石子者胜，问先手胜负？
做法：SG函数，sg[0]=0,sg[i] = mex(j),这里的j可以是sg[0~i-1]，还可以是分成的三堆，若是分成三堆则j为sg[x]^sg[y]^sg[i-x-y]。
打表找规律发现只有在模8余0和余7处sg交换了，其他位置都是sg[i] = i
H题
题意：给n个物品，每个物品有体积，定义f(i,j,k,l,m)表示i、j这两个物品必须选，k、l这两个物品必须不选，总体积为m的方案数(m的范围为1~s)
首先m那一维可以转化成体积不超过s的方案数。
然后我们容易想到一个简单的DP，dp[i][j][k]表示前i个物品选了j个，总体积为k的方案数，则它对答案的贡献是
但是这样的复杂度是O(N^3)会超时。
换个方向DP，发现我们总共选了几个物品并不是很关心，关键是必选的和必须不选的4个物品的状态。
所以我们在状态中记录必选的两个我定了几个，必须不选的我确定了几个，令dp[i][j][k][l]表示前i个物品总体积为j，且必选的有k个，必须不选的有l个的方案数，
转移是比较显然的：
- 选第i个物品，但不是必选物品
- 选第i个物品，且是必选物品
- 不选第i个物品，不是必须不选的物品
- 不选第i个物品，且是必须不选的物品
J题
题意：将电脑音量从p变为q，你每秒可以：
- 将当前音量+1
- 停止不动
- 降低当前音量：如果上一秒也是降低音量，且降低了x，则这次会降低2x，否则只-1
另外，降低音量时如果结果为负数，只会变成0（神坑啊啊啊啊啊）
所以我们搜索就可以了。每次如果按了降低音量以后还比q高，那肯定不会选其他的方案= =果断按降，其他的选择只会更劣。
然后记一下中间停顿了几次，因为最后+1加回来的时候，并不需要全都等到最后再加，中间停顿的时候也是可以用+1来替代的。
An undergraduate at Shanghai Jiao Tong University who studies CS.