UVA 11255 - Necklace

第一次練Burnside@@
主要是把每次fix point的個數算出來就好惹。
雖然複雜度可以壓到O(40^3 + N*(a+b+c))但反正會過XD

1. 算
2. 把答案存起來XD

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long int int64;

struct Key{int a, b, c; Key(int _a, int _b, int _c):a(_a), b(_b), c(_c){return;}};
bool operator==(const Key& p, const Key& q){return p.a == q.a and p.b == q.b and p.c == q.c;}
struct KeyHash{size_t operator()(const Key& key)const{ return (hash<int>()(key.a)<<14)^(hash<int>()(key.b)<<7)^hash<int>()(key.c);}};

void dumpvec(vector<int>& vec){printf("vec:");for(int ii : vec) printf(" %d", ii);printf("\n");return;}

struct Ans{int v[3]; Ans(int a, int b, int c){v[0] = a, v[1] = b, v[2] = c; sort(v, v+3);return;}};
bool operator==(const Ans& p, const Ans& q){return p.v[0] == q.v[0] and p.v[1] == q.v[1] and p.v[2] == q.v[2];}
struct AnsHash{size_t operator()(const Ans& a)const{return (hash<int>()(a.v[0])<<14)^(hash<int>()(a.v[1])^7)^hash<int>()(a.v[2]);}};

int main(){
    int N; scanf("%d", &N);
    unordered_map<Ans, int64, AnsHash> anstab;
    while(N--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        if(anstab.count(Ans(a, b, c))){
            printf("%lld\n", anstab[Ans(a, b, c)]);
            continue;
        }

        int64 ans = 0;
        int n = a+b+c;
       
        // 0-turn
        for(int tptr = 0;tptr < n;tptr++){
            bool vis[40] = {0};
            vector<int> vec;
            for(int lx = 0;lx < n;lx++){
                int cc = 0;
                int ptr = lx;
                while(!vis[ptr]){
                    vis[ptr] = 1;
                    cc++;
                    ptr = (ptr+tptr)%n;
                }
                if(cc) vec.push_back(cc);
            }
            unordered_map<Key, int64, KeyHash> bfs[2];
            bfs[0][Key(a, b, c)] = 1;
            int pp = 0;
            for(int dt : vec){
                bfs[pp^1].clear();
                for(auto it : bfs[pp]){
                    Key k = it.first; int64 val = it.second;
                    if(k.a >= dt) bfs[pp^1][Key(k.a-dt, k.b, k.c)] += val;
                    if(k.b >= dt) bfs[pp^1][Key(k.a, k.b-dt, k.c)] += val;
                    if(k.c >= dt) bfs[pp^1][Key(k.a, k.b, k.c-dt)] += val;
                }
                pp ^= 1;
            }
            ans += (int64)bfs[pp][Key(0, 0, 0)];
        }
       
        // 1-turn
        for(int tptr = 0;tptr < n;tptr++){
            bool vis[40] = {0};
            vector<int> vec;
            for(int lx = 0;lx < n;lx++){
                int cc = 0;
                int ptr = lx;
                while(!vis[ptr]){
                    vis[ptr] = 1;
                    ptr = (n-1-ptr+tptr)%n;
                    cc++;
                }
                if(cc) vec.push_back(cc);
            }
            unordered_map<Key, int64, KeyHash> bfs[2];
            bfs[0][Key(a, b, c)] = 1;
            int pp = 0;
            for(int dt : vec){
                bfs[pp^1].clear();
                for(auto it : bfs[pp]){
                    Key k = it.first; int64 val = it.second;
                    if(k.a >= dt) bfs[pp^1][Key(k.a-dt, k.b, k.c)] += val;
                    if(k.b >= dt) bfs[pp^1][Key(k.a, k.b-dt, k.c)] += val;
                    if(k.c >= dt) bfs[pp^1][Key(k.a, k.b, k.c-dt)] += val;
                }
                pp ^= 1;
            }
            ans += (int64)bfs[pp][Key(0, 0, 0)];
        }
       
        anstab[Ans(a, b, c)] = ans/2/n;

        printf("%lld\n", ans/2/n);
    }
    return 0;
}

POI 21th Couriers

http://main.edu.pl/en/archive/oi/21/kur

題目：區間查詢有沒有數字的量嚴格大於一半，假如有就輸出，沒有則輸出0

一直覺得很神奇XD 首先抓出候選人，然後真的去確認他的數量


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

using namespace std;

