2020暑期D3-D 思路+证明

2020暑期D3-D 思路+证明
主为自用，欢迎指正。

https://ac.nowcoder.com/acm/contest/5668/D

前置知识：

题意：
一无限大二维平面中，存在无穷的单位方格，所有方格初始为白色，现给n方格涂黑，要求存在m个点对。
点对符合：上下左右相邻的点为异色。
输入 n，m。
输出 存在则‘Yes’，且给出符合坐标；否则‘No’。

思路：
先判是否存在，不存在的情况同意输出‘No’。容易得到若有n个黑格，则点对数量m必然存在上下界，同时m必须为偶数（若存在黑格相邻，点对数量4n-2相邻次数）
if(m>4n||m%2)，则为‘No’；
设黑格存在与不同a行，不同b列。则点对数量为2（a+b）；
首先对黑格团进行模拟，得到黑格为n时最少的点对数，且记录黑格块位置。判断掉不可能的情况，在存在题意情况下遍历找出成团黑格的数量，并记录位置，后输出不成团的位置即可。

随后翻阅大佬题解发现一种思路清晰，代码明了的思路。特在此说明。（参考自http://www.koule2333.top:3000/s/r13vgvelP）
首先考虑所有黑格皆排成一排，则mm=2*n+2(除第一个点提供四个点对)，若m>mm，则每取走一个末尾黑格，对点数+2；若m<mm，则将原一排黑格尽量均分长高相等的‘L’形，随后从末尾取黑格放置最小行，最小列处，点对数-2.

代码步骤：

AC代码：
第一种思路：

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 111;
ll num[100];
ll mp[1000][1000] = {0};
pair<ll, ll> pp[100];
int main() {
    num[1] = 4;
    pp[1] = {1, 1};
    for (ll i = 2; i <= 50; ++i) {    //黑格块模拟
        ll j;
        for (j = 1; j <= i; ++j) {
            if (j * j >= i) {
                break;
            }
        }
        num[i] = (j + (i + j - 1) / j) * 2;    //得黑格块点对
        pp[i] = {j, (i + j - 1) / j};        //确定黑格块相异行列值
    }
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n, m;
        scanf("%lld%lld", &n, &m);
        for (int i = 1; i <= 100; ++i) {
            for (int j = 1; j <= 100; ++j) {
                mp[i][j] = 0;
            }
        }
        if ((m & 1) || (m > 4 * n)) {
            puts("No");
        } else {
            ll flag = 0;
            ll depe = 0;
            ll trans = 0;
            ll nnn, mmm;
            for (ll i = 1; i <= n; ++i) {
                // 黑格团点数
                ll num_d = i;
                ll minn = num[i] + 4 * (n - i), maxx = 2 * i + 2 + 4 * (n - i);    //确定m的上下界
                if (m <= maxx && m >= minn) {
                    flag = 1;
                    depe = n - i;
                    trans = (m - minn) / 2;    //实际相邻黑格数
                    nnn = pp[i].first, mmm = pp[i].second;
                    for (int ii = pp[i].first; ii >= 1; --ii) {
                        for (int jj = pp[i].second; jj >= 1; --jj) {    //位置递减遍历，黑格团位置被登记。
                            mp[ii][jj] = 1;
                            --num_d;
                            if (!num_d) break;
                        }
                        if (!num_d) break;
                    }
                    break;
                }
            }
            if (!flag) {
                puts("No");
            } else {
                puts("Yes");
                for (int i = 1, num = 1; num <= depe; ++num, i += 5) {
                    printf("%d %d\n", i, 10000000);
                }
                int ni = 1, nj = 1;
                while (mp[ni][nj] == 0) {
                    ++nj;
                    if (nj == mmm) {
                        nj = 1;
                        ++ni;
                    }
                }
                int toi = nnn, toj = mmm + 1;
                while (trans--) {
                    mp[ni][nj] = 0;
                    ++nj;
                    if (nj == mmm) {
                        nj = 1;
                        ++ni;
                    }
                    mp[toi][toj++] = 1;
                }
                for (int i = 1; i <= 100; ++i) {
                    for (int j = 1; j <= 100; ++j) {
                        if (mp[i][j]) {
                            printf("%d %d\n", i, j);
                        }
                    }
                }
            }
        }
    }
    return 0;
}

第二种思路：

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
struct Point{
    int x,y;
}p[N]; int n,m,tot,t;
bool solve(){
    tot=0;
    if(m&1) return false;
    if(n*4<m) return false;
    if(n==1){
        if(m==4){
            p[++tot].x=1;
            p[tot].y=1; return true;
        }
        else return false;
    }
    if(m<4) return false;
    if(n*4==m){
        for(int i=1;i<=n;++i)
            p[i].x=i*2+12345,p[i].y=i*2+12345;
        tot=n;
        return true;
    }
    int x=0,y=0,z=0;
    x=m/2-1;
    if(x>n){
        for(int i=1;i<=x-n;++i){
            p[i].x=i*2+12345,p[i].y=i*2+12345;
        }
        tot=x-n; x-=x-n;
        if(x<0) return false;
        for(int i=tot+1;i<=n;++i){
            p[i].x=1; p[i].y=i;
        } tot=n;
        return true;
    }else{
        z=x; x=(z+1)/2; y=(z+1)-x;
        if(x*y<n) return false;
        for(int i=1;i<=x;++i){
            ++tot; p[tot].x=i; p[tot].y=1;
        }
        for(int i=2;i<=y;++i){
            ++tot; p[tot].y=i; p[tot].x=1;
        }
        for(int i=2;i<=x;++i){
            for(int j=2;j<=y;++j){
                if(tot==n) break;
                tot++;
                p[tot].x=i; p[tot].y=j;
            }
            if(tot==n) break;
        }
        return true;
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        if(!solve()) printf("No\n");
        else{
            printf("Yes\n");
            for(int i=1;i<=tot;++i)
                printf("%d %d\n",p[i].x,p[i].y);
        }
    }
}

简单图证：

注：
代码还将另作注释。