D. Divide and Equalize
思路：
1.某个数除以x，某个数再乘以x，可发现数组总的乘积没有变化
2.也就是说，要使数组中的每一个元素相同，它们总的质因子应该满足：某个质因子的数量%n==0
E. Block Sequence
简单的dp
dp[i]，表示删除这个数字后的最小删除次数
可以正的枚举，也可以倒着来
转移方程为dp[i]=min(dp[i],dp[i+a[i]+1])；
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
void solve() {
int n;
cin >> n;
vector<int> a(n + 1),d(n+3);
for (int i = 1; i <= n; i++) cin >> a[i];
d[n + 1] = 0;
d[n] = 1;
for (int i = n - 1; i >= 1; i--) {//倒着枚举
d[i] = d[i + 1]+1;
if (i + a[i] <= n) {//如果不出界
d[i] = min(d[i], d[i + a[i]+1]);//选着删除，或者不删除。不删除，则最小次数取决上一个
}
}
cout << d[1] << '\n';
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
简单来说就是求两标记点的最大距离len，ans为(len+1)/2 (向上取整)
问题求的是点i距离标记点的最大距离f[i]的最小值
了解：
1.k==1时，ans=0
自己距离自己为0
2.k==2时，答案在两标记点之间的位置：外面的点距离最大一定大于中间的点
3.k>2
依旧可以证明答案的位置在两标记点的最大距离之间的点
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int vis[N],len;
int pos;
vector<int> g[N];
void dfs(int u, int fa, int l) {
if (vis[u] && l > len) pos = u, len = l;//如果是标记点，且距离变大则更新最大标记点
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u, l + 1);
}
}
void solve() {
memset(vis, 0, sizeof vis);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i <= k; i++) cin >> pos, vis[pos] = 1;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
len = 0;
dfs(pos, 0, 0);//一个标记点到其他标记点的最大距离
dfs(pos, 0, 0);//寻找最大距离
cout << (len + 1) / 2 << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}