Luogu – P7568 -「MCOI-05」追杀

题意

有 $m$ 位玩家 $1\sim m$,初始血量均为 $3$。玩家活着当且仅当生命值大于 $0$.

有 $n$ 次按时间顺序给定的追杀操作,每次形如 $(u_k,v_k)$,追杀操作按顺序进行。

执行操作 $u$ 追杀 $v$ 时,若二者都活着,那么 $v$ 的生命值减 $1$;否则不执行该操作。

现在有一名特殊玩家 $0$ 号,可以选取任意 $(i,v)$,其中 $1\leq i\leq n+1$,$1\leq v\leq m$,表示时空穿越到第 $i$ 次追杀前,并追杀玩家 $v$。

显然 $(i,v)$ 共有 $(n+1)\times m$ 个不同的选择方法,且不同的 $(i,v)$ 会导致最终存活玩家的集合不同。

对每个 $0\leq x\leq m$,求有多少种 $(i,v)$ 的选取方法,使最终恰有 $x$ 位玩家存活,输出 $m+1$ 个数。

 

对于 $16\%$ 的数据,$n,m\leq 100$.

对于另外 $41\%$ 的数据,$n\leq 10^3$.

对于 $100\%$ 的数据:$1\leq n\le 6\times 10^4$,$1\leq m\leq 10^3$,$1\leq u_i,v_i\leq m$.

可以接受 $\mathcal{O}(nm)$ 的复杂度。

题解

暴力?$\mathcal{O}(n^2m)$.

 

设 $f_{i,j}$ 表示:若在 $i$ 前穿越,追杀 $j$,最后存活的玩家数量。

对于追杀操作 $(u,v)$,无论在它前面还是后面,插入一个操作 $(0,x\neq u)$,对结果的影响都是相同的。

因此,只有当 $j=u_i$ 时,$f_{i+1,j}\neq f_{i,j}$,其他情况下都有 $f_{i,j}=f_{i+1,j}$.

所以我们尝试在每个操作 $(u,v)$ 前插入追杀 $u$ 的操作,插入后 $\mathcal{O}(n)$ 模拟一遍进程,更新 $f_{i,u_i}$.

这样的复杂度是 $\mathcal{O}(n^2)$ 的。

 

注意到,若第 $i$ 次追杀操作没有生效,也有 $f_{i,j}=f_{i+1,j}$,因此只需对所有生效的操作重新跑一遍。

最多有 $3m$ 次生效操作,复杂度变为 $\mathcal{O}(nm)$,可以通过。

#include <bits/stdc++.h>
using namespace std;
inline int read() {}
const int MAXN = 6e4 + 10, MAXM = 1e3 + 10;
int n, m, u[MAXN], v[MAXN], ans[MAXM];
int hp[MAXM], hp_cur[MAXM]; //血量、计算过程中临时更改的血量
int f[MAXM]; //f[i]:在人物i前面穿越,杀i,能有多少人活
int main() {
	n = read(), m = read();
	for(int i = 1; i <= n; i++) u[i] = read(), v[i] = read();
	//预处理,若穿越到1前面,杀i,计算此时的f数组
	for(int i = 1; i <= m; i++) {
		for(int j = 1; j <= m; j++) hp[j] = 3;
		hp[i]--;
		for(int j = 1; j <= n; j++) if(hp[u[j]] && hp[v[j]]) hp[v[j]]--;
		for(int j = 1; j <= m; j++) if(hp[j]) f[i]++;
	}
	for(int i = 1; i <= m; i++) hp[i] = 3;
	for(int i = 1; i <= n; i++) {
		//每次都加一遍贡献
		for(int j = 1; j <= m; j++) ans[f[j]]++;
		if(hp[v[i]] && hp[u[i]]) {
			hp[v[i]]--; //顺次进行,模拟掉血
			memcpy(hp_cur, hp, sizeof(hp));
			//穿越到 u 前面
			hp_cur[u[i]]--;
			if(hp_cur[u[i]] == 0) {
				for(int j = i + 1; j <= n; j++) //把剩下的操作模拟一遍
					if(hp_cur[u[j]] && hp_cur[v[j]]) hp_cur[v[j]]--;
				f[u[i]] = 0;
				for(int j = 1; j <= m; j++)
					if(hp_cur[j]) f[u[i]]++;
			}
		}
	}
	for(int i = 1; i <= m; i++) //穿越到第n个人后面的情况
		ans[f[i]]++;
	for(int i = 0; i <= m; i++) printf("%d ", ans[i]); putchar('\n');
	return 0;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