Codeforces 980B 题解报告

我不是女神ヾ 2022-05-25 07:44 170阅读 0赞

# 一、题目 #

[http://codeforces.com/contest/980/problem/B][http_codeforces.com_contest_980_problem_B]

（一）本题考察对称性  
n = 5, k = 4时，以下两种方案符合题意

..... 
    .##..
    .##..
    .....

..... 
    .#.#.
    .#.#.
    .....

以下一种方案不符合题。因为这种方案，从（1，1）到（5，5）有2条最短距离，从（4，1）到（1，5）有4条最短距离。

..... .###. .#... .....

（二）考虑到四个边不能放旅馆，所以最多可放2 (n - 2)个旅馆。题目中k的取值范围为(0, 2(n - 2)。结果必然为”YES”，不可能是”NO”

（三）无论旅馆数量是奇数还是偶数，都能找到符合条件的放置方法。  
k为偶尔时，放置方法有两种:  
（1）第二行和第三行的旅馆对称；  
（2）旅馆关于j = k / 2对称  
k为奇数时，放置方法为：  
第二行的中间位置要放上旅馆，然后往两边放；如果第二行不够放，则继续放到第三行，但是第三行的中间位置不能放（否则k会变成偶数）。

# 三、程序 #

#include <bits/stdc++.h>
    using namespace std;
    string str[5];
    int main()
    {
        int n,k;
        cin >>n>>k;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<n;j++)
            {
                str[i]+='.';
            }
        }
    
        if(k%2==0)  // 偶数个旅馆
        {
            k/=2;
            for(int i=1;i<=2;i++)
            {
                for(int j=1;j<=k;j++)
                {
                    str[i][j]='#';
                }
            }
        }
        else        // 奇数个旅馆
        {
            str[1][n/2]='#';
            if(k!=1)
            {
                if(k<=n-2)
                {
                    for(int i=1;i<=(k-1)/2;i++)
                    {
                        str[1][i]='#';
                        str[1][n-1-i]='#';
                    }
                }
                else
                {
                    for(int i=1;i<=n-2;i++)
                    {
                        str[1][i]='#';
                    }
    
                    k -= (n-2);
                    for(int i=1;i<=k/2;i++)
                    {
                        str[2][i]='#';
                        str[2][n-1-i]='#';
                    }
                }
            }
        }
    
        puts("YES");
        for(int i=0;i<4;i++)
        {
            cout<<str[i]<<endl;
        }
    }

> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public\_header.jpg][wechat_public_header.jpg]

[http_codeforces.com_contest_980_problem_B]: http://codeforces.com/contest/980/problem/B
[wechat_public_header.jpg]: /images/20220525/802c6c40851d4ce19ccfd23f25f5b6d8.png