文章关键词:2021 CCPC 网络 重赛

2021 CCPC网络赛重赛

作者:神秘网友 发布时间:2021-10-13 07:24:02

2021 CCPC网络赛重赛

1005:
二分题,题目不难,思路也简单清晰的,考的是细节
每个数首先如果刚好有我这个值,那么肯定直接拿,否则要靠前缀和拿多轮的话肯定是拿的轮数越少越好,那么就把模完以后相同的前缀放到一个\(vector\)里面,直接二分找到小于等于我的那个即可,负的情况就是大于等于我的那个。注意模0的情况。

#define int long long
const int maxn = 1e5 + 10, mod =  998244353;
mapint, int mp, mp2;
int tot = 0;
struct node{
    int x, y;
    node(int x = 0, int y = 0) : x(x), y(y){}
    bool operator  (const node a) const {
        return x  a.x;
    }
};
vectornode v[maxn];
int a[maxn];
void run() {
    int n, m, pre = 0;
    cin  n  m;
    mp.clear();
    mp2.clear();
    tot = 0;
    for(int i = 1; i = n; ++ i) cin  a[i], pre += a[i];
    int sum = pre;
    pre = 0;
    if(sum == 0) {
        mp2[0] = 0;
        for(int i = 1; i = n; ++ i) {
            pre += a[i];
            if(!mp2.count(pre)) mp2[pre] = i;
        }
        for(int i = 1; i = m; ++ i) {
            int x; cin  x;
            if(mp2.count(x))    cout  mp2[x]  '\n';
            else cout  -1  '\n';
        }
        mp2.clear();
        return ;
    }
    mp[0] = ++tot;
    v[1].push_back({0, 0});
    mp2[0] = 0;
    //if(sum = 0) {
        for(int i = 1; i = n; ++ i) {
            pre += a[i];
            int now = pre % sum;
            if(now  0) now += abs(sum);//assert(now = 0)!
            if(!mp.count(now))  mp[now] = ++ tot;
            if(mp2.count(pre))  continue;
            int id = mp[now];
            v[id].push_back({pre, i});
            mp2[pre] = i;
        }
        for(auto it : mp)   if(v[it.second].size())    sort(v[it.second].begin(), v[it.second].end());
        for(int i = 1; i = m; ++ i) {
            int x; cin  x;
            int now = x % sum;
            if(now  0) now += abs(sum);
            if(!mp.count(now)) {
                cout  "-1\n";
            }
            else {
                int id = mp[now];
                int pos = lower_bound(v[id].begin(), v[id].end(), x) - v[id].begin();
                if(sum = 0) {
                    if(pos != v[id].size()  v[id][pos].x == x)   cout  v[id][pos].y  '\n';
                    else if(pos == 0)   cout  "-1\n";
                    else cout  v[id][pos - 1].y + (x - v[id][pos - 1].x) / abs(sum) * n  '\n';
                }
                else {
                    if(pos == v[id].size()) cout  "-1\n";
                    else cout  v[id][pos].y + (v[id][pos].x - x) / abs(sum) * n  '\n';
                }
            }
        }
        for(auto it : mp)   v[it.second].clear();
    //}
    return ;
}

1010:构造题
很清晰就是如果任意一个点到其他点都有两条以上不同路径,那么图上必定有环并且所有点都在环上
然后可以发现给的边是互不连通的,那么必然有方法构造出2n条边环的情况。关键是字典序最小。
可以并查集贪心拿取,因为每个点只连两条边,所以连玩的点就扔掉,复杂度可以\(O(n)\)

#define int long long
const int maxn = 1e5 + 10, mod =  998244353;
struct node{
    int x, y;
    node(int x = 0, int y = 0) : x(x), y(y){}
    bool operator  (const node a) const {
        if(x != a.x)    return x  a.x;
        else return y  a.y;
    }
}a[maxn];
bool vis1[maxn], vis2[maxn];
int fa[maxn * 2];
int find(int x) {
    return x == fa[x]  x : fa[x] = find(fa[x]);
}
void un(int x, int y) {
    if(find(x) != find(y))
        fa[fa[x]] = fa[y];
}
void run() {
    int n, m; cin  n  m;
    for(int i = 1; i = n; ++ i)    vis1[i] = vis2[i] = 0;
    for(int i = 1; i = m; ++ i)    cin  a[i].x  a[i].y, vis1[a[i].x] = 1, vis2[a[i].y] = 1;
    cout  2 * n - m  '\n';
    vectorint v1, v2;
    for(int i = 1; i = n; ++ i) {
        if(!vis1[i])    v1.push_back(i);
        if(!vis2[i])    v2.push_back(i);
    }
    vectornode ans;
    vectorint sz(2 * n + 1);
    //for(int i = 0; i  v1.size(); ++ i) a[++ m] = {v1[i], v2[i]}, ans.push_back({v1[i], v2[i]});
    for(int i = 1; i = n; ++ i)    fa[i] = i, fa[i + n] = i + n;
    for(int i = 1; i = m; ++ i)    un(a[i].x, a[i].y + n), sz[a[i].x] ++, sz[a[i].y + n] ++;
    dequeint q;
    for(int i = 1; i = n; ++ i)    q.push_back(i);
    for(int i = 1; i  n; ++ i) {
        vectorint tmp;
        while(1) {
            int top = q.front();
            q.pop_front();
            if(find(i) != find(top + n)) {
                un(i, top + n), ans.push_back({i, top});
                sz[i] ++; sz[top + n] ++;
            }
            if(sz[top + n]  2) tmp.push_back(top);
            if(sz[i] == 2)  break;
        }
        for(int j = tmp.size() - 1; j = 0; -- j)   q.push_front(tmp[j]);
        /*int top = q.front();
        q.pop_front();
        if(find(i) != find(top + n))    un(i, top + n), ans.push_back({i, top});
        else {
            int tpp = q.front();
            q.pop_front();
            q.push_front(top);
            un(i, tpp + n), ans.push_back({i, tpp});
        }*/
    }
    ans.push_back({n, q.front()});  q.pop_front();
    if(q.size())    ans.push_back({n, q.front()});
    sort(ans.begin(), ans.end());
    for(auto it : ans)  cout  it.x  ' '  it.y  '\n';
    return ;
}

