2018-03-10 刷题

1087 All roads 最短路径算法，所有的最短路径，各种回溯

这是我最近写过的最丑的代码，没有之一。太繁琐，变量名都起不过来，只能加注释，顾不上那么多了。发现所有 test case 都过了的时候我简直惊呆了。

在dijkstra最短路算法的基础上，对于路径一样长的情况都要存下来。

然后就可以递归回溯各种可能的路径，寻找happiness最大的或者平均happiness最大的。这里

# include <cstdio>
# include <cstring>

int N, K; //number of cities, number of roads
int dest;
int happy[200];
int cost[200][200];
char name[200][4];

int p[200][200]; //id of the city's parent
int np[200]; //number of parents
int dist[200]; // total cost of coming 
bool status[200]; //if its shortest dist is known

int nRoute = 0; //有多少条路线是最短路
int h, mh; //当前路线的happy, 最优路线的happy
int nNode, mnNode; //当前经历的节点，最优路线的节点数
int route[200], mRoute[200]; //当前路线，最优路线

int id(char *str) {
    for (int i = 0; i < N; i++) {
        if (strcmp(str, name[i]) == 0) {
            return i;
        }
    }
    return -1;
}

void read() {
    scanf("%d %d %s", &N, &K, name[0]); //start point at 0
    for (int i = 1; i < N; i++) {
        scanf("%s %d", name[i], happy + i);
    }
    dest = id("ROM");

    //init the graph
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cost[i][j] = 1 << 30;
        }
        cost[i][i] = 0;
        dist[i] = (1 << 30);
    }

    for (int i = 0; i < K; i++) {
        char a1[4], a2[4];
        int d, ia1, ia2;
        scanf("%s %s %d", a1, a2, &d);
        ia1 = id(a1); ia2 = id(a2);
        cost[ia1][ia2] = (cost[ia2][ia1] = d);
    }
}

void dijk() {
    dist[0] = 0;
    while (1) {
        int m = 0, md = 1 << 30; //m = 最短路径未知的集合里距离最小的点
        for (int i = 0; i < N; i++) {
            if (!status[i] && dist[i] < md) {
                md = dist[i];
                m = i;
            }
        }
        if (m == 0 && status[0]) { //说明所有的点 status 都为真了，所以m才没变
            break;
        }

        status[m] = true; // 最短路已知
        for (int i = 0; i < N; i++) {
            if (!status[i] && cost[m][i] < (1 << 30)) { //有路
                if (cost[m][i] + dist[m] < dist[i]) { //比之前的路更短
                    np[i] = 1;
                    p[i][0] = m;
                    dist[i] = cost[m][i] + dist[m];
                }
                else if (cost[m][i] + dist[m] == dist[i]) { //和之前的路一样短
                    p[i][(np[i] ++)] = m;
                }
            }
        }
    }
}

void backward(int x) {
    route[nNode++] = x;
    h += happy[x];
    if (x == 0) { //回溯到了起点
        nRoute++;
        if (h > mh || (h == mh && (h / (float)nNode) > (mh / (float)mnNode))) { //更好的路线
            mh = h;
            mnNode = nNode;
            memcpy(mRoute, route, sizeof(int) * 200);
        }
    }
    else {
        for (int i = 0; i < np[x]; i++) { //i的每一个祖先
            backward(p[x][i]);
        }
    }
    h -= happy[x];
    nNode--;
}

int main() {
    read();
    dijk();

    backward(dest); 

    printf("%d %d %d %d\n", nRoute, dist[dest], mh, mh / (mnNode - 1));
    for (int i = mnNode - 1; i >= 1; i--) {
        printf("%s->", name[mRoute[i]]);
    }
    printf("%s", name[mRoute[0]]);

    return 0;
}

1086. Tree Traversals Again 中序遍历的逆向，后序遍历

给了一堆做中序遍历时的 push 和 pop 的命令，要求输出后续遍历。

