题目地址:http://codeforces.com/contest/980/problem/B

官方题解:

 

题意:

  有一个城市有4行n列,n是奇数,有一个村庄在(1,1),村民在(4,n)钓鱼;还有一个村庄在(4,1),村民在(1,n)钓鱼;现在要修建k个宾馆,不能修建在边界上,问能否给出一种安排方案使得两个村庄的村民到他们各自的活动地点的最短路的条数相等。

思路:

  画了几个实例就应该知道,无论n和k是多少,都可以构建出合理的方案,并且 0k2×(n2),所以全是YES。

  如果k为偶数,那么就上下对称,一列一列横着输出;当k为奇数,我采用的是首先把第二排从中间开始向两边填满,然后第三排则是从中间一格的两边开始填。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<iostream>
 7 #include<map>
 8 #include<vector>
 9 #include<set>
10 #include<queue>
11 using namespace std;
12 const int N = 100;
13 int main() {
14     int n, k;
15     char ans[5][N];
16     scanf("%d %d", &n, &k);
17     printf("YES\n");
18     for (int i = 0; i < 5; i++)
19     {
20         for (int j = 0; j < N; j++)
21         {
22             ans[i][j] = '.';
23         }
24     }
25     if (k % 2 == 0) 
26     {
27         int p = 2;
28         while (k > 0) 
29         {
30             ans[2][p] = '#';
31             ans[3][p] = '#';
32             p++;
33             k -= 2;
34         }
35     }
36     else 
37     {
38         if (k == 1) 
39         {
40             ans[2][n / 2 + 1] = '#';
41         }
42         else if (k == 3) 
43         {
44             int s = (n + 1) / 2;
45             ans[2][s] = '#';
46             ans[2][s - 1] = '#';
47             ans[2][s + 1] = '#';
48         }
49         else 
50         {
51             ans[2][2] = '#';
52             ans[2][3] = '#';
53             ans[3][2] = '#';
54             int p = 4;
55             k -= 3;
56             while (k > 0) 
57             {
58                 k -= 2;
59                 ans[2][p] = '#';
60                 ans[3][p] = '#';
61                 p++;
62             }
63         }
64     }
65     for (int i = 1; i <= 4; i++) 
66     {
67         for (int j = 1; j <= n; j++) 
68         {
69             printf("%c", ans[i][j]);
70         }
71         printf("\n");
72     }
73     return 0;
74 }