1011:思维题
很巧妙的题目,真的感觉比前两题难度大,只能说太离谱


#define int long long
const int maxn = 1e5 + 10, mod =  998244353;
int fa[maxn], d[maxn];
int find(int x) {
    if(x == fa[x])  return x;
    int y = fa[x];
    fa[x] = find(fa[x]);
    d[x] += d[y];
    return fa[x];
}
struct node{
    int x, id;
    node(int x = 0, int id = 0) : x(x), id(id){}
    bool operator  (const node a) const {
        return x  a.x;
    }
}a[maxn];
int un(int x, int y) {
    find(x) != find(y);
    d[fa[x]] = 1;
    fa[fa[x]] = fa[y];
}
//按点权从小到大枚举结点 u,并将u作为所有与u 相连的(已经枚举过的)连通块的根。从而建立一棵新树,每个结点的深度(根的深度为 1)即是答案
vectorint g[maxn];
int b[maxn];
void run() {
    int n; cin  n;
    for(int i = 1, u, v; i  n; ++ i) {
        cin  u  v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i = n; ++ i) {
        cin  b[i];
        a[i] = {b[i], i};
        fa[i] = i;
        d[i] = 0;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i = n; ++ i)
        for(auto it : g[a[i].id])
            if(b[it]  a[i].x)
                un(it, a[i].id);
    for(int i = 1; i = n; ++ i) {
        find(i);
        cout  d[i] + 1  '\n';
        g[i].clear();
    }
    return ;
}
``

本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

