2024ICPC网络赛第二场题解(部分)

前言

这场相对作用大一点，最后顶着队友的怀疑压力乱搞出了C，但是后面看题解发现似乎是数据弱了跑过去，其实复杂度是队友分析的那样，是不正确的，但是毕竟是打名额的比赛，过了就是过了，这里分享一下C题的乱搞做法，以及其他题的我们队赛时代码。下面的顺序按过题顺序(也差不多是难度递增顺序)

F(00:06 1A)

签到题，题干也是致敬了codeforces 传奇4k分Tourist,直接按照题意模拟一下得分，判断有没有超过4k分即可。开局跟榜一眼秒了，直接手速签上。

代码

点击查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 999;
int c[N], w[N], n, k;
int bl[N], m;
map<string, int> mp;
vector<int> s[N];
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> k;int x = n;for (int i = 1; i <= k; i++)cin >> c[i], x = min(x, c[i]);for (int i = 1; i <= n; i++) {cin >> w[i];string st;cin >> st;int id;if (mp.count(st))id = bl[i] = mp[st];elseid = bl[i] = mp[st] = ++m;s[id].push_back(w[i]);}for (int i = 1; i <= m; i++)sort(s[i].begin(), s[i].end(), greater<int>());vector<int> gp;for (int i = 1; i <= m; i++) {for (int j = 0; j < s[i].size() && j < x; j++)gp.push_back(s[i][j]);}sort(gp.begin(), gp.end());int tot = gp.size();for (int i = 1; i <= n; i++) {int rk =tot - (upper_bound(gp.begin(), gp.end(), w[i]) - gp.begin()) + 1;if (s[bl[i]].size() > x && w[i] < s[bl[i]][x - 1])rk--;cout << rk << '\n';}return 0;
}

J(00:20 1A)

这题其实看数据范围，就能大概猜出来肯定是要sort一下后按题意去算答案，关键是要找排序的cmp函数规则。然后就发现肯定只要考虑相邻两项，谁放上面(这也是这种排序题的套路，有一个经典的类似题，字符串排序 return a + b < b + a)，就列两项，字母表示一下对应答案，就能发现规则就是看那两个参数比值，不过要注意一下，比值最好化除为乘，防止精度之类的问题。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2e5+9999;
int v[N], n;
pair<int, int> p[N];
bool cmp(pair<int, int> a, pair<int, int> b){return a.second * b.first > a.first * b.second;
}
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;long long ans = 0;for(int i = 1; i <= n; i++)cin >> p[i].first >> v[i] >> p[i].second, ans += v[i];sort(p + 1, p + n + 1, cmp);long long sum = 0;for(int i = n; i >= 1; i--){ans -= sum * p[i].second;sum += p[i].first;}    cout << ans << '\n';return 0;
}

I(00:31 1A)

看题意，就会想到计算机系统基础的补码、二进制那些知识，所以自然会往这边想，然后邓队想了一会儿后单切了，大概是去找新定义下二进制跟原先的对应关系再去替换。

代码

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
void solve() {int n;cin >> n;if (n % 4 == 0) {cout << "NO\n";return;}int a[32]{};int ans[32]{};for (int i = 30; i >= 0; i--) {a[i] = n >> i & 1;}vector<int> v;for (int i = 31; i >= 0; i--) {v.pb(i);if (a[i] == 1) {for (auto p : v)ans[p] = -1;ans[v[0]] = 1;v.clear();}}cout << "YES\n";for (int i = 0; i <= 31; i++) {cout << ans[i];if (i % 8 == 7)cout << '\n';elsecout << " ";}
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--)solve();return 0;
}

L(00:54 1A)

我读完题意后告诉队友，后面主要是范队推的式子。首先会自然想到肯定有一个分界点，一直随机，直到随机出来的数据小于分界点后就不操作了，动作上肯定是前面一直随机，后面不操作。因为不操作也花1秒，如果后面还要随机，那这样就浪费了1秒，所以前面肯定一直在随机。然后范队发现，分界点后面的期望都相同，然后就推推推，最后化了个对勾函数式子，不过他对勾函数最小值想错了，我纠正了一下，后面就让他上去写了。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n;
#define pi pair<int, int> 
#define i128 __int128_t
void update(int k, int T, pi &ans){pi now;now.first = 2 * k;now.second = 2 * T + k * k - k;int g = __gcd(now.first, now.second);now.first /= g, now.second /= g;if((i128)now.second * ans.first < (i128)now.first * ans.second) ans = now;
}
void solve(){int T;cin >> T;int k = sqrt(2 * T);pi ans = {1, 1e9};if(k <= T && k) update(k, T, ans);if(k-1 <= T && k-1) update(k-1, T, ans);if(k+1 <= T && k+1) update(k+1, T, ans);cout << ans.second << " " << ans.first << '\n';
}
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;while(n--) solve();return 0;
}

