Codeforces Round #306 (Div. 2), problem: (D) Regular Bridge

只要是偶數，就不可能，因為k-1 + n*k是奇數無法被2整除
然後 就是構造奇數case

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

typedef long long int int64;

void ff(int st, int k){
    for(int lx = 1;lx <= k-1;lx++) printf("%d %d\n", st, st+lx);
    for(int lx = 1;lx <= k-1;lx++)
        for(int ly = k;ly <= 2*k-2;ly++)
            printf("%d %d\n", st+lx, st+ly);
    for(int lx = k;lx <= 2*k-2;lx+=2)
        printf("%d %d\n", st+lx, st+lx+1);
    return;
}

int main(){
    int k; scanf("%d", &k);
    if(k%2 == 0){
        puts("NO");
        return 0;
    }
    puts("YES");
    printf("%d %d\n", 4*k-2, (k-1)*(2*k+1)+1);
    printf("%d %d\n", 1, 2*k);
    ff(1, k);
    ff(2*k, k);
    return 0;
}

Codeforces Round #306 (Div. 2), problem: (C) Divisibility by Eight

因為最多只需要三個，所以直接搜。

比較好奇假如是'k'倍數的話要如何處理。

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

typedef long long int int64;

int gg(char a){return a-'0';}

int main(){
    char buf[1000]; scanf("%s", buf);
    int n = strlen(buf);
    for(int lx = n-1;lx >=0;lx--)
        buf[lx+2] = buf[lx];
    buf[1] = '0', buf[0] = '0';
    n += 2;
    for(int lx = 0;lx < n;lx++){
        for(int ly = lx+1;ly < n;ly++){
            for(int lz = ly+1;lz < n;lz++){
                int test = gg(buf[lx])*100 + gg(buf[ly])*10 + gg(buf[lz]);
                if(test%8 == 0){
                    printf("YES\n%d\n", test);
                    return 0;
                }
            }
        }
    }
    puts("NO");
    return 0;
}

Codeforces Round #306 (Div. 2), problem: (B) Preparing Olympiad

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

typedef long long int int64;

int main(){
    int n, l, r, x;
    int cc[20];
    scanf("%d %d %d %d", &n, &l, &r, &x);
    for(int lx = 0;lx < n;lx++) scanf("%d", cc+lx);
    int cnt = 0;
    for(int sts = 0;sts < (1<<n);sts++){
        int pmin = 1000000000, pmax = -1, pcnt = 0, psum = 0;
        for(int lx = 0;lx < n;lx++)
            if(sts&(1<<lx))
                pcnt++, pmax = max(pmax, cc[lx]), pmin = min(pmin, cc[lx]), psum += cc[lx];
        cnt += (pcnt >= 2) and (l <= psum) and (psum <= r) and (x <= pmax-pmin);
    }
    printf("%d\n", cnt);
    return 0;
}

Codeforces Round #306 (Div. 2), problem: (A) Two Substrings

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

using namespace std;

typedef long long int int64;

char buf[100001];
vector<int> aa, bb;

int main(){
    scanf("%s", buf);
    for(int lx = 0; buf[lx+1] != 0;lx++){
        if(buf[lx] == 'A' and buf[lx+1] == 'B') aa.push_back(lx);
        if(buf[lx+1] == 'A' and buf[lx] == 'B') bb.push_back(lx);
    }
    
    if(aa.size() == 0 or bb.size() == 0){
        puts("NO");
        return 0;
    }

    if(aa.size() + bb.size() >= 4){
        puts("YES");
        return 0;
    }
    
    bool ok = false;
    if(aa.size() + bb.size() == 2) ok = abs(aa[0]-bb[0]) >= 2;
    else{
        if(aa.size() == 1) ok = abs(bb[0]-bb[1]) >= 3;
        else ok = abs(aa[0]-aa[1]) >= 3;
    }

    puts(ok ? "YES" : "NO");

    return 0;
}

TIOJ 1224 . 矩形覆蓋面積計算

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

using namespace std;

typedef long long int int64;

struct bst{ // 0-base
    vector<int> ncnt;
    vector<int> cnt;
    vector<int> col;
    int base;
    bst(int n){
        base = (1<<(int)(ceil(log2(n+2))))-1;
        ncnt = vector<int>(2*base+2, 0);
        cnt = vector<int>(2*base+2, 0);
        col = vector<int>(2*base+2, 0);
        for(int lx = 0;lx < n;lx++) cnt[base+lx+2] = 1;
        for(int lx = base;lx;lx--) cnt[lx] = cnt[lx<<1] + cnt[(lx<<1)^1];
        return;
    }

