A.Direction Change

在这里插入图片描述

E. Half Queen Cover（GOOD）

在这里插入图片描述

思路（找必要条件然后构造）

假定 $k$ 个皇后满足题意，这 $k$ 个皇后至多占据k行，至多占据k列。因此至少 $n ? k$ 行没有皇后占据，至少 $n ? k$ 列没有皇后占据。因此至少有 $\times (n-k)$ 格点未被占据。
必须要使这k个半皇后覆盖至少这 $\times （n - k)$ 个格点。考察这些格点的第一行，第一列所有格点。每一个只能由一个不同的半皇后得到。因此必须要有
$\geq (n - k - 1) + (n - k - 1) + 1$
即 $\geq \lceil \frac{2n - 1}{3} \rceil$
目标转换为构造 $k = (n ? k ? 1) + (n ? k ? 1) + 1$ 的方案。

构造思路1（官方）

分n的不同情况讨论。
当 $n = 3 x + 2$ ,则 $k = 2 x + 1$ 。放置策略如图所示：
当 $n = 3 x$ ，则 $k = 2 x$ .先在右下角放置1个，转换为 $n = 3 (x ? 1) + 2$ ， $k = 2 (x ? 1) + 1$ 的上述问题。
当 $n = 3 x + 1$ ,则 $k = 2 x + 1$ 。现在右下角放置2个。转换为 $n = 3 (x ? 1) + 2$ ， $k = 2 (x ? 1) + 1$ 的上述问题。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <chrono>
#include <math.h>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int count = 0;
    int n1 = n;
    if(n == 1) {cout <<1 << endl;cout << 1 << " " << 1 << endl;return 0;}
    while(n%3 !=2)
    {
        n--;    
        count ++;
    }
    int x = (n - 2) / 3;
    count += (2*x+1);
    cout << count << "\n";
    for(int i = n+1;i<=n1;i++)
    {
        cout << i << " " << i << "\n";
    }
    //开始的x+1个放在左上角
    for(int i = 1;i<=x+1;i++) cout << i << " " << x+2-i<<"\n";
    //剩下的x个放在右下角
    for(int i = n-x+1;i<=n;i++) cout<<i<<" "<<2*n-x+1 - i << "\n";
    //system("pause");
    return 0;
}

构造思路2

如果能使得 $(n ? k) ? (n ? k)$ 的方格点紧靠一起，形成方阵，最有可能使用为了将该方阵第一行，第一列的格点填满而必须添加的皇后将该方阵填满的目的。
可以让未摆放皇后的行集中在下侧，未摆放皇后的列集中在右侧。从而形成 $(n ? k) ? (n ? k)$ 的方阵。在左上角的 $\times k$ 方阵中，每条蓝线和绿线上都应摆放一个半皇后，如图所示，显然存在将这些皇后放在不同行，不同列上的摆法（打勾位子）。
当 $k = (n ? k ? 1) + (n ? k ? 1) + 1$ 不存在整数解时，参照官方解答在右下角摆放后再转换为上述问题。

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <map>
#include <queue>
#include <chrono>
#include <math.h>
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int count = (int)ceil((double)(2*n - 1) /3);
    cout << count << endl;
    if(n==1) {cout << 1 << " " << 1 << endl;return 0;}
    while((2*n - 1) % 3 != 0)
    {
        cout << n << " " << n << endl;
        n--;
    }
    int k = (2*n-1)/3;
    int j = 1;
    for(int i = 1;i<=k;i++)
    {
        cout << i <<" "<< j << endl;
        j+=2;
        if(j>k) j=2;
    }
    system("pause");
    return 0;
}