A (1:12 1A)

这题前面算是歪榜了，开局都没什么人做，可能是题面有点小长且绕，然后我一下想到了贪心，选人最少的赛站，发现样例能过，想的也挺对，就大力怂恿范队去写这个二分，他也一发过了。这题难得算我完整提供IDEA的一题。

代码

点击查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 999;
int c[N], w[N], n, k;
int bl[N], m;
map<string, int> mp;
vector<int> s[N];
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> k;int x = n;for (int i = 1; i <= k; i++)cin >> c[i], x = min(x, c[i]);for (int i = 1; i <= n; i++) {cin >> w[i];string st;cin >> st;int id;if (mp.count(st))id = bl[i] = mp[st];elseid = bl[i] = mp[st] = ++m;s[id].push_back(w[i]);}for (int i = 1; i <= m; i++)sort(s[i].begin(), s[i].end(), greater<int>());vector<int> gp;for (int i = 1; i <= m; i++) {for (int j = 0; j < s[i].size() && j < x; j++)gp.push_back(s[i][j]);}sort(gp.begin(), gp.end());int tot = gp.size();for (int i = 1; i <= n; i++) {int rk =tot - (upper_bound(gp.begin(), gp.end(), w[i]) - gp.begin()) + 1;if (s[bl[i]].size() > x && w[i] < s[bl[i]][x - 1])rk--;cout << rk << '\n';}return 0;
}

G(01:32 1A)

邓队单切的，我前面也看了一眼，不过读错题了，自动代入了暑期多校的那题博弈，当初那题记得是打表找规律，不然dfs可能会有环很难处理，这题我就放弃了思考，后面邓队过了，最后我问了下他怎么做才发现我读错题了，这里输了不是给赢家钱，而是丢掉，所以直接递归模拟题意，最多log轮就结束了。

代码

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int M = 998244353;int fp(int a, int b) {int re = 1;while (b) {if (b & 1)re = re * a % M;a = a * a % M;b = b >> 1;}return re;
}
int div(int a) {return fp(a, M - 2);
}
int upd(int a, int b) {return (a + b - 1) / b;
}int dfs(int x, int y, int a, int b) {if (x > y)return (1 - dfs(y, x, b, a) + M) % M;int re = fp(a, upd(y, x));if (y % x) {re += dfs(x - y % x, y % x, a, b) * (fp(a, upd(y, x) - 1)) % M * b % M;}return (re % M + M) % M;
}void solve() {int x, y;cin >> x >> y;int a, b, c;cin >> a >> b >> c;c = a + b;a = a * div(c) % M;b = b * div(c) % M;cout << (dfs(x, y, a, b) % M + M) % M << "\n";
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while (t--)solve();return 0;
}

E(2:48 3A)

题面很长，很绕，我看了好久才看懂题意。不过看懂题意后，就比较容易有大致思路。会去处理每个点，可能有机器人到达的最早时间，之后因为机器人可以反复横跳，所以最早时间之后的同奇偶性时间内，也可以有机器人，所以要分开考虑每个点有机器人到达的奇偶时间的最早时间。至于机器人的参数d，可以bfs后看每个点的最早时间，如果大于d就说明其实不能到达。之后就从1节点开始bfs，避开可能有机器人的点，最后递归输出答案即可。实现上，范队是把一个点拆成 \(i\) 和 \(i + n\) 表示奇偶的做，中间有一发 wa了是因为判无解时候只是bfs后看 \(n\) 号点的距离是不是大于 \(n\)， 但是由于可能走个环改变奇偶性，所以最终距离可能是大于 \(n\) 的，改了之后就过了。

