外观
Even Picture 的 n+O(√n) 构造
本蒟蒻的第一篇题解,求过。
成为最优构造的必要条件:
AC CF1368C Even Picture(加强加强加强加强版)
大概是最优构造:
由于楼上同样是 n+O(n) 的大佬没有贴代码,所以比较不了。
用不同颜色将其分成了九块。
左上角/右下角块只有一个点染色,中间块除对角线外染色,其余块按三角形染色。
推算
设每块大小为 s×s,由小学奥数可得
S总=4s2+2s+2
S冗余=8s
S有效=4s2−6s+2
由于 S有效≤n,根据求根公式,令
s=⌊86+16n+4⌋
假如 n−S有效 的剩余部分用形如
##
###
###
###
##
的尾巴接在原图形上面,则有
k=S总+3(n−S有效)
稍加计算可得
n+4n≤k≤n+12n
对于 n≤500 有 k≤748.
优化
如果小尾巴改成递归构造,则上界更新为 min(x+6x+43,x+12x) (纯靠手动调参拟合,一点都不紧)
对于 n≤1000 有 k≤1192.
欣赏一下构造的图形
(在代码中调用 canvas.debug()
即可欣赏)
n=500,k=640
n=500, k=640
##
####
######
########
##########
############
##############
################
##################
####################
#######################
# #####################
### ###################
##### #################
####### ###############
######### #############
########### ###########
############# #########
############### ####### ##
################# ##### ####
################### ### ######
##################### # ########
#################################
#################### # #########
################## ### #######
################ ##### #####
############## ####### ###
############ ######### # ##
########## ###############
######## ######## # ###
###### ###### ### #
#### #### #####
## ## ##
Code:
从普通版一直改到四次加强的屎山。
#include <bits/stdc++.h>
using namespace std;
int n;
void small_main(){
printf("%d\n", 3*n+4);
printf(
"1 1\n"
"1 2\n"
"2 1\n"
"2 2\n"
);
for (int i=1; i<=n; i++){
printf(
"%d %d\n%d %d\n%d %d\n",
i+1, i+2,
i+2, i+1,
i+2, i+2
);
}
}
struct coord {
int x, y;
};
const int maxdebug=80;
char buf[90][90]; // debug only
inline int __flip(bool flip, int size, int x){
return flip ? (size+1-x) : x;
}
struct Canvas {
int xoff, yoff; // 每次画完之后把原点移动到特定位置,方便前后衔接
vector<coord> ans;
int cur_row = 1;
void draw(int x, int y){
ans.push_back({x+xoff, y+yoff});
}
void debug(){
memset(buf, ' ', sizeof buf);
for (int i=0; i<=maxdebug; i++){
buf[i][maxdebug+2] = '\n';
buf[i][maxdebug+3] = '\0';
}
for (coord &c: ans) {
buf[c.x][c.y] = '#';
}
for (int i=0; i<=maxdebug; i++){
cout << buf[i];
}
}
void output(){
printf("%d\n", ans.size());
for (coord &c: ans) {
printf("%d %d\n", c.x, c.y);
}
}
void draw_triangle(int size, int row, int col, bool xflip, bool yflip){
// xflip=yflip=0时
// ###
// ##
// #
// xflip 上下翻转,yflip 左右翻转
int x0 = row * size, y0 = col * size;
for (int i=1; i<=size; i++){
for (int j=1; i+j<=size+1; j++){
draw(x0 + __flip(xflip, size, i),
y0 + __flip(yflip, size, j));
}
}
}
void draw_dhyy(int size, int row, int col){
// 缺对角线的正方形
// ##
// # #
// ##
int x0 = row * size, y0 = col * size;
for (int i=1; i<=size; i++){
for (int j=1; j<=size; j++){
if (i != j){
draw(x0+i, y0+j);
}
}
}
}
} canvas;
int main(){
cin >> n;
if (n<=30){
small_main();
return 0;
}
bool flag = false;
// flag = not 是不是最左上角的
// 处理衔接用
while (n >= 7) {
if (flag){
n--;
}
int size = sqrt(16*n+4);
size = (size + 6) / 8;
// printf("size=%d\n", size);
if (!flag){
canvas.draw(size, size);
}
// 预留空间,1, 1 -> size, size
if (flag){
canvas.xoff -= size - 1;
canvas.yoff -= size - 1;
} else {
flag = true;
}
canvas.draw_triangle(size, 0, 1, 1, 1);
canvas.draw_triangle(size, 0, 2, 1, 0);
canvas.draw_triangle(size, 1, 0, 1, 1);
canvas.draw_dhyy(size, 1, 1);
canvas.draw_triangle(size, 1, 2, 0, 0);
canvas.draw_triangle(size, 2, 0, 0, 1);
canvas.draw_triangle(size, 2, 1, 0, 0);
canvas.draw(2*size+1, 2*size+1);
n -= 4*size*size - 6*size + 2;
// move 2*size+1, 2*size+1 -> 1, 1
canvas.xoff += 2*size;
canvas.yoff += 2*size;
}
for (int i=1; i<=n; i++){
canvas.draw(i+1, i);
canvas.draw(i, i+1);
canvas.draw(i+1, i+1);
}
// canvas.debug();
canvas.output();
return 0;
}