题解 P6558 【[APIO2017] 考拉的游戏】

Froggy · 2020-05-25 22:05:09 · 题解

好van的交互题。。

Subtask 1

询问一次即可。

直接询问 [1,0,0,\cdots,0]，输出得到的数组中为 0 的位置。

理由很简单，Koala 至少得不到一个物品，那么不要的物品一定是价值最小的物品。

code:

int minValue(int n, int W) {
    static int a[N],b[N];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    a[0]=1;
    playRound(a,b);
    for(int i=0;i<n;++i){
        if(b[i]<=a[i])return i;
    }
    return 114514; //真香
}

Subtask 2

这个 Subtask 不是很好想。

首先发现这个 Subtask 的套路一定是逐步缩小前若干大值位置的集合大小，直到集合大小为 1。

下面就是拿交互库乱试了！

首先每个位置放一个 1，可以确定权值在区间 [51,100] 的位置集合。

然后再把这个集合中的每个位置放 2，其他位置放 0，就可以确定 [76,100] 了。

按照这个套路，之后分别放 4 个，最后分别放 11 个，就能确定区间 [92,100] 然后确定 [100,100]，成功找到最大值。

刚好询问 4 次。

code:

int maxValue(int n, int W) {
    static int a[N],b[N];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        a[i]=1;
    }
    playRound(a,b);
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        if(b[i]>1)a[i]=2;
    }
    playRound(a,b);
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        if(b[i]>2)a[i]=4;
    }
    playRound(a,b);
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        if(b[i]>4)a[i]=11;
    }
    playRound(a,b);
    for(int i=0;i<n;++i){
        if(b[i]>11)return i;
    }
    return 1919810;   //越来越香
}

Subtask 3

有了 Subtask 2 的经验，不难想到一定存在一个数 x，询问 [x,x,0,\cdots,0] 使得 Koala 选择位置 0 的物品和位置 1 的物品中的一个。

显然 1\leq x\leq 14，因为 \sum_{i=1}^{15}i>100，无论前两个物品的价值有多大 Koala 都不会选择。

把 x 二分出来即可。

但现在最多还是要询问 4 次，所以还需要人工细化二分的过程（就是把循环拆开）。

经过尝试，我下面这种二分方法也可以 AC。（当然，手工二分最保险）

code:

