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

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

时间：2024-09-15 20:13:37浏览次数：9  
标签：cout 2024ICPC int 题解 long edge 第一场 debug define

这一场基本纯挂件，给队友翻译翻译题面，帮队友打打板子了，可惜最后40sL题冲了一个 \(O(\frac{n^3}{w})\) 的bitset最后wa了，所以下面的题解我也只能看着队友代码说说大概，主要参考一下代码吧。

A

题意

给出32个队伍的能力值，和比赛的规则，其中中国队是第一个队伍，问所有分组的情况下，中国队的最好可能成绩是什么。
签到，首先因为32个队能力值都不同，所以只需要看中国队的能力值排名，就决定了最终的答案。具体的话队友应该是手玩了各个情况，写了一堆if else过的。

代码

点击查看代码 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using namespace std;
bool debug = 1;
#define dbg(x)                                                   \
    if (debug)                                                   \
        cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) \
             << NORMAL_FAINT << COLOR_RESET << endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m",
             NORMAL_FAINT = "\033[0;2m";

void solve() {
    int a[32];
    int de = 0;
    for (int i = 0; i < 32; i++) {
        cin >> a[i];
        if (a[i] <= a[0])
            de++;
    }
    if (de == 32) {
        cout << 1;
    } else if (de >= 28) {
        cout << 2;
    } else if (de >= 14) {
        cout << 4;
    } else if (de >= 7) {
        cout << 8;
    } else if (de >= 3) {
        cout << 16;
    } else
        cout << 32;

    cout << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

//__builtin_popcountll()
// cout<<fixed<<setprecision(2);

C

题意

给定 \(n\) 个限制 \((l_i, r_i)\)， 问长度为 \(n\) 的全排列中，且满足第 \(i\) 个数位于区间 \((l_i, r_i)\)内的排列数个数的奇偶性。

首先题目既然只问的奇偶性，就说明不太可能暴力求出来真正的总个数。然后队友画画图，最后猜了个结论，对每个限制 \((l_i, r_i)\) 建一条边 \(l-1, r\)，最后看建出来的图是不是一棵树。瞪眼法秒了，具体原理还不太清楚，看群里别人说好像跟什么满秩，线性代数什么的知识有关。

代码

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define pii pair<int,int>
using namespace std;
bool debug = 1;
#define dbg(x) if(debug) cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<NORMAL_FAINT<<COLOR_RESET<<endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";


void solve(){
    int n;
    cin >> n;
    int sum = 0;
    vector<int> a[n + 1]{};
    vector<int> vis(n+1);
    for (int i = 1; i <= n;i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        a[u].pb(v);
        a[v].pb(u);
    }
    function<void(int)> dfs = [&](int u) {
        if(vis[u]==0)
            sum++, vis[u] = 1;
        for(auto p:a[u]){
            if(vis[p]==0)
                dfs(p);
        }
    };
    dfs(0);
    if(sum==n+1)
        cout << 1;
    else
        cout << 0;
    cout << '\n';
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

//__builtin_popcountll()
// cout<<fixed<<setprecision(2);

F

题意

给一个数组，每次操作选择一个区间，满足区间内的数不能完全相同，然后将区间里的数全都改为区间最大值，问最多能操作多少次

首先容易去考虑，对于每个数，利用单调栈求出它作为区间内唯一最大值的范围，那么操作的时候，就可以从小到大依次操作这些区间，然后基本上就做完了，具体的式子可能还得推推，看代码似乎就是把这样的区间长度加起来。

代码

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define pii pair<int,int>
using namespace std;
bool debug = 1;
#define dbg(x) if(debug) cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<NORMAL_FAINT<<COLOR_RESET<<endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";

const int N = 2e5 + 999;
int n, a[N], stk[N], top, l[N], r[N];
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    stk[top = 0] = 0;
    for (int i = 1; i <= n; i++){
        while(top && a[i] > a[stk[top]])
            top--;
        l[i] = stk[top] + 1;
        stk[++top] = i;
    }
    stk[top = 0] = n + 1;
    a[n + 1] = 0;
    for (int i = n; i >= 1; i--){
        while(top && a[i] > a[stk[top]])
            top--;
        r[i] = stk[top] - 1;
        if(a[r[i] + 1] == a[i])
            r[i] = i;
        stk[++top] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += r[i] - l[i];
    cout << ans << '\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

//__builtin_popcountll()
// cout<<fixed<<setprecision(2);

G

题意

给一个长度 \(2\times 10^3\) 的数组 \(a[n]\), 可以得到一个 \(n \times n\) 的二维数组 \(b[i][j]\)， 表示数组\(a\) 在区间 \([i, j]\) 的中位数。再由数组 \(b[n][n]\) 得到一个二维数组 \(c[i][j]\) 表示数组 \(b[n][n]\) 在 \((i, i) to (j, j)\) 这个矩形范围内的中位数。最后问你数组 \(c[n][n]\) 的中位数是多少。

首先看到中位数很容易去考虑二分答案后，转01矩阵。那么这题同理，首先因为 \(n\) 很小，最终答案肯定是数组 \(a[n]\) 的某个数，只要在这些数里面二分，然后数组 \(b[i][j]\) 直接 \(O(n^2)\) 的枚举，用前缀和暴力算。对数组 \(b[n][n]\) 再去二维前缀和， \(O(n^2)\) 地暴力求出数组 \(c\)，最后判断数组 \(c[n][n]\) 里1的个数。详见代码

代码

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define pii pair<int,int>
using namespace std;
bool debug = 1;
#define dbg(x) if(debug) cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<NORMAL_FAINT<<COLOR_RESET<<endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";

const int N = 2033;

int n, a[N], rk[N], s[N], b[N][N], c[N][N], sb[N][N];

bool check(int x){
    for (int i = 1; i <= n; i++){
        s[i] = s[i - 1] + (a[i] > x);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            b[i][j] = !(j - i + 1 - s[j] + s[i - 1] >= (j - i + 2) / 2);
    /*for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cout << b[i][j] << " \n"[j == n];*/
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            sb[i][j] = sb[i - 1][j] + sb[i][j - 1] + b[i][j] - sb[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++){
            c[i][j] = (sb[j][j] - sb[i - 1][j] - sb[j][i - 1] + sb[i - 1][i - 1]);
            int sz = (j - i + 2) * (j - i + 1) / 2;
            if(sz - c[i][j] >= (sz + 1) / 2)
                cnt++;
        }
    return cnt >= (n * (n + 1) / 2 + 1) / 2;
}
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], rk[i] = a[i];
    sort(rk + 1, rk + n + 1);
    int l = 1, r = n, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(rk[mid]))
            r = mid;
        else
            l = mid + 1;
    }
    cout << rk[l];
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    while(t--)
        solve();
    return 0;
}

