TIOJ 1501 . Dead at the end of sixth sense

枚舉最小值

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long int int64;

const int64 inf = 10000000000LL;

int64 iabs(int64 a){return max(a, -a);}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        int64 arr[1001];
        for(int lx = 0;lx < n;lx++) scanf("%lld", arr+lx);
        int64 ans = inf;
        for(int lx = 0;lx < n;lx++){
            int64 tab[1001];
            for(int ly = 0;ly < n;ly++) tab[ly] = inf;
            tab[n-1] = arr[n-1], tab[n] = arr[n-1];
            arr[n] = arr[n-1];
            for(int ly = n-2;ly>=0;ly--){
                if(arr[ly] < arr[lx]) continue;
                int64 mm = inf;
                if(arr[ly+1] >= arr[lx]) mm = min(mm, tab[ly+1]);
                if(arr[ly+2] >= arr[lx]) mm = min(mm, tab[ly+2]);
                tab[ly] = max(arr[ly], mm);
            }
            int64 cal = tab[0]-arr[lx];
//            printf("%d -> cal = %lld\n", lx, cal);
            ans = min(tab[0]-arr[lx], ans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

1111 . [入門] Crucio

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

char tab[510][510];

int main(){
    int n;
    for(;;){
        scanf("%d", &n);
        if(!n) break;
        for(int lx = 0; lx < n;lx++)
            scanf("%s", tab[lx]);
       
        int dx[4] = {1, 1, 1, 0};
        int dy[4] = {-1, 0, 1, 1};

        int pts[3] = {0};
        for(int lx = 0;lx < n;lx++){
            for(int ly = 0;ly < n;ly++){
                char ch = tab[lx][ly];
                if(ch == '.') continue;
                for(int ld = 0;ld < 4;ld++){
                    bool ok = true;
                    for(int len = -1;len <= 5 and ok;len++){
                        int nx = lx+len*dx[ld], ny = ly+len*dy[ld];
                        bool fg = true;
                        if(nx < 0 or nx >= n or ny < 0 or ny >= n or tab[nx][ny] != ch){
                            fg = false;
                        }
                        ok = fg^(len == -1 or len == 5);

                    }
                    if(ok)
                        pts[ch-'A']++;
                }
            }
        }

        printf("A %d\nB %d\nC %d\n\n", pts[0], pts[1], pts[2]);

    }
    return 0;
}

TIOJ 1108 . 樹的三兄弟

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

char pre[100], in[100];

void print_tree(int pre1, int pre2, int in1, int in2){

    if(pre1 == pre2) return;

    

    int ptr = in1;

    for(;ptr < in2;ptr++)

        if(in[ptr] == pre[pre1])

            break;

    print_tree(pre1+1, pre1+(ptr-in1)+1, in1, ptr);

    print_tree(pre1+(ptr-in1)+1, pre2, ptr+1, in2);

    printf("%c", pre[pre1]);

    return;

}

int main(){

    while(scanf("%s %s", pre, in) != EOF){

        print_tree(0, strlen(pre), 0, strlen(in)) ;

        puts("");

    }

    return 0;

}   

SPOJ QTREE - Query on a tree

樹鍊剖分


#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>

using namespace std;

struct BST{
    vector<int> tree;
    int base;
    BST(const vector<int>& arr){
        base = (1<<(int)(ceil(log2((int)arr.size() + 4)))) - 1;
        tree = vector<int>(base*2 + 2, 0);
        for(int lx = 0;lx < arr.size();lx++) tree[base+2+lx] = arr[lx];
        for(int lx = base;lx;lx--) tree[lx] = max(tree[lx*2], tree[lx*2+1]);
        return;
    }
   
    void modify(int p, int val){
        p+=base+2; tree[p] = val;
        for(p>>=1;p;p>>=1)
            tree[p] = max(tree[p*2], tree[p*2+1]);
        return;
    }

    int query(int a, int b){
        assert(a <= b);
        int ret = 0;
        for(a+=base+1, b+=base+3;a^b^1;a>>=1, b>>=1){
            if(~a&1) ret = max(ret, tree[a^1]);
            if(b&1) ret = max(ret, tree[b^1]);
        }
        return ret;
    }
};

vector<int> tab[10000];
vector<int> tabwei[10000];

int  siz[10000];
int  dep[10000];
int  fat[10000];
int  nup[10000][15];
int  wei[10000];
BST* bst[10000];
vector<int> lin[10000];

void initial(int n){
    for(int lx = 0;lx < n;lx++) tab[lx].clear(), tabwei[lx].clear();
    return;
}

void finish(int n){
    for(int lx = 0;lx < n;lx++)
        if(fat[lx] == lx)
            delete bst[lx];
    return;
}

void dfs(int v, int ft){
    siz[v] = 1, fat[v] = v;
    int sz = 0, max_nd;
    for(int lx = 0;lx < tab[v].size();lx++){
        int nd = tab[v][lx];
        if(nd == ft) continue;
        nup[nd][0] = v, dep[nd] = dep[v]+1;
        wei[nd] = tabwei[v][lx];
        dfs(nd, v);
        siz[v] += siz[nd];
        if(siz[nd] > sz) sz = siz[nd], max_nd = nd;
    }
    if(sz) fat[max_nd] = v;
    return;
}

int get_fat(int a){return a == fat[a] ? a: fat[a] = get_fat(fat[a]);}

int st_by_dep(int a, int b){return dep[a] < dep[b];}

void make_drec(int n){
    dep[0] = 0;
    dfs(0, 0);

    nup[0][0] = 0;
    for(int lx = 1;lx < 15;lx++)
        for(int ly = 0;ly < n;ly++)
            nup[ly][lx] = nup[nup[ly][lx-1]][lx-1];

    for(int lx = 0;lx < n;lx++) lin[lx].clear();
    for(int lx = 0;lx < n;lx++) lin[get_fat(lx)].push_back(lx);
    for(int lx = 0;lx < n;lx++){
        if(fat[lx] != lx) continue;
        sort(lin[lx].begin(), lin[lx].end(), st_by_dep);
        vector<int> tmp;
        for(int ly = 0; ly < lin[lx].size();ly++)
            tmp.push_back(wei[lin[lx][ly]]);
        bst[lx] = new BST(tmp);
    }
    return;
}

int get_nup(int v, int step){
    for(int lx = 0;lx < 15;lx++)
        if(step&(1<<lx))
            v = nup[v][lx];
    return v;
}

int get_lca(int a, int b){
    if(dep[a] > dep[b]) a = get_nup(a, dep[a]-dep[b]);
    else if(dep[b] > dep[a]) b = get_nup(b, dep[b]-dep[a]);
    int ls = 0, rs = 10000;
    while(ls < rs){
        int ts = (ls+rs)>>1;
        if(get_nup(a, ts) == get_nup(b, ts))
            rs = ts;
        else
            ls = ts+1;
    }
    return get_nup(a, ls);
}

void change_edge(int a, int b, int c){
    // a--> b
    if(dep[a] > dep[b]) swap(a, b);
    bst[fat[b]]->modify(dep[b]-dep[fat[b]], c);
    return;
}

int _query_path(int anc, int chd){
    int ret = 0;
    while(chd != anc){
        int fat_id = fat[chd];
        if(dep[anc] >= dep[fat_id]){
            ret = max(ret, bst[fat_id]->query(dep[anc]-dep[fat_id]+1, dep[chd]-dep[fat_id]));
            break;
        }else{
            ret = max(ret, bst[fat_id]->query(0, dep[chd]-dep[fat_id]));
            chd = nup[fat_id][0];
        }
       
    }
    return ret;
}

int query_path(int a, int b){
    int anc = get_lca(a, b);
    assert(dep[anc] <= dep[a] and dep[anc] <= dep[b]);
    // anc --> a
    // anc --> b
    return max(_query_path(anc, a), _query_path(anc, b));
}

struct edge{int a, b;};

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        initial(n);
        vector<edge> es;
        for(int lx = 0;lx < n-1;lx++){
            int a, b, c; scanf("%d %d %d", &a, &b, &c);
            a--, b--;
            tab[a].push_back(b), tabwei[a].push_back(c);
            tab[b].push_back(a), tabwei[b].push_back(c);

            edge _e = {a, b};
            es.push_back(_e);
        }
        make_drec(n);
        for(;;){
            char cmd[10]; scanf("%s", cmd);
            int a, b;
            if(cmd[0] == 'Q'){
                scanf("%d %d", &a, &b);
                a--, b--;
                printf("%d\n", query_path(a, b));
            }else if(cmd[0] == 'C'){
                scanf("%d %d", &a, &b);
                a--;
                change_edge(es[a].a, es[a].b, b);
            }else if(cmd[0] == 'D'){
                break;
            }else{
                assert(0);
            }
        }
        finish(n);
        puts("");
    }
    return 0;
}