struct node{int id, hp; node(int _id = 0, int _hp = 0):id(_id),hp(_hp){return;}};

node operator+(const node& a, const node& b){
    node ret;
    if(a.id == b.id){
        ret = node(a.id, a.hp+b.hp);
    }else if(a.hp > b.hp){
        ret = node(a.id, a.hp-b.hp);
    }else{
        ret = node(b.id, b.hp-a.hp);
    }
    if(ret.hp == 0) ret.id = 0;
    return ret;
}

struct sumbst{
    vector<node> tree;
    int base;
    sumbst(int n, int* arr){
        base = (1<<(int)(ceil)(log2(n+3)))-1;
        tree = vector<node>(base*2+2, node());
        for(int lx = 0; lx < n;lx++)
            tree[lx+base+2] = node(arr[lx], 1);

        for(int lx = base;lx;lx--)
            tree[lx] = tree[lx<<1]+tree[(lx<<1)^1];
    }
    int query(int a, int b){
        node ret;
        for(a += base+1, b += base+3;a^b^1;a>>=1, b>>=1){
            if(~a&1) ret = ret + tree[a^1];
            if(b&1) ret = ret + tree[b^1];
        }
        return ret.id;
    }
};

int arr[500000];

map<int, vector<int> > qmap;

int main(){
    int n, q; scanf("%d %d", &n, &q);
    for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
    for(int lx = 0;lx < n;lx++) qmap[arr[lx]].push_back(lx);
   
    sumbst bst(n, arr);
    for(int lx = 0;lx < q;lx++){
        int a, b; scanf("%d %d", &a, &b); a--, b--;
        int id = bst.query(a, b);
        if(id == 0){ printf("0\n"); continue;}
        vector<int>& vec = qmap[id];
        int lowptr = lower_bound(vec.begin(), vec.end(), a) - vec.begin();
        int uppptr = upper_bound(vec.begin(), vec.end(), b) - vec.begin();
        int count = uppptr-lowptr;
        if(count > (b-a+1)/2)
            printf("%d\n", id);
        else
            printf("0\n");
    }
    return 0;
}

TIOJ 1106 . 遇見一株樹

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

using namespace std;

struct node{
    int nc, h;
    node(int _h = 0){nc = 0;h = _h;return;}
}stk[1000000];

int ptr;

char buf[1000000];

int main(){
    while(scanf("%s", buf) != EOF){
        ptr = 1;
        stk[0] = node(1);
        int max_nc = 0;
        int max_h = 1;
        int leaf_cnt = 0;
        for(int lx = 0;buf[lx] != 0;lx++){
            if(buf[lx] == '('){
                stk[ptr-1].nc++;
                stk[ptr] = node(stk[ptr-1].h+1);
                ptr++;
            }else if(buf[lx] == ')'){
                max_h = max(max_h, stk[ptr-1].h);
                max_nc = max(max_nc, stk[ptr-1].nc);
                ptr--;
            }else if(buf[lx] == '*'){
                stk[ptr-1].nc++;
                leaf_cnt++;
            }
        }

        printf("%d %d %d\n", leaf_cnt, max_h, max_nc);
    }
    return 0;
}

DQUERY - D-query

跟兔子王國類似的手法，對Query x排序，準備sumbst，處理pop數字ptr和push數字ptr..

[兔子王國]

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

using namespace std;

struct sumbst{
    vector<int> tree;
    int base;
    sumbst(int n){
        base = (1<<(int)(ceil(log2(n+3))))-1;
        tree = vector<int>(2*base+2, 0);
        return;
    }
    void modify(int p, int v){
        p += base + 2;
        tree[p] = v;
        for(p>>=1;p;p>>=1)
            tree[p] = tree[p<<1] + tree[(p<<1)^1];
        return;
    }
    int query(int a, int b){
        int ret = 0;
        for(a+=base+1,b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) ret += tree[a^1];
            if(b&1) ret += tree[b^1];
        }
        return ret;
    }
};


