The Preliminary Contest for ICPC Asia Xuzhou 2019 徐州网络赛 B so easy

风骨散人Chiam

发布于 2020-10-28 10:15:53

3290

发布于 2020-10-28 10:15:53

文章被收录于专栏：CSDN旧文

题目链接：https://nanti.jisuanke.com/t/41384

这题暴力能过，我用的是并查集的思想，这个题的数据是为暴力设置的，所以暴力挺快的，但是当他转移的点多了之后，我觉得还是我这种方法更好一点。注意这里一定要用内部是hash的unordered_map 做，因为查询为o(1)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <cmath>
#include <map>
#define N 100010
using namespace std;
typedef long long ll;
unordered_map<int,int>fa;
int n,q;
int get(int x)
{
    if(fa.count(x)==0) return x;
    fa[x]=get(fa[x]);
}
int main()
{
    scanf("%d%d",&n,&q);
    //  for(int i=1;i<=n+1;i++)fa[i]=i;
    int a,b;
    while(q--)
    {
        scanf("%d%d",&a,&b);
        if(a==1)
            fa.insert(make_pair(b,b+1));
        else
        {
            printf("%d\n",get(b));
        }
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/07 ，如有侵权请联系 cloudcommunity@tencent.com 删除

hash