這個(gè)月內(nèi)的一些有趣的題

Letter Array

http://codeforces.com/gym/100482/problem/C
tag: 線段樹加懶人標(biāo)記O(mlogn)或前綴和 O(Σ(r-l+1))

題解:

1. 因?yàn)榕判蛑挥绊憛^(qū)間[l,r]的前綴和，其他不影響，所以只更改[l,r]的前綴和就可以了。
2. 但我一看到區(qū)間修改就想到線段樹加懶人標(biāo)記了，所以自己就實(shí)現(xiàn)了個(gè)。
3. 需要注意的是排序操作，可能把一個(gè)結(jié)點(diǎn)對(duì)應(yīng)區(qū)間的元素值移動(dòng)到與它毫不相關(guān)的區(qū)間結(jié)點(diǎn)上，所以需要先查詢一次統(tǒng)計(jì)元素值，再找到對(duì)應(yīng)區(qū)間挨個(gè)倒出來。

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1e5+1e3;
#define dbg 1
struct Seg{
    int cnt[27], sz;
    bool srt;
    Seg() {
        clr();
        srt = false;
        sz = 0;
    }
    void clr() {
        memset(cnt, 0, sizeof(cnt));
    }
    Seg operator + (const Seg& b) {
        Seg c;
        for(int i=0; i<26; ++i) {
            c.cnt[i] = cnt[i]+b.cnt[i];
            c.sz += c.cnt[i];
        }
        return c;
    }
}seg[MAXN<<2], ans;
char s[MAXN];
int len, l, r;
void build(int id, int tl, int tr) {
    seg[id].sz = tr-tl+1;
    seg[id].clr();
    if(tl==tr) {
        ++seg[id].cnt[s[tl]-'A'];
        return;
    }
    int tm=tl+tr>>1;
    build(id<<1, tl, tm);
    build(id<<1|1, tm+1, tr);
    seg[id] = seg[id<<1]+seg[id<<1|1];
}
void pushdown(int id) {
    int lch=id<<1;
    int rch=id<<1|1;
    int lsz = seg[lch].sz;
    int rsz = seg[rch].sz;
    seg[lch].clr();
    seg[rch].clr();
    seg[lch].srt=seg[rch].srt=true;
    for(int i=0; i<26&&lsz; ++i) {
        if(lsz>=seg[id].cnt[i]) 
            lsz -= (seg[lch].cnt[i]=seg[id].cnt[i]);
        else {
            seg[lch].cnt[i]=lsz;
            lsz=0;
        }
    }
    for(int i=25; i>-1&&rsz; --i) {
        if(rsz>=seg[id].cnt[i]) 
            rsz -= (seg[rch].cnt[i]=seg[id].cnt[i]);
        else {
            seg[rch].cnt[i]=rsz;
            rsz=0;
        }
    }
}
void Sort(int id, int tl, int tr) {
    if(l<=tl&&tr<=r) {
        int sz = seg[id].sz;
        seg[id].clr();
        for(int i=0; i<26&&sz; ++i) {
            if(sz>=ans.cnt[i]) {
                sz -= (seg[id].cnt[i]=ans.cnt[i]);
                ans.cnt[i] = 0;
            }
            else {
                ans.cnt[i] -= (seg[id].cnt[i] = sz);
                sz = 0;
            }
        }
        seg[id].srt = true;
        return;
    }
    if(tl<tr&&seg[id].srt)
        pushdown(id);
    int tm = tl+tr>>1;
    if(tl<=r&&tm>=l) Sort(id<<1, tl, tm);
    if(tm<r&&tr>=l) Sort(id<<1|1, tm+1, tr);
    seg[id] = seg[id<<1]+seg[id<<1|1];
}
void query(int id, int tl, int tr) {
    if(l<=tl&&tr<=r) {
        ans = ans+seg[id];
        return;
    }
    if(tl<tr&&seg[id].srt)
        pushdown(id);
    int tm = tl+tr>>1;
    if(tl<=r&&tm>=l) query(id<<1, tl, tm);
    if(tm<r&&tr>=l) query(id<<1|1, tm+1, tr);
}
int main() {
    int t, kcase=0;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s);
        len = strlen(s);
        build(1,0,len-1);
        int m;scanf("%d", &m);
        printf("Case #%d:\n", ++kcase);
        while(m--) {
            char cmd[3];
            scanf("%s%d%d", cmd, &l, &r);
            ans.clr();
            if(cmd[0]=='g') {
                query(1, 0, len-1);
                for(int i=0; i<26; ++i)
                {
                    if(i) putchar(' ');
                    printf("%d", ans.cnt[i]);
                }
                puts("");
            }
            else {
                query(1, 0, len-1);
                Sort(1, 0, len-1);
            }
        }
    }
    return 0;
}

Training Camp

https://vjudge.net/problem/Gym-100676G
tag: dp
題解:

1. 印象非常深刻，個(gè)人想著用拓?fù)渑判蚣迂澬牡霓k法，找到當(dāng)前可以選的值最小的點(diǎn)，把他刪去，依次下去.但提交后一直WA, 補(bǔ)題時(shí)也是如此，搞得都想日站了。
2. 后來想到一點(diǎn)，自己的解法不一定是最優(yōu)的，比如數(shù)據(jù)

1
3 1
a 1
b 3
c 4
c -> a

最佳排列為 c, a, b 而非 b, c, a.

Problem Arrangement

https://vjudge.net/problem/ZOJ-3777
tag: dp
題解：
1.這回長記性了，遇到求排列權(quán)值的首先想的是dp;
2.要求權(quán)值>=m的方法數(shù)，用的是一個(gè)很經(jīng)典的套路。

8244525.jpg

Paint the Grid Again

https://vjudge.net/problem/ZOJ-3780
tag: 拓?fù)渑判?br> 題解：一道拓?fù)渑判虻慕?，但不知道為什么我的逆推法不行?/p>