藍雪的Online Judge日誌

/**************************************************************

    Problem: 1031

    User: mudream4869

    Language: C++

    Result: Accepted

    Time:1296 ms

    Memory:3544 kb

****************************************************************/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

void dump(int n, int* arr){

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

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

    puts("");

    return;

}

char buf[200010], ret[200010];

int rnk[2][200000];

int sa[200000];

struct CMP{

    int* rk;

    int n, len;

    bool operator()(const int& i, const int& j){

        if(rk[i] != rk[j]) return rk[i] < rk[j];

        int a = (i+n < len) ? rk[i+n] : -1;

        int b = (j+n < len) ? rk[j+n] : -1;

        return a < b;

    }

};

void build_sa(){

    int len = strlen(buf);

    int now = 0;

    for(int lx = 0;lx < len;lx++) rnk[0][lx] = buf[lx];

    for(int lx = 0;lx < len;lx++) sa[lx] = lx;

    for(int l = 2; l <= len;l<<=1){

        CMP cmp = {rnk[now], l>>1, len};

        sort(sa, sa+len, cmp);

        rnk[now^1][sa[0]] = 0;

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

            rnk[now^1][sa[lx]] = rnk[now^1][sa[lx-1]] + cmp(sa[lx-1], sa[lx]);

        now ^= 1;

    }

    return;

}

int main(){

    scanf("%s", buf);

    int len = strlen(buf);

    for(int lx = len;lx>=0;lx--) buf[lx+len] = buf[lx];

    build_sa();

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

        if(sa[lx] >= len) continue;

        printf("%c", buf[sa[lx]+len-1]);

    }

    puts("");

    return 0;

}

2015年5月27日星期三

Codeforces Round #305 (Div. 1), problem: (A) Mike and Frog,

Case炸了QAQ

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

using namespace std;

typedef long long int int64;

int64 get64(){
    int inp; scanf("%d", &inp);
    return inp;
}

int64 m;
void make(int64* lst, int64 x, int64 y, int64& r, int64& l, int64 st){
    lst[st] = 1;
    int64 step = 1;
    for(;;){
        st = (x*st + y)%m;
        step++;
        if(lst[st] != 0){
            l = lst[st]-1;
            r = step-lst[st];
            break;
        }
        lst[st] = step;
    }
    return;
}

int64 sp1[1000000] = {0}, sp2[1000000] = {0};

int64 inv(int64 a, int64 mm){
    for(int64 lx = 1;lx <= mm-1;lx++)
        if((a*lx)%mm == 1)
            return lx;
    return 0;
}

int main(){
    m = get64();
    int64 h1 = get64(), a1 = get64(), x1 = get64(), y1 = get64();
    int64 h2 = get64(), a2 = get64(), x2 = get64(), y2 = get64();
    int64 l1, l2, r1, r2;
    make(sp1, x1, y1, r1, l1, h1);
    make(sp2, x2, y2, r2, l2, h2);
    
    if(sp1[a1] == 0 or sp2[a2] == 0){ puts("-1"); return 0; }

    int64 la1 = sp1[a1], la2 = sp2[a2];
    int64 t1, t2;
    t1 = (la1 <= l1) ? 0:r1;
    t2 = (la2 <= l2) ? 0:r2;

    if(t1 == 0 and t2 == 0){ printf("%I64d\n", la1 == la2 ? (la1-1) : -1); return 0; }
    
    int64 gg = (t1 and t2) ? __gcd(t1, t2) : t1+t2;

    if((la1-la2)%gg != 0){ puts("-1"); return 0;}
    
    int64 dl = (la1-la2)/gg, d1 = t1/gg, d2 = t2/gg;    

    int64 cal = d2 ? (-inv(d1, d2)*dl)%d2 : (-dl);
    
    if(d2 == 0 and cal < 0){
        puts("-1");
        return 0;
    }
     
    if(cal < 0) cal += d2;
    while(d1*cal+dl<0) cal += d2;

    printf("%I64d\n", t1*cal+la1-1);

    return 0;
}

Codeforces Round #305 (Div. 1), problem: (B) Mike and Feet

用線段樹加減暴力尻過

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

using namespace std;

typedef long long int int64;

void dump(int n, int* arr){
    for(int lx = 0;lx < n;lx++)
        printf("%d ", arr[lx]);
    puts("");
    return;
}

struct minbst{
    vector<int> tree;
    int base;
    minbst(int n, int* arr){
        base = (1<<(int)(ceil(log2(n+3))))-1;
        tree = vector<int>(base*2+2, 2000000000);
        for(int lx = 0;lx<n;lx++)
            tree[lx+base+2] = arr[lx];
        for(int lx = base;lx;lx--)
            tree[lx] = min(tree[lx<<1], tree[(lx<<1)^1]);
        return;
    }
    int query(int a, int b){
        int ans = 2000000000;
        for(a += base+1, b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) ans = min(ans, tree[a^1]);
            if(b&1) ans = min(ans, tree[b^1]);
        }
        return ans;
    }
};


int n;
int arr[200000];
int bas[200000] = {0};
int poi[200001] = {0};
int ans[200001];
int main(){
    scanf("%d", &n);
    for(int lx = 0;lx < n;lx++)
        scanf("%d", arr+lx);

    //dump(n, arr);

    for(int _ = 0; _ < 2;_++){
        minbst bst(n, arr);
        for(int lx = 0;lx < n;lx++){
            int ll = 0, rr = n-lx;
            while(ll < rr-1){
                int test = (ll+rr)>>1;
                if(bst.query(lx, lx+test) >= arr[lx])
                    ll = test;
                else
                    rr = test;
            }
            bas[lx] += ll;
        }
        //dump(n, bas);
        reverse(arr, arr+n);
        reverse(bas, bas+n);
    }

    for(int lx = 0;lx < n;lx++)
        poi[bas[lx]+1] = max(arr[lx], poi[bas[lx]+1]);

    //dump(n, poi);
    
    int mm = 0;
    for(int lx = n;lx;lx--){
        mm = max(mm, poi[lx]);
        ans[lx-1] = mm;
    }

    dump(n, ans);
    
    return 0;

}

