首页 > 其他分享 >2024ICPC网络赛第二场题解(部分)

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

时间：2024-09-23 12:02:53浏览次数：10  
标签：第二场 return cout 2024ICPC int 题解 cin long st

前言

这场相对作用大一点，最后顶着队友的怀疑压力乱搞出了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];
        else
            id = 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';
        else
            cout << " ";
    }
}

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];
        else
            id = 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]) //动态维护border
            j = 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];
                else
                    sum[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;
}

标签：第二场,return,cout,2024ICPC,int,题解,cin,long,st
From： https://www.cnblogs.com/TJUHuangTao/p/18426822

相关文章

  • 网站程序打不开数据库错误等常见问题解决方法
    当遇到网站打不开或者数据库错误等问题时，可以按照以下步骤来诊断并解决问题：检查网站根目录：如果上传数据后显示“主机开设成功！”或“恭喜，lanmp安装成功！”，这通常是因为服务器默认放置了一个index.htm文件。此时应检查wwwroot目录内是否有自己的程序文件，并考虑删除默认的index.h......
  • 题解：AT_arc184_a [ARC184A] Appraiser
    本质上还是官方题解的分组并利用\(M\)不大的思路。询问次数\(Q\)离最简单的每个扫一遍就可以知道答案的做法少了\(50\)次。我们考虑如何减少这个次数。首先你可以发现一次询问可以覆盖到两个数，也就是说所有的数都被覆盖时只需要询问\(500\)次。我们考虑把不同的对拉出......
  • 网站打不开数据库错误等常见问题解决方法
    当遇到网站打不开且出现数据库错误等问题时，可以采取以下步骤进行排查和解决：检查默认页面：如果网站显示“主机开设成功！”或者“恭喜，lanmp安装成功！”这样的信息，这可能是服务器默认放置的页面。检查wwwroot目录下是否有自己的程序文件，如果没有，上传正确的文件，并删除默认的index.ht......
  • [ABC371F] Takahashi in Narrow Road 题解
    洛谷题目链接Atcoder题目链接前言这道题我赛时想到了正解并打了出来，然后因为把\(l\)打成了\(1\)导致WA\(\times23\)，然后又没场切六道题（悲。然后赛后有人说正解是珂朵莉树/线段树，然而我是珂朵莉树\(+\)线段树，呵。题意数轴上有\(n\)个人，第\(i\)个人初始在\(X_i\)处，每一次操作......
  • CF1239E Turtle 题解
    Description一只乌龟从\(2\timesn\)的棋盘的左上角走到右下角，只能往下或往右，需要给出一种方案来分配\(2n\)个数字使得乌龟走过的路径上的数之和的最大值最小。\(2\leqn\leq25,0\leqa_{1,i},a_{2,i}\leq5\times10^4\)。Solution设\(pre_{i}=\sum_{j=1}^{i}{a_{1,i}......
  • P5975 photo 题解
    Solution先离散化，记\(f(l,r,p)\)为覆盖了\([l,r]\)区间内纵坐标\(\gep\)的点最少矩形个数。则：\[f(l,r,p)=\min(f(l,r,p),f(l,mid,p)+f(mid+1,r,p))\]\[f(l,r,p)=\min(f(l,r,p),f(l,r,res)+1)\]令\(h\)为用面积为\(S\)的矩形去覆盖\([l,r]\)区间的高度，即\(S/(r......
  • P9192 Pareidolia 题解
    Statement给串\(t\)，定义\(B(s)\)为\(s\)删一些字符后能出现最多多少个bessie，\(A(t)\)表示对\(t\)的所有子串\(s\)求\(B(s)\)的和，有\(q\)次单点修改，每次改完输出\(B(s)\).Solution动态dp，但是带矩乘\(6^3\)常数，不好.还是考虑分治咋做.现在有区间\([l,mid],......
  • P3703 树点涂色 题解
    Statement树，每个点有一个颜色，初始每个点颜色互不相同到根链涂上新颜色链颜色数\(u\)子树内点\(v\)到根路径的最多颜色数Solution首先，相同颜色的点一定构成一条从下往上的链考虑LCT，维护一个性质：一条实链的点的颜色相同.于是\(u\)到根的颜色数\(=\)\(u\)到根的虚......
  • 最长公共子串 题解
    StatementQ7.1.2.4，时限4s给一个串，定义\(\mathrm{LCS}\)为最长公共子串长度，\(q\)次询问，每次给出\(l,r\)，求\[\operatorname{xor}_{i=1}^{r-l+1}\{i+\mathrm{LCS}(S[l,l+i-1],S[l+i-1,r])\}\]\(n\le10^5,q\le30\)Solutiontag：SA，线段树维护分治结构，orzhunction题目就是......
  • BZOJ 2555 = P5212 SubString 题解
    Statement给你一个字符串 \(\text{init}\)，要求你支持两个操作：在当前字符串的后面插入一个字符串；询问字符串 \(s\) 在当前字符串中出现了几次？（作为连续子串）你必须在线支持这些操作。Solutionextend中link[cur]=q，相当于link，链加新建copy那里，相当于link，cut，链加询......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99