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

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

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

我相信我可以的。

Fight！！

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

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

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

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

代码如下：

#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，对于描述中child和parent，只需要判断相等，而对于ancestor和descendant的判断，顺着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;
    }
}