    void modify(int a, int b, int v){
        int nodes[30]; int nc = 0;
        for(a+=base+1, b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) nodes[nc++] = a^1;
            if(b&1) nodes[nc++] = b^1;
        }
        for(int lx = 0;lx < nc;lx++){
            int nd = nodes[lx];
            //printf("%d -> %d\n", nd, v);
            ncnt[nd] += v;
            if(ncnt[nd] == 0){
                // 1->0
                int det = cnt[nd]-col[nd];
                for(int prc = nd>>1;prc;prc>>=1){
                    col[prc] -= det;
                    if(ncnt[prc]) break;
                }
            }else if(ncnt[nd] == 1 and v == 1){
                // 0->1
                int det = cnt[nd]-col[nd];
                for(int prc = nd>>1;prc;prc>>=1){
                    col[prc] += det;
                    if(ncnt[prc]) break;
                }
            }
        }
        return;
    }

    int query()const{
        return col[1];
    }
};

struct qry{int l, r, v, x; qry(int _l = 0, int _r = 0, int _v = 0, int _x = 0):l(_l),r(_r),v(_v),x(_x){return;}}qrys[200000];
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++){
        int l, r, d, u; scanf("%d %d %d %d", &l, &r, &d, &u);
        qrys[lx<<1] = qry(d,u-1,1,l);
        qrys[(lx<<1)^1] = qry(d,u-1,-1,r);
    }
    sort(qrys, qrys+2*n);
    int64 ans = 0;
    int org = 0;
    bst BST(1000000);
    for(int lx = 0;lx < 2*n;lx++){
        //printf("%d %d %d %d\n", qrys[lx].x, qrys[lx].l, qrys[lx].r, qrys[lx].v);
        ans += ((int64)BST.query())*((int64)(qrys[lx].x-org));
        //printf("%lld\n", ans);
        org = qrys[lx].x;
        BST.modify(qrys[lx].l, qrys[lx].r, qrys[lx].v);
    }
    printf("%lld\n", ans);
    return 0;
}

Looksery Cup 2015, problem: (G) Happy Line

pi < pj => ai+i < aj+j
我覺得我真太廢惹，為啥比賽時弄不出來啦QAQQQ

--聽說寫結論題要寫證明，那就留個證明--

讓a[i]為該陣列，p[i]是a[i]移動後的位置
則p[i] < p[j] if and only if a[i]-p[i]+i < a[j]-p[j]+j

to pf: p[i] < p[j] if and only if a[i]+i < a[j]+j

左到右：  o.k.

右到左：

assume p[i] >= p[j]
~> a[i]-p[i]+i >= a[j]-p[j]+j
~>a[i]+i >= a[j]+j  -X-

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

using namespace std;


int ans[200000];
struct pack{
    int val;
    int index;
}ps[200000];

bool operator<(const pack& pa, const pack& pb){
    return pa.val < pb.val;
}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++){
        int inp; scanf("%d", &inp);
        ps[lx].val = inp + lx;
        ps[lx].index = lx;
    }
    sort(ps, ps+n);
    bool check = true;
    for(int lx = 1;lx < n and check;lx++)
        check = ps[lx].val != ps[lx-1].val;
    if(not check){
        puts(":(");
        return 0;
    }

    for(int lx = 0;lx < n;lx++)
        ans[ps[lx].index] = ps[lx].val-lx;
    sort(ans, ans+n);
    for(int lx = 0;lx < n;lx++)
        printf("%d ", ans[lx]);
    puts("");
    return 0;
}

Looksery Cup 2015, problem: (H) Degenerate Matrix

code好久qaq

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

using namespace std;

//  a-p b-q   <= t
//  c-r d-s
//  a-t <= p <= t+a

const long double inf = 1e27;

struct pr{long double l, r; pr(long double _l = 0, long double _r = 0):l(_l), r(_r){return;}};

pr operator*(const pr& p1, const pr& p2){
    long double par[4] = {p1.l*p2.l, p1.r*p2.r, p1.l*p2.r, p1.r*p2.l};
    pr ret(inf, -inf);
    ret.l = min(ret.l, par[0]), ret.r = max(ret.r, par[0]);
    ret.l = min(ret.l, par[1]), ret.r = max(ret.r, par[1]);
    ret.l = min(ret.l, par[2]), ret.r = max(ret.r, par[2]);
    ret.l = min(ret.l, par[3]), ret.r = max(ret.r, par[3]);
    return ret;
}

bool check(pr p1, pr p2){
    if(p1.l > p2.l) swap(p1, p2);
    return p1.r >= p2.l;
}

int getint(){ int r; scanf("%d", &r); return r;}

