CF536D Tavas in Kansas

IOI2020集训队作业

吐槽,这是第几次做作业了?/xyx

...感受...作业一下子....加难度了?QAQ

给定一张 $n$ 个点 $m$ 条边的可能有自环和重边的无向连通图，每条边都有一个非负边权。
小 X 和小 Y 在这张图上玩一个游戏，在游戏中，第 $i$ 个城市有一个权值 $p_i$ 。
一开始，小 X 在城市 $s$ 中，小 Y 在城市 $t$ 中，两人各有一个得分，初始为 $0$ ，小 X 为先手，然后轮流进行操作。
当轮到某一个人时，他必须选择一个非负整数 $x$ ，以选定所有与他所在的城市的最短距离不超过 $x$ 的还未被选定过的城市，他的得分将会加上这些城市的权值。
另外，每个人每次必须能够至少选定一个城市。
当没有人可以选择时，游戏结束，得分高者获胜。
现在请你计算出，在两人都使用最佳策略的情况下，谁会获胜（或者判断为平局）。
$n \le 2 \times 10^3$ , $m \le 10^5$ ， $|p_i| \le 10^9$ 。

首先跑两遍dijkstra算出s,t到其他点的最短路,然后我们得到两个dis数组

紧接着我们离散化,这样方便DP,而且整个局面可以很轻松的被纪录下来,因为我们只考虑每个点选还是没选,具体得分记在值里就好,所以从S出发半径为i和从T出发半径为j包住的所有点就成为被选的点, $dp[i][j]$ 一个就能推出哪些点被选了

$dp_{1,i,j},dp_{2,i,j}$ 表示初始局面是 $S_{i,j}$ 然后第一步由A,B操作,A的最大得分是多少,转移就枚举下一步选取什么点

dp1_{i,j}=MAX_{\sum_{o=i+1}^k\sum_{dis1_P=o}[dis2_P>j]>0}{dp2_{k,j}+\sum_{o=i+1}^k\sum_{dis1_P=o}[dis2_P>j]v_P}

dp2_{i,j}=min_{\sum_{o=j+1}^k\sum_{dis2_p=0}[dis1p>i]>0}{dp1_{i,k}}

一次转移是O(n)的,复杂度就是O(n^3),T掉了

考虑处理前缀

Cnt1_{i,j}=\sum_{k=1}^i\sum_{dis1_o=k}[dis2_o>j]

Sum1_{i,j}=\sum_{k=1}^i\sum_{dis1_o=k}[dis2_o>j]v_p

cnt2和sum2同理

转移方程就...唉...

dp1_{i,j}=MAX_{cnt1_{k,j}>cnt1_{i,j}}{dp2_{k,j}+sum1_{k,j}-sum1_{i,j}}

dp2_{i,j}=min_{cnt2_{i,k}>cnt2_{i,j} }{dp1_{i,k}}

你就会发现那个取miin取max的操作可以双指针,因为随着i下降,k的上界不变而下界不升,所以可以双指针....

最后比较 $dp1_{0,0}$ 和 $\sum_{i=1}^nv_i-dp1_{0,0}$

QAQ还是不太会啊

code:

#include<bits/stdc++.h>
#define ll long long
#define int long long

#define pb push_back
#define mp make_pair
#define se second
using namespace std;
const int N = 2e3 + 20;
const int MAXN = 5e5 + 7;
const ll inf = 1e18;
int home[MAXN], to[MAXN], nxt[MAXN], ccnt;
int n, m, S, T, a[N], v[N], cs, ct, c[N][N], ns[N][N], nt[N][N];
ll ds[N], dt[N], num[N], f[2][N][N], s[N][N], len[MAXN];

inline CT(int x, int y, int z) {
	nxt[++ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	len[ccnt] = z;
}

inline void dij(int s, ll *d, int &c) {
	for(int i = 1; i <= n; ++i)d[i] = inf, v[i] = 0;
	priority_queue<pair<ll, int> > q;
	d[s] = 0, q.push(mp(0, s));
	while(!q.empty()) {
		int x = q.top().se;
		q.pop();
		if(v[x])continue;
		v[x] = 1;
		for(int i = home[x]; i; i = nxt[i]) {
			int v = to[i], z = len[i];
			if(d[v] > d[x] + z)d[v] = d[x] + z, q.push(mp(-d[v], v));
		}
	}
	//dijkstra部分,他没有用比较算子所以用的-
	//puts("\n");
	for(int i = 1; i <= n; ++i)num[i] = d[i];// printf("%d ", num[i]);
	sort(num + 1, num + n + 1);
	c = unique(num + 1, num + n + 1) - (num + 1);
	for(int i = 1; i <= n; ++i)
		d[i] = lower_bound(num + 1, num + c + 1, d[i]) - num;
	//把权值排序去重
}

signed main() {
	scanf("%lld%lld", &n, &m);
	scanf("%lld%lld", &S, &T);
	for(int i = 1; i <= n; ++i)scanf("%lld", &a[i]);
	for(int i = 1; i <= m; ++i) {
		int u, v, w;
		scanf("%lld%lld%lld", &u, &v, &w);
		CT(u, v, w);
		CT(v, u, w);
	}
	dij(S, ds, cs), dij(T, dt, ct);
	//求出两个dis数组,cs是本质不同的
	//ds是S的,dt是T的
	for(int i = 1; i <= n; ++i)++c[ds[i]][dt[i]], s[ds[i]][dt[i]] += a[i];
	//sum,cnt...这个好像是处理了边界的一个
	//就是第一维正好等于,第二维正好大于等于
	for(int i = cs; i; --i) {
		for(int j = ct; j; --j) {
			//枚举两个半径,表示他两个选的半径大小
			s[i][j] += s[i + 1][j] + s[i][j + 1] - s[i + 1][j + 1];
			//s数组显然是高维后缀和就能处理的
			ns[i][j] = min(i == cs ? cs : ns[i + 1][j], j == ct ? cs : ns[i][j + 1]);
			//ns数组的记录是后缀的一个最小的i值,就是第一维
			//并且对于每个k>=i,e>=j,c(k,e)<c(i,j)...的最小,所以这样可以O1转移
			//你会发现他的转移显然要么是i+1
			nt[i][j] = min(i == cs ? ct : nt[i + 1][j], j == ct ? ct : nt[i][j + 1]);
			//nt数组定义是后缀最小的j值,就是第二维
			if(c[i][j])ns[i][j] = i, nt[i][j] = j;
			//这一步是处理如果这有人,那么接下来一定是后缀最小
			//就可以直接拿出来转移
			f[0][i][j] = s[i][j] - f[1][ns[i][j] + 1][j];
			f[1][i][j] = s[i][j] - f[0][i][nt[i][j] + 1];
			//直接转移即可,注意这个+1,因为我们定义中这个<并不严格,可能等于
			if(i == 1 && j == 1)continue;
			//这个特判不多BB
			f[0][i][j] = min(f[0][i][j], f[0][i][j + 1]);
			f[1][i][j] = min(f[1][i][j], f[1][i + 1][j]);
			//否则我呢也可以从上一个状态继承过来,而且是看上去更劣的
		}
	}
	ll ans = s[1][1] - 2 * f[0][1][1];
	if(ans < 0)puts("Break a heart");
	else if(ans > 0)puts("Cry");
	else puts("Flowers");
	return 0;
}

夏晓光(loveJY)的博客

P5358 [SDOI2019]快速查询