传送门: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了

分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

1 条评论

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

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

XZYQvQ进行回复 取消回复

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

你是机器人吗? =。= *