Apio2017 第二题 考拉游戏 题解

Posted by EtaoinWu on 周三 17 五月 2017

介绍

本次是文学编程 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\) 时 , 可以证明 \( \forall i \neq j, \exists x \in \{1,2,4,8\}, x \in 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\) 时 , 可以证明 \( \forall i \neq j, 100 \in 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;
        }
    }
}

tags: APIO, Contest