NOIP2023模拟12联测33 A. 构造
文章目录
- NOIP2023模拟12联测33 A. 构造
- 题目大意
- 思路
- code
题目大意
构造题
思路
想一种构造方法,使得 y y y 能够凑成尽可能多的答案
第一行 x y r y ⋯ r xyry \cdots r xyry⋯r
第二行 r y x y ⋯ x ryxy \cdots x ryxy⋯x
第三行 x y r y ⋯ r xyry\cdots r xyry⋯r
把最后一列空出来。
此时有 2202 2202 2202 个答案
如果 n < 2202 n < 2202 n<2202
贪心从后往前把 y y y 变成 x x x
然后按照 r y x y r ⋯ ryxyr \cdots ryxyr⋯ 填最后一列,直到现在的答案为 n n n 为止,剩下的用 x x 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;
}