拿了 \(100 + 65 + 100 + 100 = 365\)，rank 2。
膜拜 george AK %%%。
T1 冒泡排序
见过结论（）
题意简述
有 \(T(T \leq 10^5)\) 次询问，每次给定 \(n(n \leq 10^7)\)，求长为 \(n\) 的随机排列期望最少 swap 多少次可以有序。
题解
结论：\(ans_i = i - \sum\limits_{j = 1}^i \frac{1}{j}\)。
参考代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){int x = 0, f = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}return x * f;
}
inline void write(int x){if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;
}
inline int fp(int a, int b, int p){int res = 1;while(b){if(b & 1) res = res * a % p;a = a * a % p;b >>= 1;}return res;
}
const int Mod = 998244353;
int inv[10000005], ans[10000005];
//ans[i] = i - (1/1 + 1/2 + ... + 1/i)
inline void init(){inv[1] = 1;for(int i = 2; i <= 1e7; i++){inv[i] = Mod - Mod / i * inv[Mod % i] % Mod;ans[i] = ((ans[i - 1] + 1 - inv[i]) % Mod + Mod) % Mod;}return;
}
signed main(){init();int T = read();while(T--) write((ans[read()] % Mod + Mod) % Mod), putchar('\n');return 0;
}
T2 情报中心
以为能过就没上 bitset（\kk
题意简述
给定一张 \(n\) 个点，\(m\) 条边的 \(1\) 权图，共有 \(q\) 次询问，每次给定 \(k\) 组 \((u, d)\)，表示距 \(u\) 不超过 \(d\) 的点都是好的，求出每次询问好的点的个数。
数据范围：\(1 \leq n,q \leq 1000\)，\(1 \leq m \leq 10^5\)，\(1 \leq \sum k \leq 2 \times 10^6\)。
题解
记 \(v_{u, d}\) 表示距离 \(u\) 不超过 \(d\) 的点的集合。
显然，可以通过 \(n\) 次 bfs 求出所有 \(v\)（这是 \(1\) 权图）。
此时，使用 bitset 按位或运算即可。
时间复杂度会除个 \(w\)，然后就过了。
参考代码：
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fstrict-aliasing")
#include<bits/stdc++.h>
// #define int long long
using namespace std;
inline int read(){int x = 0, f = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}return x * f;
}
inline void write(int x){if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;
}
bitset<1005> v[1005][1005], res;
vector<int> e[1005];
int n, m;
queue<pair<int, int> > q;
int vis[1005];
inline void bfs(int s){while(!q.empty()) q.pop();memset(vis, 0, sizeof(vis));q.push({s, 0}), vis[s] = true;while(!q.empty()){int u = q.front().first, d = q.front().second;q.pop();v[s][d][u] = 1;for(auto v : e[u]){if(!vis[v]){vis[v] = true;q.push({v, d + 1});}}}return;
}
signed main(){n = read(), m = read(); int qq = read();for(int i = 1; i <= m; i++){int u = read(), v = read();e[u].push_back(v), e[v].push_back(u);}for(int i = 1; i <= n; i++) bfs(i);for(int u = 1; u <= n; u++){for(int d = 1; d <= n; d++){v[u][d] |= v[u][d - 1];}}while(qq--){int k = read();res.reset();for(int i = 1; i <= k; i++){int u = read(), d = read();res |= v[u][d];}write(res.count()), putchar('\n');}return 0;
}
T3 百鸽笼
怎么还有板子题（
题意简述
维护一个序列，支持如下操作：
-
把序列最左边的那个数扬了
-
在序列最左边插入一个数
-
查询区间第 \(k\) 小
保证 \(n, q \leq 10^5, |V| \leq 10^9\)，256 MB。
题解
主席树板子啊，第二个操作和建主席树的操作一样。
注意卡卡空间。
参考代码：
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fstrict-aliasing")
#include<bits/stdc++.h>
// #define int long long
using namespace std;
bool ST;
inline int read(){int x = 0, f = 1;char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}return x * f;
}
inline void write(int x){if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;
}
int n, q, a[200005], b[400005], rt[400005], tot;
struct Ask{int op;int l, r, k;
}ask[400005];
struct SegT{int ls, rs;int sum;
}t[20000005];
inline void build(int &p, int l, int r){if(!p) p = ++tot;if(l == r) return;int mid = (l + r) >> 1;build(t[p].ls, l, mid), build(t[p].rs, mid + 1, r);return;
}
inline void modify(int &p, int yuanp, int x, int PL, int PR){if(x < PL || x > PR) return;p = ++tot;t[p] = t[yuanp], t[p].sum++;if(x <= PL && PR <= x) return;int mid = (PL + PR) >> 1;modify(t[p].ls, t[yuanp].ls, x, PL, mid), modify(t[p].rs, t[yuanp].rs, x, mid + 1, PR);return;
}
inline int query(int pl, int pr, int k, int PL, int PR){if(PL == PR) return PL;int cntl = t[t[pr].ls].sum - t[t[pl].ls].sum;int mid = (PL + PR) >> 1;if(cntl >= k) return query(t[pl].ls, t[pr].ls, k, PL, mid);return query(t[pl].rs, t[pr].rs, k - cntl, mid + 1, PR);
}
bool ED;
signed main(){// freopen("input.in", "r", stdin);// freopen("output.out", "w", stdout);n = read(), q = read();int btot = 0;for(int i = 1; i <= n; i++) a[i] = b[++btot] = read();for(int i = 1; i <= q; i++){ask[i].op = read();if(ask[i].op == 1){//}else if(ask[i].op == 2){ask[i].k = read();b[++btot] = ask[i].k;}else{ask[i].l = read(), ask[i].r = read(), ask[i].k = read();}}sort(b + 1, b + 1 + btot);int V = unique(b + 1, b + 1 + btot) - b - 1;for(int i = 1; i <= n; i++){a[i] = lower_bound(b + 1, b + 1 + V, a[i]) - b;}for(int i = 1; i <= q; i++){if(ask[i].op == 2){ask[i].k = lower_bound(b + 1, b + 1 + V, ask[i].k) - b;}}// for(int i = 1; i <= n; i++) cout << a[i] << ' ';// cout << '\n' << V << '\n';build(rt[0], 1, V);for(int i = 1; i <= n; i++) modify(rt[i], rt[i - 1], a[n - i + 1], 1, V);int nowr = n;for(int i = 1; i <= q; i++){if(ask[i].op == 1){nowr--;}else if(ask[i].op == 2){modify(rt[nowr + 1], rt[nowr], ask[i].k, 1, V);nowr++;}else{int r = nowr - ask[i].l + 1, l = nowr - ask[i].r + 1;// cout << l << ' ' << r << '\n';write(b[query(rt[l - 1], rt[r], ask[i].k, 1, V)]), putchar('\n');}}// cerr << 1.0 * (&ED - &ST) / 1024.0 / 1024.0 << " MB" << '\n';return 0;
}
T4 方块
感觉不难，为啥只有两个人过这题（
题意简述
赛后被翻出原题了：https://www.luogu.com.cn/problem/UVA1030。
题解
考虑贪心，每次从近到远删方块即可。
时间复杂度大概是 \(\mathcal{O}(Tn^4)\) 的（？）
#include<bits/stdc++.h>
using namespace std;int n;
string view[10][20];
char cube[20][20][20];// 从左到右，从上到下，从前到后
inline tuple<int, int, int> calc(int s, int r, int c, int t){if(s == 1) return {c, r, t};else if(s == 2)return {t, r, n - c + 1};else if(s == 3) return {n - c + 1, r, n - t + 1};else if(s == 4) return {n - t + 1, r, c};else if(s == 5) return {c, t, n - r + 1};else if(s == 6)return {c, n - t + 1, r};return {-1, -1, -1};
}inline void Solve(){for(int i = 1; i <= n; i++){for(int s = 1; s <= 6; s++){cin >> view[s][i];view[s][i] = ' ' + view[s][i];}}for(int x = 1; x <= n; x++){for(int y = 1; y <= n; y++){for(int z = 1; z <= n; z++){cube[x][y][z] = '#';}}}for(int s = 1; s <= 6; s++){for(int x = 1; x <= n; x++){for(int y = 1; y <= n; y++){if(view[s][x][y] == '.'){for(int t = 1; t <= n; t++){auto [xx, yy, zz] = calc(s, x, y, t);cube[xx][yy][zz] = '.';}}}}}bool changed = true;while(changed){changed = false;for(int s = 1; s <= 6; s++){for(int x = 1; x <= n; x++){for(int y = 1; y <= n; y++){char want = view[s][x][y];if(want == '.') continue;// 近 -> 远for(int t = 1; t <= n; t++){auto [xx, yy, zz] = calc(s, x, y, t);if(cube[xx][yy][zz] == '.') continue;if(cube[xx][yy][zz] == '#'){cube[xx][yy][zz] = want;changed = true;break;}if(cube[xx][yy][zz] == want) break;cube[xx][yy][zz] = '.', changed = true;}}}}}int ans = 0;for(int x = 1; x <= n; x++){for(int y = 1; y <= n; y++){for(int z = 1; z <= n; z++){if(cube[x][y][z] != '.'){ans++;}}}}cout << "Maximum weight: " << ans << " gram(s)" << '\n';return;
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);while(cin >> n && n) Solve();return 0;
}
/*
3
.R. YYR .Y. RYY .Y. .R.
GRB YGR BYG RBY GYB GRB
.R. YRR .Y. RRY .R. .Y.
2
ZZ ZZ ZZ ZZ ZZ ZZ
ZZ ZZ ZZ ZZ ZZ ZZ
0
*/