這個(gè)月內(nèi)的一些有趣的題
Letter Array
http://codeforces.com/gym/100482/problem/C
tag: 線段樹加懶人標(biāo)記O(mlogn)或前綴和 O(Σ(r-l+1))
題解:
- 因?yàn)榕判蛑挥绊憛^(qū)間[l,r]的前綴和铐然，其他不影響，所以只更改[l,r]的前綴和就可以了礁鲁。
- 但我一看到區(qū)間修改就想到線段樹加懶人標(biāo)記了，所以自己就實(shí)現(xiàn)了個(gè)农渊。
- 需要注意的是排序操作固阁，可能把一個(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
題解:
- 印象非常深刻其做，個(gè)人想著用拓?fù)渑判蚣迂澬牡霓k法友扰，找到當(dāng)前可以選的值最小的點(diǎn)彤叉，把他刪去，依次下去.但提交后一直WA, 補(bǔ)題時(shí)也是如此村怪，搞得都想日站了。
- 后來想到一點(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.這回長(zhǎng)記性了，遇到求排列權(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>
