Apio2017 第二题 考拉游戏 题解

介绍

本次是文学编程 style 的题解…夹杂题面、代码、思路等等

思路请看注释

题面

Koala 发明了一个新游戏,来邀请你一起玩!游戏的开始,她会在桌上放 \(N\) 个物品,物品从 \(1\)\(N\) 标号。接着,她会秘密地给每个物品分配一个 \(1\)\(N\) 之间的整数权值,且任意两个物品不会被分配到相同的权值。其中,第 \(i\) 个物品的权值为 \(P_i\) 。她请你来确定由这些权值构成的序列 \(P=P_0,P_1...,P_{N-1}\) 的一些特征。

描述

为了回答她的问题,你可以请 Koala 玩若干轮游戏。每一轮中,你会得到 \(W\) 个蓝色石子,Koala 会得到 \(W\) 个红色石子。首先,你可以选择若干个物品,再把你的一些(或全部)石子放在这些物品的旁边。Koala 会观察你的石子分配,然后类似地把她的一些(或全部)石子放在若干个物品旁边。如果一个物品旁边的红色石子数 严格大于 蓝色石子数,那么,Koala可以获得这个物品。Koala 分配她的石子时,总会选择使她获得的物品的权值和最大的方案,如果有多种方案可以做到这一点,她会选择一种获得的物品数最多的方案,如果仍然有多种方案,她会选择其中任意一种。

Koala 非常懒,如果你和她玩太多轮游戏,她就会睡着。你的任务是通过尽可能少轮数的游 戏,确定 Koala 的序列 \(P\) 的相关特征。

任务

在这个任务中,你需要实现 \(4\) 个函数:minValue, maxValue, greaterValueallValues。每个函数需要你确定序列 \(P\) 的不同特征。我们强烈推荐在我们提供的模版的基础上进行作答。注意,即使你只想获得部分子任务的分数,你也必须为四个函数都提供一个实现(尽管一些函数的内部可能为空)。你的程序禁止从标准输入读数据、向标准输出写数据或与任何文件交互。

交互方式

在每个函数中,参数 \(N\) 表示游戏中物品的个数,参数 \(W\) 表示你和Koala 在每一轮游戏中拥有的石子数。

  • minValue(N, W)—这个函数需要返回权值最小的物品的标号 ,即 \(P_i=1\)
  • maxValue(N, W)—这个函数需要返回权值最大的物品的标号 ,即 \(P_i=N\)
  • greaterValue(N, W)—这个函数需要比较物品 \(0\) 和物品 \(1\) 的权值,返回权值较大的物品的标号。具体来说,若 \(P_0>P_1\) ,它应该返回 \(0\) ,否则返回 \(1\)
  • allValues(N, W, P)—这个函数需要确定整个排列 ,并将其存放在给定的数组 \(P\) 中:具体来说,\(P[i]\) 应该保存物品 \(i\) 的权值 \(P_i(0\leq i\leq N-1)\)

在每个测试点中,交互库会一次或多次调用这些函数中的一个。每次函数调用代表不同的任务,哪个函数会被调用、以及最多被调用多少次取决于子任务(见下文)。你可以认为Koala 在每次函数调用前确定了她的序列 \(P\) ,并且序列不会在一次函数的调用过程中改变。

一次调用结束后,她可以在下次函数调用之前改变她的序列。

你实现的四个函数可以通过调用函数 playRound 来获取 Koala 的序列的相关信息。

  • playRound(B, R),请 Koala 和你玩一轮游戏。
    • 数组 B 描述你在每个物品旁边放了多少蓝色石子。具体来说,对任意 \(0\leq i\leq N-1\)\(B[i]\) 个蓝色石子将会被放在物品 \(i\) 旁边。每个 \(B[i]\) 必须是一个非负整数,且 \(B[0]+B[1]+\cdots+B[N-1]\) 不能超过 \(W\)
    • 交互库会把 Koala 的回应存放在你提供的数组 R 中。具体来说,对任意 \(0\leq i\leq N-1\) ,Koala 会在物品 \(i\) 旁边放 \(R[i]\) 个红色石子。
    • 每个子任务对你在每次游戏中调用 playRound 的次数有所限制。注意,调用次数越少你的得分可能会越高。(具体限制和评分方式参见下文)
#include "koala.h"
#include "bits/stdc++.h"
using namespace std;
const int maxn = 233;
int a[maxn], b[maxn];
int n,w;
// hit[i] 表示 Koala 占据了 i 号位置。
bool hit[maxn];
bool allhit[maxn];
void gh() {
    playRound(a,b);
    for(int i = 0; i < n; ++i) {
        hit[i] = b[i]>a[i];
    }
}