bool Comp(int i,int j){      //比较i的价值和j的价值
    int l=1,r=14;
    static int a[N],b[N];
    while(l<r){
        int mid=(l+r)>>1;
        memset(a,0,sizeof(a));
        a[i]=a[j]=mid;
        playRound(a,b);
        if(b[i]>mid&&b[j]<=mid)return false;
        if(b[i]<=mid&&b[j]>mid)return true;
        if(b[i]<mid&&b[j]<mid){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return false;
}
int greaterValue(int n, int W) {
    return Comp(0,1);
}

Subtask 4

最多询问 700 次，看这个数字可以猜要询问 \mathcal{O}(n\log n) 次。

这个 W=200 的性质非常好,可以找到一种 1 次就完成比较两个物品价值的方法：

设比较的物品分别为 i 和 j，那么只需要在位置 i 和 j 分别放上 100 个，其他位置放 0 个即可。因为这样 Koala 一定会选择 i 和 j 其中的一个物品。被选择的物品价值较大。

有了比较方法下面只需要找个东西排个序啦！

stable_sort 可以胜任。（用法与 sort 一摸一样）

注：做交互题比较多的同学一定明白 sort 这个玩意千万不要用。由于它过于追求速度所以当递归到较小的区间后就会改成插入排序之类的，这样就浪费了很多询问。

code:

bool cmp(int i,int j){
    int tmp[N]={},gugu[N];
    tmp[i]=tmp[j]=100;
    playRound(tmp,gugu);
    return gugu[i]<=100;
}
void allValues(int n, int W, int *p) {
    if(W==(n<<1)){
        static int a[N];
        memset(a,0,sizeof(a));
        for(int i=0;i<n;++i){
            a[i]=i;
        } 
        stable_sort(a,a+n,cmp);    //好东西，其实就是归并排序
        for(int i=0;i<n;++i){
            p[a[i]]=i+1;
        }
    }
}

Subtask 5

重头戏。（否则怎么可能占一半一上的分数呢？）

首先有个很显然的做法就是结合 Subtask 3 和 Subtask 4，用 stable_sort 排个序，这样大约询问 700 多次，实测能得 29 分。

然鹅只能询问 n 次，考虑分治。

类似于 Subtask 2 的做法，维护权值在 [l,r] 的位置集合，然后通过分治逐渐缩小区间。

每次都可以找到一个权值 w，然后把当前分治的位置集合中的位置放 w 个，其他位置放 0 个，使得得到的数组 b 中存在集合中的某些位置为 0。假设这些位置有 k(0< k<r-l+1) 个，那么可以分成 [l,l+k-1] 和 [l+k,r] 两个区间。

边界即 l=r 的时候直接存下来然后跳出，就不需要再询问了。

这样只需要询问 99 次就可以了。（自行思考为什么是 99 次）

现在的问题就在于如何找到一个 w 了。

可以直接暴力枚举，然后进行判断。由于我们只想去知道能否把集合分成两半，所以并不需要通过询问交互库来判断。构造一个价值依次为 [1,2,\cdots,100] 的权值序列，然后求出 Koala 给的序列就能轻松判断了。

你问我怎么求？像我这种懒人就直接复制交互库的代码然后瞎魔改一下了。。（没说过不让复制交互库吖^_^) 其实就是一个背包。

还有一些细节写到注释里了。

code:

//别看挺长的，check函数都是复制交互库的qwq。
bool check(int x,int l,int r){           //判断是否能把 [l,r] 切成两部分 
    int cache[2][205];
    int num[2][205];
    char taken[N][205];

    memset(cache[1],0,sizeof(cache[1]));
    memset(num[1],0,sizeof(num[1]));

    const int W=100;
    for(int i=0;i<N;++i) {
        int v=(i>=l&&i<=r)?x+1:1;
        int ii=i&1;
        int o=ii^1;
        for(int j=0;j<=W;++j) {
            cache[ii][j]=cache[o][j];
            num[ii][j]=num[o][j];
            taken[i][j]=0;
        }
        for(int j=W;j>=v;--j) {
            int h=cache[o][j-v]+i+1;
            int hn=num[o][j-v]+1;
            if(h>cache[ii][j]||(h==cache[ii][j]&&hn>num[ii][j])){
                cache[ii][j]=h;
                num[ii][j]=hn;
                taken[i][j]=1;
            }
            else{
                taken[i][j]=0;
            }
        }
    }
    int cur=W;

    static int qwq[N];

    for(int i=N-1;i>=0;--i) {
        int tmp=taken[i][cur]?((i>=l&&i<=r)?x+1:1):0;
        qwq[i]=tmp;
        cur-=tmp;
    }
    int jb=qwq[l];
    for(int i=l+1;i<=r;++i)if(qwq[i]^jb)return true;  //对于集合中的位置，存在两个位置放个红色石子数量不同就说明可以把集合分开。
    return false;
}
int get_val(int l,int r){
    for(int i=1;i<=100/(r-l+1);++i){  //暴力枚举是否合法
        if(check(i,l,r))return i;
    }
    exit(-1);
}
void Solve(int l,int r,vector<int> &vec,int *ans){
    if(l==r){
        ans[vec[0]]=l+1;
        return;
    }
    static int a[N],b[N];
    memset(a,0,sizeof(a));

    int w=get_val(l,r);
    for(int i=0;i<(int)vec.size();++i){
        a[vec[i]]=w;
    }
    playRound(a,b);
    vector<int> L,R; 
    for(int i=0;i<(int)vec.size();++i){
        if(b[vec[i]]<=w)L.push_back(vec[i]);
        else R.push_back(vec[i]); 
    }
    Solve(l,l+L.size()-1,L,ans);
    Solve(l+L.size(),r,R,ans);
}
void allValues(int n, int W, int *p) {
    if(W==n){
        vector<int> myh;   //实在不知道用什么变量名了就用我npy的名字。
        for(int i=0;i<n;++i){
            myh.push_back(i);
        }
        Solve(0,n-1,myh,p);  //开心分治
    }
}

最后提醒一句：多测不清空，爆蛋两行泪。

最终全部代码：

#include "koala.h"
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

void playRound(int*,int*);
#define N 100

int minValue(int n, int W) {
    static int a[N],b[N];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    a[0]=1;
    playRound(a,b);
    for(int i=0;i<n;++i){
        if(b[i]<=a[i])return i;
    }
    return 114514;
}

int maxValue(int n, int W) {
    static int a[N],b[N];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        a[i]=1;
    }
    playRound(a,b);
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        if(b[i]>1)a[i]=2;
    }
    playRound(a,b);
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        if(b[i]>2)a[i]=4;
    }
    playRound(a,b);
    memset(a,0,sizeof(a));
    for(int i=0;i<n;++i){
        if(b[i]>4)a[i]=11;
    }
    playRound(a,b);
    for(int i=0;i<n;++i){
        if(b[i]>11)return i;
    }
    return 1919810;
}