struct qry{int id, x, y;};
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int arr[200000];
int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);
   
    map<int, vector<int> > posrec;
    map<int, int > posptr;
    for(int lx = 0;lx < n;lx++){
        posrec[arr[lx]].push_back(lx);
        posptr[arr[lx]] = 1;
    }

    int q; scanf("%d", &q);
    vector<qry> qrys(q);
    for(int lx = 0;lx < q;lx++){
        int a, b;
        scanf("%d %d", &a, &b);
        qrys[lx].x = a-1, qrys[lx].y = b-1, qrys[lx].id = lx;
    }
    sort(qrys.begin(), qrys.end());
   
    vector<int> ans(q);
    sumbst bst(n);
    for(auto& it : posrec)
        bst.modify(it.second[0], 1);

    int now = 0;
    for(qry& qq : qrys){
        while(now < qq.x){
            auto& vec = posrec[arr[now]];  
            auto& ptr = posptr[arr[now]];
            bst.modify(vec[ptr-1], 0);
            if(vec.size() > ptr)
                bst.modify(vec[ptr], 1);
            ptr++, now++;
        }
        ans[qq.id] = bst.query(qq.x, qq.y);
    }
   
    for(int lx = 0;lx < q;lx++)
        printf("%d\n", ans[lx]);

    return 0;
}

HOJ 327 - 兔子王國

http://hoj.twbbs.org/judge/problem/view/327

題目：給一串數列，和一堆查詢，每次查詢[a, b]之間有多少數字和這區間其他數互質，不強迫在線，多筆測資

N = 200000, Time Limit = 3000/per file

是某區域賽，原本想了個36*N^1.5的做法，可是T了，大概是因為常數再加上多筆測資，只好怒看題解。

主要概念是對每個數字紀錄和他互質最左界可以到哪裡，最右界可以到哪裡。
對於一個區間，我們希望的答案就是 數字左界<=區間左界 且 數字右界>=區間右界 的個數

然後對查詢做離線處理，根據查詢區間左界做排序。

準備一個和線段樹。對於每筆查詢，我們都要先像是維護單調性調整左界，
(1) 當一個數字的左界被左指標指到時， 這個數字可能可以在接下來的查詢出現
(2) 當一個數字的位置被左指標超越時，這個數字不可能在接下來的查詢出現


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

using namespace std;

