T1 减去因子

题意

一开始有一个整数 $n$ ，两个人轮流选数，每次可以选择一个当前数字的非 $1$ 非 $n$ 的因子，让当前数字减去该因子，不断操作，直到没得选为止，问谁会赢。

思路

我们分下面 $3$ 种情况讨论：

1. 当前的数 n 是个奇数；
2. 当前的数 n 是偶数但不是 2 的幂。
3. 当前的数 n 是 2 的幂。

• 第 1 种情况：由于 n 是奇数，那么选择的 n 的约数 k 肯定也是奇数（奇数×偶数会产生偶数），而且由于 k∣n 和 k∣k，所以 k∣(n−k)，所以 n−k 一定不是 2 的次幂（因为有约数 k），转化为第 2 种情况。
• 第 2 种情况：接下来我们要证明面对这种情况先手是必胜的。由于 n 是偶数但不是 2 的幂，那么一定存在一个奇数非 1 约数 k，考虑让 n 减掉这个 k，就转化为第 1 种情况。而这样循环会在哪一步结束呢？很显然是在第 1 种情况结束，因为第 2 种情况的操作是无论 n 为任意满足条件的值都可以进行的，而第 1 种情况的会在面对质数的时候停止。

至此我们证明了第 1 种情况必败，第 2 种情况必胜。

• 第 3 种情况：n 是 2 的幂时，我们可以减去 $\frac{n}{2}$ 使得 n 仍然是第 3 种情况，也可以减去一个其他数使得转化为第 2 种情况。但是第 2 种情况是必胜的，所以不应该转化为第 2 种情况。于是唯一的选择就是对半减。所以 n 是 2 的奇数次幂时必败，n 是 2 的偶数次幂时必胜。

T2 袜子

题意

有 $N$ 双袜子，第 $i$ 双由两枚颜色为 $i$ 的袜子组成。现在丢失了颜色为 $A_1, A_2, \dots, A_K$ 的袜子各一枚，于是他决定用剩下的 $2N - K$ 枚袜子重新组成 $\lfloor \frac{2N - K}{2} \rfloor$ 双袜子。由颜色为 $i$ 和 $j$ 的袜子组成的双袜子的奇异度定义为 $|i - j|$，高桥君希望使奇异度的总和尽可能小。

请计算在最优组合下，奇异度的最小总和是多少。注意，如果 $2N - K$ 是奇数，会有一枚袜子不被包含在任何双袜子中。

思路

不难发现如果有成对的袜子，互相匹配是最优的，那么就剩下来 $k$ 只落单的如何匹配。

可以观察到，如果 $A_i$ 参与匹配时能找到一个存在的 $A_j$，使得 $\left | A_i - A_j\right |$ 最小，那么将数组排序后，$A_i$ 与 $A_j$ 一定相邻。所以，将数组从小到大排序，逐个将 $A_{i + 1}$ 与 $A_i$ 的差相加即可。

然而，我们并没有AC。再看一遍题目，可以注意到题目中没有限制 $K$ 不为奇数，在 $k$ 是偶数时，这个方式显然最优。但 $k$ 是奇数，就需要扔掉一只袜子。

扔哪只呢？如果直接逐个枚举，时间复杂度为 $O(K^2)$，显然会超时；但如果我们预先将前缀和求出来，求值部分时间复杂度就可降低到 $O(K)$。

设从 $1$ 开始往后求相邻差的前缀和的数组为 $b$，从 $K$ 往前求相邻差的前缀和的数组为 $e$，如下图：

如果我们要删除的是图中黑色部分，那么剩下的差异和就为e[1] + b[1] + a[4] - a[2]。

也就是说，如果要删除第 $i$ 个颜色，当 $i$ 为偶数时，差异和为b[i - 2] + e[i + 2] + a[i + 1] - a[i - 1]；$i$ 为奇数时，差异和为b[i - 1] + e[i + 1]。

T3 幻想机器人

题意

走格子

思路

模拟

T4 石头

题意

$alice$ 和 $bob$ 在玩一个取石子的游戏。

刚开始，有 $N$ 个石子，还有一个长度为 $K$ 的序列 $A = \{A_1,A_2,\cdots,A_K\}$。

现在，他们要按照以下规则轮流取石子：

• 对于每次操作，他可以选择一个 $i$（$1 \leq i \leq K$），这时他会取走 $A_i$ 块石子。

• 当一个人没法取石子时，游戏结束。

