CF103C Russian Roulette

smyslenny · 2021-05-16 16:51:37 · 题解

CF103C Russian Roulette

题目传送门

首先分析题意，我们可以得出三个性质：

如果最大程度上保证第一个人安全的话，第一个位置不要放子弹，不然上来就死了(除非所有的位置都要放子弹)。
让第二个人死的快点，那么需要隔一个放一个子弹 (从第二个位置开始放)。
如果 k>0 ，最后一个位置一定放子弹，因为要保证字典序最小。

当当前的弹槽数为奇数时，由于性质3，易知最后一位一定是子弹，我们把最后一位删去，转换成偶数个，与偶数的情况一起讨论。

然后我们考虑两种情况：

子弹数 > 弹槽数的一半

由性质2，可知，从第二个个位置开始，每隔一个位置都有一个子弹，也就是偶数位置一定有子弹。非偶数位置，由于子弹数 > 弹槽数的一半，肯定有的位置有子弹。为了保证字典序最小，剩余的子弹一定是从后往前填的，所以我们可以筛去偶数的情况进行计算。

如上图，假设我们 k=5 ,筛去偶数，给我们的弹槽重新编个号。

因为已经使用了 4 颗子弹，剩下那颗子弹一定在最后一个位置。

因为我们已经筛去了偶数，所以说剩下的子弹就从后往前放就可以啦，判断一下我们要找的位置是否在后面的子弹序列里，就完成了。
子弹数 \leqslant 弹槽个数的一半

此时弹槽中的偶数位可能会填不满，所以我们不能按照之前那样先把偶数筛去，但是我们可以发现，奇数位置一定是没有子弹的，我们就可以按照之前的思路，把奇数筛去，子弹同样也是从后往前排的，判断查询位置是否在后面的子弹序列里就可以了。如下图， k=3

然后记得开 long \ long ,不然亲测只能过五个点。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>

#define int long long
#define INF 0x3f3f3f3f

using namespace std;
int n,k,q; 
int read()
{
    register int x=0,y=1;
    register char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') y=0;c=getchar();}
    while(c>='0'&&c<='9') { x=x*10+(c^48),c=getchar();}
    return y?x:-x;
}
bool check(int x,int n,int k)
{
    if(n&1) { //子弹隔一个放一个最优，如果是奇数，且 k > n/2 那么一定有两个相同的弹夹，
        if(x==n && k) //如果是最后一位 ,当前还有子弹，最后一位一定是子弹 
            return true;
        n--;//不是最后一位，最后一位放子弹字典序最小，先排除了
        k--; 
    }
    if(k-n/2>0)//子弹数 > 弹夹容量一半 一定有三个相邻的位置装子弹 
    {
        if(x%2==0) //偶数一定有子弹 
            return true;
        k-=n/2;//减去使用了的子弹 
        x=x/2+1;//重新编号 
        k=n/2-k;//剩下子弹从后依次排列，找到子弹排列的最前面一个的前一个位置 
        if(x>k) return true;//在后面的子弹序列里 
        return false;
    }
    else
    {
        if(x&1) return false;//奇数位置，一定没有子弹
        x=x/2;//筛去奇数，重新编号 
        k=n/2-k;//子弹序列前端的上一位置 
        if(x>k) return true;
        return false;
    }
}
signed main()
{
    n=read(),k=read(),q=read();
    while(q--)
    {
        int pot=read();
        if(check(pot,n,k))
        printf("X");
        else printf(".");
    }
    return 0;
}