comehome：赤裸裸的最短路径

出口都给了，求每个点的最短路径，之中再选最短的即可。

数据量很小，只有 52 个点。

我用了好写的 spfa， 调了一点就跑通了。看题解推荐的是更加好写的 floyd 算法，毕竟数据量太小了，节省一点 code 时间还是不错的。

这道题还有一点交代：可能有 x -> x 的路（没有用，我在输入的时候就排除掉了），可能两点有不止一条路（有用的一定是更短的，同样在输入的时候检查掉了），都没什么要考虑的。

最近我写的宏定义越来越多了……不得不说这玩意挺方便的。

AC 代码：

#include <cstdio>
#define N 52
#define Inf (1 << 30)
#define isCap(c) ((c) >= 'A' && (c) <= 'Z')
//52个字母的顺序是，a-z,A-Z
#define idx(c) (isCap(c)? ((c) - 'A' + 26): ((c) - 'a'))
#define chr(n) (char('A' + (n) - 26))

int map[N][N];
int dist[N];

void spfa(){
    bool inq[N] = {0};
    int queue[N * N], end = 1, start = 0;

    dist[idx('Z')] = 0;
    queue[0] = idx('Z');
    inq[idx('Z')] = true;

    int x;
    while(end > start){
        x = queue[start ++]; //出队
        for(int i = 0; i < N; i ++){
            if(i != x && map[i][x] != Inf){ //邻居
                if(dist[x] + map[x][i] < dist[i]){ //更短
                    dist[i] = dist[x] + map[x][i];
                    queue[end ++] = i;
                }
            }
        }
    }
}

int main(){
    FILE *fin = fopen("comehome.in", "r");
    FILE *fout = fopen("comehome.out", "w");

    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j ++){
            map[i][j] = Inf;
        }
        map[i][i] = 0;
        dist[i] = Inf;
    }

    int nRoad, d;
    char from, to;
    fscanf(fin, "%d\n", &nRoad);
    for(int i = 0; i < nRoad; i ++){
        fscanf(fin, "%c %c %d \n", &from, &to, &d);
        if(d < map[idx(from)][idx(to)]){
            map[idx(from)][idx(to)] = d;
            map[idx(to)][idx(from)] = d;
        }
    }

    spfa();

    int quickest = 26, minDist = Inf;
    for(int i = 26; i < N - 1; i ++){
        if(dist[i] < minDist){
            minDist = dist[i];
            quickest = i;
        }
    }

    fprintf(fout, "%c %d\n", chr(quickest), minDist);

    return 0;
}

速度：

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4184 KB]
   Test 2: TEST OK [0.000 secs, 4184 KB]
   Test 3: TEST OK [0.000 secs, 4184 KB]
   Test 4: TEST OK [0.000 secs, 4184 KB]
   Test 5: TEST OK [0.000 secs, 4184 KB]
   Test 6: TEST OK [0.000 secs, 4184 KB]
   Test 7: TEST OK [0.000 secs, 4184 KB]
   Test 8: TEST OK [0.000 secs, 4184 KB]
   Test 9: TEST OK [0.000 secs, 4184 KB]

All tests OK.
YOUR PROGRAM ('comehome') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

fracdec：好像是玩字符串？

在第 8 个点就超时的代码：

#include <cstdio>
#define N 200010

//整数的位数
int intLen(int n){
    int counter = 0;
    do{
        n /= 10;
        counter ++;
    }while(n != 0);
    return counter;
}

//找到循环节 T[start: end)
void findLoop(char T[], int len, int &start, int &end){
    bool flag = false;
    int k;
    for(end = 1; end < len && !flag; end ++){
        for(start = 0; start < end && !flag; start ++){
            for(k = 0; start + k < end; k ++){
                if(T[start + k] != T[end + k]) break;
            }
            if(start + k == end){
                int tStart, tEnd;
                for(tStart = start, tEnd = end; tEnd < len; tEnd ++, tStart ++){
                    if(T[tStart] != T[tEnd]) break;
                }
                if(tEnd == len) flag = true;
            }
        }
    }
    start --; end --;
}

//格式化输出带循环的小数部分
void printLoopDecimal(FILE *fout, char T[], int start, int end, int count){
    for(int i = 0; i < start; i ++, count ++){
        if(count == 76) {fprintf(fout, "\n"); count = 0;}
        fprintf(fout, "%c", T[i]);
    }

    if(count == 76) {fprintf(fout, "\n"); count = 0;}
    fprintf(fout, "("); count ++;

    for(int i = start; i < end; i ++, count ++){
        if(count == 76) {fprintf(fout, "\n"); count = 0;}
        fprintf(fout, "%c", T[i]);
    }

    if(count == 76) {fprintf(fout, "\n"); count = 0;}
    fprintf(fout, ")\n");
}

