link
思维 2400
题意
给你一个 n n n 行 n n n 列的棋盘，一个皇后可以控制住它所在的行、列、及其对角线的所有格子，问最少需要多少个皇后可以控制住整个棋盘，并构造一种放置方案。
思路
emm，其实并不会证明这是最少的。
显然，不会有两个皇后出现在同一行or同一列，也就是说，假设最少需要
k
k
k 个皇后，那么一定有
k
k
k 行
k
k
k 列直接被控制了，而剩下的一个
(
n
?
k
)
×
(
n
?
k
)
(n-k) \times (n-k)
(n?k)×(n?k) 的矩形需要由对角线控制，这个矩形一共有
2
×
(
n
?
k
)
?
1
2\times (n-k)-1
2×(n?k)?1 条对角线，所以
k
≥
2
×
(
n
?
k
)
?
1
k \geq 2\times (n-k)-1
k≥2×(n?k)?1，也就是
k
=
(
2
n
?
1
)
/
3
k = (2n-1)/3
k=(2n?1)/3 向上取整。
构造方法：只要在左上角的
k
×
k
k\times k
k×k 矩形中选不在同一行同一列且包含所有对角线的就可以了，画一画就比较容易得出。
代码
void solve() {
int n;
cin >> n;
int ans = (2 * n - 1 + 2) / 3;
cout << ans << endl;
for(int i = 1, j = 1; i <= ans; i++) {
cout << i << ' ' << j << endl;
j += 2;
if(j > ans) j = 2;
}
}
