6 October

P1514 引水入城

题目描述

在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 \(N\) 行 \(\times M\) 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。

为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。

因此，只有与湖泊毗邻的第 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 \(N\) 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。

BFS 记忆化搜索（优先队列优化）+ 区间完全覆盖问题（贪心）。

定理：蓄水厂所在城市海拔必然不低于左右城市。即对于可能建造蓄水厂的城市 \(G(1,i)\)，满足 \(G(1,i-1) \leq G(1,i) \geq G(1,i+1)\)。

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

int n, m, G[503][503], v[503][503], cc[503], rat, tot;

struct node {

	int a, b;

	bool operator < (const node& aa) const {return a<aa.a; }

} ra[503];

priority_queue<node> q;

int main() {

	scanf("%d%d", &n, &m);

	for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j)

		scanf("%d", &G[i][j]);

	for (int i=1; i<=m; ++i) ra[i].a=1000003;

	for (int i=1; i<=m; ++i) if (G[1][i-1]<=G[1][i] && G[1][i]>=G[1][i+1]) {

		q.push((node) {1, i}); ++rat;

		memset(v, 0, sizeof v);

		while (!q.empty()) {

			node p=q.top(); q.pop(); int &x=p.a, &y=p.b;

			if (v[x][y]) continue; v[x][y]=i;

			if (x==n) {

				if (!cc[y]) ++tot; cc[y]=1;

				ra[rat].a = min(ra[rat].a, y),

				ra[rat].b = max(ra[rat].b, y);

			}

			else if (!v[x+1][y]) if (G[x+1][y]<G[x][y]) q.push((node) {x+1, y});

			if (x>1) if (!v[x-1][y]) if (G[x-1][y]<G[x][y]) q.push((node) {x-1, y});

			if (y<m) if (!v[x][y+1]) if (G[x][y+1]<G[x][y]) q.push((node) {x, y+1});

			if (y>1) if (!v[x][y-1]) if (G[x][y-1]<G[x][y]) q.push((node) {x, y-1});

		}

	}

	if (tot<m) printf("0\n%d\n", m-tot);

	else {

		printf("1\n");

		sort(ra+1, ra+rat+1);

		int ans=0, bat=0, bat2=0, i=1;

		while (bat<m) {

			for (; i<=rat && ra[i].a-1<=bat; ++i)

				bat2=max(bat2, ra[i].b);

			bat=bat2, ++ans;

		}

		printf("%d\n", ans);

	}

	return 0;

}

抽象出来的 区间完全覆盖问题：

求给定区间集合的一个子集，使得覆盖全部区间，且该子集的元素个数最小。

贪心：左端点排序，按照能否覆盖前一区间贪心统计。

int maxLen, n;

struct node {

	int l, r;

	bool operator < (const node& aa) const {return l<aa.l; }

} D[503];

int main() {

	scanf("%d", &n);

	for (int i=1; i<=n; ++i)

		scanf("%d%d", &D[i].l, &D[i].r), maxLen=max(maxLen, D[i].r);

	sort(D+1, D+n+1);

	int ans=0, end=0, end2=0, i=1;

	while (end<maxLen) {

		for (; i<=n&& D[i].l-1<=end; ++i)

			end2=max(end2, D[i].r);

		end=end2, ++ans;

	}

	printf("%d\n", ans);

	return 0;

}

[SCOI2009] Windy数

参考数位 DP - OI Wiki.

\(f(x, pre, op) = \displaystyle \sum_{|pre-i|\geq 2} f(x-1, i, op \operatorname{and} i=M)\).

数位 DP 的 记忆化搜索实现:

#include <cstdio>

#include <cmath>

#include <cstring>

int G[13], gt; long long A, B, f[13][13];

long long search(int x, int pre, int op) {

	if (!x) return 1;

	if (!op && ~f[x][pre]) return f[x][pre];

	int M = op ? G[x] : 9; long long res=0;

	for (int i=0; i<=M; ++i) if (abs(pre-i)>=2) {

		if (pre==11 && !i) res+=search(x-1, 11, op && i==M);

		else res+=search(x-1, i, op && i==M);

	}

	if (!op) f[x][pre]=res;

	return res;

}

long long sum(long long x) {

	gt=0;

	while (x) G[++gt]=x%10, x/=10;

	G[gt+1]=-1;

	return search(gt, 11, 1);

}

int main() {

	scanf("%lld%lld", &A, &B);

	memset(f, -1, sizeof f);

	printf("%lld\n", sum(B)-sum(A-1));

	return 0;

}

简便写法 Get:

~a \(\Leftrightarrow\) a!=-1
!a \(\Leftrightarrow\) a==0.

巴特西

6 October

P1514 引水入城

[SCOI2009] Windy数

最新文章

热门文章