先从操作逆推了一棵树。写中序遍历的时候，对左孩子入栈，一直到没有左孩子为止，然后出栈后找右孩子。因此找到了规律，如果操作是 push，那下一步准备插入的位置就是它的左子树（如果下一步不是 push 就算了）；如果 pop 了一个，那么下一步准备插入的位置是它的右子树。逻辑想了半天，写起来很简单。

恰好节点的 key 都是 1-N的，我就不开树了，直接拿几个数组存下来，免得还得根据 key 查找节点的位置，多麻烦。

最后做一个后序遍历，很简单，过了。

1085. Perfect Sequence

很简单的逻辑，简单到我有点不会做了，卡了半天。

1084. Broken Keyboard

也很简单，按照顺序比对字符就可以了。注意指针怎么向后挪。记一下缺少的键是否输出过了。

1083. List Grades 过于简单

结构体，排个序，输出。本来以为肯定超时，结果case也很弱……

1082 read number in Chinese 复杂逻辑

给出不多于9位的数字，要输出汉语读法。刚开始的思路是每4位读一下，最后结合到一起，结果发现逻辑太复杂了，前面0，后面0，中间两个0，写得很晕。

最终的写法是，先识别不同位置的 0，该跳过还是读一次。标记完 0 之后就很简单了，打表输出。贴代码如下：

# include <cstdio>
# include <cstring>

char digits[10][6] = { "ling ", "yi ", "er ", "san ", "si ", "wu ", "liu ", "qi " , "ba ", "jiu " };
char pos[9][6] = { "", "Qian ", "Bai ", "Shi ", "", "Qian ", "Bai ", "Shi ", "" };
char result[9][20];
char num[11];
int len;

int main() {
    scanf("%s", num);
    if (num[0] == '-') {
        printf("Fu ");
        for (int i = 0; num[i] != '\0'; i++) {
            num[i] = num[i + 1];
        }
    }
    len = strlen(num);

    int i = 0;
    while (num[i] == '0' && i < len) { //刚开始的0要跳过
        num[i] = 's'; //skip
        i++;
    }
    int start = i; //除去0后数字真正开始的地方
    i = len - 1;
    while (num[i] == '0' && i >= 0) { //最后的0也跳过
        num[i] = 's';
        i--;
    }
    i = len - 5;
    while (num[i] == '0' && i >= 0) { //万位及之前相邻的跳过
        num[i] = 's';
        i--;
    }
    i = 0;
    while (i < len) { //其它地方连0都读一个0
        if (num[i] == '0') {
            num[i] = 'r'; //read
            i++;
            while (num[i] == '0' && i < len) {
                num[i] = 's';
                i++;
            }
        }
        i++;
    }

    char read[200] = "";
    for (i = 0; i < len; i++) {
        if (num[i] >= '1' && num[i] <= '9') {
            strcat(read, digits[num[i] - '0']);
            strcat(read, pos[i + 9 - len]);
        }
        else if (num[i] == 'r') {
            strcat(read, digits[0]);
        }
        if (i >= start && i + 9 - len == 0) { //到了亿位
            strcat(read, "Yi ");
        }
        if (i >= start && i + 9 - len == 4) { //到了万位
            strcat(read, "Wan ");
        }
    }
    
    if (strlen(read) == 0) { //输入的是0
        strcpy(read, "ling");
    }
    else {
        read[strlen(read) - 1] = '\0';
    }
    

    printf("%s", read);
    return 0;
}

//Fu yi ba er jiu san Yi si Qian wu Bai liu Shi qi Wan ba Qian jiu Bai
//Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu

1081. Rational Sum 简单

和 1088 的要求很相似，甚至还变简单了。刚开始跑出了浮点错误，后来看论坛发现是 gcd（） 里面没有判断有 0 的情况，有 0 直接返回 1 就可以了。

1079. Total Sales of Supply Chain 超时

题目很简单，一棵树，最后需要一些节点的深度。刚开始我是用 bfs 把所有节点的深度记了一遍，发现超时严重；后来改成需要哪个的深度，就递归往爹娘求，一直求到根节点。结果还是有一个case超时。我把后面需要用的 pow(x, y) 打表了一遍，那个case还是超时。