子任务 1 (4分)

  • 在这个子任务中,交互库只会调用函数 minValue,每个测试点中,这个函数最多会被调用 100 次。
  • \(N=100\)
  • \(W=100\)
  • 每一次游戏中,你可以调用 playRound 至多 2 次。
// 其实一次就够了,任意一个位置放1
// 唯一一个没 hit 的就是最小值

int minValue(int N, int W) {
    n=N;w=W;
    memset(a,0,sizeof a);
    a[0] = 1;
    gh();
    for(int i = 0; i < N; ++i) {
        if(!hit[i]) return i;
    }
    return 0;
}

子任务 2 (15分)

  • 在这个子任务中,交互库只会调用函数 maxValue。每个测试点中,这个函数最多会被调用 100 次。
  • \(N=100\)
  • \(W=100\)
  • 为了获得7分,你可以调用 playRound 至多 13 次。
  • 为了获得15分,你可以调用 playRound 至多 4 次。
// allhit[x]为每次都hit的位置
// 显然,只有最大的权值才值得交互库每次都hit

int maxValue(int N, int W) {
    n=N;w=W;
    memset(allhit, 1, sizeof allhit);
    int allhitc = n;
    while(allhitc > 1) {
        int zr = w / allhitc;
        for(int i = 0; i < n; ++i) {
            a[i] = allhit[i] ? zr : 0;
        }
        gh();
        allhitc = 0;
        for(int i = 0; i < n; ++i) {
            allhit[i] &= hit[i];
            allhitc += allhit[i];
        }
    }
    for(int i = 0; i < n; ++i) {
        if(allhit[i]) return i;
    }
    return 0;
}

子任务 3 (18分)

  • 在这个子任务中,交互库只会调用函数 greaterValue。每个测试点中,这个函数最多会被调用 100 次。
  • \(N=100\)
  • \(W=100\)
  • 为了获得5分,你可以调用 playRound 至多 14 次。
  • 为了获得11分,你可以调用 playRound 至多 5 次。
  • 为了获得14分,你可以调用 playRound 至多 4 次。
  • 为了获得18分,你可以调用 playRound 至多 3 次。
bool cmp(int,int);
int greaterValue(int N, int W) {
    n=N;w=W;
    return cmp(0,1) ? 1 : 0;
    return 0;
}
// 定义比较函数cmp(x,y)。
// 考虑在x,y两个位置同时放置大小为w的糖果,
// 如果w的值足够好,那么交互库为了获得更优结果,
// hit了x/y其中的一个。
// 当w过小时,x,y都会hit。
// 当w过大时,x,y都不会hit。
// 故可以二分。
  • 设三元组 \((x,y,w)\) 是好的表示某两个位置的值是 \(x\) , \(y\) 时,放置 \(w\) 可以将他们区分出来。
  • \(Q(x,y)\) 表示 \((x,y,w)\) 为好的的 \(w\) 构成的集合。
  • \(Q(x,y)\) 是一段连续的区间。
  • \(N\leq 100, W \leq 100\) 时,可以证明 $ i j, x {1,2,4,8}, x Q(i,j)$ 。
bool cmp(int x, int y) {
    if(x==y)return false;
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    a[x]=a[y]=4;
    gh();
    if(hit[x]&&hit[y]) {
        a[x]=a[y]=8;
        gh();
        if(hit[x]) return false;
        return true;
    } else if(hit[x]) {
        return false;
    } else if(hit[y]) {
        return true;
    } else {
        a[x]=a[y]=2;
        gh();
        if(hit[x]) return false;
        else if(hit[y]) return true;
        else {
            a[x]=a[y]=1;
            gh();
            if(hit[x]) return false;
            else return true;
        }
    }
}

子任务 4 (10分)

  • 在这个子任务中,交互库只会调用函数 allValues。每个测试点中,这个函数最多会被调用 1 次。
  • \(N=100\)
  • \(W=200\)
  • 你可以调用 playRound 至多 700 次。

承接上一个子任务的定义。

  • \(N\leq 100, W \leq 200\) 时,可以证明 $ i j, 100 Q(i,j)$ 。

so…这样写就好啦

bool cmp2(int x, int y) {
    if(x==y)return false;
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    a[x]=a[y]=w / 2;
    gh();
    if(hit[x]) {
        return false;
    } else {
        return true;
    }
}

