SS240930B. 字符画（picture）

SS240930B. 字符画（picture）

在一个 \(10^7 \times 10^7\) 的格子里，涂上至多 \(900\) 个格子。满足不存在一个格子恰好 \(1\) 个或 \(3\) 个相邻位置被涂色，定义恰好四个相邻格子都涂了颜色的格子是好的格子。构造一种涂色方案使得好的格子数量恰好是 \(n\le 300\)。

涂颜色的格子和好的格子比例是 \(3:1\)，因此需要聪明的构造方法。

这里分享一个与题解不同，应该优于题解的构造方法。

好的格子一定是需要外面有一圈涂色格子的，因此我们希望涂色的格子尽量少，就要使好的格子尽量聚集在一起，然后外面一圈涂上颜色，保住好的格子。

考虑好的格子形成一个矩形，矩形外面应该怎么涂颜色。

xxxxxxx
xxxxxxx
xxxxxxx
xxxxxxx

我们想让上面这些 x成为好的格子，它们必须四个方向都涂了颜色。用 o 表示涂了颜色但是不好的格子。

 ooooooo
oxxxxxxxo
oxxxxxxxo
oxxxxxxxo
oxxxxxxxoooooooo

显然这样不行，因为有很多 o 有 \(3\) 个方向上涂了颜色，这样不合法。

然后我们惊奇的发现，对于连续长度为 \(len\) 的一坨 oooooooo，可以在它外面涂 \(len-2\) 个格子，这样原来这一坨就都合法了，其中中间有些变成了四度点好的格子，也就是 x。可以变成这样：

       ooxooxxxooxxxxxooxxxxxxxoo xxxxxxxxx o
ox xxxxxxxxx xo
ox xxxxxxxxx xoo xxxxxxxxx ooxxxxxxxooxxxxxooxxxooxoo

大概是一个菱形的样子。因为我们原来 x 的矩形是 \(4\times 7\) 的，所以这个菱形上下是尖锐的，左右是合法的。如果使原来的矩形长宽都是偶数，就可以构造出一个合法的矩形。这样构造需要用的涂色格子很少。

但是 \(n\) 不一定恰好可以构造出这样的菱形。我们可以想到多搞几个菱形凑出 \(n\)。

我们发现尖锐的点是好拼上另一个菱形的，大概这样：

      ooxooxxxooxxxxxooxxxxxooxxxooxooooxooxxxooxxxxxooxxxxxxxooxxxxxxxxxo
oxxxxxxxxxxxo
oxxxxxxxxxxxooxxxxxxxxxooxxxxxxxooxxxxxooxxxooxoo

当然你也可以把左右变成尖锐的，然后把菱形左右连起来。

假设我们把上下变成尖锐的，上下连接菱形。

因为题目给的 \(900\) 足够宽裕，而且坐标可以到 \(10^7\)，所以我们干脆只上下拼，菱形的左右全部设成不尖锐的。

这样的菱形高度是偶数，宽度是奇数。

设高度是 \(2x+2\)，计算这样的菱形可以贡献多少个好的节点。等差数列计算。

\[2((1+(2x-1))\times x \div 2 )= 2x^2 \]

于是我们从大到小枚举 \(x\)，然后把菱形拼起来。

对于最上面和最下面的尖锐的点，可以参考样例二，把它们连起来。

像这样：

      oooooooooo       ooxo      ooxxxo     ooxxxxxo    ooxxxxxo    ooxxxo     ooxo      oo       oo       ooxo      ooxxxo     ooxxxxxo    ooxxxxxxxo   ooxxxxxxxxxo  o
oxxxxxxxxxxxo o
oxxxxxxxxxxxo ooxxxxxxxxxo  ooxxxxxxxo   ooxxxxxo    ooxxxo     ooxo      oo       oooooooooo

反正我们有 \(900\) 可以涂，所以绰绰有余。

然后还有个问题，就是这样的最小的菱形的贡献是 \(2\)，所有这样的菱形贡献都是偶数。因此如果 \(n\) 是奇数就无法构造。

继续参考样例二，可以弄一个交叉。反正有 900 随便弄，类似这样：

         ooooooo    ooooxoo  oo  o o  ooxo ooo  ooxxxo     ooxxxxxo    ooxxxxxo    ooxxxo     ooxo      oo       oo       ooxo      ooxxxo     ooxxxxxo    ooxxxxxxxo   ooxxxxxxxxxo  o
oxxxxxxxxxxxo o
oxxxxxxxxxxxo ooxxxxxxxxxo  ooxxxxxxxo   ooxxxxxo    ooxxxo     ooxo      oo       oooooooooo

完美解决问题。\(n=300\) 只用涂 \(441\) 个，至少比题解优秀。

这个做法最大的优点，虽然对于小数据可能更劣，但是增长速度很慢。比如当 \(n=10^5\) 的时候，只需要涂 \(103226\) 个。

当然如果更精细地构造，比如横着竖着都拼菱形，肯定可以有更优的构造方案。但是那样不好写

code

#include<bits/stdc++.h>
//#define LOCAL 
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
const int N=1e5+7;
int n;
int a[N];
int cnt;
int x=1,y;
typedef pair<int,int> pii;
#define fi first
#define se second
vector<pii > vec;
void paint(int m) {if(cnt==1) x=m,y=0;int xx=x;rep(i,0,m) {y++;rep(j,0,2*i) {vec.push_back({xx+j,y});}xx--;}per(i,m,0) {y++;xx++;rep(j,0,2*i) {vec.push_back({xx+j,y});}}
}
const int ans1[500]={33,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,2,1,2,8,3,1,3,4,3,5,3,6,3,8,4,1,4,4,4,6,4,8,5,1,5,4,5,5,5,6,5,7,5,8,6,1,6,6,7,1,7,2,7,3,7,4,7,5,7,6,};//n=1 的方案，应该要特判。懒得再构造一个，直接复制样例
int main() {#ifdef LOCALfreopen("in.txt","r",stdin);freopen("my.out","w",stdout);#else freopen("picture.in","r",stdin);freopen("picture.out","w",stdout);#endifsf("%d",&n);if(n==1) {rep(i,0,66) pf("%d ",ans1[i]);return 0;}per(x,12,1) {while(2*x*x<=n) {a[++cnt]=x;n-=2*x*x;paint(x);//画菱形}}if(n) {//画交叉并连起尖锐的点++y;rep(i,0,5) vec.push_back({x+i,y});rep(i,-2,2) if(i!=0) vec.push_back({x+3,y+i});vec.push_back({x+4,y-2}),vec.push_back({x+5,y-2});vec.push_back({x+5,y-1});rep(i,4,7) vec.push_back({x+i,y+2});int mx=max(x+7,x+x+2);rep(i,8,x+2) vec.push_back({x+i,y+2});rep(i,x,mx) vec.push_back({i,0});y+=2;rep(i,1,y-1) vec.push_back({mx,i});}else{//连起尖锐的点++y;rep(i,0,x+2) vec.push_back({x+i,0}),vec.push_back({x+i,y});rep(i,1,y-1) vec.push_back({x+x+2,i});}pf("%d\n",(int)vec.size());for(auto u:vec) {pf("%d %d\n",u.fi+2,u.se+2);}
}

如果要跑更大的 \(n\) 就把 \(x\) 从大一点开始枚举就好了。