//__builtin_popcountll()
// cout<<fixed<<setprecision(2);

H

题意

括号序列长度为 \(2 * n\) ，每个位置给定了颜色 \(col[i]\)， 并且有一个价值 \(val[i]\)， 括号序列的价值定义为左括号所在位置的价值和。一个括号序列合法，需要括号序列本身是正则匹配的，还对每种颜色要求了，\(n\) 个左括号中对应颜色的数量至少达到 \(cnt[i]\) 个。问所有合法的括号序列的最大价值是多少。数据范围比较小， \(n \leq 100\) 左右。

括号序列会想起来很久之前牛客的一次练习赛(https://ac.nowcoder.com/acm/contest/75768/F)里面有跟网络流结合起来判合法括号，看到数据范围挺小，就让队友想想能不能用网络流，最大流保证括号合法，费用流求最大价值。然后队友比划比划后想出来建模了，把左括号数量下界的限制，转化为右括号的数量上界限制，先把所有价值加起来，然后匹配上一个右括号，相当于去掉所在位置的价值，所以最小费用就可以让最后剩的价值最大。具体建模可以看看代码里面，而且有一个wa点，就是如果给的左括号数量本身不合法，可能建模会建出来负的边权，需要特判掉-1.

代码

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define pii pair<int,int>
using namespace std;
bool debug = 1;
#define dbg(x) if(debug) cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<NORMAL_FAINT<<COLOR_RESET<<endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";
const int N = 1009;
int n, m, dist[N], head[N], flow[N], vis[N], S, T, tot, pre[N];
struct Edge{
    int v, rest, p, nxt;
} edge[N * 40];
typedef long long ll;
int col[N], cnt[N], val[N];
bool SPFA() {
    for (int i = 1; i <= n + m + 10; i++)
        dist[i] = flow[i] = 1e16, vis[i] = 0;
    queue<int> q;
    q.push(S), dist[S] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].nxt) {
            if (edge[i].rest && dist[edge[i].v] > dist[u] + edge[i].p) {
                dist[edge[i].v] = dist[u] + edge[i].p;
                pre[edge[i].v] = i;
                flow[edge[i].v] = min(flow[u], edge[i].rest);
                if (!vis[edge[i].v])
                    q.push(edge[i].v), vis[edge[i].v] = 1;
            }
        }
    }
    return dist[T] < 1e15;
}
void maxflow() {
    ll ans = 0, f = 0;
    //cout << "maxflow" << endl;
    while (SPFA()) {
        //cout << "SPFA" << endl;
        //cout << flow[T] << " " << dist[T] << endl;
        f += flow[T];
        ans += flow[T] * dist[T];
        int x = T;
        while (x != S) {
            int y = pre[x];
            edge[y].rest -= flow[T];
            edge[y ^ 1].rest += flow[T];
            x = edge[y ^ 1].v;
        }
    }
    if(f < n / 2)
        cout << "-1\n";
    else {
        ans = -ans;
        for (int i = 1; i <= n; i++)
            ans += val[i];
        cout << ans << '\n';
    }    
}
void add(int u, int v, int c, int w, int t = 1){
    edge[++tot] = (Edge){v, c, w, head[u]};
    head[u] = tot;
    if(t)
        add(v, u, 0, -w, 0);
}
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> cnt[i], cnt[i] = -cnt[i];
    n *= 2;
    for (int i = 1; i <= n; i++){
        cin >> col[i];
        cnt[col[i]]++;
    }
    for (int i = 1; i <= n; i++)
        cin >> val[i];
    //cout << "finish" << endl;
    memset(head, 0, sizeof head);
    S = 1, T = 2;
    tot = 1;
    add(S, n + 2, n / 2, 0);
    for (int i = n; i > 1; i--)
        add(i + 2, i + 1, (i - 1) / 2, 0), add(i + 2, n + 2 + col[i], 1, val[i]);
    add(1 + 2, n + 2 + col[1], 1, val[1]);
    bool flag = 1;
    for (int i = 1; i <= m; i++){
        add(n + 2 + i, T, cnt[i], 0);
        if(cnt[i] < 0)
            flag = 0;
    }
    if(flag) maxflow();
    else
        cout << "-1\n";
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

