AtCoder Beginner Contest 392(A-G)题解

A-B：略

C：可能题意比较绕，第i个答案就是穿着i这个号码（也就是Q[j] = i,这个时候j这个位置），看向的那个人的号码（也就是P[j])

代码：

void solve()
{int n;cin >> n;vi p(n + 1), q(n + 1), ans(n + 1);rep(i, 1, n) {cin >> p[i];}rep(i, 1, n) {cin >> q[i];}rep(i, 1, n) {ans[q[i]] = q[p[i]];}rep(i, 1, n) {cout << ans[i] << ' ';}
}

D：枚举哪两个集合[i,j]计算贡献，用map记录每个集合每个元素a个数，最后枚举i和j中间最小那个map计算贡献即可。

void solve()
{int n;cin >> n;vector<map<int, int>> cnt(n + 1);vi k(n + 1);rep(i, 1, n) {cin >> k[i];int x;rep(j, 1, k[i]) {cin >> x;cnt[i][x]++;}}double ans = 0;rep(i, 1, n) {rep(j, i + 1, n) {if (sz(cnt[i]) < sz(cnt[j])) {double dw = 1.0 * k[i] * k[j];double up = 0;for (auto &[x, c] : cnt[i]) {if (cnt[j].count(x)) {up += 1.0 * cnt[j][x] * c;}}ans = max(ans, up / dw);} else {double dw = 1.0 * k[i] * k[j];double up = 0;for (auto &[x, c] : cnt[j]) {if (cnt[i].count(x)) {up += 1.0 * cnt[i][x] * c;}}ans = max(ans, up / dw);}}}cout << fixed << setprecision(10) << ans << '\n';
}

E:考虑用并查集把没用到的边筛除出来，然后每次根据没用到的边再根据所在连通块合并即可，直到最后只剩下一个连通块。

void solve()
{int n, m;cin >> n >> m;DSU dsu(n);vector<pii> edges(m + 1);vi vec;rep(i, 1, m) {int u, v;cin >> u >> v;edges[i] = {u, v};if (dsu.same(u, v)) {vec.pb(i);} else {dsu.merge(u, v);}}if (dsu.getBlocks() == 1) {cout << 0 << '\n';return;}set<int> st;rep(i, 1, n) {if (i == dsu.find(i)) {st.insert(i);}}vector<tuple<int, int, int>> ans;for (auto &i : vec) {auto [u, v] = edges[i];int t = v;u = dsu.find(u);v = dsu.find(v);st.erase(u);int z = *st.begin();st.erase(z);dsu.merge(u, z);ans.pb({i, t, z});st.insert(dsu.find(u));if (sz(st) == 1) {break;}}cout << sz(ans) << '\n';for (auto &[i, x, y]: ans) {cout << i << ' ' << x << ' ' << y << '\n';}
}

F:因为前面的总会被后面的顶掉，所以我们直接倒置放，一定不会被顶掉，每次从头开始找到未被放数字的第a[i]个位置，这个位置就是当前数字，寻找的过程可以通过维护线段树，每次放一个数字就可以把这个位置上的sum标成1，在线段树上二分这个sum去寻找位置，复杂度nlogn。

const int N = 5e5 + 5;
struct node {int l, r;int sum;
} tr[N << 2];void push_up(int u) {tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void build(int u, int l, int r) {tr[u] = {l, r, 0};if (l == r) {tr[u].sum = 1;return;}int mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);push_up(u);
}void modify(int u, int p) {if (tr[u].l == tr[u].r) {tr[u].sum = 0;return;}int mid = (tr[u].l + tr[u].r) >> 1;if (p <= mid) {modify(u << 1, p);} else {modify(u << 1 | 1, p);}push_up(u);
}int find_pos(int u, int sum) {if (tr[u].l == tr[u].r) {return tr[u].l;}if (tr[u << 1].sum >= sum) {return find_pos(u << 1, sum);}return find_pos(u << 1 | 1, sum - tr[u << 1].sum);
}void solve()
{int n;cin >> n;vi a(n + 1);vi ans(n + 1);rep(i, 1, n) {cin >> a[i];}build(1, 1, n);per(i, n, 1) {int p = find_pos(1, a[i]);ans[p] = i;modify(1, p);}rep(i, 1, n) {cout << ans[i] << ' ';}
}

G:经典FFT，考虑把值域a[i]看成多项式的x^a[i],把方案数看成系数，最后把多项式相乘系数就是每个值的方案数，由于原式子可以化成A+C=2B,因此我们枚举2B，只可能是偶数，且B一定要出现在原来的a数组中，这就可以计算到答案中去。

void solve()
{vl A(1e6 + 1), B(1e6 + 1), C(1e6 + 1);int n;cin >> n;rep(i, 1, n) {int x;cin >> x;A[x]++;B[x]++;C[x]++;}auto ret = atcoder::convolution_ll(A, B);ll ans = 0;REP(i, 2, 2000000, 2) {if (C[i >> 1]) {ans += ret[i] / 2;}}cout << ans;
}