struct sumbst{ // 0-base
    int base;
    vector<int> tree;
    sumbst(int n){
        base = (1<<(int)(ceil(log2(n+3))))-1;
        tree = vector<int>(2*base+2, 0);
        return;
    }
    void modify(int p, int v){
        p += base+2; tree[p] += v;
        for(p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[(p<<1)^1];
        return;
    }
    int query(int a, int b){
        int ret = 0;
        for(a += base+1, b += base+3;a^b^1;a>>=1, b>>=1){
            if(~a&1) ret += tree[a^1];
            if(b&1) ret += tree[b^1];
        }
        return ret;
    }
};

int arr[200000];

vector<int> rad[200001];

int rn[200000];
vector<int> adat[200000];

void make(int n){
    for(int lx = 0;lx < n;lx++) adat[lx].clear();
    vector<int> ap(200000, 0);
    for(int lx = 0;lx < n;lx++){
        int pos = 0;
        for(int pp : rad[arr[lx]]){
            pos = max(pos, ap[pp]);
            ap[pp] = lx+1;
        }
        adat[pos].push_back(lx);
    }
    ap = vector<int>(200000, n-1);
    for(int lx = n-1;lx >= 0;lx--){
        int pos = n-1;
        for(int pp : rad[arr[lx]]){
            pos = min(pos, ap[pp]);
            ap[pp] = lx-1;
        }
        rn[lx] = pos;
    }
    return;
}

struct qry{
    int x,y,id;
    qry(int _x = 0, int _y = 0, int _id = 0):x(_x), y(_y), id(_id){return;}
};
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int main(){
    {
        vector<int> seive(200000, 1);
        for(int lx = 2;lx < 200000;lx++)
            if(seive[lx])
                for(int ly = 1;ly*lx <= 200000;ly++)
                    rad[ly*lx].push_back(lx), seive[lx*ly] = 0;
    }
    int n, q;
    while(scanf("%d %d", &n, &q) != EOF){
        for(int lx = 0;lx < n;lx++) scanf("%d", arr+lx);
        make(n);
        vector<qry> qrys(q);
        for(int lx = 0;lx < q;lx++){
            int x, y; scanf("%d %d", &x, &y);
            x--, y--;
            qrys[lx] = qry(x, y, lx);
        }
        sort(qrys.begin(), qrys.end());
       
        vector<int> ans(q, 0);
        sumbst bst(n+1);
        int nl = -1;
        for(qry& qq : qrys){
            while(nl < qq.x){
                if(nl != -1){
                    bst.modify(nl, -1);
                    bst.modify(rn[nl]+1, 1);
                }
                nl++;
                for(int id: adat[nl]){
                    bst.modify(id, 1);
                    bst.modify(rn[id]+1, -1);
                }
            }
            ans[qq.id] = bst.query(qq.x, qq.y);
        }
        for(int lx = 0;lx < q;lx++)
            printf("%d\n", ans[lx]);
    }
    return 0;
}

TIOJ 1085 . 三維迷宮問題

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int gx(int a){return (a%50) + 1;}
int gy(int a){return ((a/50)%50) + 1;}
int gz(int a){return ((a/2500)%50) + 1;}
int tv(int x, int y, int z){return (x-1) + (y-1)*50 + (z-1)*2500;}

int tab[52][52][52] = {0};
int vis[52][52][52];

int main(){
    int xx, yy, zz; scanf("%d %d %d", &xx, &yy, &zz);
    memset(vis, -1, sizeof(vis));

    for(int lx = 1;lx <= xx;lx++) for(int ly = 1;ly <= yy;ly++) tab[lx][ly][0] = tab[lx][ly][zz+1] = 1;
    for(int lx = 1;lx <= xx;lx++) for(int lz = 1;lz <= zz;lz++) tab[lx][0][lz] = tab[lx][yy+1][lz] = 1;
    for(int lz = 1;lz <= zz;lz++) for(int ly = 1;ly <= yy;ly++) tab[0][ly][lz] = tab[xx+1][ly][lz] = 1;
   
    for(int lz = 1;lz <= zz;lz++)
        for(int ly = 1;ly <= yy;ly++)
            for(int lx = 1;lx <= xx;lx++)
                scanf("%d", &tab[lx][ly][lz]);
   
    if(tab[1][1][1]){
        puts("no route");
        return 0;
    }
   
    vis[1][1][1] = 0;
    queue<int> que;
    que.push(0);
   
    const int dx[] = {0, 0, 0, 0, 1, -1},
              dy[] = {1, -1, 0, 0, 0, 0},
              dz[] = {0, 0, 1, -1, 0, 0};
   
    while(que.size()){
        int prc = que.front(); que.pop();
        int px = gx(prc), py = gy(prc), pz = gz(prc);
        for(int t = 0;t < 6;t++){
            int nx = px + dx[t], ny = py + dy[t], nz = pz + dz[t];
            if(tab[nx][ny][nz]) continue;
            if(vis[nx][ny][nz]!=-1) continue;
            vis[nx][ny][nz] = prc;
            que.push(tv(nx, ny, nz));
        }
    }
   
    if(vis[xx][yy][zz] == -1){
        puts("no route");
        return 0;
    }
   
    vector<int> hist;
    int now = tv(xx, yy, zz);
    while(now){
        hist.push_back(now);
        now = vis[gx(now)][gy(now)][gz(now)];
    }
   
    printf("(1,1,1)");
    for(int lx = ((int)hist.size())-1;lx>=0;lx--){
        int prc = hist[lx];
        printf("->(%d,%d,%d)",gx(prc),gy(prc),gz(prc));
    }
    puts("");
    return 0;
}

TIOJ 1084 . 一筆畫問題

dfs倒著吐回去


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

using namespace std;

int tab[500][500];
int vcnt[500];
int stk[1025], stkcnt;

void dfs(int a){
    bool flag = false;
    for(int lx = 0;lx < 500;lx++){
        if(tab[a][lx]){
            tab[a][lx]--;
            tab[lx][a]--;
            dfs(lx);
            flag = true;
            stk[stkcnt++] = a+1;
        }
    }
    if(!flag) stk[stkcnt++] = a+1;
    return;
}

int main(){
    int c;
    while(scanf("%d", &c)&&c){
        memset(tab, 0, sizeof(tab));
        memset(vcnt, 0, sizeof(vcnt));
        stkcnt = 0;

        while(c--){
            int a, b; scanf("%d %d", &a, &b); a--, b--;
            tab[a][b]++, tab[b][a]++;
            vcnt[a]++, vcnt[b]++;
        }
        bool check = true;
        for(int lx = 0;lx < 500 and check;lx++)
            check = not (vcnt[lx]&1);
       
        int sm = -1;
        if(check) while(!vcnt[++sm]);
        else  while(!(vcnt[++sm]&1));
        dfs(sm);

        for(int lx = stkcnt-1;lx>=0;lx--)
            if(lx == stkcnt-1 or stk[lx] != stk[lx+1])
                printf("%d\n", stk[lx]);
        puts("");
    }
    return 0;
}