现在，$alice$ 先取石子，$bob$ 后取石子。他们都想尽可能的最大化他们自己取走的石子数量。

若他们都以最优策略取石子，最后 $alice$ 会取走多少块石子？

思路

博弈论dp，设 $dp[i]$ 表示当前的石子数量为 $i$ 时，先手能取的最大值。

假设先手 alice 取的是 $a[j]$ ，那么石子数变为 $i - a[j]$ ，alice 取完后，此时的先手是 bob，则此时 bob 能取到的最大石子数表示为 $dp[i - a[j]]$ ，所以 $dp[i]$ 可以由 $a[j] + i - a[j] - dp[i - a[j]]$ 转移得到，即 $dp[i]$ 由 $i - dp[i - a[j]]$ 转移得到。

$dp[i] = max(dp[i],i − dp[i − a[j]])$

时间复杂度：$O(nk)$

T5 传感器优化困境

题意

有一种商品的制造需要在工厂流水线经过 $1,2,\dots,N$ 的 $N$ 个步骤，才算完成。

对于每个步骤 $i$，都有两种处理该步骤的机器 $S_i$ 和 $T_i$ 可供购买：

• 机器 $S_i$：每台可处理 $A_i$ 个产品，每台价格为 $P_i$ 日元。

• 机器 $T_i$：每台可处理 $B_i$ 个产品，每台价格为 $Q_i$ 日元。

在每个步骤中，两种机器可以购买任意数量（包括零台）。

假设步骤 $i$ 在引入机器后，可以处理 $W_i$ 个需要经过步骤 $i$ 的产品，我们把这个 $W_i$ 定义为步骤 $i$ 的处理量。

同时将工厂流水线的处理能力定义为所有步骤的处理量中的最小值，即 $\displaystyle\ \min^{N}_{i=1}\ W_i$。

现在问在总预算为 $X$ 日元的情况下，工厂流水线可达到的最大处理能力是多少。

思路

注意到 $N \le 100$ 和 $A_i,B_i \le 100$，这个数据范围比较小，很可能与时间复杂度有关。

题目要求 $\displaystyle W=\min_{i=1}^N W_i$ 的最大值，看到最小值最大，果断二分。于是思路就出来了：二分 $W$，看能否用 $X$ 的预算达到。

具体来讲，二分 $W$，对于第 $i$ 轮加工，我们要使 $W_i \ge W$，也就是找到这样的 $a_i,b_i$，使得 $W_i = a_iA_i+b_iB_i \ge W$ 且 $\sum_{i=1}^N a_iP_i+b_iQ_i \le X$。

要想不超过预算，花费就得尽可能少，也就是要使 $a_iP_i+b_iQ_i$ 最小，同时要让 $a_iA_i+b_iB_i \ge W$。

这就引出本题的一个结论：第 $i$ 轮加工的两种机器中，必有一种机器的购入数量少于另一种的单台机器产量。

换句话说，如果你主要购入 $S_i$，那么你购入的 $T_i$ 的数量少于 $A_i$。反之亦然。

这是因为，每当你购入 $B_i$ 台 $S_i$ 或 $A_i$ 台 $T_i$，你都会获得 $A_iB_i$ 的产量。而对于相同的 $A_iB_i$ 的产量，为使花费最少，一定只会选择两种方案中更便宜的那一种（也就是 $\min(B_iP_i,A_iQ_i)$）。所以，当你主要购入 $S_i$ 的时候（此时 $B_iP_i \le A_iQ_i$），每当你购入 $A_i$ 台 $T_i$，你都可以将其换成更优的 $B_i$ 台 $S_i$。

那么我们直接在二分里面枚举 $S_i$ 或 $T_i$ 的数量，取花费最小值即可。

bool check(int x) {
	int sum = 0;  //达到x生产容量的最小花费 
	for(int i = 1; i <= n; i++) {
		int res = 1e15;   //寻找最小花费 
		for(int j = 0; j < a[i]; j++) {
			//枚举主要购买Si时，购入的Ti数量 
			if(j*b[i] > x) break;
			int tmp = x-j*b[i];
			res = min(res, j*q[i]+(tmp+a[i]-1)/a[i]*p[i]);
		}
		for(int j = 0; j < b[i]; j++) {
			//枚举主要购买Ti时，购入的Si数量 
			if(j*a[i] > x) break;
			int tmp = x-j*a[i];
			res = min(res, j*p[i]+(tmp+b[i]-1)/b[i]*q[i]);
		}
		sum += res;
	}
	return sum <= X; 
}