介绍
本次是文学编程 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
,
greaterValue
和
allValues
。每个函数需要你确定序列 \(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() {
(a,b);
playRoundfor(int i = 0; i < n; ++i) {
[i] = b[i]>a[i];
hit}
}
子任务 1 (4分)
- 在这个子任务中,交互库只会调用函数
minValue
,每个测试点中,这个函数最多会被调用 100 次。 - \(N=100\)
- \(W=100\)
- 每一次游戏中,你可以调用
playRound
至多 2 次。
// 其实一次就够了,任意一个位置放1
// 唯一一个没 hit 的就是最小值
int minValue(int N, int W) {
=N;w=W;
n(a,0,sizeof a);
memset[0] = 1;
a();
ghfor(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;w=W;
n(allhit, 1, sizeof allhit);
memsetint allhitc = n;
while(allhitc > 1) {
int zr = w / allhitc;
for(int i = 0; i < n; ++i) {
[i] = allhit[i] ? zr : 0;
a}
();
gh= 0;
allhitc for(int i = 0; i < n; ++i) {
[i] &= hit[i];
allhit+= allhit[i];
allhitc }
}
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;w=W;
nreturn 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;
(a,0,sizeof a);
memset(b,0,sizeof b);
memset[x]=a[y]=4;
a();
ghif(hit[x]&&hit[y]) {
[x]=a[y]=8;
a();
ghif(hit[x]) return false;
return true;
} else if(hit[x]) {
return false;
} else if(hit[y]) {
return true;
} else {
[x]=a[y]=2;
a();
ghif(hit[x]) return false;
else if(hit[y]) return true;
else {
[x]=a[y]=1;
a();
ghif(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;
(a,0,sizeof a);
memset(b,0,sizeof b);
memset[x]=a[y]=w / 2;
a();
ghif(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;w=W;
nif (W == 2*N) {
for(int i = 0; i < n; ++i) q[i]=i;
(q,q+n,cmp2);
stable_sortfor(int i = 0; i < n; ++i) {
[q[i]] = i+1;
P}
} 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();
[l]=x;
qreturn;
}
int w = getar(l,r); // 获取一个合法w
for(int i = 0; i < n; ++i) {
[i] = s.count(i) ? w : 0; // 全部填成一样的数字
a}
();
gh<int> s0, s1; // 获取交互库不同反馈
setfor(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) {
<< l << " " << r << " " << s0.size() << " " << s1.size() << " " << w << endl;
cerr (-1);
exit}
// 分治
(l,q,s0);
dfs(q+1,r,s1);
dfs}
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) {
[zr--] = mid+1;
cho-=mid+1;
fr}
[zr]=fr;
choint 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);
+= ned;
zl --zr;
if(zr < l) break;
}
bool lb = cho[l] > mid;
bool rb = cho[r] <= mid;
if(lb) {
= mid + 1;
tl } else if(rb) {
tr = mid - 1;
} else {
return mid;
}
}
return tl;
}
void allValues(int N, int W, int *P) {
=N;w=W;
nif (W == 2*N) {
// TODO: Implement Subtask 4 solution here.
// You may leave this block unmodified if you are not attempting this
// subtask.
} else {
<int> all;
setfor(int i = 0; i < n; ++i) all.insert(i);
(0,n-1, all);
dfsfor(int i = 0; i < n; ++i) {
[q[i]] = i+1;
P}
}
}