sgu 109 Magic of David Copperfield II

这个题意一开始没弄明白，后来看的题解才知道这道题是怎么回事，这道题要是自己想难度很大……

你一开始位于（1，1）这个点，你可以走k步，n <= k < 300，由于你是随机的走的，所以你具体在那个格子不确定，但你可以删掉一些你肯定不在的格子，然后你再走，再删，直到只剩下一个格子。

真是不知道怎么想出来的，所以没办法写思路了，直接写答案好了。

我们把格子黑白染色，如果走奇数步，那么所位于的格子一定和上一个格子颜色不同。所以我们可以利用这个性质，不断把所在的格子往左上角赶。怎么做到的呢？一开始我们走n步，那么此时一定有一些格子由于距离太远达不到，删掉。注意，此时我们不能立刻删去和此时你所在格子颜色不同的所有格子，如果那样下一步就没法走了，但是，此刻剩下的不止一个格子。假设此时位于黑色格子，那么再走奇数步，此时一定位于白色格子，那么位于此时图的最下部的黑色格子一定没有你，删掉。诸如此类，直到只剩下（1,1）这个格子。

这样可能有些难于理解，画一个图就清晰了。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <cmath>

#define N 100

#define M 5010

using namespace std;

struct sss

{

    int num, place;

}ask[M];

int n, K;

int ans[M];

bool pd[N]={};

bool cmp(sss x, sss y)

{

    if (x.num == y.num) return x.place < y.place;

    else return x.num < y.num;

}

int calc(int now)

{

    int a = ;

    while (now)

    {

        a += now % ;

        now /= ;

    }

    return a;

}

int main()

{

    scanf("%d%d", &n, &K);

    for (int i = ; i <= K; ++i)

    {

        scanf("%d", &ask[i].num);

        ask[i].place = i;

    }

    sort(ask+, ask+K+, cmp);

    int num = , nowask = ;

    int lastnum = ;

    for (int i = ; i <= n; ++i)

    {

        if (!pd[i%])

        {

            num++;

            while (num == ask[nowask].num)

            {

                ans[ask[nowask].place] = i;

                nowask++;

            }

        }

        pd[i%] = ;

        if (i %  == )

        {

            lastnum = calc(i);

            pd[(lastnum+i) % ] = ;

        }

        else

        {

            lastnum++;

            pd[(lastnum+i) % ] = ;

        }

    }

    printf("%d\n", num);

    for (int i = ; i < K; ++i)

        printf("%d ", ans[i]);

    printf("%d\n", ans[K]);

    return ;

}

巴特西

sgu 109 Magic of David Copperfield II

最新文章

热门文章