D. Carousel
题解
仔细思考一下，会发现至多可能用到3种颜色（oooorz）
分类讨论
- (n)个数相同，只用一种颜色
- (n)是偶数，只用两种颜色：1， 2， 1， 2，，，
- (n)是奇数
- 如果存在(a[i] = a[i \% n + 1])，那么将(a[i])和(a[i \% n + 1])染上同一种颜色，就成了第二种情况
- 不存在的话，就用三种颜色，前(n - 1)个数的染色为：1，2，1，2，，，。最后一个数染色为 3。
我的(idea) ：当(n)是奇数，则前(n - 1)个数按第二类染色就行。讨论(a[n])和(a[1])的关系：①(a[n] = a[1])，②(a[n]) != (a[1])。①显然只要两种颜色，②需要三种颜色，既(a[n])染色为3。对于②，考虑这样的样例: 1 2 2，很明显只需要用到两种颜色，而不是三种颜色。这时候，很自然的会想到判断(a[n - 1])和(a[n])的关系。emmmm，再进一步，考虑样例：2 1 1，发现只判断(a[n - 1])和(a[n])的关系是不够的。所以将思路打开，判断(a[i] == a[i \% n + 1])，相同，就合并染同一种颜色。
void Solve() {
cin >> n;
vector<int> a(n);
myfor(i, 0, n) cin >> a[i];
if (count(a.begin(), a.end(), a[0]) == n) {
cout << 1 << endl;
myfor(i, 0, n) cout << 1 << " ";
cout << endl;
return;
}
if (n % 2 == 0 || a[0] == a[n]) {
cout << 2 << endl;
myfor(i, 0, n) cout << i % 2 + 1 << " ";
cout << endl;
return;
}
int pos = -1, k = 0;
myfor(i, 0, n) if (a[i] == a[(i + 1) % n]) {
pos = i;
break;
}
if (pos == -1) {
cout << 3 << endl;
myfor(i, 0, n - 1) cout << i % 2 + 1 << " ";
cout << 3 << endl;
}
else {
cout << 2 << endl;
myfor(i, 0, n) {
cout << (i + k) % 2 + 1 << " ";
if (i == pos) k = 1;
}
cout << endl;
}
return;
}
E. Tree Queries
(n)个点组成了一棵以1为根的树，有(m)次询问，每次询问给出一个点集(S)，然后问：是否存在一条从(root)到节点(u)的路径，使得(S)中的点要么在这条路径上，要么离这条路径的距离为1 ？
题解：
其实仔细体会一下：(S)中的点离这条路径小于等于1 (Longrightarrow) (S)中的点的父亲节点都在这条路径上，也就是判断它们的父亲节点是不是在一条链上。这儿要用到一个叫 (dfs) (order) 的东西，假如 (u = pa[v])，(timein_u < timein_v) (&&) (timeout_u > timeout_v)。因为在一条链上，所以这种关系是层层嵌套的。
void DFS(int u, int p) {
pa[u] = p;
st[u] = cnt++;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (v == p) continue;
DFS(v, u);
}
ed[u] = cnt;
}
void Solve() {
DFS(1, 1);
int k;
while(m--) {
cin >> k;
int mx = -1, mi = INF, x;
myfor(i, 0, k) {
cin >> x;
x = pa[x];
mi = min(mi, ed[x]);
mx = max(mx, st[x]);
}
puts(mx < mi ? "YES" : "NO");
}
return;
}
int main() {
Inite();
cin >> n >> m;
myfor(i, 1, n) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
Solve();
return 0;
}
我的(idea)：考虑(u)的选择，首先有一个假设，如果存在这样一条路径，那么：(u in S)一定能够成立，所以(u)的深度在(S)中一定最大。找到(u)以后，怎么判断(S)中的点到这条路径的距离小于等于1呢？很简单，举例：(v in S)，(p = LCA(v, u))，判断(dep[v] - dep[p] <= 1)是否成立即可。
void DFS(int u, int p, int deep) {
dp[u] = deep;
pa[0][u] = p;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (v == p) continue;
DFS(v, u, deep + 1);
}
}
void Inite_Pa() {
DFS(1, -1, 0);
for (int k = 0; k + 1 < 17; k++) {
for (int v = 1; v <= n; v++) {
if (pa[k][v] < 0) pa[k + 1][v] = -1;
else pa[k + 1][v] = pa[k][pa[k][v]];
}
}
}
int LCA(int u, int v) {
if (dp[u] > dp[v]) swap(u, v);
myfor(k, 0, 17) if ((dp[v] - dp[u]) >> k & 1) v = pa[k][v];
if (v == u) return v;
for (int k = 15; k >= 0; k--) if (pa[k][v] != pa[k][u]) {
v = pa[k][v];
u = pa[k][u];
}
return pa[0][v];
}
void Solve() {
Inite_Pa();
int k;
while(m--) {
cin >> k;
vector<int> a(k);
int mx = -1, u = -1;
myfor(i, 0, k) {
cin >> a[i];
if (dp[a[i]] > mx) {
mx = dp[a[i]];
u = a[i];
}
}
bool flag = true;
myfor(i, 0, k) {
int p = LCA(u, a[i]);
if (dp[a[i]] - dp[p] > 1) {
flag = false;
break;
}
}
puts(flag ? "YES" : "NO");
}
}
F. Make k Equal
有(n)个数，问最少需要几次操作使得其中至少有(k)个数相同？
一次操作：对最大的数减一或者最小的数加一
题解
原数列当中没有(k)个数相同时，才会有如下讨论。假设这(k)个相同的数为(x)，考虑如下情况：
- 只移动小于(x)的数，使得有(k)个数相同
- 只移动大于(x)的数，使得有(k)个数相同
- 上述两种情况都不行，需要小于(x)和大于(x)的数都移动
推导第一种情况的公式：
(ans_l) = ((x - 1 - a_1)) + ((x - 1 - a_2)) + ··· + ((x - 1 - a_t)) + (k)
整理一下得：
(ans_l) = ((x - 1) * t) (-) ((a_1 + a_2 + ··· + a_t)) + (k)
对于第一种情况，每次只能移动最小的数，所以小于(x)的数在几次操作后，都会变成(x - 1)，然后再从其中选(k)个数分别执行一次操作就行，这就是为啥会再加一个(k)。
(x)一定是原数列当中的某个数（可以证明）
int main() {
int n, k;
cin >> n >> k;
vector<long long> a(n);
long long sum_all = 0;
myfor(i, 0, n) cin >> a[i], sum_all += a[i];
sort(a.begin(), a.end());
/*检查是否有k个数已经相同*/
int cnt = 1;
myfor(i, 0, n) {
if (i + 1 < n && a[i] == a[i + 1]) cnt++;
else cnt = 1;
if (cnt >= k) {
puts("0");
return 0;
}
}
long long sum = 0, ans = 9223372036854775800;
myfor(i, 0, n) {
sum += a[i];
if (i + 1 >= k) ans = min(ans, i * (a[i] - 1) - (sum - a[i]) + k - 1);
if (i + k <= n) ans = min(ans, sum_all - sum - (a[i] + 1) * (n - i - 1) + k - 1);
ans = min(ans, (a[i] - 1) * i - (sum - a[i]) + sum_all - sum - (a[i] + 1) * (n - i - 1) + k - 1);
}
cout << ans << endl;
return 0;
}