ACM模版

描述

题解

这个题,放在五级题有些过了,撑死了三级题难道,如果放在三级题,我想过的人会更多,放在五级题让人高估了它!!!

其实就是一个贪心,我们想要挂的几率最低,实际上就是尽量隔一个放一个,所以也就是说,点都尽量放在前边,而 X 尽量往后隔一个放一个,如果说,我们放不下怎么办?当然还是优先往后放,从后往前依次取缔点。所以最后的情况一般有如下几种(我用 Y 取代点,容易对齐):
YYYYYXYXYX
YYYYYYXYXYX
YXYXYXXXXX
XYXYXYXXXXX
……
大致就是这样,注意长度的奇偶性问题,代码有那么一丢丢区别,但是贪心思路上是一样的,这个思路并不难想,只是你是否相信它这么简单?

当然,我想没有人傻到去枚举每个位置的值吧?毕竟人家只要不到一千个询问,只需要根据这个规律直接求出这个位置的值即可。

代码

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

typedef long long ll;

int p;
ll n, k, x;
string s = "";


int main()
{
    scanf("%lld%lld%d", &n, &k, &p);

    ll tmp = k - n / 2;
    if (tmp < 0)
    {
        tmp = 0;
    }

    while (p--)
    {
        scanf("%lld", &x);
        if (k == 0)
        {
            s.push_back('.');
        }
        else if (k == 1)
        {
            if (x == n)
            {
                s.push_back('X');
            }
            else
            {
                s.push_back('.');
            }
        }
        else
        {
            ll t1 = n - 2 * (k - 1);
            ll t2 = n - (1 + (tmp - 1) * 2);
            if (n & 1)
            {
                if (x == n)
                {
                    s.push_back('X');
                }
                else
                {
                    if (x < t1)
                    {
                        s.push_back('.');
                    }
                    else if ((x - t1) & 1)
                    {
                        s.push_back('X');
                    }
                    else if (x >= t2)
                    {
                        s.push_back('X');
                    }
                    else
                    {
                        s.push_back('.');
                    }
                }
            }
            else
            {
                if (x < t1)
                {
                    s.push_back('.');
                }
                else if (!((x - t1) & 1))
                {
                    s.push_back('X');
                }
                else if (x >= t2)
                {
                    s.push_back('X');
                }
                else
                {
                    s.push_back('.');
                }
            }
        }
    }
    s.push_back(10);

    cout << s;

    return 0;
}