Codeforces Round #307 (Div. 2), problem: (D) GukiZ and Binary Operations

以前碰到的題目好像都有保證m > 1之類，看來以後要多注意._.

#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

int64 n, k, m;

int64 mul(int64 a, int64 b){
    return (a*b)%m;
}

int64 Pow(int64 a, int64 n){
    if(n == 0) return 1;
    if(n == 1) return a;
    int64 P = Pow(a, n>>1);
    P = mul(P, P);
    if(n&1) return mul(P, a);
    return P;
}

struct Mat{
    int64 a, b, c, d;
    Mat(int64 _a = 1, int64 _b = 0, int64 _c = 0, int64 _d = 1):
        a(_a%m), b(_b%m), c(_c%m), d(_d%m){return;}
};

Mat operator*(Mat& s, Mat& t){
    return Mat(mul(s.a,t.a) + mul(s.b,t.c),
               mul(s.a,t.b) + mul(s.b,t.d),
               mul(s.c,t.a) + mul(s.d,t.c),
               mul(s.c,t.b) + mul(s.d,t.d));
}

Mat Pow(Mat a, int64 n){
    if(n == 0) return Mat();
    if(n == 1) return Mat(a);
    Mat P = Pow(a, n>>1);
    P = P*P;
    if(n&1) return P*a;
    return P;
}