//__builtin_popcountll()
// cout<<fixed<<setprecision(2);

M

题意

给出每个提交，包含队伍名、题号、通过情况，问哪个题通过的队伍数最多

整场就这个题是我写的/(ㄒoㄒ)/~~，直接用STL暴力对每个题号的通过队伍名字放set去重，然后遍历map已经是按字典序从小到大，然后判断一下就行。

代码

点击查看代码 
#include<bits/stdc++.h>
#define int long long 
#define pb push_back
#define pii pair<int,int>
using namespace std;
bool debug = 1;
#define dbg(x) if(debug) cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<NORMAL_FAINT<<COLOR_RESET<<endl;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";


void solve(){
    int n; cin >> n;
    //teamA A accepted
    map<string, set<string>> mp;
    for (int i = 1; i <= n; i++) {
        string a, b, c;
        cin >> a >> b >> c;
        if (c[0] == 'a') {
            mp[b].insert(a);
        }
    }
    int mx = 0;
    string ans;
    for (auto it : mp) {
        if (it.second.size() > mx) {
            mx = it.second.size();
            ans = it.first;
        }
    }
    cout << ans << "\n";
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

//__builtin_popcountll()
// cout<<fixed<<setprecision(2);

L (参考思路)

题意

有 \(n\) 个点，恰好有一个点没有奶牛，其他都有奶牛，还有 \(l\) 个按钮，每个按钮按下后，可以控制点 \(i\) 处的奶牛移动到 \(t_i\) 位置，只有保证奶牛不能移动到同一个点才能去按按钮。还有 \(q\) 次询问，每次询问，初始没有点的奶牛在 \(a\) 处，最终想要让 \(b\) 点没有奶牛，并且仅使用前 \(c\) 个按钮，问能否实现，用0/1回答。

首先注意到，一个按钮如果能使用，要么移动的到的 \(t_i\) 恰好是一个排列，要么恰有2个 \(t_i\) 相同，且洞位于其中一个位置，否则按按钮必会使奶牛相撞。所以，按一次按钮，相当于让洞移动，而询问相当于问洞从 \(a\) 出发，到达 \(b\)，我们就去考虑按按钮对于没有奶牛的洞的影响。对于排列的情况，相当于有一个置换环，因为可以无限次使用按钮，所以同一个环上的点一定可以互相到达。而第二种情况，相当于两条边，(方向还没想好)，因为洞只能在重复的那两个点之一。询问相当于问操作前 \(c\) 个按钮，让洞从 \(a\) 移动到 \(b\) 点。所以可以对询问离线，维护每个点到其他点的连通性，但是一直没想到好的维护方法，最后想用bitset冲一下，但是时间来不及了，过样例只剩40s直接交了，赛后看到wa了。不过也知道了是因为前面两条边那个情况应该哪个点往哪个点建边这个没考虑清楚，还是前面做太慢了这题没做出来可惜。

标签：cout,2024ICPC,int,题解,long,edge,第一场,debug,define
From： https://www.cnblogs.com/TJUHuangTao/p/18415578

相关文章

  • 1928.规定时间内到达终点的最小话费，题解
    1928.规定时间内到达终点的最小花费-力扣（LeetCode）有点难，参考官方题解代码：利用了动态规划思想，逐步计算从起点到各个城市在不同时间下的最小费用。 1.代码解释，涉及，static关键字，constexpr关键字，INT_MAX除以2赋值的含义staticconstexprintINFTY=INT_MAX/2; 1.**`......
  • Hetao P1391 操作序列 题解 [ 绿 ] [ 二维线性 dp ]
    操作序列：简单的二维dp。观察我们每次操作可以让\(x\)变为\(2x-1\)，或者当\(x\)为奇数时让\(x\)变为\(\frac{x+1}{2}\)。显然，执行第一种操作，会使\(x\)变成奇数。那一旦我们连续执行两次操作，\(x\)就会变为：\[\frac{(2x+1)-1}{2}=\frac{2x}{2}=x\]也就是说，当\(x\)......
  • 语言 题解
    语言题解本题其实没有什么好说的，主要是提供一种强大的，神秘的，诡异的，跑得飞快的，逆天的，唐诗的双\(\log\)做法首先考虑将答案分类，分成跨过这个语言的lca的和没跨过的对于没跨过的，可以发现就是对于每个点，求能扩展到的深度最低的节点，这个直接暴力做就是\(O(n)\)的，所以说我们直......
  • 题解：AT_pakencamp_2019_day3_d パ研軍旗
    题意简述给定\(5\)行\(N\)列的网格，每个格子有四种可能的颜色。要使网格中每一列的颜色都一样但不能是黑色，并且相邻两列的颜色不相同。问最少改变多少个格子的颜色能满足要求。思路分析为方便处理，把给定的红色、蓝色、白色、黑色分别转成数字\(1,2,3,4\)。考虑dp。不妨......
  • 题解：AT_abc371_c [ABC371C] Make Isomorphic
    题目大意有两个简单无向图，你每一次可以给第二个图添上或去掉一条边，有相应花费，问将两个图变为同构最少需要花费多少钱。思路观察数据范围，可以发现NNN非常小，可以考虑枚......
  • 「KDOI-06-S」题解
    T2树上异或题面分析树形DP题考虑一颗子树内部的某种割边方式，假设其被分为\(n\)个连通块，每个连通块的权值分别为\(a_1,a_2,\dots,a_n\)，那么该子树在这种割边方式下对答案的贡献就为\(\prod_{i=1}^{n}a_i\)。因此就可以从叶子向根不断合并，求出每种割边状态的值，时......
  • 【洛谷 P1596】[USACO10OCT] Lake Counting S 题解（深度优先搜索）
    [USACO10OCT]LakeCountingS题面翻译由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个的网格图表示。每个网格中有水（W）或是旱地（.）。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，......
  • Codeforces Round 972 (Div. 2) 2005C. Lazy Narek 题解
    原题链接：https://codeforces.com/contest/2005/problem/C看了教程发现都是用dp做的，在这里分享一个差不多的SPFA的思路（赛场上忘了Dijkstra不能有负边所以炸了）时间复杂度与dp同样是O(nm)形式化题意和翻译：有n个长度为m的字符串，你可以选择或不选择来拼接它们，但是不能更改字符串的......
  • 食物链题解
    双倍经验：P2024[NOI2001]食物链当问题要求维护一些对立的关系时（朋友、敌人），就可以用种类并查集实现。因为有三种关系所以并查集的数组要开三倍空间，第一倍空间存同类关系，第二倍存捕食关系，第三倍存被捕食关系。注意：一的猎物的猎物就是一的天敌，其他就可以直接并查集维护即可。注......
  • [ABC371D] 1D Country 题解
    这题，怎么说呢，\(STL\)大法好。前置芝士：lower_pound函数在结构体上的使用。那其实这题便是一个二分前缀和的水题了。结构体存储每个村庄的距离\(x\)，人口\(d\)。对于每个输入的\([l,r]\)二分查找其对应的村庄，进行一次答案的统计，输出即可。代码:#include<bits/stdc++.......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99