int main(){
    long double a, b, c, d;
    a = getint(); b = getint(); c = getint(); d = getint();
    long double tmin = 0, tmax = max(max(max(fabs(a), fabs(b)), fabs(c)), fabs(d));
    while(tmax-tmin >= 1e-9){
        long double tmid = (tmax+tmin)/(long double)2;
        //printf("[%.9f %.9f %.9f]\n", (double)tmin, (double)tmax, (double)tmid);
        pr rg1 = pr(a-tmid, a+tmid)*pr(d-tmid, d+tmid);
        pr rg2 = pr(b-tmid, b+tmid)*pr(c-tmid, c+tmid);
        if(check(rg1, rg2))
            tmax = tmid;
        else
            tmin = tmid;
    }
    printf("%.9lf\n", (double)tmax);
    return 0;
}

SPOJ BOBERT - Stick values

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

using namespace std;

typedef long long int int64;

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

const int64 INF = 1000000001;

struct maxspt{
    VVI maxarr;
    maxspt(int n, int64* arr){
        int k = (int)log2((double)n+0.2);
        maxarr = VVI(n, VI(k+1));
        for(int lx = 0;lx < n;lx++) maxarr[lx][0] = arr[lx];
        for(int lx = 1;lx <= k;lx++)
            for(int ly = 0;ly+(1<<(lx-1)) < n;ly++)
                maxarr[ly][lx] = max(maxarr[ly][lx-1], maxarr[ly+(1<<(lx-1))][lx-1]);
        return;
    }
    int query(int a, int b){
        int k = (int)(log2(b-a+1.2));
        return max(maxarr[a][k], maxarr[b-(1<<k)+1][k]);
    }
};

struct minspt{
    VVI minarr;
    minspt(int n, int64* arr){
        int k = (int)log2((double)n+0.2);
        minarr = VVI(n, VI(k+1));
        for(int lx = 0;lx < n;lx++) minarr[lx][0] = arr[lx];
        for(int lx = 1;lx <= k;lx++)
            for(int ly = 0;ly+(1<<(lx-1)) < n;ly++)
                minarr[ly][lx] = min(minarr[ly][lx-1], minarr[ly+(1<<(lx-1))][lx-1]);
        return;
    }
    int query(int a, int b){
        int k = (int)(log2(b-a+1.2));
        return min(minarr[a][k], minarr[b-(1<<k)+1][k]);
    }
};

int64 dp[1<<20] = {0};
bool vis[1<<20] = {0};
int64 stl[30];
int64 arr[100000];


int main(){
    int n, s;
    scanf("%d", &n);
    for(int lx = 0;lx < n;lx++) scanf("%lld", arr+lx);

    maxspt maxtb(n, arr);
    minspt mintb(n, arr);

    scanf("%d", &s);
    for(int lx = 0;lx < s;lx++) scanf("%lld", stl+lx);

    queue<int> que;
    que.push(0);
    while(que.size()){
        int sts = que.front(); que.pop();
        int64 len = 0; for(int lx = 0;lx < s;lx++) if(sts&(1<<lx)) len += stl[lx];
        for(int lx = 0;lx < s;lx++){
            if(sts&(1<<lx)) continue;
            int nsts = sts|(1<<lx);
            if(stl[lx]) dp[nsts] = max(dp[nsts], dp[sts] + ((int64)(maxtb.query(len, len+stl[lx]-1) - mintb.query(len, len+stl[lx]-1)))*stl[lx]);
            else dp[nsts] = max(dp[nsts], dp[sts]);
            if(!vis[nsts]){
                que.push(nsts);
                vis[nsts] = 1;
            }
        }
    }
    printf("%lld\n", dp[(1<<s)-1]);
    return 0;
}

Looksery Cup 2015, problem: (D) Haar Features

有O(n^2) 沒好好推就是

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

using namespace std;

int mm[110][110];
int tmp[110][110];

void draw(int a, int b, int v){
    for(int lx = 0;lx < a;lx++)
        for(int ly = 0;ly < b;ly++)
            tmp[lx][ly] += v;
    return;
}

void prt(int a, int b){
    for(int lx = 0;lx < a;lx++){
        for(int ly  = 0;ly < b;ly++)
            printf("%c", tmp[lx][ly] ? 'W':'B');
        puts("");
    }
    return;
}

int main(){
    int n, m; scanf("%d %d", &n, &m);
    for(int lx = 0;lx < n;lx++){
        char buf[200]; scanf("%s", buf);
        for(int ly = 0;ly < m;ly++)
            mm[lx][ly] = (buf[ly] == 'W');
    }
    int cnt = 1;
    for(int lx = 0;lx < n;lx++)
        for(int ly = 0;ly < m;ly++)
            tmp[lx][ly] = mm[n-1][m-1];
    //prt(n, m);
    for(int cc = n+m-3;cc>=0;cc--){
        for(int x = 0;x <= cc;x++){
            int y = cc-x;
            if(x >= n or y >= m) continue;
            if(tmp[x][y] != mm[x][y]){
                draw(x+1, y+1, mm[x][y]-tmp[x][y]), cnt++;
                //printf("draw at %d %d\n", x, y);
                //prt(n, m);
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}