ABC 293 ABCD(并查集)

A - Swap Odd and Even

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-1e18;
const LL N=1e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        for(int i=0;i<s.size();i+=2)
        {
            cout<<s[i+1]<<s[i];
        }
    }
    return 0;
}

B - Call the ID Number

难在读题，题目读懂了就没问题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-1e18;
const LL N=1e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],sum[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        map<LL,LL> mp;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(mp[i]!=0) continue;
            else if(mp[i]==0&&mp[a[i]]==0) mp[a[i]]++;
        }
        vector<LL> v;
        for(int i=1;i<=n;i++)
        {
            if(mp[i]==0) //cout<<i<<" ";
                v.push_back(i);
        }
        cout<<v.size()<<endl;
        for(int i=0;i<v.size();i++)
            cout<<v[i]<<" ";
        cout<<endl;
    }
    return 0;
}

C - Make Takahashi Happy

直接爆搜

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-1e18;
const LL N=1e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL n,m,a[M][M];
LL sum=0;
LL dx[]={-1,0,0,1},dy[]={0,1,-1,0};
vector<LL> v;
map<LL,LL> mp;
void dfs(LL x,LL y)
{
    if(x==n&&y==m)
    {
        bool flag=true;
        mp.clear();
        for(int i=0;i<v.size();i++)
        {
            mp[v[i]]++;
            if(mp[v[i]]>=2)
            {
                flag=false;
                break;
            }
        }
        if(flag==true) sum++;
        return ;
    }
    if(x+1<=n)
    {
        v.push_back(a[x+1][y]);
        dfs(x+1,y);
        v.pop_back();
    }
    if(y+1<=m)
    {
        v.push_back(a[x][y+1]);
        dfs(x,y+1);
        v.pop_back();
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }
        v.push_back(a[1][1]);
        dfs(1,1);
        cout<<sum<<endl;
    }
    return 0;
}

D - Tying Rope

https://atcoder.jp/contests/abc293/tasks/abc293_d

题目大意:

N根绳子从1到N。每根绳子的一端被涂成红色，另一端被涂成蓝色。

M次系绳子的操作。

在第i个操作中，绳子A的某个颜色的一端和绳子B的某个颜色的一端相连。（对于每根绳子，颜色相同的一端不会被系多次）

在所有运算之后，找出形成循环的相连绳子的组数，以及不形成循环的绳子的组数。

Sample Input 1  
5 3
3 R 5 B
5 R 3 B
4 R 2 B
Sample Output 1  
1 2

我自己的写法没有加上sz，卡了两天（傻狗爆哭

学一下佬儿的做法，一下子过了hh（：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-1e18;
const LL N=1e6+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL n,m;
LL a[N],c[N];
char b[N],d[N];
LL father[N],sz[N];
LL find(LL x)
{
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i]>>b[i]>>c[i]>>d[i];
        }
        for(int i=1;i<=n;i++)
        {
            father[i]=i;
            sz[i]=1;
        }
        for(int i=1;i<=m;i++)
        {
            if(a[i]>c[i]) swap(a[i],c[i]),swap(b[i],d[i]);
            LL fai=find(a[i]);
            LL fci=find(c[i]);
            if(fai==fci) ;
            else
            {
                //从前往后
                sz[fai]+=sz[fci];
                father[fci]=fai;
            }
        }
        map<LL,LL> mp;
        for(int i=1;i<=m;i++)//m条边中最早的那根线的位置在哪里
        {
            LL fai=find(a[i]);
            mp[fai]++;//标注位置
        }
        LL sum1=0,sum2=0;
        for(int i=1;i<=n;i++)
        {
            if(find(i)==i)//根节点
            {
                //如果以它为根节点的数量和我们直接添加边长数量是一样的
                if(mp[i]==sz[find(i)]) sum1++;//环++
                else sum2++;
            }
        }
        cout<<sum1<<" "<<sum2<<endl;
    }
    return 0;
}