T1 求余来咯

考察枚举答案

由于 较小，所以我们考虑枚举所有可能的答案 ，对于每一个 来说，用所有数字都进行求余，得到求余的和，同时记录最小值。

时间复杂度

#include <bits/stdc++.h>
using namespace std;
int a, cnt[5005];
int main(){
	int n, minn = 1e9, ans, l, r;
	cin >> n >> l >> r;
	for(int i = 1; i <= n; i++){
		cin >> a;
		for(int j = l; j <= r; j++){
			cnt[j] += a % j;
		}
	}
	for(int i = l; i <= r; i++){
		if(cnt[i] < minn){
			minn = cnt[i];
			ans = i;
		}
	}
	cout << ans << endl;
}

T2 牛牛的乘法考验

假设 个零

对题意进行转化，得到我们最终输出的答案 满足： 是 的因子。

也就是说对于 Q 来说，一部分是由 贡献的，另一部分是由 贡献的，两个数字乘起来得到

所以考虑 和 的最大公因数，这个最大公因数就是 对 的贡献。那么剩余的因数需要 来贡献，所以用 除以这个最大公因数就知道 的值了。

#include <bits/stdc++.h>
using namespace std;
long long a, k;
int main(){
	int t;
	cin >> t;
	while(t--){
		cin >> a >> k;
		long long Q = 1;
		for(int i = 1; i <= k; i++){
			Q *= 10;
		}
		cout << now / __gcd(Q, a) << '\n';
	}
}

T3 二叉树

每次修改实际上只会修改沿着当前点向上的一条链，这是 的。 下面考虑如何判断能否形成回文：只需要判断其中数量为奇数的字符不超过 1 种即可。

于是做法为：

• 初始先进行一遍树形 DP，求初始情况下到每个点上各个字母有几个，统计一个初始的答案并输出。
• 之后对于每次修改，沿着当前修改点向上逐个修改字符数量，修改完成后检查节点的改变情况，对答案数量做增减。改到根节点后停止并输出。

T4 普通的构造

首先考虑共有几个位置对。显然有 对。其中应该一半逆序对，一半顺序对。可以求出来一共是多少逆序对/顺序对。

考虑希望字典序最小。不妨逐位考虑：

• 第一位放 时，后面的所有位置一定比 大，一定提供的是顺序对。会提供 对。
• 第二位放 时，后面的所有位置一定比 大，会提供 对。
• 一直重复第 位放入 的策略，直到某个放进去会导致顺序对超过需要的位置。

下面讨论这个位置：假设这个位置需要提供 对顺序对，那么这个位置最小只能填入 。 先把这个数字填进去，接下来考虑剩余位置不能提供任何顺序对。将剩余数字倒序填入剩下位置即可。