2021 CCPC网络赛重赛 相关文章

  1. 2021 CCPC 网络重赛题解

    2021 CCPC 网络重赛题解 1006 大致的题意为 给一个字符串,要求满足下列条件的字串个数: 能够被分为两部分 第一部分为 nunehhe 第二部分为个数大于一个的a的连续字串 思路: 对于每一个位置,分为前缀部分和后缀部分求解,我...

  2. 2020CCPC网络选拔赛:CCPC Training Class

    2020CCPC网络选拔赛:CCPC Training Class Sample Input 5abcdesankaranarayananabbccaabcprogrammingmonotone Sample Output Case #1: 1Case #2: 7Case #3: 3Case #4: 2Case #5: 3 这道题是一个典型的签到题,因为可以在不理解题目的情况下知道,将其AC。 思

  3. 补题 hdu 6440 (ccpc网络赛)

    补题 hdu 6440 (ccpc网络赛) 题意:给出素数p,要求自定义乘法与加法使得对于任意n,m∈[0,p-1],都能满足(m+n) p=m p+n^p。自定义加法是指你自己构造出p*p的矩阵,让第i行第j列表示i+j的自定义值。自定义乘法也构造这样一个矩阵。 ...

  4. 2020 CCPC - 网络赛 1011 3x3 Convolution

    2020 CCPC - 网络赛 1011 3x3 Convolution 3x3 Convolution Problem Description Given annnmatrixAand a33matrixK. These two matrices are very special : they are both non-negative matrices and the sum of all elements in matrixKis 1 (In order to a

  5. 2020CCPC网络赛1005 Lunch (变形Nim博弈)

    2020CCPC网络赛1005 Lunch (变形Nim博弈) 题意:给定你n个巧克力块,每一块巧克力的长度为l[i],两个人轮流操作,每一次操作选择一个当前的长度l的一个大于等于2的因子,然后将这个巧克力分为l/factor(l)块,当所有的巧克力变为1...

  6. 2020CCPC网络选拔赛:Express Mail Taking

    2020CCPC网络选拔赛:Express Mail Taking Output For each test case,Output a single line contains one integer,representing for the minimal walking distance. Sample Input 210 2 56 710 2 53 4 Sample Output 1410 题意:有n个柜子,将m个快递放到n个

  7. HDU6897 Reports(水题)2020CCPC网络选拔赛

    HDU6897 Reports(水题)2020CCPC网络选拔赛 原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=6897 测试样例 Sample Input 4 3 1 1 1 3 1 0 1 5 0 1 0 1 0 4 1 0 1 1 Sample Output NO YES YES NO 题意: 给你某一天的报告,在这一天总共报告nnn次

  8. 2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛 1010 Reports

    2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛 1010 Reports 2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛 1010 Reports(签到题) 如果相邻的任意两个数相同的话,则输出NO,反之输出YES。 #includecstdio#includeiostream#includecstring#inc...

  9. HDU6890 Express Mail Taking(贪心)(2020CCPC网络选拔赛

    HDU6890 Express Mail Taking(贪心)(2020CCPC网络选拔赛) 原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=6890 测试样例 Sample Input 2 10 2 5 6 7 10 2 5 3 4 Sample Output 14 10 题意: 现在有nnn个柜子依次排列,这些柜子编号从1~n。每

  10. 2020中国大学生程序设计竞赛(CCPC)网络选拔赛min25筛

    2020中国大学生程序设计竞赛(CCPC)网络选拔赛min25筛 这次B题ac太多人了,现场时过了快700多人。导致我们队写完签到拼命打表这个题。思路不难,求一次[3,n+1]的连续和,再求[3,n]的素数和。但问题是n太大了,线性筛必定tle,而...

  11. 2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛----HDU--6899

    2020中国大学生程序设计竞赛(CCPC) - 网络选拔赛----HDU--6899、Xor(数位dp) 题目链接 题面: 题意: 求解符合 x∈[0,a],y∈[0,b]x\in[0,a],y\in[0,b]x∈[0,a],y∈[0,b] 且 x?y≤k|x-y|\le kx?y≤k 且 x xory≤wx\ xor\ y \le wxxory≤w 的 (x,y)

  12. 2021年网络维护个人年终总结述职报告及2021年工作规划

    范文大全-www.tqwba.com 报告使用范围很广。按照上级部署或工作计划,每完成一项任务,一般都要向上级写报告,反映工作中的基本情况、工作中取得的经验教训、存在的问题以及今后工作设想。下面是跳墙网为大家带来的2021年...

  13. 2020CCPC威海游记

    2020CCPC威海游记 感谢教练争取的外卡, 感谢教练带我们出去吃两次饭 个人首铜。终于能写一次游记,虽然这次我并没有出去。 从准备环节开始讲吧。 某一天看到出题是南京大学,然后意外翻到南大那个强队的一个人的博客,...

  14. 2020CCPC威海站(部分)

    2020CCPC威海站(部分) 目录 A Golden Spirit 思路: 代码: D ABC Conjecture 思路: 代码: H Message Bomb 思路: 代码: L Clock Master 思路: 代码: A Golden Spirit 思路: 两岸各n个老人,都想去对岸并且休息x分钟。你每次可以带一个老人过桥需...

  15. CCPC2020 长春. H. Combination Lock(二分图博弈 最大流ISAP)

    题目链接

  16. 2019CCPC女生赛总结

    2019CCPC女生赛总结 这大概真的是我最后一场ACM现场赛了吧,每一次参加现场赛后都是难过和遗憾…(文末附上照片) 前几天刚毕业答辩结束,明天就要上班了。昨天来到南京参加CCPC女生赛,今天上午8:30-9:30热身赛,10:30-15:30正...

  17. CCPC2018吉林

    A-a fool 求这个东西: \[\sum_{i=1}^{n}\lfloor{\frac{n}{i}}\rfloor\] 整除分块即可 #includebits/stdc++.husing namespace std;int T,n,cnt;int main(){#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d",T);while(T--){cnt++;scanf("%d"

  18. 2021.2.7网络流习题总结

    2021.2.7网络流习题总结 总是在后一天补前一天的锅,不过没办法,我太菜了,不能像TX他们一样快速AK列表。 1.【模板】最小费用最大流 题目链接: there 由普通的 最大流扩展而来,是网络流、二分图中常用的,方法是将找最大...

  19. CCPC2016长春站打铁记

    CCPC2016长春站打铁记 晚上到的长春。很冷。到了宾馆。放了行李。然后就去吃了点火锅。很好吃。在福建吃的都没有酱。但是回去后有点拉肚子。。几个队友也有同样的反应。路过了吉大。拍了一张照片。哎。压力好大。 来到...

  20. 轻工业大学CCPC竞赛总结回顾

    轻工业大学CCPC竞赛总结回顾 之前参加蓝桥杯省赛侥幸得了个二等奖,比赛后我本来打算开始学习HTML、CSS语言好赶一下我在小组的学习进度,一天上午,李老师找到了我,说:“你想参加咱们省的ACM竞赛吗?”我当时犹豫了一下...

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词