Codeforces Gym-102219 2019 ICPC Malaysia National J. Kitchen Plates (暴力,拓扑排序)

Codeforces Gym-102219 2019 ICPC Malaysia National J. Kitchen Plates (暴力,拓扑排序)

  • 题意:给你5个\(A,B,C,D,E\)大小关系式,升序输出它们,如果所给的大小矛盾,输出\(impossible\).

  • 题意:当时第一眼想到的就是连边然后排序,很明显是拓扑排序(然而我不会qwq,之后再补),但貌似可以直接暴力来写,用二维数组来记录两个数之间的大小关系,如果一维\(>\)二维就记录true,然后我们要对题目所给的关系进行合并,将所有大小关系弄清楚,三个for就可以搞定了,之后判断一下是否有矛盾存在,最后再统计一下大小然后再按顺序输出即可(这题的输出其实没怎么看懂,之前写的桶排输出不知道为什么不给过qaq).

  • 代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <unordered_set>
    #include <unordered_map>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<long,long> PLL;
     
    string s;
    int v[100][100];
    int cnt[N];
    map<int,int> mp;
    vector<int> rest;
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);
        for(int i=1;i<=5;++i){
            cin>>s;
            //初始化记录
             for(int j=0;j<s.size();++j){
                 if(s[1]=='>') v[s[0]-'A'][s[2]-'A']=1;
                 else v[s[2]-'A'][s[0]-'A']=1;
             }
        }
        //合并
        for(int k=0;k<5;++k){
            for(int i=0;i<5;++i){
                for(int j=0;j<5;++j){
                    if(v[i][k] && v[k][j]) v[i][j]=1;
                }
            }
        }
     
        for(int i=0;i<5;++i){
            for(int j=0;j<5;++j){
                if(v[i][j] && v[j][i]){
                    puts("impossible");
                    return 0;
                }
            }
        }
        //统计大小
        for(int i=0;i<5;++i){
            for(int j=0;j<5;++j){
                if(v[i][j]) cnt[i]++;
            }
        }
        for(int len=0;len<5;++len){
            for(int num=0;num<5;++num){
                if(cnt[num]==len) printf("%c",num+'A');
            }
        }
     
        return 0;
    }
    
上一篇:华为杯中国地质大学(武汉)第十七届ICPC程序设计大赛暨华中地区部分高校第十五届ICPC邀请赛


下一篇:00 后程序员征战国际,如何拿下计算机领域的奥林匹克?