Codeforces Round #309 (Div. 1), problem: (C) Love Triangles

可以發現love的關係是等價關係，
然後這世界只有兩種值: 0, 1

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;

typedef long long int int64;
const int64 P = 1000000007;

typedef vector<int> VI;

int Fat(VI& fat, int a){return (fat[a] == a) ? a: fat[a] = Fat(fat, fat[a]);}
void Onion(VI& fat, int a, int b){fat[Fat(fat, a)] = Fat(fat, b);return;}

struct _rel{int a, b, c;};

_rel rel[100000];

int main(){
    int n, k; scanf("%d %d", &n, &k);
    for(int lx = 0;lx < k;lx++){
        scanf("%d %d %d", &rel[lx].a, &rel[lx].b, &rel[lx].c);
        rel[lx].a--, rel[lx].b--;
    }

    VI test(2*n);
    for(int lx = 0;lx < 2*n;lx++) test[lx] = lx;
    for(int lx = 0;lx < k;lx++){
        if(rel[lx].c)
            Onion(test, rel[lx].a, rel[lx].b),
            Onion(test, rel[lx].a+n, rel[lx].b+n);
        else
            Onion(test, rel[lx].a, rel[lx].b+n),
            Onion(test, rel[lx].b, rel[lx].a+n);
    }
    
    bool check = true;
    for(int lx = 0;lx < n and check;lx++)
        if(Fat(test, lx) == Fat(test, lx+n))
            check = false;
    if(!check){
        puts("0");
        return 0;
    }

    for(int lx = 0;lx < n;lx++)
        Onion(test, lx, lx+n);

    set<int> sign;
    int64 ans = (1+P)/2;
    for(int lx = 0;lx < n;lx++){
        if(sign.count(Fat(test, lx))) continue;
        ans = (ans*2)%P;
        sign.insert(Fat(test, lx));
    }

    printf("%d\n", (int)ans);

    return 0;
}

Codeforces Round #309 (Div. 1), problem: (A) Kyoya and Colored Balls

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

using namespace std;

typedef long long int int64;

int64 mut[1000001];;

const int64 P = 1000000007;

int64 npow(int64 a, int n){
    if(!n) return 1;
    int64 g = npow(a, n>>1);
    g = (g*g)%P;
    if(n&1) return (g*a)%P;
    return g;
}

int64 rev(int64 n){ return npow(n, P-2);}

int64 C(int64 a, int64 b){
    int64 ret = mut[a];
    ret *= rev(mut[b]); ret %= P;
    ret *= rev(mut[a-b]); ret %= P;
    return ret;
}

int main(){
    mut[0] = 1;
    for(int lx = 1;lx <= 1000000;lx++)
        mut[lx] = (mut[lx-1]*lx)%P;

    int n; scanf("%d", &n);
    int64 ans = 1; int sum = 0;
    for(int lx = 0;lx < n;lx++){
        int k; scanf("%d", &k);
        ans *= C(sum+k-1, sum);
        ans %= P;
        sum += k;
    }
    printf("%d\n", (int)ans);
    return 0;
}

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;
}