邮寄
开场直接随机跳题。
开 C。
C 做出来了，开 E。
稍微想了一会，E 是一个高维前缀和。秒了。
然后发现 I 是小模拟，秒了。
然后：
list ex = {C, E, I}
REPEAT when 1
FOR problem cur in [A, K] except ex
try
solve cur
catch (cur solved)
ex.append(cur)
caught problem K: 无脑分层图。
然后
REPEAT when 1
FOR problem cur in {D, H, J}
try
solve cur
catch (cur solved)
__ins.erase(cur)
然后再循环了 2h 之后 3:07:58 极限过掉 D。
此时，一声“卧槽！————”响彻机房。
按照开题顺序。
Link。
C
double、python：你在干什么
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
int n, x, ans;
double tmp = 1;
int main() {
for(cin >> n; n--; ) {
cin >> x;
tmp *= x;
}
for(; tmp - 1 >= eps; ) {
ans++, tmp /= 2024;
}
cout << ans << '\n';
return 0;
}
E
状压每种可以拼接的串，高位前缀和，\(O(2^V)\)。
#include <bits/stdc++.h>
using namespace std;
int n, arr[1000010], sum[1 << 18], is[1 << 18];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
}
for(int l = 1; l <= n; l++) {
int mask = 0;
for(int r = l; r <= n; r++) {
if((mask >> (arr[r] - 1)) & 1) {
break;
}
mask |= (1 << (arr[r] - 1));
sum[mask] = __builtin_popcount(mask);
is[mask] = 1;
}
}
for(int i = 0; i < 18; i++) {
for(int j = 0; j < (1 << 18); j++) {
if((j >> i) & 1) {
sum[j] = max(sum[j], sum[j - (1 << i)]);
}
}
}
int ans = 0;
for(int i = 0; i < (1 << 18); i++) {
if(is[i]) {
ans = max(ans, __builtin_popcount(i) + sum[((1 << 18) - 1) ^ i]);
}
}
cout << ans << '\n';
return 0;
}
I
小模拟。
#include <bits/stdc++.h>
using namespace std;
int n, k, m, q, a, arr[10010];
int h(int x, int i) {
int rs = 1;
for(; i--; ) {
rs = rs * x % n;
}
return rs;
}
int main() {
cin >> n >> k >> m >> q;
for(int i = 1; i <= m; i++) {
cin >> a;
for(int j = 1; j <= k; j++) {
arr[h(a, j)] = 1;
}
}
for(int i = 1; i <= q; i++) {
cin >> a;
int f = 1;
for(int j = 1; j <= k; j++) {
f &= arr[h(a, j)];
}
cout << f << ' ';
}
return 0;
}
K
建立一个超级源点，对于每一个点 \(i (1 \le i \le N)\) 有一个对应的用了法器的点 \(i + n\)，
然后：
\(u \to v, u + n \to v + n, u \to v + n, 0 \to u\)
权值不难想。
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
int v, w;
bool operator >(const node &b) const {
return w > b.w;
}
};
//Super:0, normal:1~n, used:n+1~2n
int n, m, u, v, c, arr[100010], vis[200020], dis[200020], ans = -1;
vector<node> to[200020];
priority_queue<node, vector<node>, greater<node> > pq;
void BFS() {
pq.push({0, 0});
for(; pq.size(); ) {
node tmp = pq.top();
pq.pop();
if(vis[tmp.v]) {
continue;
}
vis[tmp.v] = 1, dis[tmp.v] = tmp.w;
for(auto i : to[tmp.v]) {
pq.push({i.v, tmp.w + i.w});
//cout << i.v << ' ' << i.w << '\n';
}
//cout << 'e' << ' ' << tmp.v << ' ' << tmp.w << '\n';
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> u >> v >> c;
to[u].push_back({v, c});
to[v].push_back({u, c});
to[u + n].push_back({v + n, c});
to[v + n].push_back({u + n, c});
to[u].push_back({v + n, 0});
to[v].push_back({u + n, 0});
}
for(int i = 1; i <= n; i++) {
cin >> arr[i];
to[0].push_back({i, arr[i]});
}
BFS();
//cout << "alive" << '\n';
for(int i = 1; i <= n; i++) {
ans = max(ans, min(dis[i], dis[i + n]));
}
cout << ans << '\n';
return 0;
}
D
假设 \(b\) 两两互质，\(\forall i (1 \le i < n), a_i \ge a_{i + 1}\)，可以如此计算答案（注意到 \(d(S_i, S_j) = d(S_j, S_i)\)）：
\[2 \sum \limits_{i = 1}^n \sum \limits_{j = i + 1}^n (a_i - a_j)b_{i}b_{j} \]\[= 2 \sum \limits_{i = 1}^n b_{i} \sum \limits_{j = i + 1}^n (a_i - a_j)b_{j} \]\[= 2 \sum \limits_{i = 1}^n b_{i} \sum \limits_{j = i + 1}^n a_{i}b_{j} - a_{j}b_{j} \]\[= 2 \sum \limits_{i = 1}^n b_{i} (\sum \limits_{j = i + 1}^n a_{i}b_{j} - \sum \limits_{j = i + 1}^n a_{j}b_{j}) \]\[= 2 \sum \limits_{i = 1}^n b_{i} (a_{i} \sum \limits_{j = i + 1}^n b_{j} - \sum \limits_{j = i + 1}^n a_{j}b_{j}) \]所以预处理 \(s_i = \sum \limits_{j = i + 1}^n b_{j}, S_i = \sum \limits_{j = i + 1}^n a_{j}b_{j}\)，答案为
\[2 \sum \limits_{i = 1}^n b_{i}(a_{i}s_{i + 1} - S_{i + 1}) \]对于有一些数不互质的情况，枚举 \(\gcd\)，排除掉 \(\gcd(b_i, b_j) > 1\) 的情况，再直接计算，就可以知道 \(\gcd(b_i, b_j) = d\) 的情况。
直接算就可以了，\(O(\text{能过})\)。
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(3)
using namespace std;
const int kMod = 998244353;
struct node {
int a, b;
}arr[200020];
int n, s[200020], ss[200020], res[200020];
vector<node> cur, val[200020], vval[20];
int get(int x, int i) {
for(; i--; x /= 10) {
}
return x % 10;
}
int solve() {
for(int i = 0; i <= 5; i++) {
for(auto j : cur) {
vval[get(j.a, i)].push_back(j);
}
cur.clear();
for(int j = 9; j >= 0; j--) {
for(auto k : vval[j]) {
cur.push_back(k);
}
vval[j].clear();
}
}
int nn = cur.size();
s[nn] = ss[nn] = 0;
for(int i = nn - 1; i >= 0; i--) {
s[i] = (s[i + 1] + cur[i].b) % kMod;
ss[i] = (ss[i + 1] + cur[i].a * cur[i].b) % kMod;
}
int ans = 0;
for(int i = 0; i < nn; i++) {
ans = (ans + cur[i].b * (cur[i].a * s[i + 1] % kMod + kMod - ss[i + 1]) % kMod) % kMod;
//cout << i << ',' << cur[i].a << ',' << cur[i].b << ',' << s[i + 1] << ',' << ss[i + 1] << '\n';
}
//ans = (ans + ans) % kMod;
return ans;
}
int gans() {
int ans = 0;
for(int i = 200000; i >= 1; i--) {
cur.clear();
for(int j = i, c = 1; j <= 200000; j += i, c++) {
for(auto k : val[j]) {
cur.push_back({k.a, k.b / i});
}
if(j != i) {
res[i] = (res[i] - res[j] * c % kMod * c % kMod + kMod) % kMod;
}
}
res[i] = (res[i] + solve()) % kMod;
ans = (ans + res[i]) % kMod;
//cout << i << ' ' << res[i] << '\n';
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i].a;
}
for(int i = 1; i <= n; i++) {
cin >> arr[i].b;
val[arr[i].b].push_back(arr[i]);
}
//cout << gans() << '\n';
cout << gans() * 2 % kMod << '\n';
return 0;
}