UVA 820 - Internet Bandwidth

這才是重點 "Print a blank line after each test case."

#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
struct{ int a, b, val; }es[10001]; int ecnt;
vector<int> to[1000];
int _n;
void init(int n){
    ecnt = 0;
    _n = n;
    for(int lx = 0;lx <= n;lx++)
        to[lx].clear();
    return;
}
void add_edge(int a, int b, int ab, int ba){
    es[ecnt].a = a, es[ecnt].b = b, es[ecnt].val = ab; to[a].push_back(ecnt++);
    es[ecnt].a = b, es[ecnt].b = a, es[ecnt].val = ba; to[b].push_back(ecnt++);
    return;
}
int from[1000];
int vis[1000];
int que[1000];
int path[1000]; int pathcnt;
int bfs(int s, int t){
    int n = _n;
    for(int lx = 0;lx <= n;lx++)
        vis[lx] = 0, from[lx] = -1;
    int qs = 0, qt = 1;
    que[0] = s; vis[s] = 1;
    while(qs < qt){
        int g = que[qs++];
        for(int lx = 0;lx < to[g].size();lx++){
            int lind = to[g][lx];
            int pind = es[lind].b;
            if(vis[pind]) continue;
            if(es[lind].val <= 0) continue;
            from[pind] = lind;
            vis[pind] = 1;
            que[qt++] = pind;
        }
    }
    if(vis[t] == 0) return 0;
    pathcnt = 0;
    int pp = t;
    int min_val = 100000;
    while(pp != s){
        int lid = from[pp];
        //printf("%d ~ %d at %d\n", es[lid].a, es[lid].b, es[lid].val);
        path[pathcnt++] = lid;
        min_val = min(es[lid].val, min_val);
        pp = es[lid].a;
    }
    for(int lx = 0;lx < pathcnt;lx++){
        int lind = path[lx];
        es[lind].val -= min_val;
        es[lind^1].val += min_val;
    }
    return min_val;
}
int Ekarp(int s, int t){
    int f = 0, df;
    for(;;){
        //printf("============\n");
        df = bfs(s, t);
        if(df == 0) break;
        f += df;
    }
    return f;
}
int main()
{
    int n; int cs = 0;
    for(;;){
        cs++;
        scanf("%d", &n);
        if(n == 0) break;
        init(n);
        int s, t, c; scanf("%d %d %d", &s, &t, &c);
        int mat[101][101] = {0};
        while(c--){
            int a, b, val;
            scanf("%d %d %d", &a, &b, &val);
            mat[a][b] += val;
            mat[b][a] += val;
        }
        for(int lx = 1;lx <= n;lx++)
            for(int ly = lx+1;ly <= n;ly++)
                if(mat[lx][ly])
                    add_edge(lx,ly,mat[lx][ly], mat[lx][ly]);
        printf("Network %d\n", cs);
        printf("The bandwidth is %d.\n\n", Ekarp(s, t));
    }
    return 0;
}

TIOJ 1349 [特別加考題] 平方國的平方幣

四平方合定理：任意數可表a*a + b*b + c*c + d*d
三平方合定理：只要數不是4^a(8*k+7) 就可以表成 a*a + b*b + c*c
二平方合定理：p is prime，p = a*a + b*b if and only if 4|p-1

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
bool isq(int n){
    if(n == 1) return true;
    int h = (int)(sqrt(n));
    return h*h == n;
}
vector<int> prime;
bool seive[10000]={0};
int main()
{
    for(int lx = 2;lx < 10000;lx++){
        if(seive[lx] == false){
            prime.push_back(lx);
            for(int ly = 2;ly*lx < 10000;ly++)
                seive[ly*lx] = true;
        }
    }
    int n;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        // check 1
        if(isq(n)){
            puts("1");
            continue;
        }
        int prcn = n;
        while(prcn%2 == 0)
            prcn>>=1;
        if(prcn%4 == 1){
            bool ok2 = true;
            for(int lx = 1;lx < prime.size() and prime[lx] <= prcn and ok2;lx++){
                int cc = 0;
                while(prcn%prime[lx] == 0)
                    cc++, prcn/=prime[lx];
                if(prime[lx]%4 == 3)
                    if(cc%2 != 0)
                        ok2 = false;
            }
            if((prcn != 0) and (prcn%4 == 3))
                ok2 = false;
            if(ok2){
                puts("2");
                continue;
            }
        }
        while(n%4 == 0)
            n /= 4;
        puts( (n%8 == 7)? "4":"3");
    }
    return 0;
}

TIOJ 1449 郵局設置問題EXTREME

