Codeforce s Round 920 (Div. 3) G题 旋转矩阵,斜缀和,平移

发布时间:2024年01月18日

Problem - G - Codeforces

目录

题意:

思路:

总思路:

旋转矩阵:

前缀和预处理:

平移的处理,尤其是越界的处理:

核心代码:


题意:

给你个n*m的矩阵,里面要么是目标' # ',要么是空的' . '。

还有值k,代表这样的范围:

我们有四个方向可选。图中黑点即是我们落脚点,可以随意选,要使黑色区域的目标'#'最多,输出这个最大值

思路:

总思路:

‘#’是随机给的,我们只能暴力。暴力上做优化即可。

如果这四种都做,代码是类同但细节处理太多,而只用一种方向然后旋转矩阵这样是等价的。

我们选择第三种,使用前缀和(列缀和,斜缀合)方便:

由于面积可能很大,每个落脚点都数时间消耗太多。我们可以发现相邻的是平移过去的,只差一列和斜着一列:

所以我们对上次的‘#’数目,加上这列的'#'数目,再减去斜着的'#'数目,就是这次的'#'数目了。

预处理出前缀和,这样平移时加的减的都可以直接算出来。(越界的处理需要注意)

旋转矩阵:

(这个C语言OJ就写过。我好像有一次没写出来,然后就有了心理阴影,其实很好写)

我们再创个二维char数组next,把旋转的写进这个数组,然后覆盖原数组即可。

我们可以借助个例子去想,比如顺时针旋转:

1 2 3 4      5 1		
5 6 7 8	     6 2
	         7 3
	         8 4

我们可以发现第一行变成了倒数第一列,而原来的列数变成了新的行数。

所以next[ j ][ chars.size()-1-i?] = chars[ i ][ j ]? ? ? ? (chars就是原始图)

vector<vector<char>>next(chars[0].size(), vector<char>(chars.size()));
for (int i = 0; i < chars.size(); i++)
{
	for (int j = 0; j < chars[0].size(); j++)
	{
		next[j][chars.size()-1 - i] = chars[i][j];
	}
}
chars = next;

(注意新的图的n和m是变的。)

前缀和预处理:

可能没写过斜缀和。然后下标可以从1开始,我是写的从0开始的。

	int t = 4;
	while (t--)
	{
		n = chars.size(), m = chars[0].size();
		vector<vector<int>>narr(n, vector<int>(m)), rd(n, vector<int>(m));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (i > 0)
					narr[i][j] = narr[i - 1][j] + (chars[i][j] == '#');
				else
					narr[i][j] = chars[i][j] == '#';
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if(i>0&&j>0)
					rd[i][j] = rd[i - 1][j - 1] + (chars[i][j] == '#');
				else
					rd[i][j] = chars[i][j] == '#';
			}
		}

平移的处理,尤其是越界的处理:

for (int i = 0; i < n; i++)
{
	int tmp = narr[min(i + k, n - 1)][0] - (i - 1 >= 0 ? narr[i - 1][0] : 0);
	ans = max(ans, tmp);
	for (int j = 1; j < m; j++)//右平移
	{
		//x,y:前一个位置最下面那个点
		int x = i + k, y = j-1;
		if (x >= n)
		{
			y -= x - (n - 1);
			x = n - 1; 
		}
		tmp += narr[min(i+k,n-1)][j] - (i - 1 >= 0 ? narr[i - 1][j] : 0);
		if(y>=0)
		tmp	-= rd[x][y] - (j - 1 - k - 1 >= 0&&i-1>=0 ? rd[i - 1][j - 1 - k - 1] : 0);
		ans = max(ans, tmp);
	}
}

代码中x,y就是1点。

1的列缀合-2的列缀合就是新增的'#'

3的斜缀合-4的斜缀合就是失去的'#'

最难处理的就是3越界后的斜缀合:

我们可以发现,不管下面什么情况越界,最后一行都是n-1。我们取n-1对应着的斜缀合即可。

x,y仍代表1点(见上面),(x,y-1)就是原来的斜缀合的点,现在往左上角移动了,行的变换数是等于列的变换数的,而行变换(x-(n-1)),那么列也减去这个,即行为n-1,列为y-1 - (x-(n-1))。

其余的越界是好处理的,代码里有我的处理情况。

核心代码:

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<char>>chars(n, vector<char>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> chars[i][j];

	int ans = 0;
	int t = 4;
	while (t--)
	{
		n = chars.size(), m = chars[0].size();
		vector<vector<int>>narr(n, vector<int>(m)), rd(n, vector<int>(m));
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (i > 0)
					narr[i][j] = narr[i - 1][j] + (chars[i][j] == '#');
				else
					narr[i][j] = chars[i][j] == '#';
			}
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if(i>0&&j>0)
					rd[i][j] = rd[i - 1][j - 1] + (chars[i][j] == '#');
				else
					rd[i][j] = chars[i][j] == '#';
			}
		}

		for (int i = 0; i < n; i++)
		{
			int tmp = narr[min(i + k, n - 1)][0] - (i - 1 >= 0 ? narr[i - 1][0] : 0);
			ans = max(ans, tmp);
			for (int j = 1; j < m; j++)//右平移
			{
				//x,y:前一个位置最下面那个点
				int x = i + k, y = j-1;
				if (x >= n)
				{
					y -= x - (n - 1);
					x = n - 1; 
				}
				tmp += narr[min(i+k,n-1)][j] - (i - 1 >= 0 ? narr[i - 1][j] : 0);
				if(y>=0)
				tmp	-= rd[x][y] - (j - 1 - k - 1 >= 0&&i-1>=0 ? rd[i - 1][j - 1 - k - 1] : 0);
				ans = max(ans, tmp);
			}
		}

		vector<vector<char>>next(chars[0].size(), vector<char>(chars.size()));
		for (int i = 0; i < chars.size(); i++)
		{
			for (int j = 0; j < chars[0].size(); j++)
			{
				next[j][chars.size()-1 - i] = chars[i][j];
			}
		}
		chars = next;
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

文章来源:https://blog.csdn.net/JK01WYX/article/details/135669217
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。