题目传送门
题意简述
构造一个 \(n\) 行 \(m\) 列（\(m\) 为偶数）的矩阵使得：
- 每行恰好有 \(\frac{m}{2}\) 个 \(0\) 和 \(\frac{m}{2}\) 个 \(1\)。
- 有一个机器人从 \((1,1)\) 出发，每次可向左/右一步或不动，然后向下走一格。
- 机器人会选择经过格子之和最大的路径。
要求最小化这个最大路径和，输出构造出来的矩阵。
思路
设机器人当前处于第 \(i\) 行，则显然它能到达列的范围是 \([1,\min(i+1,m)]\)。
第一部分（\(1 \leq i \leq \frac{m}{2}-1\)）
为使机器人经过的格子中 \(1\) 的个数最少，考虑在机器人无法到达时将右侧的 \(\frac{m}{2}\) 个格子全都放上 \(1\)，其余放 \(0\)。此时显然满足 \(1 \leq i \leq \frac{m}{2}-1\)。
代码如下：
if(i+1<=m/2)
{for(int k=m;k>m/2;k--){a[i][k]=1;}continue;
}
第二部分（\(\frac{m}{2} \leq i < m\)）
此时显然不能继续刚才右侧全放 \(1\) 的策略，这样只会让机器人拿到更多的 \(1\)。
由刚才思路的启发，依然可以在右侧的一部分放上 \(1\)，前提是机器人无法到达，所以可在 \(i+2 \sim m\) 列放上 \(1\)。
那剩下没放的 \(1\) 怎么办？
由于机器人在 \(1\) 行中最多只能左右移动 \(1\) 步，所以只需要间隔着放 \(1\) 即可使机器人在当前行不连续拿到 \(1\)。
代码，注意到达右边放 \(1\) 的地方时回头重新放：
y=i+1-m/2;
for(int k=m;k>i+1;k--)
{a[i][k]=1;
}
while(y>0)
{x+=2;if(x>i+1){x=1;}a[i][x]=1;y--;
}
接下来进入下一行。我们需要跨行错开 \(1\) 的位置。
举个例子：
假设第 \(i\) 行放的间隔的 \(1\) 位于 \(2,4,6\)：
- 当前列 \(x\) 还在最后一个放的位置 \(6\)。
- \(x+2\) 后从第 \(8\) 列开始放。
我们发现，机器人拿到位置 \(6\) 的 \(1\) 后会选择向右，向下，再向右。此时它又拿到了位置 \(8\) 的 \(1\)，显然不优。为使机器人不连续拿到 \(1\)，只需使 \(x+1\) 即可。
第三部分（\(i \geq m\)）
这种情况无法按前两部分的方法在右侧放 \(1\)。
但是每一行仍需放置 \(\frac{m}{2}\) 个 \(1\)。所以，我们应在无法避免的情况下尽可能地少让机器人连续拿到 \(1\)。
所以我们应避免出现连续的 \(1\)，此时行内交替放 \(1\) 即可：
if(i>=m)
{for(int k=1;k<=m;k++){a[i][k]=k%2;}continue;
}
代码
AC Code
#include <iostream>
using namespace std;
int n,m,a[5005][5005],x=-1,y;
int main()
{cin >> n >> m;for(int i=1;i<=n;i++){if(i+1<=m/2){for(int k=m;k>m/2;k--){a[i][k]=1;}continue;}else if(i>=m){for(int k=1;k<=m;k++){a[i][k]=k%2;}continue;}y=i+1-m/2;for(int k=m;k>i+1;k--){a[i][k]=1;}while(y>0){x+=2;if(x>i+1){x=1;}a[i][x]=1;y--;}x++;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout << a[i][j] << " ";}cout << "\n";}return 0;
}