「WC2018即时战略」

题目描述

小 M 在玩一个即时战略 (Real Time Strategy) 游戏。不同于大多数同类游戏，这个游戏的地图是树形的。也就是说，地图可以用一个由 $n$ 个结点，$n - 1$ 条边构成的连通图来表示。这些结点被编号为 $1 \sim n$。

每个结点有两种可能的状态：“已知的”或“未知的”。游戏开始时，只有 $1$ 号结点是已知的。

在游戏的过程中，小 M 可以尝试探索更多的结点。具体来说，小 M 每次操作时需要选择一个已知的结点 $x$，和一个不同于 $x$ 的任意结点 $y$（结点 $y$ 可以是未知的）。然后游戏的自动寻路系统会给出 $x$ 到 $y$ 的最短路径上的第二个结点 $z$，也就是从 $x$ 走到 $y$ 的最短路径上与 $x$ 相邻的结点。此时，如果结点 $z$ 是未知的，小 M 会将它标记为已知的。

这个游戏的目标是：利用至多 $T$ 次探索操作，让所有结点的状态都成为已知的。然而小 M 还是这个游戏的新手，她希望得到你的帮助。

解题思路 :

首先有一个比较直观的暴力，random_shuffle一个询问顺序，同时维护一棵“已知树”。

每次从根节点开始询问，回答要么是当前点的儿子，要么是一个未知节点，如果是当前点的儿子就进入儿子节点，否则就把未知节点添加进树。

这样子做复杂度和询问次数都是 $O(n^2)$，加上一条链的暴力可以得到 $65$ 分。

实际上每次如果是已知节点的话，只需要进入儿子对应的子树询问即可，所以很容易想到用点分树维护这个“已知树”，每次直接找到这个儿子对应的点分中心进行询问，树高变成 $logn$ 。

但是加点操作会破坏点分树的性质，使得树高会大于 $logn$ 以至于退化到平方级别的复杂度，在这里可以用替罪羊树的思想，每次加完点后暴力向上检查子树的平衡性暴力重构，$\alpha$ 这里一般设 $0.7$ 。

不过由于我维护点分树信息的时候用 $map$ 存了每个儿子对应的点分中心是什么，所以我的复杂度是 $O(nlog^2n) $ ，有点卡常数，不保证所有地方都能过。

#include "rts.h"

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

const int N = 1000005;

map<int, int> mp[N], ss[N];

int vis[N], vi[N], sz[N], in[N], cc[N], mx[N], fa[N];

int size[N], id[N], ps[N], all, mn, rt, Root = 1;

map<int, int>::iterator it;

namespace Line{

	int s[2] = {1, 1};

	inline void solve(int n){

		for(int i = 1, x; i < n; i++){

			int now = id[i], tw = 1;

			while(!vis[now]){

				x = explore(s[tw], now);

				if(vis[x]) x = explore(s[tw^=1], now);

				vis[x] = 1, s[tw] = x;

			}

		}

	}

}

inline void cleartag(int u){

	in[u] = 1;

	for(map<int,int>::iterator it = mp[u].begin(); it != mp[u].end(); it++)

		if(it->second) cleartag(it->second);

}

inline void getsize(int u, int ff){

	int now = 0; sz[u] = 1;

	for(map<int, int>::iterator it = mp[u].begin(); it != mp[u].end(); it++){

		int v = it->first;

		if(v == ff || !in[v]) continue;

		getsize(v, u), sz[u] += sz[v];

		if(sz[v] >= now) now = sz[v];

	}

	now = max(now, all - sz[u]);

	if(now <= mn) mn = now, rt = u;

}

inline void rebuild(int u){

	int last = all; in[u] = 0;

	for(map<int, int>::iterator it = mp[u].begin(); it != mp[u].end(); it++){

		int v = it->first;

		if(!in[v]) continue;

		mn = all = sz[v] >= sz[u] ? last - sz[u] : sz[v];

		getsize(v, u);

		size[rt] = all, fa[rt] = u, mx[u] = Max(mx[u], all);

		mp[u][v] = rt, ss[u][rt] = v, mp[v][u] = 0, rebuild(rt);

	}

}

inline void update(int u){

	int ned = 0;

	for(int x = u; x != Root; x = fa[x]){

		size[fa[x]]++;

		if(size[x] > mx[fa[x]]) mx[fa[x]] = size[x];

		if(mx[fa[x]] >= size[fa[x]] * 0.735) ned = fa[x];

	}

	if(!ned) return;

	if(ned){

		cleartag(ned);

		all = mn = size[ned], getsize(ned, fa[ned]);

		if(ned == Root) Root = rt;

		size[rt] = all, fa[rt] = fa[ned];

		int k = ss[fa[rt]][ned];

		ss[fa[rt]][rt] = k, mp[fa[rt]][k] = rt, rebuild(rt);

	}

}

inline void addnode(int pos){

	for(register int u = Root; ; ){

		int x = explore(u, pos);

		if(!vis[x]){

			fa[x] = u, size[x] = vis[x] = 1;

			mp[u][x] = ss[u][x] = x, mp[x][u] = 0, update(x);

			break;

		} u = mp[u][x];

	}

}

void play(int n, int T, int datatype){

	srand(19262333);

	for(int i = 1; i < n; i++) id[i] = i + 1;

	random_shuffle(id + 1, id + n), vis[1] = 1;

	if(datatype == 3) return (void) (Line::solve(n));

	for(int i = 1; i < n; i++) while(!vis[id[i]]) addnode(id[i]);

}

巴特西

「WC2018即时战略」

「WC2018即时战略」

解题思路 :

最新文章

热门文章