2019牛客国庆集训派对day1 K 双向链表练习题

古城微笑少年丶 2023-06-02 15:52 14阅读 0赞

## 题意：[https://ac.nowcoder.com/acm/contest/1099/K][https_ac.nowcoder.com_acm_contest_1099_K] ##

## 分析：要求不断地让一个列表追加到另一个列表中，并反转。但是不停反转是很耗性能的，不停地反转将会导致超时。为了解决这个反转超时问题，我们开两个表，一个正向表，一个反向表。把正向表与反向表的元素对调一下，就相当于反转了。这样就不会超时了。用c++list（双向链表）模拟很方便。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e6+5;
    int n,m,a,b;
    list<int> Z[N],D[N];
    
    int main(){
        while(~scanf("%d%d",&n,&m)) {
            for(int i=1;i<=n;i++) {
                Z[i].clear(),Z[i].push_back(i);
                D[i].clear(),D[i].push_back(i);
            }
            while(m--) {
                scanf("%d%d",&a,&b);
                Z[a].splice(Z[a].end(),Z[b]);
                D[b].splice(D[b].end(),D[a]);
                swap(Z[a],D[b]);
                swap(D[a],D[b]);
                Z[b].clear();
                D[b].clear();
            }
            printf("%d",Z[1].size());
            for(auto it:Z[1])
                printf(" %d",it);
            printf("\n");
        }
    	return 0;
    }

[https_ac.nowcoder.com_acm_contest_1099_K]: https://ac.nowcoder.com/acm/contest/1099/K

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019牛客国庆集训派对day1 C Distinct Substrings

题意：[https://ac.nowcoder.com/acm/contest/1099/C][https_ac.nowcoder.com_acm_contest_1099_

亦凉/ 2023年06月02日 15:56/ 0 赞/ 14 阅读

相关 2019牛客国庆集训派对day1 K 双向链表练习题

题意：[https://ac.nowcoder.com/acm/contest/1099/K][https_ac.nowcoder.com_acm_contest_1099_

古城微笑少年丶/ 2023年06月02日 15:52/ 0 赞/ 15 阅读

相关 2019牛客国庆集训派对day1（A, B E F K）

链接：[https://ac.nowcoder.com/acm/contest/1099\question][https_ac.nowcoder.com_acm_contest

客官°小女子只卖身不卖艺/ 2023年06月01日 11:15/ 0 赞/ 75 阅读

相关牛客国庆集训派对Day4H 树链博弈

题目：[点击打开链接][Link 1] 题意：开始题意没弄明白，必须选一个节点变白，然后再选择祖先或者重新选择其他一个节点变白。分析：结论是如果树的所有层的黑点

爱被打了一巴掌/ 2022年05月09日 10:12/ 0 赞/ 231 阅读

相关牛客国庆集训派对Day3 B Tree

题目：[点击打开链接][Link 1] 题意：略。分析：树形dp（树上dfs），两遍dfs，一遍求下面（儿子）的贡献，一遍求他父亲节点的贡献，两部分相乘得结果，

野性酷女/ 2022年05月09日 10:06/ 0 赞/ 224 阅读

相关牛客国庆集训派对Day3 A Knight

题目：[点击打开链接][Link 1] 题意：略。分析：规律题，打了表半天没找出规律。。。网友思路：如果目的点不在第一象限，将其转化到第一象限，

￡神魔★判官ぃ/ 2022年05月09日 08:28/ 0 赞/ 228 阅读

相关牛客国庆集训派对Day3 J Graph Coloring I

题目：[点击打开链接][Link 1] 题意：判断一个图是否能用两种颜色染色，满足相邻点的颜色不同。分析：可以直接对图进行染色，如果发现当前点的颜色与已经染色的

骑猪看日落/ 2022年05月09日 07:14/ 0 赞/ 220 阅读

相关牛客国庆集训派对Day1 L New Game!——————建图+

链接：[https://www.nowcoder.com/acm/contest/201/L][https_www.nowcoder.com_acm_contest_201_L

比眉伴天荒/ 2022年05月09日 05:18/ 0 赞/ 238 阅读

相关牛客国庆集训派对Day3 I Metropolis

题目：[点击打开链接][Link 1] 题意：略。分析：多源点最短路，只要两个不同源点的最短路相遇，我们就更新两个源点的答案。代码： pragm

谁践踏了优雅/ 2022年05月08日 11:52/ 0 赞/ 246 阅读

相关牛客国庆集训派对Day6 J-最短路

题目：[点击打开链接][Link 1] 题意：略。分析：（lca+100次最短路）先把题目给的边存起来，先取n-1个边（不能有环）构成生成树，然后求lca，对于漏掉

悠悠/ 2022年05月05日 13:57/ 0 赞/ 229 阅读