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

· · 题解

题目大意

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

解题

零分 做法

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

#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(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 最优\ 可以用二分求解

#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

#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";}
        }
    }
}