一道简单的构造题,其实不用想的十分复杂的说。
首先,最多发射的宇宙射线 \(sum\) 也最多为 \(sum_{max}=min(m,n)\) 也就是说,无论如何摆放石子,也只能达到这个数量。那么我们的目的便变成了如何让石子变成这一个形状。
如上图,在一个 \(3\times6\) 的矩阵中,其实只要三颗石子即可满足最多的射线,那其他的石子呢?随便放,直到放完,其他的石子并无作用。
将上一个特殊的例子推广一下,对于一个矩阵 \(a[m][n]\) 来说,只需沿着 \(a[i][j](其中i=j)\) 放置即可达到最多的射线量,剩下的石子即可随便摆放。
#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 2010;
int t,n,m,k;
char a[maxn][maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
cin>>n>>m>>k;
seq(i,1,n){
seq(j,1,m){
if(j==i&&k>0){ //为对角线,且有石子剩余
a[i][j]='S'; //摆放石子
k--;
}
else{
a[i][j]='.';
}
}
}
seq(i,1,n){
seq(j,1,m){
if(k>0&&a[i][j]!='S'){
cout<<'S'; //能放就放,随便
k--;
}
else{
cout<<a[i][j];
}
}
cout<<'\n';
}
}
return 0;
}
标签:seq,题解,石子,Radiation,LAOI,摆放,&&
From: https://www.cnblogs.com/adsd45666/p/18402828