Life of xhu

赶紧刷题 & HOJ_1492 & HOJ_1504

Apr 06, 2014  |  日常  |  HOJ  |  Algorithm

现在是找工作+毕设+《RailsTutorial》三管齐下,非常充实啊有木有。

唯一有点蛋疼的是工作还没找到,现在已经是4月份了,一份保底的Offer都没有,说实话,还是有点担心的。

不过担心归担心,眼下能做的,只有多看点书,多学一点实用的东西,趁双休日赶紧刷几道题练一下基础知识,在面试时不要卡壳就好。

我相信我可以的。

Fight!!

~~我是萌萌的昏割线~~~

1492:题意是某一个城镇里的房子由若干条路线连起来,其中有些房子的连接处是坏的,如果一条路线上有一个房子是坏的,那么这条路线就不能通电,并且只要一个房子在一条可以通电的路线上,这个房子就是可以通电的,然后给出所有的路线和坏掉的房子,求无法通电的房子数量。

知道题意后,这道题就简单了,先建一个bool数组,哪个房子是坏的,就把对应下表的数组元素置为true。然后遍历一条路线,如果有任意一个房子在数组中对应为true,则不进入下一次遍历。然后进入第二次遍历,对于路线中每一个房子,只要还没有计算过(这里还是通过bool数组实现),就对计数器加一。最后输出房子总数和计数器的差即可。

其实上面的两次遍历完全可以用一次遍历来做的,不过这样的话需要的标记变量太多,写起来还麻烦,干脆就写两次好了,在10^4int这个数量级上,耗时其实相差很小。

代码如下:

#include <iostream>
#include <iostream>
#include <memory>
using namespace std;

typedef struct Path{
    int length, node[10100];
}Path;

int main(){
    int N, M, K, tmp, count, case_count = 0;
    bool flood[10100], power[10100], bad;
    while(cin >> N >> M >> K && !(N == -1 && M == -1 && K == -1)){
        Path p[60];
        memset(flood, false, sizeof(flood));
        memset(power, false, sizeof(power));
        count = 0;
        if(case_count++)
            cin >> N >> M >> K;   //因为每次一组数据前面都输入了一个0 0 0,所以这里重新输入一次,才是实际数据
        for(int i = 0; i < M; i++){
            cin >> p[i].length;
            for(int j = 0; j < p[i].length; j++)
                cin >> p[i].node[j];
        }
        for(int i = 0; i < K; i++){
            cin >> tmp;
            flood[tmp] = true;
        }
        for(int i = 0; i < M; i++){
            bad = false;
            for(int j = 0; j < p[i].length; j++){
                if(flood[p[i].node[j]]){
                    bad = true;
                    break;
                }
            }
            if(!bad){
                for(int j = 0; j < p[i].length; j++){
                    if(!power[p[i].node[j]]){
                        power[p[i].node[j]] = true;
                        count++;
                    }
                }
            }

        cout << N - count << endl;
    }
}

1504:题意就是给出一个用缩进表示的家谱,然后给出关于这个家谱的描述,判断对错。

题意倒是不难理解,缩进的层数用getline输入后数空格个数即可,都是一些基本的字符串处理函数,这些都很简单。

我觉得这题的关键是需要找出每个人的parent,因为后代数不一定,但是parent只有一个,确定了每个人的parent,对于描述中childparent,只需要判断相等,而对于ancestordescendant的判断,顺着parent的关系一层一层往上找即可。

说一下我的做法吧,关于parent关系的处理,我用的是的方式,建立一个栈,里面包含的元素有名字和层数,然后针对每一个输入的名字和缩进的层数,作如下处理:

  • 如果栈为空,将名字和层数压栈,并置输入的名字的parent""

  • 如果栈顶的层数小于输入的层数,则置输入的名字的parent为栈顶的名字,并压栈;

  • 如果栈顶的层数大于或等于输入的层数,则对栈进行弹出,直到栈顶的层数小于输入的层数,然后置输入的名字的parent为栈顶的名字,并压栈。

关于parent和层数的关系,我并不是用数组存储,而是使用map的方式,这样在后续的处理中,查询一个名字的parent和层数的时间复杂度都是O(1)

代码如下:

#include <iostream>
#include <string>
#include <map>
using namespace std;
string name[1100];
map<string, string> parent;
map<string, int> floor;

typedef struct Stack{
    string name[1100];
    int floor[1100];
    int top;
}Stack;

int getFloor(string s){
    int i = 0;
    while(s[i] == ' ')
        i++;
    return i;
}

void push(Stack &s, string str){
    s.name[s.top] = str;
    s.floor[s.top] = floor[str];
    s.top++;
}

void pop(Stack &s){
    s.top--;
}

string getName(string s, int i, int j){
    string res;
    char des[100];
    int k = 0;
    for(;i <= j; i++, k++)
        des[k] = s[i];
    des[k] = '\0';
    res = des;
    return res;
}

string getFirstName(string s){
    int i = 0;
    while(s[i] != ' ')
        i++;
    return getName(s, 0, i - 1);
}

string getLastName(string s){
    int i = s.length() - 1;
    while(s[i] != ' ')
        i--;
    return getName(s, i + 1, s.length() - 2);
}

char getSymbol(string s){
    int i, j;
    for(i = 0, j = 0; i < s.length(); i++){
        if(s[i] == ' ')
            j++;
        if(j == 3)
            break;
    }
    return s[i + 1];
}

int main(){
    int n, m, f_tmp;
    string input, n_tmp, name1, name2;
    Stack s;
    bool res;
    while(cin >> n >> m && !(n == 0 && m == 0)){
        s.top = 0;
        for(int i = 0; i <= n; i++){
            getline(cin, input);
            f_tmp = getFloor(input);
            name[i] = getName(input, f_tmp, input.length() - 1);
            floor[name[i]] = f_tmp;
            if(i != 0){
                if(s.top != 0){
                    while(s.floor[s.top - 1] >= floor[name[i]])
                        pop(s);
                    parent[name[i]] = s.name[s.top - 1];
                }else
                    parent[name[i]] = "";
                push(s, name[i]);
            }
        }
        //for(int i = 1; i <= n; i++)
        //    cout << floor[name[i]] << '=' << name[i] << '=' << parent[name[i]] << endl;
        for(int i = 0; i < m; i++){
            getline(cin, input);
            name1 = getFirstName(input);
            name2 = getLastName(input);
            res = false;
            switch(getSymbol(input)){
                case 'c':
                    if(parent[name1] == name2)
                        res = true;
                    break;
                case 'p':
                    if(parent[name2] == name1)
                        res = true;
                    break;
                case 's':
                    if(parent[name1] == parent[name2])
                        res = true;
                    break;
                case 'a':
                    while(parent[name2] != ""){
                        if(parent[name2] == name1){
                            res = true;
                            break;
                        }
                        name2 = parent[name2];
                    }
                    break;
                case 'd':
                    while(parent[name1] != ""){
                        if(parent[name1] == name2){
                            res = true;
                            break;
                        }
                        name1 = parent[name1];
                    }
                    break;
            }
            if(res)
                cout << "True" << endl;
            else
                cout << "False" << endl;
        }
        cout << endl;
    }
}

Copyright © 2018 - xhu - Powered by Gin,jQuery,Animate.css,Semantic UI