2012-11-29 20:54:10Morris

[ITSA] 19th 總解答

這次沒有動規題,全是模擬題,雖然沒有很難,但打得很不順。
一個人參賽無助了?

打表不多語

你自己想你自己做過位元運算的二十皇后,再怎麼跑都是鄰近一秒,更不用說一百皇后,更何況你要 hash 九十度的翻轉存在,打表是肯定的。

#include <stdio.h>

int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        switch(n) {
            case 1:puts("1");break;
            case 2:puts("0");break;
            case 3:puts("0");break;
            case 4:puts("2");break;
            case 5:puts("2");break;
            case 6:puts("0");break;
            case 7:puts("0");break;
            case 8:puts("0");break;
            case 9:puts("0");break;
            case 10:puts("0");break;
            case 11:puts("0");break;
            case 12:puts("8");break;
            case 13:puts("8");break;
            case 14:puts("0");break;
            case 15:puts("0");break;
            case 16:puts("64");break;
            case 17:puts("128");break;
            case 18:puts("0");break;
            case 19:puts("0");break;
            case 20:puts("480");break;
            case 21:puts("704");break;
            case 22:puts("0");break;
            case 23:puts("0");break;
            case 24:puts("3328");break;
            case 25:puts("3264");break;
            case 28:puts("32896");break;
            case 29:puts("43776");break;
            case 32:puts("406784");break;
            case 33:puts("667904");break;
            case 36:puts("5845504");break;
            case 37:puts("8650752");break;
            case 40:puts("77184000");break;
            case 41:puts("101492736");break;
            case 44:puts("1261588480");break;
            case 45:puts("1795233792");break;
            case 48:puts("21517426688");break;
            case 49:puts("35028172800");break;
            default:
                puts("0");
        }
    }
    return 0;
}

我相信你只有一筆,別給我偷偷跟上次一樣陰測資。

#include <stdio.h>
#include <vector>
using namespace std;
vector<int> g[100005];
long long A[100005], ans;
long long dfs(int nd) {
    long long sum = 0, tmp;
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        tmp = dfs(*it);
        if(nd == 0 && tmp > ans)
            ans = tmp;
        sum += tmp;
    }
    sum += A[nd];
    return sum;
}
int main() {
    int n, i, p;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%lld", &A[i]);
    for(i = 1; i < n; i++) {
        scanf("%d", &p);
        g[p].push_back(i);
    }
    ans = 0;
    dfs(0);
    printf("%lld\n", ans);
    return 0;
}

10.5% 要四捨五入換算他所在的 percent。
扣稅要無條件進位,不知道會不會 overflow,先計算個 LONG LONG 好了。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int A[1000];
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int mx = 0, i, j;
        for(i = 0; i < n; i++) {
            scanf("%d", &A[i]);
            if(A[i] > mx)
                mx = A[i];
        }
        sort(A, A+n);
        int m = n, x;
        long long ans = 0;
        for(i = n-1; i >= 0; i--)
            if(A[i] == mx)
                m--, ans += (int)ceil(A[i]*0.4);
        for(i = n-m, j = m-1; j >= 0; i++, j--) {
            char rank[50];
            sprintf(rank, "%.lf", (double)i*100/n);
            sscanf(rank, "%d", &x);
            if(x >= 11 && x <= 30)
                ans += (int)ceil(A[j]*0.3);
            else if(x <= 60)
                ans += (int)ceil(A[j]*0.2);
            else if(x <= 80)
                ans += (int)ceil(A[j]*0.1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

其實題目沒有表達得很好,不過大概懂他想作什麼。

#include <stdio.h>

int main() {
    int n;
    int D[7] = {1000,500,100,50,10,5,1};
    while(scanf("%d", &n) == 1) {
        int A[7] = {};
        int i;
        for(i = 0; i < 7; i++) {
            A[i] = n/D[i];
            n %= D[i];
        }
        int M[7] = {}, N[7] = {};
        for(i = 0; i < 7; i++) {
            if(A[i]%2) {
                M[i] = A[i]/2+1;
                N[i] = A[i]-M[i];
                for(i++; i < 7; i++)
                    N[i] = A[i];
                break;
            }
            M[i] = A[i]/2;
            N[i] = A[i]/2;
        }
        int s1 = 0, s2 = 0;
        for(i = 0; i < 7; i++) {
            if(i)   putchar(' ');
            printf("%d", M[i]);
            s1 += M[i] * D[i];
        }
        puts("");
        for(i = 0; i < 7; i++) {
            if(i)   putchar(' ');
            printf("%d", N[i]);
            s2 += N[i] * D[i];
        }
        puts("");
        printf("%d\n", s1-s2);

    }
    return 0;
}

找出 LCS,應該已經寫到爛掉了,就不多說了。

#include <stdio.h>
#include <string.h>
char x[105], y[105];
int dp[105][105], arg[105][105];
void print(int i, int j) {
    if(dp[i][j] == 0)   return;
    if(arg[i][j] == 1) {
        print(i-1, j-1);
        printf("%c", x[i-1]);
    } else if(arg[i][j] == 2) {
        print(i-1, j);
    } else
        print(i, j-1);
}
int main() {
    int i, j;
    while(scanf("%s %s", x, y) == 2) {
        int la = strlen(x), lb = strlen(y);
        memset(dp, 0, sizeof(dp));
        for(i = 1; i <= la; i++) {
            for(j = 1; j <= lb; j++) {
                if(x[i-1] == y[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                    arg[i][j] = 1;
                } else {
                    if(dp[i-1][j] > dp[i][j-1]) {
                        dp[i][j] = dp[i-1][j];
                        arg[i][j] = 2;
                    } else {
                        dp[i][j] = dp[i][j-1];
                        arg[i][j] = 3;
                    }
                }
            }
        }
        if(dp[la][lb] == 0)
            puts("none");
        else
            print(la, lb), puts("");
    }
    return 0;
}