int main(){
    int l;
    scanf("%I64d %I64d %d %I64d", &n, &k, &l, &m);
    int64 ans = 1%m;
    Mat gg(Pow(Mat(0, 1, 1, 1), n-2));
    // b1 = 2, b2 = 3, b3 = 5
    int64 bb = (3*gg.a+5*gg.b)%m;
    int64 aa = (Pow(2, n)-bb+m)%m;
    for(int lx = 0;lx < l;lx++){
        if(k&1) ans = mul(ans, aa); 
        else ans = mul(ans, bb);
        k>>=1;
    }
    if(k) ans = 0;
    printf("%I64d\n", ans);
    return 0;
}

Codeforces Round #307 (Div. 2), problem: (B) ZgukistringZ

#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

char bufc[100010];
char stra[100010];
char strb[100010];

int cnta[26] = {0}, cntb[26] = {0}, cntc[26] = {0};

int gety(int x){
    int y = 100000000;
    for(int lx = 0;lx < 26;lx++){
        if(cntc[lx] < cnta[lx]*x) return -1;
        if(cntb[lx] != 0)
            y = min(y, (cntc[lx]-cnta[lx]*x)/cntb[lx]);
    }
    return y;
}

void build(char* str, int* cc){
    for(int lx = 0;str[lx] != 0;lx++)
        cc[str[lx]-'a']++;
    return;
}

