SDUT 2018 暑期集训之大一鲤鱼跳龙门周赛(4)部分题解

k.Find them, Catch them

题目链接:https://cn.vjudge.net/problem/POJ-1703
并查集,想了很久,本来想开两个并查集,将敌人放在一个并查集里,朋友放在一个并查集里,但是,敌人的敌人是朋友,然而敌人的敌人的敌人又是敌人了,这样敌人这个并查集里的关系并不能确定,后来看了ZYL的代码才想到,只要先用朋友的并查集来判断是不是朋友,不是朋友再判断是不是敌人就可以将敌人并查集里的那部分并不是敌人的避规过去了,实在是巧妙。
代码


#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int prea[100010],preb[100010],f[100010];

int finda(int a)
{
    if(a!=prea[a])
    {
        prea[a]=finda(prea[a]);
    }
    return prea[a];
}

int findb(int a)
{
    if(a!=preb[a])
    {
        preb[a]=findb(preb[a]);
    }
    return preb[a];
}

void zhana(int a,int b)
{
    if(finda(a)!=finda(b))
    {
        prea[finda(a)]=finda(b);
    }
}

void zhanb(int a,int b)
{
    if(findb(a)!=findb(b))
    {
        preb[findb(a)]=findb(b);
    }
}

int main()
{
    //ios::sync_with_stdio(false);
    int T;
    cin>>T;
    int n,m;
    char c;
    int u,v;
    while(T--)
    {
        memset(f,0,sizeof(f));
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            prea[i]=i;
            preb[i]=i;
        }
        for(int i=0;i<m;i++)
        {
            getchar();
            scanf("%c%d%d",&c,&u,&v);
            if(c=='D')
            {
                if(f[u]!=0)
                {
                    zhana(v,f[u]);
                }
                if(f[v]!=0)
                {
                    zhana(u,f[v]);
                }
                f[u]=v;
                f[v]=u;
                zhanb(u,v);
            }
            if(c=='A')
            {
                if(finda(u)==finda(v))
                {
                    printf("In the same gang.\n");
                }
                else if(findb(u)==findb(v))
                {
                    printf("In different gangs.\n");
                }
                else printf("Not sure yet.\n");
            }
        }
    }
    return 0;
}

G.罐子和硬币

题目链接:https://cn.vjudge.net/problem/51Nod-1246
思维题
比赛时没想明白他是要怎么取,也就没弄明白怎么放
这个题要将放了物品的罐子都平均,其余都留空才是最少的,比如说 5 12 12 这个如果是平均分配的话,就是 2 2 2 3 3,那么最坏情况的最少询问是15次,但是我们可以分配0 3 3 3 3 ,那么最少的询问就是13次了
代码

#include <iostream>

using namespace std;

int main()
{
    int n,k,c;
    cin>>n>>k>>c;
    int ans=k/n*n;//先向下取整再乘上去,得到的结果就是平均分的情况下所有罐子里的总和
    if(ans>=c)cout<<c<<endl;//平均分的状态下总数大于要取的,直接取
    else
    {
        cout<<n-k/(k/n+1)+c<<endl;//*1
    }
    return 0;
}
/*
*1 :
5 18 18
5-(18/((18/5)+1))
    意思就是说每个罐子平均放三个 然后加一就是说  如果每个罐子放四个
那么只需要四个罐子   这样子有一个空的   最坏情况下先摸到一个空的 
*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注