int main(){
    FILE *fin = fopen("fracdec.in", "r");
    FILE *fout = fopen("fracdec.out", "w");

    int n, d, integer, len = 0; //分子，分母，整数部分，小数长度
    char decimal[N]; //小数部分
    int count; //记录输出字符数

    fscanf(fin, "%d %d", &n, &d);
    integer = n / d; //分离整数部分
    count = intLen(integer);//计算整数部分位数
    
    n = n % d; //留下的产生小数部分
    while(len < N){ //做除法，直至除尽或者除了N位
        decimal[len ++] = (n * 10 / d) + '0';
        n = (n * 10) % d;
        if(n == 0) break;
    }
    fprintf(fout, "%d.", integer);
    count ++;

    
    if(n == 0){ //是个有限小数
        for(int i = 0; i < len; i ++, count ++){
            if(count == 76) {fprintf(fout, "\n"); count = 0;}
            fprintf(fout, "%c", decimal[i]);
        }
        fprintf(fout, "\n");
    }else{ //是个无限循环小数，寻找循环节
        int start, end;
        findLoop(decimal, N, start, end);
        printLoopDecimal(fout, decimal, start, end, count);
        
        // 用于检查
        // fprintf(fout, "%d %d\n", start, end);
        // for(int i = 0; i < 100; i ++){
        //     fprintf(fout, "%c", decimal[i]);
        // }
    }

    return 0;   
}

其中寻找循环节的函数findLoop(char, int, int&, int&)用的是最最暴力的算法，明显需要改进。

最后的最后我求助 KMP 算法了。滚回去又学了一遍，见今日完成的另一篇文章。整体思路是，用 KMP 的一些东西改进findLoop函数。我惊喜地发现用求 next 数组的方法来做时，循环部分的值会不断增加。于是，这个函数被改成这样：

oid reverse(char *s, int len){
    char t;
    int i;
    for(i = 0; i < len - 1 - i; i ++){
        t = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = t;
    }
}

//kmp中的next数组
void buildNext(char *P, int m, int* next){ 
    next[0] = -1;
    int j = 0, t = -1;
    while(j < m){
        if(t < 0 || P[j] == P[t]){
            j ++, t ++;
            next[j] = t;     
        }else{
            t = next[t];
        }
    }
}

//找到循环节 T[start: end)
void findLoop(char T[], int len, int &start, int &end){
    int next[len + 1], lenLoop = 0;
    reverse(T, len);
    buildNext(T, len, next);
    int maxIdx = 0;
    for(int i = 1; i < len + 1; i ++){ //找到next[i]的最大值
        if(next[i] > next[maxIdx]) maxIdx = i;
    }
    lenLoop = maxIdx - next[maxIdx];
    start = len - maxIdx;
    
    reverse(T, len);

    end = start + lenLoop;
    // for(int i = 0; i <= len; i ++){
    //     fprintf(fout, "[%d] = %d\t", i, next[i]);
    // }
}

我基本是用观察的方法猜出来的。对于

小数部分  2 5 8 1 8 1 8 1 8
秩       0 1 2 3 4 5 6 7 8
前后倒置  8 1 8 1 8 1 8 2 5
next数组 -1 0 0 1 2 3 4 5 0

这个数组倒过来，肯定是直接开始循环的，但是由于有两个 0，next数组的值相比于秩，被耽误了 2 下，以至于循环里面每一个秩-next都等于循环节长度 2。

我原来想从前往后，发现 next 大于 0 的时候就用i - next[i]作为循环节长度，结果出了问题，因为循环节内部可能仍有重复的数字序列，比如一个循环节反过来是8123245，很快就会出现非零的 next 值。又想了其它方法，总有漏洞，其中一个甚至通过了所有数据的测试。

最后，我由于取得小数位数足够长，直接寻找next[i]的最大值位置了。这个位置，正是循环节消失的地方，i - next[i]是循环节长度，后面留下的小尾巴也就是非循环节的部分了。