然后可以 \(O(n\log n)\) sort 一发。

  • 如果使用了std::sort,恭喜你,次数过多
  • 如果使用了std::stable_sort,可过(233)

这个我在讲题的时候上台吐槽了一发…

void allValues(int N, int W, int *P) {
    n=N;w=W;
    if (W == 2*N) {
        for(int i = 0; i < n; ++i) q[i]=i;
        stable_sort(q,q+n,cmp2);
        for(int i = 0; i < n; ++i) {
            P[q[i]] = i+1;
        }
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

子任务 5 (53分)

  • 在这个子任务中,交互库只会调用函数 allValues。每个测试点中,这个函数最多会被调用 1 次。
  • \(N=100\)
  • \(W=100\)
  • 你可以调用 playRound 至多 3200 次。
  • 这个子任务中,一个测试点的分数取决于 playRound 被调用的次数 \(C\) ,具体的说,你的得分为:
    • \(C\leq 100\) ,获得 53 分。
    • \(101 \leq C \leq 3200\) ,获得 \(\lfloor 53-8\log_2{(C-100)}\rfloor\) 分。其中, \(\lfloor x \rfloor\) 为不大于 \(x\) 的最大整数。举例来说,若 \(C=3200\) ,那么你的解答将获得 \(13\) 分。

做法: 分治。

int q[maxn];
int cho[maxn];
int getar(int, int);

在比较这个Subtask中,为了比较两个数的大小,我们将它们填成一样的数字 \(w\) 来利用交互库的不同反馈比较大小。

在获取全部值的Subtask中,为了将一些数字分成两部分,我们将它们填成一样的数字 \(w\) ,那么交互库的反馈(如果有意义那么代表着)hit的部分每一个都大于没有hit的部分。

考虑每次把值域分成两部分,只要找到了正确的 \(w\) ,就可以利用交互库的反馈来分而治之。

void dfs(int l, int r, const set<int> &s) { // 值域为[l+1,r+1](此处是我写的时候脑残了),位置属于s集合的分治操作。
    if(l==r) {
        int x = *s.begin();
        q[l]=x;
        return;
    }
    int w = getar(l,r); // 获取一个合法w
    for(int i = 0; i < n; ++i) {
        a[i] = s.count(i) ? w : 0; // 全部填成一样的数字
    }
    gh();
    set<int> s0, s1; // 获取交互库不同反馈
    for(const auto &x:s) {
        if(hit[x]) s1.insert(x);
        else s0.insert(x);
    }
    int q = r - s1.size();
    if(s0.size() == 0 || s1.size() == 0) {
        cerr << l << " " << r << " " << s0.size() << " " << s1.size() << " " << w << endl;
        exit(-1);
    }
    // 分治
    dfs(l,q,s0); 
    dfs(q+1,r,s1);
}
int su(int l, int r) {
    return (l+r)*(r-l+1)/2;
}
int getar(int l, int r) { // 获取一个数字
    int tl = 1, tr = w/(r-l+1);
    while(tl<tr) {
        int mid((tl+tr)/2);
        int fr = 0;
        for(int i = 0; i < n; ++i) {
            if(i<l||i>r) cho[i]=1;
            else cho[i]=0, ++fr;
        }
        int zr = r;
        while(fr>mid) {
            cho[zr--] = mid+1;
            fr-=mid+1;
        }
        cho[zr]=fr;
        int zl = 0;
        // 贪心模拟交互库
        // 其实也可以写个背包
        while(true) {
            int ned = mid+1-cho[zr];
            if(zl > l) break;
            if(zl+ned>l) break;
            if(su(zl + 1, zl+ned) >= zr) break;
            for(int i = zl; i < zl+ned; ++i) {
                --cho[i];
                ++cho[zr];
            }
            assert(cho[zr] > mid);
            zl += ned;
            --zr;
            if(zr < l) break;
        }
        bool lb = cho[l] > mid;
        bool rb = cho[r] <= mid;
        if(lb) {
            tl = mid + 1;
        } else if(rb) {
            tr = mid - 1;
        } else {
            return mid;
        }
    }
    return tl;
}
void allValues(int N, int W, int *P) {
    n=N;w=W;
    if (W == 2*N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    } else {
        set<int> all;
        for(int i = 0; i < n; ++i) all.insert(i);
        dfs(0,n-1, all);
        for(int i = 0; i < n; ++i) {
            P[q[i]] = i+1;
        }
    }
}