B. Nauuo and Chess （简单构造）
Nauuo is a girl who loves playing chess.
One day she invented a game by herself which needs 𝑛n chess pieces to play on a 𝑚×𝑚m×m chessboard. The rows and columns are numbered from 11 to 𝑚m. We denote a cell on the intersection of the 𝑟r-th row and 𝑐c-th column as (𝑟,𝑐)(r,c).
The game's goal is to place 𝑛n chess pieces numbered from 11 to 𝑛n on the chessboard, the 𝑖i-th piece lies on (𝑟𝑖,𝑐𝑖)(ri,ci), while the following rule is satisfied: for all pairs of pieces 𝑖i and 𝑗j, |𝑟𝑖−𝑟𝑗|+|𝑐𝑖−𝑐𝑗|≥|𝑖−𝑗||ri−rj|+|ci−cj|≥|i−j|. Here |𝑥||x| means the absolute value of 𝑥x.
However, Nauuo discovered that sometimes she couldn't find a solution because the chessboard was too small.
She wants to find the smallest chessboard on which she can put 𝑛n pieces according to the rules.
She also wonders how to place the pieces on such a chessboard. Can you help her?
The only line contains a single integer 𝑛n (1≤𝑛≤10001≤n≤1000) — the number of chess pieces for the game.
The first line contains a single integer — the minimum value of 𝑚m, where 𝑚m is the length of sides of the suitable chessboard.
The 𝑖i-th of the next 𝑛n lines contains two integers 𝑟𝑖ri and 𝑐𝑖ci (1≤𝑟𝑖,𝑐𝑖≤𝑚1≤ri,ci≤m) — the coordinates of the 𝑖i-th chess piece.
If there are multiple answers, print any.
2
2 1 1 1 2
4
3 1 1 1 3 3 1 3 3
In the first example, you can't place the two pieces on a 1×11×1 chessboard without breaking the rule. But you can place two pieces on a 2×22×2 chessboard like this:
In the second example, you can't place four pieces on a 2×22×2 chessboard without breaking the rule. For example, if you place the pieces like this:
then |𝑟1−𝑟3|+|𝑐1−𝑐3|=|1−2|+|1−1|=1|r1−r3|+|c1−c3|=|1−2|+|1−1|=1, |1−3|=2|1−3|=2, 1<21<2; and |𝑟1−𝑟4|+|𝑐1−𝑐4|=|1−2|+|1−2|=2|r1−r4|+|c1−c4|=|1−2|+|1−2|=2, |1−4|=3|1−4|=3, 2<32<3. It doesn't satisfy the rule.
However, on a 3×33×3 chessboard, you can place four pieces like this:
思路：
其实不难想到如果想要放的棋子最多，我们肯定是把最大的放在右下角，最小的放左上角。 那么可以得到 2 * (n - 1) >= m-1 (n是棋盘行数，m是棋子数)
也就是 2 *n - 1 >= m
有了这个关系，我们就沿着边拜放就可以了
1 #include <iostream> 2 #include <time.h> 3 #include <algorithm> 4 #include <stdio.h> 5 6 typedef long long LL; 7 8 using namespace std; 9 10 int main(){ 11 int m; 12 scanf("%d",&m); 13 int n = m/2+1; 14 printf("%d\n",n); 15 for (int i=1;i<=n && i<=m;i++){ 16 printf("%d %d\n",1,i); 17 } 18 int cnt = m-n; 19 for (int i=2;cnt;cnt--,i++){ 20 printf("%d %d\n",i,n); 21 } 22 return 0; 23 24 }
查看13道真题和解析