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

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