HOJ 401 - 完美小矩陣

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm>   using namespace std;   int sqrroot(int n){     if(n < 0) return -1;     int sqr1 = max(0, (int)(sqrt(n) - 2));     for(int lx = sqr1;lx*lx <= n;lx++)         if(lx*lx == n)             return lx;     return -1; }   int main(){          int n, k;     while(scanf("%d %d", &n, &k) != EOF){         if(n%2 == 0){             printf("22222\n");             for(int lx = 0;lx < n;lx++){                 for(int ly = 0;ly < n;ly++){                     if(ly == lx-1 and ly%2 == 0) printf("1 ");                     else if(ly == lx+1 and ly%2 == 1) printf("%d ", k);                     else printf("0 ");                 }                 puts("");             }             continue;         }         int res = sqrroot(k);         if(res == -1){             puts("11111");             continue;         }         puts("22222");         for(int lx = 0;lx < n;lx++){             for(int ly = 0;ly < n;ly++)                 printf("%d ", (lx==ly)*res);             puts("");         }     }     return 0; }

TIOJ 1029 A遊戲

第二次寫精煉很多

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#define INF 10000000

using namespace std;

// 1base

int arr[2000][2000] = {0};

int inp[2000];

int sum[2000];

int poi(int a, int b){

    if(a == b) return inp[a];

    if(arr[a][b] != 0) return arr[a][b];

    arr[a][b] = max(

        inp[a] + sum[b]-sum[a]-poi(a+1, b),

        inp[b] + sum[b-1]-sum[a-1]-poi(a, b-1)

    );

    return arr[a][b];

}

int main(){

    int n;scanf("%d", &n);

    sum[0] = 0;

    for(int lx = 1;lx <= n;lx++){

        scanf("%d", &inp[lx]);

        sum[lx] = sum[lx-1] + inp[lx];

    }

    int fst = poi(1, n);

    int scn = sum[n]-fst;

    printf("%d %d\n", fst, scn);

    return 0;

}

TIOJ 1036 How Many Primes?

一開始看成10^8....

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

char seive[1300000] = {0};

int sum[10000001] = {0};

inline void setb(int n){ seive[n>>3] |= 1<<(n&7); }

inline bool getb(int n){ return seive[n>>3]&(1<<(n&7)); }

int main(){

    setb(0), setb(1);

    for(int lx = 2;lx < 10000000;++lx)

        if(getb(lx) == 0)

            for(int ly = 2;ly*lx <= 10000000;++ly)

                setb(ly*lx);

    sum[0] = 0;

    for(int lx = 1;lx <= 10000000;lx++)

        sum[lx] = sum[lx-1] + (getb(lx) == 0);

    int m; scanf("%d", &m);

    for(int lx = 0;lx < m;lx++){

        int poi; scanf("%d", &poi);

        printf("%d\n", sum[poi]) ;

    }

    return 0;

}

TIOJ 1022 . H.跑跑卡恩車

#include <cstdio>

#include <cstdlib>

struct pt{ int x, y; pt(int _x = 0, int _y  =0){x = _x, y = _y;}};

int main(){

    int T; scanf("%d", &T);

    while(T--){

        int n,m; scanf("%d %d", &n, &m);

        int tab[200][200];

        for(int lx = 0;lx < n; lx++)

            for(int ly = 0;ly < m;ly++)

                scanf("%d", &tab[lx][ly]);

        pt que[400];

        int qs = 0, qe = 0;

        int rad[200][200];

        for(int lx = 0;lx < n;lx++)

            for(int ly = 0;ly < m;ly++)

                rad[lx][ly] = 500;

        rad[0][0] = 0;

        que[qe++] = pt(0, 0);

        int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

        while(qe > qs){

            pt prc = que[qs++];

            int px = prc.x, py = prc.y;

            for(int w = 0;w < 4;w++){

                int nx = px + dx[w], ny = py + dy[w];

                if(nx < 0 or nx >= n or ny < 0 or ny >= m) continue;

                if(abs(tab[nx][ny] - tab[px][py]) > 5) continue;

                if(rad[nx][ny] != 500) continue;

                rad[nx][ny] = rad[px][py] + 1;

                que[qe++] = pt(nx, ny);

            }

        }

        printf("%d\n", rad[n-1][m-1]);

    }

    return 0;

}

TIOJ 1020 . F.Number Insertion

這竟然只是暴搜OAO

#include <cstdio>

#include <cstdlib>

int ans[100] = {0};

int dfs(int* arr, int k, int klim, int len){

    if(k > klim){

        bool bigger = false;

        for(int lx = 0;lx < len;lx++){

            if(arr[lx] == ans[lx]) continue;

            if(arr[lx] > ans[lx]) bigger = true;

            if(arr[lx] < ans[lx]) bigger = false;

            break;

        }

        if(bigger){

            for(int lx = 0;lx < len;lx++)

                ans[lx] = arr[lx];

        }

        return 1;

    }

    int cnt = 0;

    for(int lx = 0;lx+1 < len;lx++){

        if(k%(arr[lx] + arr[lx+1]) == 0){

            for(int ly = len;ly >= lx+2;ly--)

                arr[ly] = arr[ly-1];

            arr[lx+1] = k;

            cnt += dfs(arr, k+1, klim, len+1);

            for(int ly = lx+1;ly < len;ly++)

                arr[ly] = arr[ly+1];

        }

    }

    return cnt;

}

int main(){

    int k; scanf("%d", &k);

    int arr[100] = {0, 1};

    int cc = dfs(arr, 2, k, 2);

    printf("%d\n", cc);

    for(int lx = 0;lx <= k;lx++)

        printf("%d ", ans[lx]);

    puts("");

    return 0;

}