2015年5月21日星期四

TIOJ 1798 . Can You Arrive?

LCA + DisjointSet

一個樹上路徑們並查的故事。

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

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

class bst{
public:
bst(int n, int* _val){
base = (1<<(int)(ceil(log2(n+3))))-1;
tree = new int[base*2+2];
val = new int[base+2];
for(int lx = 0;lx < base+1;lx++) val[lx] = 10000000, tree[base+lx+1]=lx;
for(int lx = 0;lx < n;lx++) val[lx+1] = _val[lx];
for(int lx = base;lx;lx--){
if(val[tree[lx*2]] > val[tree[lx*2+1]])
tree[lx]= tree[lx*2+1];
else
tree[lx] = tree[lx*2];
}
return;
}
int query(int a, int b){
a++, b++;
int ret = tree[base+a+1];
for(a+=base, b+=base+2;a^b^1;a>>=1, b>>=1){
if(~a&1) if(val[ret] > val[tree[a^1]]) ret = tree[a^1];
if(b&1) if(val[ret] > val[tree[b^1]]) ret = tree[b^1];
}
return ret-1;
}
private:
int base;
int* tree;
int* val;
};

VVI graph;
int ptr;
int hei[1000000];
int arr[2000000];
int harr[2000000];
int ac1[1000000];
int ato[1000000][2];
bst* lca_bst;

void dfs(int fa, int nd){
//printf("visit at %d\n", nd+1);
ac1[nd] = fa, hei[nd] = hei[fa]+1;
ato[nd][0] = ptr; arr[ptr] = nd; harr[ptr++] = hei[nd];
for(int lx = 0;lx < graph[nd].size();lx++){
if(graph[nd][lx] == fa) continue;
dfs(nd, graph[nd][lx]);
ato[nd][1] = ptr; arr[ptr] = nd; harr[ptr++] = hei[nd];
}
ato[nd][1] = ptr; arr[ptr] = nd; harr[ptr++] = hei[nd];
return;
}

void build(int n){
ptr = 0, hei[0] = 0; dfs(0, 0);

/*for(int lx = 0;lx < ptr;lx++)
printf("%02d ", arr[lx]+1);
puts("");

for(int lx = 0;lx < ptr;lx++)
printf("%02d ", harr[lx]);
puts("");*/

lca_bst = new bst(ptr, harr);
return;
}

int lca(int a, int b){
int ll = min(ato[a][0], ato[b][0]), rr = max(ato[a][1], ato[b][1]);
//printf("qlca(%d %d)\n", ll, rr);
return arr[lca_bst->query(ll, rr)];
}

struct path{ int h, x, y; }paths[2000000];
bool operator<(path a, path b){return a.h<b.h;}

int fat[1000000];
int qfat(int a){return fat[a]==a ? a: fat[a]=qfat(fat[a]);}
void join(int a, int b){fat[qfat(a)] = qfat(b); return;}

int main(){
int n, m, k, q;
scanf("%d %d %d %d", &n, &m, &k, &q);
graph = VVI(n, VI());
for(int lx = 0;lx < m;lx++){
int a, b; scanf("%d %d", &a, &b); a--, b--;
graph[a].push_back(b);
graph[b].push_back(a);
//printf("%d <-> %d\n", a+1, b+1);
}

build(n);

for(int lx = 0;lx < k;lx++){
int a, b; scanf("%d %d", &a, &b); a--, b--;
int c = lca(a, b);
//printf("lca(%d %d) = %d\n", a+1, b+1, c+1);
paths[lx*2].h = paths[lx*2+1].h = hei[c];
paths[lx*2].x = paths[lx*2+1].x = c;
paths[lx*2].y = a, paths[lx*2+1].y = b;
}

sort(paths, paths+2*k);

for(int lx = 0;lx < n;lx++) fat[lx] = lx;

for(int lx = 0;lx < 2*k;lx++){
int y = paths[lx].y, x = paths[lx].x;
while(qfat(y) != qfat(x)){
join(x, y);
y = ac1[y];
}
}

while(q--){
int a, b; scanf("%d %d", &a, &b); a--, b--;
printf("%d\n", qfat(a) == qfat(b));
}

return 0;
}

TIOJ 1799 . Richmen

環狀分錢問題，有點好奇推廣

0. 水母？
1. 仙人掌？
2. 2D？
3. 平面圖？
3. 一般圖？

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

using namespace std;

typedef long long int int64;

int64 arr[5000010];

int main(){
int64 n; scanf("%lld", &n);
int64 avg = 0;
arr[0] = 0;
for(int lx = 1;lx <= n;lx++){
scanf("%lld", arr+lx);
avg += arr[lx];
arr[lx] += arr[lx-1];
}
avg /= n;
for(int lx = 1;lx < n;lx++)
arr[lx] -= lx*avg;

sort(arr, arr+n);

n--;
for(int lx = n;lx >= 1;lx--)
arr[lx] = arr[lx]-arr[lx-1];

int64 ans = 0;
for(int lx = 1;lx <= n;lx++){
if(lx <= n/2) ans += lx*arr[lx];
else ans += (n-lx+1)*arr[lx];
}

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

2015年5月28日 星期四

BZOJ 1031: [JSOI2007]字符加密Cipher

2015年5月27日 星期三