传送门:D.Ithea Plays With Chtholly

题意:$Chtholly$要在长度为 $n$的空序列中填数,进行 $m$个回合,$Ithea$每个回合会给 $Chtholly$一个在 $1$到 $c$之间的数,$Chtholly$可以用这个数填入这个序列里的一个空位置里,也可以填入这个序列里一个有数字的位置,将这个位置原来的数字变为当前的这个数字,$Chtholly$能赢当且仅当序列里没有空位置且序列里的数是不下降的 (即 $\forall i\;a_i<=a_{i+1}$),如果 $m$回合后 $Chtholly$没赢就是 $Ithea$赢,我们保证 $Chtholly$能赢,现在请你帮 $Chtholly$赢得这场比赛。

数据范围:$n,m\geq 2,1\leq c\leq 1000,1\leq n\times \lceil \frac c 2\rceil \leq m \leq 1000$

吐槽:珂朵莉都进驻 codeforces 了 QAQ 我还没看这番,主要是 bilibili 没有(其实是我懒得去找百度云),有时间就去追一下 233333

因为 $APIO$里有一堆交互题,所以我就去做了几道交互题练练手。这道算是比较难的一道。

首先一个平凡的想法是把序列初值设成 $\infty$,每次从左到右选第一个比当前拿到的数大的数,这就相当于维护了序列的不下降性。

但是如果要填充完整个序列,不难想到最坏情况下需要进行 $(n-1)\times c+1$个回合,比如下面这个例子:

$n=3,c=4$

给你是数分别是 $4,3,2,1,4,3,2,1,4$,用上面那个方法则需要 $9$轮,而 $m$的下界是 $6$,因此这种方法是不对的。

那咋整呀?

首先我们看一看第一种算法的运行过程,回合主要浪费在了重复覆盖同一个位置,由数据范围可以知道,如果我们对于一个位置的覆盖次数的上界能够控制在 $\lceil \frac c 2\rceil$处,我们就能够在大于等于上界的 $m$轮次内完成这个合法序列。

可是我还是不会呀 (委屈脸.jpg)

Q: 看到这个 $\lceil \frac c 2\rceil$你想到了什么?

A: 啥都没想到。

Q:(小声) 快给我说二分。

A: 二分!

Q: 看吧你会做了吧!

A: 黑人问号???

我们可以把值域分为两部分,小于等于 $\lceil \frac c 2\rceil$的从左往右填找第一个比自己大的数,大于 $\lceil \frac c 2\rceil$的从右往左填找第一个比自己小的数,随便加点细节处理乱搞可过。

为啥?

因为填充一个格子次数的上界是 $\lceil \frac c 2\rceil$呀~

这个思路真是超级好玩~

具体如果没看明白或者不知道怎么加细节处理的可以看看代码。

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define N 1005
int n, m, c, a, f[N], mid, cnt, j, g[N];
int main ()
{
    scanf("%d %d %d", &n, &m, &c);
    memset(f, 0x3f, sizeof f);
    memset(g, 0, sizeof g);
    mid = c / 2;
    fo (i, 1, m)
    {
        scanf("%d", &a);
        if (a <= mid)
        {
            j = 1;
            while (f[j] <= a && j <= n) j++;
            if (f[j] == f[0])
                ++cnt;
            f[j] = a;
            g[j] = a;
            printf("%d\n", j);
        }
        else
        {
            j = n;
            while (g[j] >= a && j >= 1) j--;
            if (g[j] == 0)
                ++cnt;
            f[j] = a;
            g[j] = a;
            printf("%d\n", j);
        }
        fflush(stdout);
        if (cnt == n)
            return 0;
    }
    return 0;
}

作为一个 windows 玩家做交互题太累了,魔改 grader.cpp 之后才能本地测试 QAQ,不过听说 APIO 是 linux 系统所以大概可以直接用命令行啦~,好吧我得快点转 linux 了

分类: 文章

HomuraCat

明日は何になる? やがて君になる!

1 条评论

XZYQvQ · 2018年5月14日 3:05 下午

Orz 强啊,我最近都没时间打理着博客啦。。。感谢您的撑场子 QvQ
(APIO 神奇の面基 QvQ 害怕.jpg)

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注