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;
}
