暴力操作（opt）30pts
这个错解可反悔贪心30pts；
考虑正解，我们只需考虑前 $ \frac n2 + 1 $ 小的数即可；
考虑二分出一个中位数 $ mid $，那么我们要让大于它的都用最小的代价变小；
考虑如何求这个最小的代价，因为 $ \lfloor \frac{\lfloor \frac ab \rfloor}{c} \rfloor = \lfloor \frac{ab}{c} \rfloor $，我们可以预处理出所有对于除以一个数 $ i $ 的最小代价，这个可以调和级数处理，即 $ c_{i \times j} = \min(c_{i \times j}, c_i + c_j) $，然后处理完以后维护一个后缀 $ \min $ 即可；
我们还要考虑除成 $ 0 $ 的情况，我们把这种情况的最小值存到 $ c_{n + 1} $ 中，那么我们可以得到 $ c_{n + 1} = \min_{i = 1}^{n}(c_{n + 1}, c_i + c_{\lfloor \frac ni \rfloor + 1}) $，最后再维护一个后缀 $ \min $ 即可；
然后直接 check 就没了；
时间复杂度：$ \Theta(n \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long n, m, k;
long long a[500005], c[500005];
bool ck(int x) {
long long ans = 0;
for (int i = 1; i <= n / 2 + 1; i++) {
if (a[i] > x) ans += c[a[i] / (x + 1) + 1];
}
return (ans <= k);
}
int main() {
freopen("opt.in", "r", stdin);
freopen("opt.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> c[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= m; i++) {
for (int j = 1; j * i <= m; j++) {
c[i * j] = min(c[i * j], c[i] + c[j]);
}
}
for (int i = m - 1; i >= 1; i--) c[i] = min(c[i], c[i + 1]);
c[m + 1] = 2e9;
for (int i = 2; i <= m; i++) {
c[m + 1] = min(c[m + 1], c[i] + c[m / i + 1]);
}
for (int i = m; i >= 1; i--) {
c[i] = min(c[i], c[i + 1]);
}
int l = 0;
int r = m;
int ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if (ck(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
异或连通（xor）0pts
重点在于想到线段树分治；
然后直接考虑线段树分治（这个题直接 $ Trie $ 上分治就行），因为发现每条边在所有询问中出现的都是若干段不超过 $ \log k $ 段区间中的；
考虑首先建出 $ 01Trie $，那么这些询问从小到大在这个 $ 01Trie $ 上是连续的；
然后考虑一条边对于那些询问有贡献，可以发现，如果二进制位上这条边的 $ c $ 为 $ 0 $，而 $ Trie $ 上为 $ 1 $ ，异或起来就是 $ 1 $ ，$ k $ 这一位为 $ 1 $ 时可能成立，为 $ 0 $ 不成立，所以依据这个我们就可以直接给子树打上标记，然后直接 $ Trie $ 上分治即可；
时间复杂度：$ \Theta(n \log n \log V) $，其中 $ V $ 是值域；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <map>
using namespace std;
int n, m, q, k;
int x[500005], y[500005], c[500005], fa[500005], siz[500005], s[500005];
int find(int x) {
if (x == fa[x]) return fa[x];
else return find(fa[x]);
}
int tot, rt;
stack<pair<pair<int, int>, int> > sk;
long long ans;
map<int, long long> mp;
int p[35];
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (siz[x] < siz[y]) {
sk.push({{y, siz[y]}, x});
if (x == y) return;
ans -= (1ll * siz[x] * (siz[x] - 1) / 2);
ans -= (1ll * siz[y] * (siz[y] - 1) / 2);
siz[y] += siz[x];
ans += (1ll * siz[y] * (siz[y] - 1) / 2);
fa[x] = y;
} else {
sk.push({{x, siz[x]}, y});
if (x == y) return;
ans -= (1ll * siz[x] * (siz[x] - 1) / 2);
ans -= (1ll * siz[y] * (siz[y] - 1) / 2);
siz[x] += siz[y];
ans += (1ll * siz[x] * (siz[x] - 1) / 2);
fa[y] = x;
}
}
namespace Trie{
struct sss{
int ls, rs, id;
vector<int> v;
}tr[5000005];
void add(int now, int &id, int d) {
if (!id) id = ++tot;
if (!now) {
tr[id].id = d;
return;
}
if ((d >> (now - 1)) & 1) add(now - 1, tr[id].ls, d);
else add(now - 1, tr[id].rs, d);
}
void add_e(int now, int id, int x, int d) {
if (!id || !now) return;
int v = ((d >> (now - 1)) & 1);
if (p[now]) {
if (v) {
tr[tr[id].ls].v.push_back(x);
add_e(now - 1, tr[id].rs, x, d);
} else {
tr[tr[id].rs].v.push_back(x);
add_e(now - 1, tr[id].ls, x, d);
}
} else {
if (v) add_e(now - 1, tr[id].ls, x, d);
else add_e(now - 1, tr[id].rs, x, d);
}
}
void dfs(int now, int id) {
if (!id) return;
for (int i = 0; i < tr[id].v.size(); i++) {
int o = tr[id].v[i];
merge(x[o], y[o]);
}
if (!now) {
mp[tr[id].id] = ans;
for (int i = 0; i < tr[id].v.size(); i++) {
pair<pair<int, int>, int> t = sk.top();
sk.pop();
if (t.first.first == t.second) continue;
ans -= (1ll * siz[t.first.first] * (siz[t.first.first] - 1) / 2);
siz[t.first.first] = t.first.second;
fa[t.second] = t.second;
ans += (1ll * siz[t.first.first] * (siz[t.first.first] - 1) / 2);
ans += (1ll * siz[t.second] * (siz[t.second] - 1) / 2);
}
return;
}
dfs(now - 1, tr[id].ls);
dfs(now - 1, tr[id].rs);
for (int i = 0; i < tr[id].v.size(); i++) {
pair<pair<int, int>, int> t = sk.top();
sk.pop();
if (t.first.first == t.second) continue;
ans -= (1ll * siz[t.first.first] * (siz[t.first.first] - 1) / 2);
siz[t.first.first] = t.first.second;
fa[t.second] = t.second;
ans += (1ll * siz[t.first.first] * (siz[t.first.first] - 1) / 2);
ans += (1ll * siz[t.second] * (siz[t.second] - 1) / 2);
}
}
}
using namespace Trie;
int main() {
freopen("xor.in", "r", stdin);
freopen("xor.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> q >> k;
for (int i = 1; i <= 32; i++) {
p[i] = ((k >> (i - 1)) & 1);
}
for (int i = 1; i <= m; i++) {
cin >> x[i] >> y[i] >> c[i];
}
for (int i = 1; i <= q; i++) {
cin >> s[i];
add(32, rt, s[i]);
}
for (int i = 1; i <= m; i++) {
add_e(32, rt, i, c[i]);
}
for (int i = 1; i <= n; i++) {
fa[i] = i;
siz[i] = 1;
}
dfs(32, 1);
for (int i = 1; i <= q; i++) {
cout << mp[s[i]] << '\n';
}
return 0;
}
民主投票（election）25pts
呵呵，想不到；
然后直接二分答案，二分的是每个点最多被投的票数（当票数一样时），然后得到一个答案 $ res $；
考虑对于一个点 $ x $ ，如果 $ siz_x - 1 < res $，那么不可以，如果 $ siz_x - 1 > res $，那么可以，如果相等，考虑 $ res - 1 $ 对于这个点合不合法，我们就一直向上传到根，如果此时根能接收到这个票，那就可行，否则不行；
时间复杂度：$ \Theta(Tn \log n) $；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n;
int fa[5000005];
struct sss{
int t, ne;
}e[5000005];
int h[5000005], cnt;
void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
int siz[5000005];
void dfs(int x) {
siz[x] = 0;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
dfs(u);
siz[x] += siz[u] + 1;
}
}
int f[5000005];
int ans[5000005];
void afs(int x, int y) {
f[x] = 0;
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
afs(u, y);
f[x] += f[u];
}
f[x] = max(0, f[x] - y) + 1;
}
bool ck(int x) {
afs(1, x);
return (f[1] == 1);
}
void cfs(int x, int y) {
if (siz[x] == y) {
ans[x] = 1;
return;
}
for (int i = h[x]; i; i = e[i].ne) {
int u = e[i].t;
if (f[u] > 1) cfs(u, y);
}
}
int main() {
freopen("election.in", "r", stdin);
freopen("election.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> fa[i];
add(fa[i], i);
}
dfs(1);
int l = 1;
int r = n;
int res = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if (ck(mid)) {
res = mid;
r = mid - 1;
} else l = mid + 1;
}
for (int i = 1; i <= n; i++) {
if (siz[i] > res) ans[i] = 1;
else ans[i] = 0;
}
afs(1, res - 1);
if (f[1] == 2) { //根自己一个 + 上传的一个
cfs(1, res);
}
for (int i = 1; i <= n; i++) {
cout << ans[i];
}
cout << '\n';
for (int i = 1; i <= n; i++) h[i] = 0;
cnt = 0;
}
return 0;
}