四邊型不等式 OwO~~

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int dp[1011][1011] = {0};
int rg[1011][1011] = {0};
int val[1011] = {0};
int w[1011][1011] = {0};
int main()
{
    int n, k; scanf("%d %d", &n, &k);
    for(int lx = 2;lx <= n;lx++)
        scanf("%d", val+lx);
    if(n <= k){puts("0"); return 0;}
    sort(val+1, val+n+1);
    for(int lx = 1;lx <= n;lx++)
        for(int ly = lx+1;ly <= n;ly++)
            w[lx][ly] = w[lx][ly-1] + val[ly] - val[(lx+ly)/2];
    
    for(int lx = 1;lx <= n;lx++)
        dp[lx][lx] = 0, rg[lx][lx] = lx-1,
        dp[lx][1] = w[1][lx], rg[lx][1] = 0;
    
    for(int lc = 2;lc <= n;lc++){
        for(int ll = 1;ll <= n-lc;ll++){
            int x = lc+ll, y = ll+1;
            int min_i = rg[x-1][y];
            int min_val = dp[min_i][y-1] + w[min_i+1][x];
            for(int i = rg[x-1][y];i <= rg[x][y+1] and i >= y-1;i++){
                int get_val = dp[i][y-1] + w[i+1][x]; 
                if(min_val > get_val)
                    min_val = get_val,
                    min_i = i;
            }
            rg[x][y] = min_i;
            dp[x][y] = min_val;
        }
    }
    printf("%d\n", dp[n][k]);
    return 0;
}

HDU 2167 Pebbles

16*16*2^16

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int box[20][20];
char tmp[1000];
int sts[2][1<<17];
int main()
{
    for(;;){
        int n;
        if(gets(tmp)==0) break;
        n = (strlen(tmp)+1)/3;
        if(n == 0) continue;
        //printf("n = %d\n", n);
        for(int lx = 0;lx < n;lx++)
            box[0][lx] = 10*(tmp[lx*3]-'0')+tmp[lx*3+1]-'0';
        for(int lx = 1;lx < n;lx++)
            for(int ly = 0;ly < n;ly++)
                scanf("%d", &box[lx][ly]);
        for(int lx = 0;lx < n;lx++)
            box[n][lx] = 0;
        //if(gets(tmp)==0) break;
        memset(sts, 0, sizeof(sts));
        int now = 0;
        for(int lx = 0;lx < n;lx++){
        for(int ly = 0;ly < n;ly++){
            for(int s = 0;s < (1<<(n+1));s++){
                if(((s&1) == 0 or ly == 0) and ((s&2) == 0) and
                   ((s&4) == 0 or ly == n-1) and ((s&(1<<n)) == 0 or ly == 0)){
                    sts[1-now][(s>>1)|(1<<n)] = max(sts[1-now][(s>>1)|(1<<n)],
                                                    sts[now][s]+box[lx][ly]);
                    
                }
                sts[1-now][s>>1] = max(sts[1-now][s>>1], sts[now][s]);
                
            }
            memset(sts[now], 0,sizeof(sts[now]));
            now = 1-now;
        }}
        int mm = 0;
        for(int lx = 0;lx < (1<<n+1);lx++)
            mm = max(mm, sts[now][lx]);
        printf("%d\n", mm);
    }
    return 0;
}

TIOJ 1014 . 打地鼠

終於打完地鼠了XD

一直沒有注意到 "早打一定比較好" 這性質XD

亂寫亂掃，原本估計是會T的，沒想到AC了XDD

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int sts[1<<16][17];
int tn[16];
const int inf = 2000000000;
int nabs(int a){return max(a, -a);}
void printsts(int n){
    for(int lx = 0;lx < (1<<n);lx++){
        for(int ly = 0; ly < n;ly++)
            printf("%c", (lx&(1<<(n-ly-1))) ? '1':'0');
        printf("\t");
        for(int ly = 0;ly < n;ly++)
            if(sts[lx][ly] == inf)
                printf("inf\t");
            else
                printf("%d\t", sts[lx][ly]);
        puts("");
    }
    puts("----------------------------");
    return;
}

int main()
{
    int n; scanf("%d", &n);
    int MM = n;
    for(int lx = 0;lx < n;lx++){
        scanf("%d", tn+lx);
        MM += tn[lx];
    }
//    memset(sts, 0, sizeof(sts));
    for(int lx = 0;lx < 16;lx++)
        for(int st = 0; st < 1<<16;st++)
            sts[st][lx] = inf;
    for(int lx = 0;lx < n;lx++)
        sts[1<<lx][lx] = (lx+tn[lx])/tn[lx]*tn[lx];
    //printsts(n);
    for(int _ = 0;_ <= 16; _++){
        //printsts(n);
        for(int lx = 0;lx < n;lx++){
            for(int ly = 0;ly < 1<<n;ly++){
                if(sts[ly][lx] == inf) continue;
                for(int lz = 0;lz < n;lz++){
                    sts[ly|(1<<lz)][lz] = min(
                        sts[ly|(1<<lz)][lz],
                        (sts[ly][lx]+nabs(lz-lx)+tn[lz]-1)/tn[lz]*tn[lz]
                    );
                }
            }
        }
        //bool ok = false;
        //for(int lx = 0;lx < n and not ok;lx++)
        //    ok = sts[(1<<n)-1][lx] < inf;
        //if(ok)
        //    break;
    }
    //printsts(n);
    int mm = inf;
    for(int lx = 0;lx < n;lx++)
        mm = min(sts[(1<<n)-1][lx], mm);
    printf("%d\n", mm);
    //while(1);
    return 0;
}