SDOI2011

除去贪吃蛇鬼模拟和火星移民鬼六边形

P2484 [SDOI2011]打地鼠

天哪蓝题比黑题还难!

首先如果我们有给定的锤子,有一个能打就打的 $O(n^4)$ 判断可不可行的贪心,就是从左上角,我们对于一个矩阵大小然后全部打一遍...

然后这个可以二维树状数组优化?(这是我没想到的...)

然后会发现我们可以枚举一个r,c然后再去判断复杂度低达惊人的 $O(n^6)$ ,过不了100

然后有一个结论就是这个锤子他越大答案越小,没太大用处可以剪枝

所以剩下的我们就暴力吧...剪剪剪....

1.矩阵权值和一定是R*L的倍数...

2.从大到小枚举吧....

所以官方正解是什么啊?

P2491 [SDOI2011]消防

树网的核加强版

而且树网的核还比这题出的早

直接尺取找分界点就行了

然后还要和树上非直径到直径的距离的max取max

注意亿点点细节?

code:


#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int inf = 1e9 + 7;
const int MAXN = 3e5 + 7;
const int MAXM = 6e5 + 7;
int n, s, ccnt, mp, rt, sm;
int home[MAXN], nxt[MAXM], to[MAXM], fa[MAXN], len[MAXM], vis[MAXN];
ll ans, dep[MAXN], Ex;

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

inline void dfs1(int u, int F) {
	if(dep[u] > dep[mp])mp = u;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		fa[v] = u;
		dep[v] = dep[u] + len[i];
		dfs1(v, u);
	}
	return ;
}

ll dep2[MAXN];

inline void dfs2(int u, int F) {
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dep2[v] = dep2[u] + len[i];
		if(vis[v])dep2[v] = 0;
		dfs2(v, u);
	}
	return ;
}

inline void init() {
	int u = mp;
	while(u != rt) {
		vis[u] = 1;
		u = fa[u];
	}
	vis[rt] = 1;
	return ;
}

inline void solve() {
	int u = mp, v = mp;
	dep[0] = -1e9;
	while(dep[v] - dep[fa[u]] <= s) {
		u = fa[u];
	}
	ans = max(dep[u], dep[mp] - dep[v]);
	while(u != rt) {
		u = fa[u];
		while(dep[v] - dep[u] > s)
			v = fa[v];
		ans = min(ans, max(dep[u], dep[mp] - dep[v]));
	}
	ans = max(ans, Ex);
	printf("%lld\n", ans);
	return ;
}

int main() {
	scanf("%d%d", &n, &s);
	for(int i = 2, x, y, z; i <= n; ++i) {
		scanf("%d%d%d", &x, &y, &z);
		ct(x, y, z);
		ct(y, x, z);
	}
	mp = 0;
	dfs1(1, 0);//get oneside of the diameter
	rt = mp;
	dep[rt] = 0;
	fa[rt] = 0;
	dfs1(rt, 0);//get fa array /xyx
	init();
	dfs2(rt, 0);//dep node in 直径 is 0
	for(int i = 1; i <= n; ++i) {
		Ex = max(Ex, dep2[i]);
	}
	solve();//ruler is right
	return 0;
}

P2494 [SDOI2011]保密

强行组合题

SDOI2011题目质量也太差了吧?

首先整体二分求出从基地到所有出入口的最小危险度

相当于每个点带权找最小权点覆盖

然后用一个费用流求出最小权匹配即可

夏晓光(loveJY)的博客

2/3线性基与100%构造题