NOIP2023模拟12联测33 构造

本文主要是介绍NOIP2023模拟12联测33 构造，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给定一个非负整数$n$，请构造出一个不超过$40\times 40$的矩阵，每个位置填$r$、$y$、$x$三者之一，使得连续的三个格子按顺序构成字符串$ryx$恰好$n$个。

这里连续的是指同一行、同一列或者同一$45^{\circ }$度斜线，方向任意（共$8$个方向）。

$0\le n\le 2222$

题解

我们先考虑如何构造能使得字符串$ryx$能达到$2222$个。对于一个$40\times 40$的矩阵，我们可以先每一行放满$ryxy$。

$$\begin{gathered} ryxyryxy\cdots \\ ryxyryxy\cdots \\ ryxyryxy\cdots \\ ryxyryxy\cdots \end{gathered}$$

这样每一行按从前往后的顺序有$10$个字符串$ryx$，从后往前的顺序有$9$个字符串$ryx$。每列$r$往右上能有$38$个字符串$ryx$，往右下能有$38$个字符串$ryx$。除了第一列$r$，每列$r$往左上能有$38$个字符串$ryx$，往左下能有$38$个字符串$ryx$。那么总共有$(10+9)\times 40+(38+38)\times 10+(38+38)\times 9=2204$个字符串$ryx$，还差$18$个。

我们发现，最后一列的$y$是没有用到的，那么我们把这一列全部改为$ryxy$，那么从上往下有$10$个字符串$ryx$，从下往上有$9$个字符串$ryx$，那么这样的话，总共就有$2204+10+9=2223$个字符串$ryx$，我们用这个方法能够取到题目中$n$的最大值。

令矩形的长和宽为$k=40$，我们可以先打一个能够$O(k^2)$判断矩形中字符串$ryx$的个数的函数$gt()$。先将整个矩形的每个位置视为空的，然后依次在每一行中从第一个为空的位置开始放入一行$ryxy$。如果每一行都放完一次之后$gt()\le n$，则继续从第一行开始在每一行中从第一个为空的位置开始放入一行$ryxy$，直到$gt()>n$，就把当前放的$ryxy$删去。此时，$gt()$不一定等于$n$，所以我们还要用最后一列来进行调整。同样地，从上往下不断放入$ryxy$，直到$gt()>n$就将当前放入的$ryxy$删去。注意每次放入一个$ryxy$最多会使$gt()$增加$2$，那么最后$gt()$要么等于$n$，要么等于$n-1$。如果等于$n-1$，就在最后一列的末尾从下往上放入$ryx$。因为$n\le 2222<2223$，所以$ryxy$不会放到最后一列的最后三个位置，那么最后放的$ryx$对之前放的字母不会有任何影响。

对于为空的部分，我们全部填上$y$。因为左边部分结尾的都是$y$，而右边只有一列不全为$y$，所以将为空的部分填上$y$不会增加$ryx$的数量。

这样就可以构造出满足题意的矩阵了。

时间复杂度为$O(k^4)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,fl;
char a[45][45];
int gt(){int re=0;for(int i=1;i<=40;i++){for(int j=1;j<=40;j++){if(a[i][j]=='r'){if(i-2>=1){if(a[i-2][j]=='x'&&a[i-1][j]=='y') ++re;}if(i+2<=40){if(a[i+2][j]=='x'&&a[i+1][j]=='y') ++re;}if(j-2>=1){if(a[i][j-2]=='x'&&a[i][j-1]=='y') ++re;}if(j+2<=40){if(a[i][j+2]=='x'&&a[i][j+1]=='y') ++re;}if(i-2>=1&&j-2>=1){if(a[i-2][j-2]=='x'&&a[i-1][j-1]=='y') ++re;}if(i-2>=1&&j+2<=40){if(a[i-2][j+2]=='x'&&a[i-1][j+1]=='y') ++re;}if(i+2<=40&&j-2>=1){if(a[i+2][j-2]=='x'&&a[i+1][j-1]=='y') ++re;}if(i+2<=40&&j+2<=40){if(a[i+2][j+2]=='x'&&a[i+1][j+1]=='y') ++re;}}}}return re;
}
int main()
{
//	freopen("ryx.in","r",stdin);
//	freopen("ryx.out","w",stdout);scanf("%d",&n);for(int i=1;i<=40;i++){for(int j=1;j<=40;j++){a[i][j]='y';}}for(int j=1;j<=40;j+=4){fl=0;for(int i=1;i<=40;i++){a[i][j]='r';a[i][j+1]='y';a[i][j+2]='x';a[i][j+3]='y';if(gt()>n){a[i][j]='y';a[i][j+1]='y';a[i][j+2]='y';a[i][j+3]='y';fl=1;break;}}if(fl) break;}for(int i=1;i<=40;i+=4){a[i][40]='r';a[i+1][40]='y';a[i+2][40]='x';a[i+3][40]='y';if(gt()>n){a[i][40]='y';a[i+1][40]='y';a[i+2][40]='y';a[i+3][40]='y';break;}}n-=gt();if(n){a[40][40]='r';a[39][40]='y';a[38][40]='x';}printf("40 40\n");for(int i=1;i<=40;i++){for(int j=1;j<=40;j++){printf("%c",a[i][j]);}printf("\n");}return 0;
}

这篇关于NOIP2023模拟12联测33 构造的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---