代码

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+9999;
int n, dist[N*2], m, k, d, ds[N*2], pre[N * 2];
vector<int> e[N];
void print(int u){if(u == 0) return ;print(pre[u]);cout << u - (u > n) * n << " ";
}
void solve(){cin >> n >> m >> d;for(int i = 1; i <= n; i++)e[i].clear(), dist[i] = dist[i+n] = 1e8, ds[i] = ds[i + n] = 1e8;	for(int i = 1; i <= m; i++){int u, v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}cin >> k;queue<int> q;for(int i = 1; i <= k; i++){int x;cin >> x;dist[x] = 0;q.push(x);} while(!q.empty()){int u = q.front(), t = 0;q.pop();if(u > n) t = 1;for(auto v : e[u - t * n]){if(dist[v + (t ^ 1) * n] > dist[u] + 1){dist[v + (t ^ 1) * n] = dist[u] + 1;q.push(v + (t ^ 1) * n);}}}for(int i = 1; i <= n * 2; i++)if(dist[i] > d) dist[i] = 1e8;    pre[1] = ds[1] = 0;q.push(1);while(!q.empty()){int u = q.front(), t = 0;q.pop();if(u > n) t = 1;for(auto v : e[u - t * n]){v = v + (t ^ 1) * n;if(ds[v] <= ds[u] + 1) continue;if(ds[u] + 1 >= dist[v]) continue;ds[v] = ds[u] + 1;pre[v] = u;q.push(v);}}   int ed;if(ds[n] < ds[n * 2]) ed = n;else ed = n * 2;if(ds[ed] > n) {cout << "-1\n";return ;}cout << ds[ed] << '\n';print(ed);cout << '\n';
}
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}

C(4:39 3A)

这题是难得我操刀的非签到题。首先得益于范队的题意转化，把Z函数转成了kmp的border，然后去考虑答案的增量，发现了题意转化为，每次在border树上加一个叶子，然后需要统计叶子到根路径上的 \(\sum b[n - x + 1]\) ，但是由于强制在线，长度 \(n\) 在不断变化，所以好像没办法很方便维护这个权值，一直卡在这里。
刚好前段时间我一直在学字符串，在PAM里面有讲到字符串的border树上，到根的路径可以划分为不超过 \(log\) 个等差数列的性质，我就一直在想能不能用这个性质来维护这个东西。发现还是比较困难，不过发现等差数列，在那个求和里面，间隔也是若干个等差数列，我就想能不能用前缀和来维护一下不同公差的 \(b[i]\) 的和。然后考虑根号分治，但是这题空间很小，才128MB，估计就是因为正解是 \(O(n)\) 的，想卡掉这样的做法，但是没卡掉。而范队看到这个数据范围，就觉得这个复杂度肯定过不了。但我还是坚持想试试，于是我就自己主动去写了。
但是动态维护border就写不来了，，，之前kmp都是抄的板子，还是让范队帮我写一下动态维护border的部分，后面我去慢慢写等差数列的部分。
然后交上去，果然MLE了，只好调整一下块长，再交，再MLE，最后急了，直接块长调50，公差小于50的等差数列直接用前缀和一下算，大的直接暴力跳border树，然后漫长的等待后居然过了。这时我有点懊悔，前面调块长的时候应该谨慎一点让范队算一下块长多少不会MLE的，白吃了几发罚时有点可惜，不过我写的也是歪解，所以能过就别挑了。

代码

点击查看代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5 + 999;
int s[maxn], a[maxn], b[maxn], n;
ll lstans;
int nxt[maxn];
int diff[maxn], slink[maxn];
int sum[maxn][51], tag[maxn];
signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;int sqr = 50;for (int i = 1; i <= n; i++) {cin >> s[i];s[i] = (s[i] + lstans) % n;cin >> a[i] >> b[i];int j = nxt[i - 1];while(j && s[j + 1] != s[i]) //动态维护borderj = nxt[j];if(s[j + 1] == s[i])j++;if(i == 1)j = 0;nxt[i] = j;diff[i] = i - nxt[i];if (!tag[diff[i]]) tag[diff[i]] = 1; //类似pam维护等差数列if (diff[i] == diff[nxt[i]]) slink[i] = slink[nxt[i]];else slink[i] = nxt[i];j = i;for (int j = 1; j <= 50; j++) { //更新公差小的前缀和if (!tag[j]) continue;for (int k = tag[j]; k <= i; k++) {if (k - j >= 0)sum[k][j] = sum[k - j][j] + b[k];elsesum[k][j] = b[k];}tag[j] = i + 1;}ll temsum = 0;while (j) //跳border树{// temsum += b[i - j + 1];// j = nxt[j];if (diff[j] > 50) {temsum += b[i - j + 1];j = nxt[j];} else {if (i == 5) {int debug = 0;}int st = max(0, i + 1 - j - diff[j]), ed = i + 1 - slink[j] - diff[j];temsum += sum[ed][diff[j]] - sum[st][diff[j]];j = slink[j];}}lstans += temsum * a[i];cout << lstans << '\n';}return 0;
}