2016年1月10日 星期日

[FHC 2016 Qualification Round]High Security

首先可以把每一條橫向的空格都塞一個守衛
那麼甚麼情況下可以讓一個守衛擔任兩個守衛的工作呢?
大概就只有一條長度1的空格對面也是空格的情況了吧
這時候,我們可以把那佔據一個空格的守衛移出來,取代對面的守衛,絕對不會吃虧
實作的話可以先找出所有"X.X",讓守衛站出來,然後把看守到的區域標記掉
接著,再掃一遍,把所有未看守的地區再補上一個守衛
不知道這樣的貪心法有沒有例外,真正的結果要等比賽結束才知道Orz

ps.最後四題全對耶真開心 :D

code:


#include<cstdio>
#include<cassert>
#define scanf(x,...) assert(scanf(__VA_ARGS__)==x)
using namespace std;
int N;
char S[2][1002];
int main()
{
    freopen("Bin","r",stdin);
    freopen("out.txt","w",stdout);
    static int testcase;scanf(1,"%d",&testcase);
    while(testcase--)
    {
        scanf(1,"%d",&N);
        assert(N<=1000);
        scanf(2,"%s%s",S[0]+1,S[1]+1);
        S[0][0]=S[1][0]=S[0][N+1]=S[1][N+1]='X';
        for(int d=0;d<2;d++)for(int i=0;i<=N+1;i++)assert(S[d][i]=='X'||S[d][i]=='.');
        int ans=0;
        for(int d=0;d<2;d++)
        {
            for(int i=1;i<=N;i++)
            {
                if(S[d][i-1]=='X'&&S[d][i]=='.'&&S[d][i+1]=='X')
                {
                    S[d][i]='X',ans++;
                    if(S[d^1][i]=='.')
                    {
                        S[d^1][i]='X';
                        for(int j=i+1;S[d^1][j]=='.';j++)S[d^1][j]='X';
                        for(int j=i-1;S[d^1][j]=='.';j--)S[d^1][j]='X';
                    }
                }
            }
        }
        for(int d=0;d<2;d++)
        {
            for(int i=1;i<=N;i++)if(S[d][i]=='.')
            {
                ans++;
                for(int j=i;S[d][j]=='.';j++)S[d][j]='X';
            }
        }
        for(int d=0;d<2;d++)for(int i=0;i<=N+1;i++)assert(S[d][i]=='X');
        static int kase=1;
        printf("Case #%d: %d\n",kase++,ans);
    }
    scanf(-1,"%d",&testcase);
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原