结果快得吓人，尽管我小数部分取了那么多位，而且非常暴力地把小数部分前后倒置。线性时间比起稍微有点平方，果然是不知道高到哪里去了。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4248 KB]
   Test 2: TEST OK [0.000 secs, 5028 KB]
   Test 3: TEST OK [0.000 secs, 5028 KB]
   Test 4: TEST OK [0.000 secs, 4248 KB]
   Test 5: TEST OK [0.000 secs, 4256 KB]
   Test 6: TEST OK [0.000 secs, 5028 KB]
   Test 7: TEST OK [0.000 secs, 5032 KB]
   Test 8: TEST OK [0.000 secs, 5036 KB]
   Test 9: TEST OK [0.000 secs, 5028 KB]

All tests OK.
Your program ('fracdec') produced all correct answers!  This is your
submission #9 for this problem.  Congratulations!

拖到现在才完成这道题，深表惭愧。加油加油。

fracdec：没这么麻烦

看了题解之后觉得自己蠢哭了，明明只要判断目前的被除数之前有没有出现过，就可以知道后面有没有一样的片段了，我竟然非要除一大串然后去玩字符串，真是服了。数学！数学不好！

说来也是，后面的数字就是由目前的被除数决定的，没毛病。

代码：

#include <cstdio>
#define N 100100

int seen[N]; 
//这个被除数是不是已经被发现过，如果是，是在要除出来小数点后第几-1位时
int count = 0, len = 0; //count到76换行，len(decimal)
char decimal[N]; //记住算过的小数

int intLen(int num){ //统计整数的位数
    int l = 0;
    if(num == 0) return 1;
    while(num > 0){
        num /= 10;
        l ++;
    }
    return l;
}

int main(){
    FILE *fin = fopen("fracdec.in", "r");
    FILE *fout = fopen("fracdec.out", "w");
    
    int n, d, integer, start, end;
    fscanf(fin, "%d %d", &n, &d);
    integer = n / d; //分离整数部分
    count = intLen(integer);//计算整数部分位数
    
    n = n % d; //留下的产生小数部分
    seen[n] = 0 + 1;
    while(1){ //做除法，直至除尽或被除数重复
        decimal[len ++] = '0' + n * 10 / d;
        n = n * 10 % d;
        if(n == 0){
            start = -1; //没有循环节的
            break;
        }
        if(seen[n] > 0){ //见过这个被除数
            start = seen[n] - 1;
            end = len;
            break;
        }
        seen[n] = len + 1;
    }

    //输出
    fprintf(fout, "%d.", integer);
    count ++;
    if(start == -1){ //除尽
        for(int i = 0; i < len; i ++){
            if(count == 76) {fprintf(fout, "\n"); count = 0;}
            fprintf(fout, "%c", decimal[i]);
            count ++;            
        }
    }else{ //有循环节
        for(int i = 0; i < start; i ++){
            if(count == 76) {fprintf(fout, "\n"); count = 0;}
            fprintf(fout, "%c", decimal[i]);
            count ++;
        }
        fprintf(fout, "("); count ++;
        for(int i = start; i < end; i ++){
            if(count == 76) {fprintf(fout, "\n"); count = 0;}
            fprintf(fout, "%c", decimal[i]);
            count ++;
        }
        fprintf(fout, ")"); count ++;
    }
    fprintf(fout, "\n");

    return 0;
}

效果：

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4664 KB]
   Test 2: TEST OK [0.000 secs, 4664 KB]
   Test 3: TEST OK [0.000 secs, 4664 KB]
   Test 4: TEST OK [0.000 secs, 4664 KB]
   Test 5: TEST OK [0.000 secs, 4664 KB]
   Test 6: TEST OK [0.000 secs, 4664 KB]
   Test 7: TEST OK [0.000 secs, 4664 KB]
   Test 8: TEST OK [0.000 secs, 4664 KB]
   Test 9: TEST OK [0.000 secs, 4664 KB]

All tests OK.
Your program ('fracdec') produced all correct answers!  This is your
submission #11 for this problem.  Congratulations!

还有更神奇的做法，还能推算到底是从第几位开始循环的，也就是算非循环节的小数位数。因为这些位数都是由于分子分母含有的 2 和 5 的因子不同导致的。抄题解代码：

int numBeforeRepeat(int n, int d) {
    int c2=0, c5=0;
    if (n == 0) return 1;
    while (d%2==0) { d/=2; c2++; }
    while (d%5==0) { d/=5; c5++; }
    while (n%2==0) { n/=2; c2--; } /* can go negative */
    while (n%5==0) { n/=5; c5--; } /* can go negative */
    if (c2>c5)
        if (c2>0) return c2;
        else return 0;
    else
        if (c5>0) return c5;
        else return 0;
}

是不是666。数学好的人真酷。