2024.09.13练习总结

没有参与比赛练习，所以没有赛时总结。

$ T1, T2 $

比较简单，似乎是签到题。

$ T3 $
题意不是很懂。
首先将题目中的要求转换为人话：
当两个区间有交，他们必须长度相同。
注意到题目中说有 $ n $ 个人要上下电梯，且每站只会有一个人的状态改变。
那么不难发现对于一段区间 $ [l, r] $ 中的位置 $ i $，如果它是另一个区间的左端点或右端点的话，那么这个区间一定是 $ [i - len + 1, i] $ 或 $ [i, i + len - 1] $。
所以每组两两相交的区间应该形如：

$ [l, r], [l + 1, r + 1]...[l + k, r + k] $

于是考虑 DP，设 $ f_i $ 表示前 $ i $ 层楼是否有解。
目标就是求出 $ f_{2n} $。
转移方程不难想到，即为

$ f_i = (f_{j - 1} \text{ & } check(i, j)) \text{ | } ... (1 < j < i \text{ && } 2 \text{ | } i − j + 1)$

但是，没有代码实现...

$ T4 $

比较常用的一个技巧是当钦定一个平均数 $ x $ 时，我们将所有数都减去 $ x $。
然后直接转化为选数使数和为 $ 0 $，而此处的又一个常用技巧是将和为 $ 0 $，转化为负数与正数和的绝对值相等。
考虑 DP，设 $ f_{i, j} $ 表示在 $ [1, i] $ 之间选，使最后数和为 $ j $。
是一个多重背包 DP，考虑用前缀和将其优化到 $ O(n ^ 3k) $

对于 $ j = 0 \sim i - 1 $，直接赋为 $ f_{i - 1, j} $ 即可。

对于 $ j = i \sim sum $，前缀和地求出 $ f_{i, j} $。

最后，对于 $ j = (k + 1) \times i \sim sum $，减去 $ f_{i, j - (k + 1) \times i} $ 即可。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 110, M = 1000010;

int n, k, m;
int f[N][M];
int res[N];

signed main()
{
	cin >> n >> k >> m;
	
	int sm = 0;
	f[0][0] = 1;
	for (int i = 1; i <= n; i ++ )
	{
		sm += i * k; 
		for (int j = 0; j < i; j ++ ) f[i][j] = f[i - 1][j];
		for (int j = i; j <= sm; j ++ ) (f[i][j] = f[i - 1][j] + f[i][j - i]) %= m;
		for (int j = sm; j >= (k + 1) * i; j -- ) (f[i][j] = f[i][j] - f[i][j - (k + 1) * i] + m) %= m;
	}
	
	for (int i = 1; i <= n; i ++ )
	{
		for (int x = 0; x <= sm; x ++ )
			(res[i] += f[i - 1][x] * f[n - i][x] % m) %= m;
		(res[i] *= (k + 1)) %= m;
		res[i] -- ;
		res[i] = (res[i] + m) % m;
	}
	
	for (int i = 1; i <= n; i ++ ) cout << res[i] << '\n';
	
	return 0;
}