Contents

拓扑排序以及C++读取空行[算法学习日常1/100]

算法学习日常第一天

2019年8月2日

  • 今天上午,重新认识算法的全貌各种资源及知识点总结

  • 并且还了解到了常见错误写法,当然自己当年也写过很多错误

  • 下午先是补牛客5的多校G题的dp–接着昨天的补都补了90mins(含对着手写第一遍),还是太菜了

  • 然后补H题,发现自己昨天写了3个小时的这个题目不是字符串插入题…而是一个拓扑排序题..真的自己菜得可怕..写错分类怎么可能做对,然后自己又焦虑了很久,知道2019年8月2日15:48:15才静下来认真地学习拓扑排序

    • 拓扑排序在紫书上学了下,就是把点对关系看成一个图里面的指向关系,即把每一个点对看做小数指向大数的有向边,如果图没有有向环的话,说明是可以的,否则是不行的
    • 记自己头铁处理空行读入,搞了整整一个小时读取空行

拓扑排序以及空行头铁见代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
/*
2019年8月2日19:25:05
拓扑排序bfs

拓扑排序算法思想
1、在AOV网络中选一个没有直接前驱的顶点, 并输出之;
2、从图中删去该顶点, 同时删去所有它发出的有向边;--->(我下面的题目使用stop实现删除)
3、重复以上步骤, 直到
◆ 全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;
◆ 或者图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶点,
它们都有直接前驱,再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
*/
#include<bits/stdc++.h>
using namespace std;
const int M = 1e4+5;
int n,m,lentmp;
string s[10][10];
/*用string本来可以不用下面的len*/
int len[10][10];
int it[10][10];
string ans,t;
bool check();
bool solve();

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<m*(m-1)/2;i++){
        cin>>t>>lentmp;
        int x=t[0]-'a',y=t[1]-'a';
        if(x>y) swap(x,y);
        len[x][y] = lentmp;
        // if(lentmp) cin>>s[x][y];
        /*我的头铁(~~比赛因此卡1小时去谷歌~~)写法
        先直接用cin.get()吃掉t和lentmp后面的回车
        再getline(),
        否则getline会吃那个回车而导致少读数据*/
        cin.get();
        getline(cin,s[x][y]);
    }
    if(!solve()) puts("-1");

    return 0;
}

/*暴力检测每队关系是否和整个串中的样子是一样的
法二: 也可以每一对关系得到一个ans的tmp串,然后再去==判断
      但是效率低
*/
bool check(){
    for(int i=0;i<m;i++){
        for(int j=i+1;j<m;j++){
            int now = 0;
            for(int k=0;k<n;k++){
                if(ans[k]=='a'+i||ans[k]=='a'+j){
                    if(ans[k]!=s[i][j][now]) return 0;
                    now++;
                }
            }
            if(now!=len[i][j]) return 0;
        }
    }
    return 1;
}

bool solve(){
    for(int i=0;i<n;i++){
        /* 这里是每个大串的排序关系-通过m次的关系问询确定的

        注意前面巧妙地处理出了j小于k--->这就是拓扑排序的思路

        1.对没有出现过的关系(即s[j][k]的那一维全为空)stop[j]和stop[k]全都赋值为1
        2.对于到最后了的关系(即s[j][k][]='\0')全赋空


        因为有m*(m-1)/2 对 关系,也就是每两个都有比较,所以一定能够得出最前面的一个字符..所以就完美了!

        这里每次stop都会清零!*/
        bool stop[10] = {};
        for(int j=0;j<m;j++){
            for(int k=j+1;k<m;k++){
                if(!s[j][k][it[j][k]]) stop[j]=stop[k]=1;
                else if(s[j][k][it[j][k]]=='a'+j) stop[k]=1;
                else stop[j] = 1;
            }
        }
        bool done = false;
        for(int j=0;j<m;j++){
            if(!stop[j]){
                ans+='a'+j;
                for(int k=0;k<m;k++){
                    if(k<j) it[k][j]++;
                    else if(k>j) it[j][k]++;
                }
                done = true;
                break;
            }
        }
        if(!done) return 0;
    }
    if(!check()) return 0;
    cout<<ans<<endl;
    return 1;
}
  • 晚上成功补完H题和I题,发现好像没有时间补B题了,明天上午来补一下B题

每日一句叨叨

杜月笙知道成功需要代价,他想为自己洗白(小时候家里穷只能混黑帮),为整个帮派洗白,但穿了大半辈子长褂(为了不露出纹身),让自己的说书先生给自己讲了大半辈子学,也为上海的繁荣安定做了大半辈子贡献,但却最终未被认可(通过人脉被选之为一个参议长,但蒋介石让他自己退位),但杜月笙却永远被后人被历史铭记

若命运不公,那就和它斗到底!