NOIP2023模拟12联测33 A. 构造
题目大意
构造题
思路
想一种构造方法，使得 \(y\) 能够凑成尽可能多的答案
第一行 \(xyry \cdots r\)
第二行 \(ryxy \cdots x\)
第三行 \(xyry\cdots r\)
把最后一列空出来。
此时有 \(2202\) 个答案
如果 \(n < 2202\)
贪心从后往前把 \(y\) 变成 \(x\)
然后按照 \(ryxyr \cdots\) 填最后一列，直到现在的答案为 \(n\) 为止，剩下的用 \(x\) 代替。
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 45;
int n , ans[N][N] , sum , x , y;
int main () {
freopen ("ryx.in" , "r" , stdin);
freopen ("ryx.out" , "w" , stdout);
scanf ("%d" , &n);
fu (i , 1 , 40) {
fu (j , 1 , 40) {
if (j % 2 == 0) ans[i][j] = 2;
else if (i % 2 == ((j - 1) / 2) % 2) ans[i][j] = 3;
else ans[i][j] = 1;
}
ans[i][40] = 1;
}
x = 40 , y = 39 , sum = 2204;
while (sum > n) {
ans[x][y] = 2;
if (x <= 2) sum -= (y != 1);
else if (y == 39) sum -= 2;
else if (y == 1) sum --;
else sum -= 3;
if (y == 1) x -- , y = 39;
else y -= 2;
}
if (n > sum) {
ans[1][40] = 1;
ans[2][40] = 2;
ans[3][40] = 3;
x = 3;
sum ++;
while (sum < n) {
x ++;
ans[x][40] = 2;
x ++;
if (((x - 1) / 2) % 2 == 0) ans[x][40] = 1;
else ans[x][40] = 3;
sum ++;
}
}
printf ("40 40\n");
fu (i , 1 , 40) {
fu (j , 1 , 40) {
if (ans[i][j] == 1) printf ("r");
else if (ans[i][j] == 2) printf ("y");
else printf ("x");
}
printf ("\n");
}
return 0;
}