AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 4278. 峰会 比较干净的写法    原题链接    简单

作者: 作者的头像   废物宝宝 ,  2022-06-22 08:54:16 ,  所有人可见 ,  阅读 32


1


暴力

#include<iostream>
#include<unordered_set>
using namespace std;
const int N=205;

int n,m,t;
int g[N][N];

int check(){//-1 不是相互伙伴 0表示合理 否则就是可以再加入的序号
    int l,a[N];//a用来记录当前的安排有哪些人
    cin>>l;
    unordered_set<int>s;//当前安排有哪些人 方便下文找
    for(int i=1;i<=l;i++)cin>>a[i],s.insert(a[i]);

    for(int i=1;i<l;i++)//是否相互是朋友
        for(int j=i+1;j<=l;j++)
            if(!g[a[i]][a[j]])
                return -1;//只有有两个人不是朋友直接gg

    for(int i=1;i<=n;i++)//尝试每一个加这个小安排中
        if(!s.count(i)){//不在安排中
            bool f=true;
            for(auto k:s)//和安排中的每个人试一试看看是不是朋友
                if(!g[i][k])
                    f=false;//只要是有一个人和他不是朋友 他就加不进去 
            if(f)return i;//最终和所有人都是朋友 则这个人可以加入
        }
    return 0;//就挺好没有多余的人
}
int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }
    cin>>t;
    for(int i=1;i<=t;i++){
        int ans=check();
        if(~ans){
            if(ans)
                printf("Area %d may invite more people, such as %d.\n",i,ans);
            else
                printf("Area %d is OK.\n",i);
        }else
            printf("Area %d needs help.\n",i);
    }
    return 0;
}

纯享版

#include<iostream>
#include<unordered_set>
using namespace std;
const int N=205;

int n,m,t;
int g[N][N];

int check(){
    int l,a[N];
    cin>>l;
    unordered_set<int>s;
    for(int i=1;i<=l;i++)cin>>a[i],s.insert(a[i]);

    for(int i=1;i<l;i++)
        for(int j=i+1;j<=l;j++)
            if(!g[a[i]][a[j]])
                return -1;

    for(int i=1;i<=n;i++)
        if(!s.count(i)){
            bool f=true;
            for(auto k:s)
                if(!g[i][k])
                    f=false; 
            if(f)return i;
        }
    return 0;
}
int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }
    cin>>t;
    for(int i=1;i<=t;i++){
        int ans=check();
        if(~ans){
            if(ans)
                printf("Area %d may invite more people, such as %d.\n",i,ans);
            else
                printf("Area %d is OK.\n",i);
        }else
            printf("Area %d needs help.\n",i);
    }
    return 0;
}

0 评论

你确定删除吗?

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息