bool Comp(int i,int j){
    int l=1,r=14;
    static int a[N],b[N];
    while(l<r){
        int mid=(l+r)>>1;
        memset(a,0,sizeof(a));
        a[i]=a[j]=mid;
        playRound(a,b);
        if(b[i]>mid&&b[j]<=mid)return false;
        if(b[i]<=mid&&b[j]>mid)return true;
        if(b[i]<mid&&b[j]<mid){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return false;
}
int greaterValue(int n, int W) {
    return Comp(0,1);
}

bool cmp(int i,int j){
    int tmp[N]={},gugu[N];
    tmp[i]=tmp[j]=100;
    playRound(tmp,gugu);
    return gugu[i]<=100;
}
bool check(int x,int l,int r){ 
    int cache[2][205];
    int num[2][205];
    char taken[N][205];

    memset(cache[1],0,sizeof(cache[1]));
    memset(num[1],0,sizeof(num[1]));

    const int W=100;
    for(int i=0;i<N;++i) {
        int v=(i>=l&&i<=r)?x+1:1;
        int ii=i&1;
        int o=ii^1;
        for(int j=0;j<=W;++j) {
            cache[ii][j]=cache[o][j];
            num[ii][j]=num[o][j];
            taken[i][j]=0;
        }
        for(int j=W;j>=v;--j) {
            int h=cache[o][j-v]+i+1;
            int hn=num[o][j-v]+1;
            if(h>cache[ii][j]||(h==cache[ii][j]&&hn>num[ii][j])){
                cache[ii][j]=h;
                num[ii][j]=hn;
                taken[i][j]=1;
            }
            else{
                taken[i][j]=0;
            }
        }
    }
    int cur=W;

    static int qwq[N];

    for(int i=N-1;i>=0;--i) {
        int tmp=taken[i][cur]?((i>=l&&i<=r)?x+1:1):0;
        qwq[i]=tmp;
        cur-=tmp;
    }
    int jb=qwq[l];
    for(int i=l+1;i<=r;++i)if(qwq[i]^jb)return true;
    return false;
}
int get_val(int l,int r){
    for(int i=1;i<=100/(r-l+1);++i){
        if(check(i,l,r))return i;
    }
    exit(-1);
}
void Solve(int l,int r,vector<int> &vec,int *ans){
    if(l==r){
        ans[vec[0]]=l+1;
        return;
    }
    static int a[N],b[N];
    memset(a,0,sizeof(a));

    int w=get_val(l,r);
    for(int i=0;i<(int)vec.size();++i){
        a[vec[i]]=w;
    }
    playRound(a,b);
    vector<int> L,R; 
    for(int i=0;i<(int)vec.size();++i){
        if(b[vec[i]]<=w)L.push_back(vec[i]);
        else R.push_back(vec[i]); 
    }
    Solve(l,l+L.size()-1,L,ans);
    Solve(l+L.size(),r,R,ans);
}
void allValues(int n, int W, int *p) {
    if(W==(n<<1)){
        static int a[N];
        memset(a,0,sizeof(a));
        for(int i=0;i<n;++i){
            a[i]=i;
        } 
        stable_sort(a,a+n,cmp);
        for(int i=0;i<n;++i){
            p[a[i]]=i+1;
        }
    }
    else{
        vector<int> myh;
        for(int i=0;i<n;++i){
            myh.push_back(i);
        }
        Solve(0,n-1,myh,p);
    }
}

Froggy's blog

呱!!