A. Meaning Mean
题意
可以选择 2 个不同的索引，将数组中这两个索引对应的数删除，然后将添加到数组的最后。可知到最后只会剩下一个数，最大化最后剩余的这个数，并输出。
数据范围
思路
考虑三个数时，按照各种顺序合并的情况下，是最好的操作。
参考代码
ll a[maxn];
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + 1 + n);
ll tot = a[1];
for (int i = 2; i <= n; i++) {
ll x = a[i];
tot = (tot + x) / 2;
}
cout << tot << '\n';
}B. Maximize Mex
题意
对一个给定的数组和给定的数，可以进行如下操作：
- 选择一个索引，。
可以执行这个操作任意次，询问这个数组最大的值是多少。
数据范围
思路
赛后再交发现 T 了…剪枝优化了一下。
首先容易观察到，的操作不会改变所属的模的同余系，在把按照模的值进行分组之后，对每个组，check 对应集合中是否能满足的范围内的都存在，遍历时，计数的的数量，如果从到每一位都满足，则说明同余集合中到的值都是可以满足的。
最后检测一下数组，寻找。
参考代码
ll a[maxn];
bool vis[maxn];
void solve() {
ll n, x;
cin >> n >> x;
for (int i = 0; i <= n; i++) {
vis[i] = false;
}
map<ll, vector<ll>> mp;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp[a[i] % x].push_back(a[i]);
}
for (auto &[i, v] : mp) {
sort(v.begin(), v.end());
ll tot = (n - 1) / x;
if ((n - 1) % x >= i)
tot += 1;
vector<ll> cnt(tot, 0);
for (auto j : v) {
if ((j - i) / x < tot) {
cnt[(j - i) / x]++;
} else {
break;
}
}
ll sum = 0ll;
for (int j = 0; j < tot; j++) {
sum += cnt[j];
if (sum <= j) {
break;
}
vis[j * x + i] = true;
}
}
for (int i = 0; i <= n; i++) {
if (!vis[i]) {
cout << i << '\n';
return;
}
}
}C. Adjust The Presentation (Easy Version && Hard Version)
题意
个人排成一队，依次播放张幻灯片，当一个人播放过幻灯片之后，可以重新将他插入任意的位置，或者留在队首播放下一张幻灯片。每张幻灯片都有一个最佳播放者，如果所有的幻灯片都由其最佳播放者播放，则整个播放是完美的，输出YA，否则输出TIDAK。询问是否可以通过调整，使得所有的幻灯片都完美播放。
同时支持次修改幻灯片的最佳播放者，询问每次修改之后的播放效果，输出YA或TIDAK。
数据范围
思路
幻灯片是否能被最佳播放者播放，只需要保证其播放者在播放时或之前出现，也就是说，如果数组中每个编号最先出现的次序排序后，若恰好是的前缀，则是可以满足的。
差分数组计数数组中第个数在中最先出现次序排序后的次序是否大于等于前一个数，即是否上升。利用更新中每个编号最先出现的位置。
每次操作后，更新检查编号前后编号的新次序是否合法（与中的前一位置的编号的最早位置相比是否上升），编号前后是否合法，更新数组和值。
ll a[maxn], b[maxn], pos[maxn], diff[maxn];
vector<set<ll>> st;
void YorT(bool f) { f ? cout << "YA\n" : cout << "TIDAK\n"; }
void solve() {
int n, m, q;
cin >> n >> m >> q;
st.assign(n + 1, set<ll>());
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[a[i]] = i;
st[i].insert(m + 1);
diff[i] = 0;
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
st[b[i]].insert(i);
}
auto check = [&](int s) { // 检查a[s-1] -> a[s]的合法情况,是否上升
if (s == 1 || s > n)
return 0;
int res = 0;
if (diff[s] && !(*st[a[s - 1]].begin() <= *st[a[s]].begin())) {
diff[s] = 0;
res = -1;
} else if (!diff[s] && *st[a[s - 1]].begin() <= *st[a[s]].begin()) {
diff[s] = 1;
res = 1;
}
return res;
};
ll sum = 0ll;
for (int i = 2; i <= n; i++) {
sum += check(i);
}
YorT(sum == n - 1);
while (q--) {
int s, t;
cin >> s >> t;
st[b[s]].erase(s);
st[t].insert(s);
sum += check(pos[b[s]]) + check(pos[b[s]] + 1) + check(pos[t]) +
check(pos[t] + 1);
b[s] = t;
YorT(sum == n - 1);
}
}D. Boss, Thirsty
E1. Digital Village (Easy Version) && (Hard Version)
题意
居民房屋构成一个无向图，包含个点条边，其中户需要网络服务，可以在任意的房屋中安置交换机，房屋与交换机所在房屋之间的延迟是到的简单路径上最大的延迟。可以任意选择放置交换机的位置，询问在逐渐增加交换机的过程中，所有需要网络服务的居民的最小总延迟。