COCI 2018/2019 CONTEST #2 T4 T5 Solution

abstract

花式暴力

#2 T5 Sunčanje

题意

按顺序给你1e5个长方形（左下角坐标&&长宽），对于每个长方形询问是否有后面的长方形盖住了它。

---

题解

暴力几何。不需要线段树维护。

用一个排序剪枝，先按矩形的左下角x坐标排序，对于每一个矩形i，枚举后面的所有矩形j，当矩形j的左下角x坐标大于i的右下角x坐标时，break掉。 数据并没有卡

---

代码

#include <queue>

#include <vector>

#include<map>

#include <cstdio>

#include <cctype>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)

using namespace std;

int cnt = 0;

const int N = 1e5+1;

inline int read()

{

	int X = 0, w = 0; char c = 0;

	while (c<'0' || c>'9') { w |= c == '-'; c = getchar(); }

	while (c >= '0'&&c <= '9') X = (X << 3) + (X << 1) + (c ^ 48), c = getchar();

	return w ? -X : X;

}

int n;

struct rec {

	int x, y, len, wid, id;

}a[N];

int ans[N];

int  main()

{

	n = read();

	rep(i, 1, n) {

		a[i].x = read(); a[i].y = read(); a[i].len = read(); a[i].wid = read();

		//a[i].x += a[i].len;

		a[i].id = i;

	}

	sort(a + 1, a + 1 + n, [](rec a, rec b)->bool {return a.x < b.x; });

	rep(i, 1, n) {

		int j = i + 1;

		while (j<=n && (a[i].x + a[i].len>a[j].x)) {

			if (a[j].y >= a[i].y + a[i].wid || a[j].y + a[j].wid <= a[i].y);

			else

			{

				if (a[i].id<a[j].id) ans[a[i].id] = 1;

				else ans[a[j].id] = 1;

			}

			j++;

		}

	}

	rep(i, 1, n)puts(ans[i]?"NE":"DA");

		cin >> n;

		return 0;

}

//按照x的右下坐标排序，反着剪枝，快了100ms吧

int cnt = 0;

const int N = 1e5+1;

inline int read()

{

	int X = 0, w = 0; char c = 0;

	while (c<'0' || c>'9') { w |= c == '-'; c = getchar(); }

	while (c >= '0'&&c <= '9') X = (X << 3) + (X << 1) + (c ^ 48), c = getchar();

	return w ? -X : X;

}

int n;

struct rec {

	int x, y, len, wid, id;

}a[N];

int ans[N];

int  main()

{

	n = read();

	rep(i, 1, n) {

		a[i].x = read(); a[i].y = read(); a[i].len = read(); a[i].wid = read();

		a[i].x += a[i].len;

		a[i].id = i;

	}

	sort(a + 1, a + 1 + n, [](rec a, rec b)->bool {return a.x < b.x; });

	rep(i, 2, n) {

		int j = i - 1;

		while (j >= 1 && (a[i].x - a[i].len<a[j].x)) {

			if (a[j].y >= a[i].y + a[i].wid || a[j].y + a[j].wid <= a[i].y);

			else

			{

				if (a[i].id<a[j].id) ans[a[i].id] = 1;

				else ans[a[j].id] = 1;

			}

			j--;

		}

	}

	rep(i, 1, n)puts(ans[i]?"NE":"DA");

		//cin >> n;

		return 0;

}

---

心路历程

为什么能暴力啊QAQ ，如果有n个长方形嵌套在一起的，上面程序就是N^N的,必T

---

T4 Maja

题意

给你一个n*m的矩阵和出发点，你可以上下左右走，最多走k步。你到达任意一点时会获得该点的数值(可重复获得)，问最终回到起点的最大收益是多少？

---

题解

两个结论：

1.路径的前半段和后半段必定是相同的(重复路径)。

证明：若不同，显然取前半段和后半段中较大的重复走两遍，答案显然不会更差。

2.当k很大时，必然是在某两点来回走动。

证明：首先，k较大（k大于n*m）必然是在某个环上绕圈，否则没地方走了。

然后，在某个长度大于2的环上绕圈必然不会比在该环相邻2个之和最大的两个点之间来回走更优。证明：我们把环上的相邻点两两分组，和最大的那组的平均值必然不小于总环的平均值。否则总和小于总和矛盾。

于是我们的路径就是从起点走到某个点，在那个点与相邻的来回走，原路回到起点。

我们可以dp来做，dp[i][j][k]表示第k步走到(i,j)这个点时最大的收益。它可以由dp[i][j][k-1]的上下左右四个点转移而来。

而由于转移第三维只由上一个状态转移而来，所以可以滚动更新。

---

代码

//用了-inf来代替判边界

# define int long long

#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr)

using namespace std;

const int maxn = 1e2 + 5;

const int INF = 1e18;

int n, m, sr, sc,k;

int c[maxn][maxn];

int f[maxn][maxn][2];

int dir[4][2] = { 1,0, -1,0, 0,1, 0,-1 };

signed  main()

{

	FAST_IO;

	cin >> n >> m >> sr >> sc>>k;

	k /= 2;

	int ans = -INF;

	rep(i, 1, n)rep(j, 1, m) {

		cin >> c[i][j];

	}

	rep(i, 0, n + 1)rep(j, 0, m + 1) { f[i][j][0]= f[i][j][1] = -INF; }

	f[sr][sc][0] = 0;

	rep(r, 1, min(k, n*m)) {

		int now = r & 1;

		int pst = !now;

		rep(i, 1, n)rep(j, 1, m) {

			int tmp = -INF; rep(k, 0, 3) { tmp = max(tmp, f[i + dir[k][0]][j + dir[k][1]][pst]); }

			f[i][j][now] = max(tmp + c[i][j], -INF);

			if (f[i][j][now] < 0) continue;//边界

			int dist = f[i][j][now] + tmp;

			tmp = 0; rep(k, 0, 3) { tmp = max(tmp, c[i + dir[k][0]][j + dir[k][1]]); }

			dist += (k - r)*(c[i][j] + tmp);

			ans = max(ans, dist);

		}

	}

	cout << ans << endl;

	cin >> n;

	return 0;

}

/*

4 1

1 3

1 4

2 2

1 4

2 3

*/

---

心路历程

---