题解：P13556 【MX-X15-T3】画圈圈

题目大意

多组数据.
数据给定一个 $k$ 和一个 $l$ 。生成一个长宽为 $n×m$ 的表格，将其中每组满足 $i+j \mod k = 0$ 的格子 $(i,j)$ 圈起来。该表格同时使得其中的连通块数量 $s≥l$ 。求出满足条件的 $n$ , $m$ 中 $n+m$ 的最小值。

解题

零分做法

看到这个联通块，我就想到了用搜索做
思路: 用广搜 (bfs) 寻找未涂色区域，但会 TLE !
~~连一个点都骗不到分 qwq~~

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
bool color[MAX][MAX],v[MAX][MAX];
int dx[4] = {-1, 1, 0, 0},dy[4] = {0, 0, -1, 1};
int count(int n, int m, int k) {
    memset(color, false, sizeof(color));memset(v, false, sizeof(v));//清空
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if ((i + j) % k == 0) {color[i][j] = true;/*涂色*/}
        }
    }
    int x = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!color[i][j] && !v[i][j]) {
                x++;int queue[MAX*MAX][2],front = 0,p = 0;
                //bfs
                queue[p][0]=i;
                queue[p][1]=j;
                p++;v[i][j] = true;
                while(front<p){
                    int x=queue[front][0],y=queue[front][1];front++;
                    for (int d = 0; d < 4; d++) {
                        int nx=x+dx[d];
                        int ny=y+dy[d];
                        if(nx>=1&&nx<=n&&ny >=1&&ny<=m&&!color[nx][ny]&&!v[nx][ny]) {
                            v[nx][ny]=true;
                            queue[p][0]=nx;queue[p][1]=ny;p++;
                        }
                    }
                }
            }
        }
    }
    return x;
}
//寻找n+m最小值
int find(int k, int l) {
    if (l == 1) {return 1;}
    for (int sum=2;sum<=100;sum++) {
        for (int n=1;n<=sum/2;n++) {
            int m=sum-n,x=count(n,m,k);
            if (m<1) continue;
            if (x>=l) {return sum;}
        }
    }
    return -1;
}
int main() {
    int t,k,l;cin>>t;
    while(t--){cin>>k>>l;cout<<find(k,l)<<endl;}
}

满分做法

可以发现:
当

k>2

时,

若矩形高为 $1$ 时 $n+m$ 最优. 例子:
$k=3,l=4$ : ■□■□□■□□■□□■......
得出最少格子数为 $k(l-1)×1$ .
即 $m = k(l-1)$ , $n = 1$ .

再看一个例子:
$k=4,l=4$ : ■□■□□□■□□□■□□□■......
最少格子数还是为 $k(l-1)×1$ .

得出 $n+m$ 最小就是 $k(l-1)+1$ .

解释一下:
$( 0 , 0 )$ 一定是画圈(黑)的,
所以 $l-1$ .
从 $( 0 , 3 )$ 开始每一段是 $1$ 个 ■ 和 $(k-1)$ 个 □,一共 $k$ 个方块,
所以要乘 $k$ .

当

k=2

时:

若矩形高和宽接近时 $n+m$ 最优
可以用二分求解

CPP

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll t,k,l;cin>>t;
	while(t--){
		cin>>k>>l;
		if (k==2){//k=2是特殊情况，用二分求解
			ll L=1,R=10000000000;
			while(L<R){
				ll mid=(L+R)/2,x;x=mid/2;
				if(x*(mid-x)>=2*l){R=mid;}else{L=mid+1;}
			}
			cout<<L<<"\n";
		}else{//使用公式
			if (l==1) cout<<"2\n";
			else{cout<<(l-1)*k+1<<"\n";}
		}
	}
}

公式解题

我们也可以想想

k=2

时的公式

不难发现：
当 $k=2$ 时， $n+m$ 最小值为 $\lfloor{\sqrt{8l}}\rfloor$ .

推出过程:
每 2x2 个方块有 2 个白块
每 2x3 个方块有 3 个白块
.....

白块数量( $l$ )总是 $n×m/2$
可以得出 $2l = nm$ .
n+m 最小值就会是 $2\sqrt{2l}$ .
简化一下就是 $\sqrt{8l}$ .
当然，记得向下取整
得出公式 $\lfloor{\sqrt{8l}}\rfloor$ .

于是我们可以写出时间复杂度为

O(T)

的代码
唉~ 也可以AC

CPP

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	ll t,k,l;cin>>t;
	while(t--){
		cin>>k>>l;
		if (k==2){
			cout<<ceil(sqrt(8*l))<<"\n";//使用新公式
		}else{//使用公式
			if (l==1) cout<<"2\n";
			else{cout<<(l-1)*k+1<<"\n";}
		}
	}
}

题解：P13556 【MX-X15-T3】画圈圈

文章操作

题目大意

解题

零分做法

满分做法

公式解题

相关推荐

评论

题解：P13556 【MX-X15-T3】画圈圈

文章操作

题目大意

解题

零分 做法

满分 做法

公式解题

相关推荐

评论

零分做法

满分做法