Points Construction Problem(构造)

admin管理员组

文章数量:1602098

Points Construction Problem(构造)

思路：构造。

考虑：如下无解的情况。

1.每个黑格子的贡献只能是 4 , 2 , 0 4,2,0 4,2,0，所以答案只能是偶数。

2.且 n n n个格子最多贡献 4 n 4n 4n个，则必须满足 m ≤ 4 n m\leq4n m≤4n。

3.考虑我们能构造 m m m的下界：

一条长为 x x x的直链的贡献为： 2 x + 2 2x+2 2x+2，一条长为 x x x，宽为 y y y，形如 L L L的链贡献为： 2 ( x + y ) 2(x+y) 2(x+y)，显然若成为一个长为 x x x，宽为 y y y的矩阵后贡献仍然不变，因为每增加一个格子，贡献 + 2 , − 2 +2,-2 +2,−2是不影响的，所以需要满足 x y ≥ n xy\geq n xy≥n，且 2 ( x + y ) 2(x+y) 2(x+y)最小。

由基本不等式可知： 2 ( x + y ) ≥ m ≥ 2 × 2 x y ≥ 4 n 2(x+y)\geq m\geq2\times 2\sqrt{xy}\geq 4\sqrt{n} 2(x+y)≥m≥2×2xy ​≥4n ​。

所以 m ≥ 4 n m\geq4\sqrt{n} m≥4n ​。即当 16 n > m 2 16n>m^2 16n>m2是无解的。

接下来分两种情况构造：

1. m > 2 n + 2 1.m>2n+2 1.m>2n+2。

我们可以构造一条一直链和若干个贡献为 4 4 4的点。

设贡献为 4 4 4的点个数为 x x x，则直链长度为 y = n − x y=n-x y=n−x。

总贡献为：

4 x + 2 y + 2 = m 4 x + 2 ( n − x ) + 2 = m x = m − ( 2 n + 2 ) 2 4x+2y+2=m\\4x+2(n-x)+2=m\\x=\dfrac{m-(2n+2)}{2} 4x+2y+2=m4x+2(n−x)+2=mx=2m−(2n+2)​

因为 m > ( 2 n + 2 ) , m m>(2n+2),m m>(2n+2),m为偶数，显然 x x x必定有解。

2. 2. 2. m ≤ 2 n + 2 m\leq 2n+2 m≤2n+2的情况。

考虑类比无解的情况 3 3 3。

我们构造一条 L L L形状的链，然后不断填充就可以了。

即：用 x + y − 1 x+y-1 x+y−1个点构造出 2 ( x + y ) = m 2(x+y)=m 2(x+y)=m贡献，然后剩下的点 r e s t = n − ( x + y − 1 ) rest=n-(x+y-1) rest=n−(x+y−1)用来填充矩形即可。

m ≤ 2 n + 2 → m 2 ≤ n + 1 m\leq2n+2\rightarrow \dfrac{m}{2}\leq n+1 m≤2n+2→2m​≤n+1。

即我们构造出长和宽和为 m 2 \dfrac{m}{2} 2m​的 L L L链，用 m 2 − 1 \dfrac{m}{2}-1 2m​−1个点 ≤ n \leq n ≤n，显然是有解的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(m&1||m>4*n||n*16>m*m) puts("No");
        else {
            puts("Yes");
            if(m>2*n+2){
                int x=(m-(2*n+2))/2,y=n-x;
                for(int i=1;i<=x;i++) printf("1 %d\n",(i<<1));
                for(int i=1;i<=y;i++) printf("3 %d\n",i);
            }
            else {
                int x=m/4,y=m/2-x;
                 for(int i=1;i<=x;i++) printf("%d 1\n",i);
                 for(int j=2;j<=y;j++) printf("1 %d\n",j);
                int rest=n-(x+y-1);
                for(int i=2;i<=x&&rest>0;i++)
                    for(int j=2;j<=y&&rest>0;j++,rest--)
                        printf("%d %d\n",i,j);
                }
        }
    }
    return 0;
}

本文标签： pointsconstructionProblem