void func(int* c1, int* c2){
    for(int lx = 0;lx < 26;lx++)
        c1[lx] -= c2[lx];
    return;
}

void print(int* a){
    for(int lx = 0;lx < 26;lx++)
        printf("%d ", a[lx]);
    puts("");
    return;
}

int main(){
    scanf("%s %s %s", bufc, stra, strb);
    build(bufc, cntc);
    build(stra, cnta);
    build(strb, cntb);
    
    int mx = 0, my = 0, mm = 0;
    for(int lx = 0;;lx++){
        int x = lx, y = gety(x);
        if(y >= 0 and x+y >= mm)
            mx = x, my = y, mm = x+y;
        if(y < 0)
            break;
    }
    
    for(int lx = 0;lx < mx;lx++){
        printf("%s", stra);
        func(cntc, cnta);
    }
    for(int lx = 0;lx < my;lx++){
        printf("%s", strb);
        func(cntc, cntb);
    }

    for(int lx = 0;lx < 26;lx++)
        while(cntc[lx]--)
            printf("%c", 'a'+lx);

    puts("");
    return 0;
}

Codeforces Round #307 (Div. 2), problem: (A) GukiZ and Contest

#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long int int64;

int arr[10000];

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
    for(int lx = 0;lx < n;lx++){
        int cc = 0; for(int ly = 0;ly < n;ly++) cc += arr[lx] < arr[ly];
        cc++;
        printf("%d ", cc);
    }
    puts("");
    return 0;
}

Codeforces Round #306 (Div. 2), problem: (E) Brackets in Implications

分三種：zerocnt = 1 or zerocnt = 2 or zerocnt = 3討論

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
using namespace std;

typedef long long int int64;

struct node{
    bool val;
    bool is_leaf;
    node *a, *b;
    node(bool v){
        val = v, is_leaf = true;
        return;
    }
    node(node* aa, node* bb){
        a = aa, b = bb; is_leaf = false;
        return;
    }

    void print(){
        if(is_leaf){printf("%d", val);return;}
        printf("(");
        a->print();
        printf(")->(");
        b->print();
        printf(")");
        return;
    }

};

int arr[100011];

vector<node*> build(int a, int b){
    vector<node*> ret;
    for(int lx = a;lx <= b;lx++)
        ret.push_back(new node(arr[lx]));
    return ret;
}

node* from_right(vector<node*> pp){
    assert(pp.size());
    node* prc = pp[(int)(pp.size())-1];
    for(int lx = (int)(pp.size())-2;lx >= 0;lx--)
        prc = new node(pp[lx], prc);
    return prc;
}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
    
    if(arr[n-1] != 0){
        puts("NO");
        return 0;
    }
    
    int zcnt = 0; for(int lx = 0;lx < n;lx++) zcnt += 1^arr[lx];
    
    if(zcnt == 1){
        puts("YES");
        from_right(build(0, n-1))->print();
        puts("");
    }else if(zcnt == 2){
        if(arr[n-2] == 0){
            puts("NO");
        }else{
            puts("YES");
            int z0, z1 = n-1; for(int lx = 0;lx < n-1;lx++) if(arr[lx] == 0){ z0 = lx; break;}
            (new node(
                new node(
                    from_right(build(0, z0)),
                    from_right(build(z0+1, z1-1))
                ),
                new node(0)
            ))->print();
            puts("");
        }
    }else{
        puts("YES");
        vector<node*> pp;
        int p1 = -1;
        for(int lx = 0;lx < n;lx++){
            if(arr[lx] == 1){
                if(p1 == -1) p1 = lx;
            }else{
                if(p1 == -1) pp.push_back(new node(0));
                else{
                    pp.push_back(from_right(build(p1, lx)));
                    p1 = -1;
                }
            }
        }
        node* tail = pp[(int)pp.size()-1];
        pp.pop_back();
        (new node(
            from_right(pp),
            tail
        ))->print();
        puts("");
    }
    return 0;
}