[JSOI2009]游戏 题解
题目地址:洛谷:【P4055】[JSOI2009]游戏 – 洛谷、BZOJ:P …
May all the beauty be blessed.
题目地址:洛谷:【P2805】[NOI2009]植物大战僵尸 – 洛谷、BZOJ:Problem 1565. — [NOI2009]植物大战僵尸
Plants vs. Zombies(PVZ)是最近十分风靡的一款小游戏。Plants(植物)和Zombies(僵尸)是游戏的主角,其中Plants防守,而Zombies进攻。该款游戏包含多种不同的挑战系列,比如Protect Your Brain、Bowling等等。其中最为经典的,莫过于玩家通过控制Plants来防守Zombies的进攻,或者相反地由玩家通过控制Zombies对Plants发起进攻。
现在,我们将要考虑的问题是游戏中Zombies对Plants的进攻,请注意,本题中规则与实际游戏有所不同。游戏中有两种角色,Plants和Zombies,每个Plant有一个攻击位置集合,它可以对这些位置进行保护;而Zombie进攻植物的方式是走到植物所在的位置上并将其吃掉。
游戏的地图可以抽象为一个N行M列的矩阵,行从上到下用0到N–1编号,列从左到右用0到M–1编号;在地图的每个位置上都放有一个Plant,为简单起见,我们把位于第r行第c列的植物记为Pr, c。
Plants分很多种,有攻击类、防守类和经济类等等。为了简单的描述每个Plant,定义Score和Attack如下:
Score[Pr, c]
Zombie击溃植物Pr, c可获得的能源。若Score[Pr, c]为非负整数,则表示击溃植物Pr, c可获得能源Score[Pr, c],若为负数表示击溃Pr, c需要付出能源 -Score[Pr, c]。
Attack[Pr, c]
植物Pr, c能够对Zombie进行攻击的位置集合。
Zombies必须从地图的右侧进入,且只能沿着水平方向进行移动。Zombies攻击植物的唯一方式就是走到该植物所在的位置并将植物吃掉。因此Zombies的进攻总是从地图的右侧开始。也就是说,对于第r行的进攻,Zombies必须首先攻击Pr, M-1;若需要对Pr, c(0≤c<M-1)攻击,必须将Pr,M-1, Pr, M-2 … Pr, c+1先击溃,并移动到位置(r, c)才可进行攻击。
在本题的设定中,Plants的攻击力是无穷大的,一旦Zombie进入某个Plant的攻击位置,该Zombie会被瞬间消灭,而该Zombie没有时间进行任何攻击操作。因此,即便Zombie进入了一个Plant所在的位置,但该位置属于其他植物的攻击位置集合,则Zombie会被瞬间消灭而所在位置的植物则安然无恙(在我们的设定中,Plant的攻击位置不包含自身所在位置,否则你就不可能击溃它了)。
Zombies的目标是对Plants的阵地发起进攻并获得最大的能源收入。每一次,你可以选择一个可进攻的植物进行攻击。本题的目标为,制定一套Zombies的进攻方案,选择进攻哪些植物以及进攻的顺序,从而获得最大的能源收入。
你在玩植物大战僵尸游戏,你操控僵尸破坏植物,破坏一棵植物要么付出代价要么获得收益,分别以正负权体现。植物的攻击力无穷,也就是说,当僵尸刚进入它能攻击的格子中时会被瞬间干掉;僵尸的攻击力也无穷,也就是说它没被干掉的时候能瞬间干掉一棵植物。求一种进攻方法,使得获得的权值最大。
输入格式:
输入文件pvz.in的第一行包含两个整数N, M,分别表示地图的行数和列数。
接下来N×M行描述每个位置上植物的信息。第r×M + c + 1行按照如下格式给出植物Pr, c的信息:第一个整数为Score[Pr, c], 第二个整数为集合Attack[Pr, c]中的位置个数w,接下来w个位置信息(r’, c’),表示Pr, c可以攻击位置第r’ 行第c’ 列。
输出格式:
输出文件pvz.out仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。
输入样例#1:
3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0
输出样例#1:
25
约20%的数据满足1 ≤ N, M ≤ 5;
约40%的数据满足1 ≤ N, M ≤ 10;
约100%的数据满足1 ≤ N ≤ 20,1 ≤ M ≤ 30,-10000 ≤ Score ≤ 10000
首先,这是一个最大权闭合子图的模型,即,建立源→负权点,正权点→汇,保护点→被保护点的网络,其中源汇连边边权为点权绝对值,保护关系边权无限。这样,正权和-最小割就是答案。但是如果正负权点和源汇的建边关系反过来了会WA,这是由于一个正权点保护一个负权点显然是不优的,这些边的存在没有意义,更应该让负权点→正权点的边参与到流中。
信心满满的你写了一个Dinic,然后发现不对劲,这个图上有环!注意到本题提供了一个隐藏条件,即一个植物也可以保护它后面的植物,如果它后面的一个植物也保护了它,那它就无敌了。我们拓扑找环,然后把环上的点连同这些点可以到达的点全删了,然后把剩下的图当网络跑最大流就是正解。
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
return res * neg;
}
const int MAXN = 605, INF = 1e9;
int n, m;
struct Edge {
int to, cap, nxt;
} gra[1000005], gra2[1000005];
int head[MAXN], head2[MAXN], deg[MAXN], tot, tot2;
inline void addedge(int u, int v, int cap) {
gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}
inline void addedge2(int u, int v) {
gra2[tot2] = Edge {v, 0, head2[u]}; head2[u] = tot2++;
deg[v]++;
}
bool del[MAXN];
void dfs_del(int u) {
del[u] = true;
for(int i = head2[u]; ~i; i = gra2[i].nxt) {
int v = gra2[i].to;
if(!del[v]) dfs_del(v);
}
}
inline void toposort() {
std::queue<int> que;
for(int i = 1; i <= n * m; i++) {
if(!deg[i]) que.push(i);
else del[i] = true;
}
while(!que.empty()) {
int u = que.front(); que.pop(); del[u] = false;
for(int i = head2[u]; ~i; i = gra2[i].nxt) {
int v = gra2[i].to;
if(!--deg[v]) que.push(v);
}
}
for(int i = 1; i <= n * m; i++) {
if(del[i]) dfs_del(i);
}
}
int level[MAXN];
inline bool bfs(int s, int t) {
memset(level, -1, sizeof(level));
std::queue<int> que;
que.push(s); level[s] = 1;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(level[v] == -1 && gra[i].cap) {
level[v] = level[u] + 1;
if(v == t) return true;
que.push(v);
}
}
}
return level[t] != -1;
}
int cur[MAXN];
int dfs(int u, int t, int left) {
if(u == t || !left) return left;
int flow = 0;
for(int &i = cur[u]; ~i; i = gra[i].nxt) {
int v = gra[i].to;
if(level[v] == level[u] + 1 && gra[i].cap) {
int d = dfs(v, t, std::min(left, gra[i].cap));
if(d) {
gra[i].cap -= d; gra[i ^ 1].cap += d;
flow += d; left -= d;
if(!left) break;
}
}
}
return flow;
}
inline int dinic(int s, int t) {
int flow = 0;
while(bfs(s, t)) {
memcpy(cur, head, sizeof(head));
int f;
while(f = dfs(s, t, INF)) flow += f;
}
return flow;
}
inline int id(int x, int y) {
return (x - 1) * m + y;
}
int w[MAXN], S, T;
int main() {
memset(head, -1, sizeof(head));
memset(head2, -1, sizeof(head2));
n = readint(); m = readint(); S = n * m + 1; T = S + 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
w[id(i, j)] = readint();
int t = readint();
while(t--) {
int x = readint() + 1, y = readint() + 1;
addedge2(id(i, j), id(x, y));
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 2; j <= m; j++) {
addedge2(id(i, j), id(i, j - 1));
}
}
toposort();
int sum = 0;
for(int i = 1; i <= n * m; i++) {
if(del[i]) continue;
if(w[i] > 0) {
sum += w[i]; addedge(i, T, w[i]);
} else {
addedge(S, i, -w[i]);
}
for(int j = head2[i]; ~j; j = gra2[j].nxt) {
int v = gra2[j].to;
addedge(i, v, INF);
}
}
printf("%d", sum - dinic(S, T));
return 0;
}
题目地址:洛谷:【P4331】[BOI2004]Sequence 数字序列 – 洛谷、BZOJ:Problem 1367. — [Baltic2004]sequence
输入格式:
输出格式:
第一行输出最小的绝对值之和。
第二行输出序列 bi ,若有多种方案,只需输出其中一种。
输入样例#1:
5 2 5 46 12 1
输出样例#1:
47 2 5 11 12 13
【数据范围】
40%的数据 n≤5000
60%的数据 n≤300000
100%的数据 n≤1000000 , 0≤a_i≤2×10^9
考虑当所求序列$z_i$是不降的情况应该如何解决。我们有两种情况:
因此,我们可以将$t$数列分为若干区间,每个区间的答案即其中位数,从而解决这个问题。
然而题目让我们求一个严格递增的序列,我们考虑将$t_i$处理成$t_i – i$,就可以用跟上面一致的方法解决这个问题,因为处理完毕后的数列不降等价于原数列单增。
实现上,我们对每个元素建一个可并堆,然后向左合并左边元素构成的可并堆(即左边的区间),直到这个区间的中位数不小于左边相邻区间的中位数。中位数可以利用大根堆维护,让堆的大小不大于$\left\lceil \frac{|S|}{2} \right\rceil$再取堆顶即可。
复杂度$O(n \log n)$。
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
const int MAXN = 1000005;
int n, a[MAXN];
struct Node {
int ch[2], fa, val, dis, siz;
} tr[MAXN];
int rt[MAXN], l[MAXN], r[MAXN], htot;
inline int merge(int x, int y) {
if(!x || !y) return x + y;
if(tr[x].val < tr[y].val) std::swap(x, y);
tr[x].ch[1] = merge(tr[x].ch[1], y);
tr[x].siz = tr[tr[x].ch[0]].siz + tr[tr[x].ch[1]].siz + 1;
tr[tr[x].ch[1]].fa = x;
if(tr[tr[x].ch[0]].dis < tr[tr[x].ch[1]].dis) std::swap(tr[x].ch[0], tr[x].ch[1]);
tr[x].dis = tr[tr[x].ch[1]].dis + 1;
return x;
}
int main() {
n = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint() - i;
}
for(int i = 1; i <= n; i++) {
htot++; rt[htot] = i;
l[htot] = r[htot] = i;
tr[i].val = a[i]; tr[i].siz = 1;
while(htot > 1 && tr[rt[htot]].val < tr[rt[htot - 1]].val) {
htot--;
rt[htot] = merge(rt[htot], rt[htot + 1]);
r[htot] = r[htot + 1];
while(tr[rt[htot]].siz * 2 > r[htot] - l[htot] + 2) {
rt[htot] = merge(tr[rt[htot]].ch[0], tr[rt[htot]].ch[1]);
}
}
}
LL ans = 0;
for(int i = 1; i <= htot; i++) {
int w = tr[rt[i]].val;
for(int j = l[i]; j <= r[i]; j++) {
ans += abs(w - a[j]);
}
}
printf("%lld\n", ans);
for(int i = 1; i <= htot; i++) {
int w = tr[rt[i]].val;
for(int j = l[i]; j <= r[i]; j++) {
printf("%d ", w + j);
}
}
return 0;
}
题目地址:洛谷:【P1486】[NOI2004]郁闷的出纳员 – 洛谷、BZOJ:Problem 1503. — [NOI2004]郁闷的出纳员
OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。
好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?
如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内
维护一个集合,四种操作:
如果全体减数以后某些元素小于了阈值,从集合中删去它们,并记录下整个过程中总共删了多少数,在最后输出。
输入格式:
第一行有两个非负整数n和min。n表示下面有多少条命令,min表示工资下界。
接下来的n行,每行表示一条命令。命令可以是以下四种之一:
名称 格式 作用
I命令 I_k 新建一个工资档案,初始工资为k。如果某员工的初始工资低于工资下界,他将立刻离开公司。
A命令 A_k 把每位员工的工资加上k
S命令 S_k 把每位员工的工资扣除k
F命令 F_k 查询第k多的工资
_(下划线)表示一个空格,I命令、A命令、S命令中的k是一个非负整数,F命令中的k是一个正整数。
在初始时,可以认为公司里一个员工也没有。
输出格式:
输出文件的行数为F命令的条数加一。
对于每条F命令,你的程序要输出一行,仅包含一个整数,为当前工资第k多的员工所拿的工资数,如果k大于目前员工的数目,则输出-1。
输出文件的最后一行包含一个整数,为离开公司的员工的总数。
输入样例#1:
9 10 I 60 I 70 S 50 F 2 I 30 S 15 A 5 F 1 F 2
输出样例#1:
10 20 -1 2
I命令的条数不超过100000
A命令和S命令的总条数不超过100
F命令的条数不超过100000
每次工资调整的调整量不超过1000
新员工的工资不超过100000
显然可以用平衡树来维护,这里写的是Splay。
插入很常规。考虑在外面维护一个标记来记录集合内的总体变化值$delta$,然后在插入删除的时候用它来处理。减数删除的时候可以先向集合中插入一个$k-delta-1$,把这个节点转到根,然后把它和左子树都删掉,往删点数里加上这一堆数的个数-1即可。
复杂度$O(n \log n)$。
// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1; register char c = fgc();
for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
return res * neg;
}
inline char readsingle() {
char c;
while(!isalpha(c = fgc())) {}
return c;
}
const int MAXN = 500005;
struct Node {
int ch[2], fa, siz, cnt, val;
} tr[MAXN];
int rt, tot, sta[MAXN], stop;
inline int newnode() {
int p;
if(stop) {
p = sta[--stop];
} else {
p = ++tot;
}
memset(tr + p, 0, sizeof(Node));
return p;
}
inline void delnode(int p) {
sta[stop++] = p;
}
inline void update(int p) {
tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + tr[p].cnt;
}
inline bool isleft(int p) {
return tr[tr[p].fa].ch[0] == p;
}
inline void rotate(int p) {
bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
tr[p].ch[!t] = fa; tr[fa].fa = p;
update(fa);
if(!tr[p].fa) rt = p;
}
inline void splay(int p, int tar) {
for(int fa = tr[p].fa; fa != tar; rotate(p), fa = tr[p].fa) {
if(tr[fa].fa != tar) rotate(isleft(fa) == isleft(p) ? fa : p);
}
update(p);
}
inline int queryk(int k) {
int p = rt;
for(;;) {
if(tr[tr[p].ch[1]].siz >= k) {
p = tr[p].ch[1];
} else if(tr[tr[p].ch[1]].siz + tr[p].cnt >= k) {
return tr[p].val;
} else {
k -= tr[tr[p].ch[1]].siz + tr[p].cnt;
p = tr[p].ch[0];
}
}
}
inline int insert(int v) {
if(!rt) {
rt = ++tot;
tr[rt].val = v;
tr[rt].siz = 1;
tr[rt].cnt = 1;
return rt;
}
int p = rt, fa = 0;
while(p) {
fa = p;
if(tr[p].val > v) p = tr[p].ch[0];
else if(tr[p].val == v) {
tr[p].cnt++; splay(p, 0); return p;
} else p = tr[p].ch[1];
}
p = ++tot;
tr[p].val = v;
tr[p].siz = 1;
tr[p].cnt = 1;
tr[p].fa = fa;
if(tr[fa].val > v) tr[fa].ch[0] = p;
else tr[fa].ch[1] = p;
splay(p, 0);
return p;
}
int n, mn, del, ltot;
int main() {
n = readint(); mn = readint();
while(n--) {
char op = readsingle();
int k = readint();
if(op == 'I') {
if(k >= mn) insert(k - del);
} else if(op == 'A') {
del += k;
} else if(op == 'S') {
del -= k;
int p = insert(mn - 1 - del);
tr[tr[p].ch[1]].fa = 0; rt = tr[p].ch[1];
ltot += tr[tr[p].ch[0]].siz + tr[p].cnt - 1;
} else {
if(k > tr[rt].siz) puts("-1");
else printf("%d\n", queryk(k) + del);
}
}
printf("%d", ltot);
return 0;
}