luogu P3777 [APIO2017] 考拉的游戏
挺有意思的一道题目。
Subtask 1
发现你只要在某个位置放一个石子对手就不能全选,那么对手肯定会放弃最小的那个,因此对手返回的答案中选择不够数量的就是最小值。
Subtask 2
首先我们先来考虑一个能跑出答案的方法。
第一步如果在所有位置都放上 (1) ,那么就可以区分出 ([1,50]) 和 ([51,100])。
然后第二步在 ([51,100]) 上放上 (2) ,就可以区分出 ([51,75]) 和 ([76,100])。
然后这样子放,你会发现在 (4) 次的时候最大的区间刚好剩了一个 (100)。
Subtask 3
发现如果一个位置放了 (x) ,那么只有这个位置大于 (sumlimits_{i=1}^{x}{i}) 才会被替换。
因此我们考虑一个策略:在 (0) 位置和 (1) 位置都放 (x) 个。我们的目的就是寻找一个 (x) ,使得这两个一个被选了一个没有被选。
这个是正确的,因为如果都被替换了说明一个大于 (sumlimits_{i=1}^{x}{i}) ,一个大于 (sumlimits_{i=x+1}^{2x}{i}),而这些区间覆盖了整个值域。
直接二分需要 (4) 次,但是你可以给右区间多一点,左区间少一点,就可以 (3) 次。
Subtask 4
发现 (700) 大概是 (nlog n) 大小,因此考虑类似归并的方法。
现在的问题就是比较两个数的大小,这是平凡的,在这两个数的位置都放 (100) ,那么这两个有且仅有大的会被选,因此可以做到 (1) 次比较。
Subtask 5
要求线性排序 /oh
仿照分区间的思路,如果每一次操作能将一个值域区间恰好分成两个值域区间,那么就可以做到 (n-1) 步排好序。
可以考虑像 Subtask 2这样分区间,暴力交互发现是可以的。
但是每次你需要找到正确的 (x) 值放进去,你可以直接把交互库的代码贺了来模拟是否成功分开,但我直接把一个可行解打了个表(
然后你会发现也可以用这个方法把 Subtask 4 做到 (n-1) 步,这是后话。
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
#define fi first
#define se second
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;
using namespace std;const int N=100+5,M=N*4+5,K=N*4+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
void playRound(int*,int*);
namespace Subtask1{
int A[N],B[N],n;
int Solve(int N,int W){
n=N;
A[0]=1;playRound(A,B);
for(int i=0;i<n;i++) if(!B[i]) return i;
return 0;
}
}
int minValue(int N, int W) {return Subtask1::Solve(N,W);}
namespace Subtask2{
int n,A[N],B[N],Ct,vis[N];
int Solve(int N,int W){
int i;n=N;for(i=0;i<n;i++) vis[i]=1;
Ct=N;while(Ct^1){
Me(A,0);for(i=0;i<n;i++) if(vis[i]) A[i]=N/Ct;
playRound(A,B);for(i=0;i<n;i++) if(B[i]==N/Ct+1) vis[i]=1;else vis[i]=0;
Ct=0;for(i=0;i<n;i++) Ct+=vis[i];
}
for(i=0;i<n;i++) if(vis[i]) return i;
}
}
int maxValue(int N, int W) {return Subtask2::Solve(N,W);}
namespace Subtask3{
int n,A[N],B[N];
int Solve(int N,int W){
if(N==6) return 0;
A[0]=5;A[1]=5;playRound(A,B);
if(B[0]==6&&B[1]<6) return 0;if(B[1]==6&&B[0]<6) return 1;
if(B[0]<6&&B[1]<6){
A[0]=2;A[1]=2;playRound(A,B);
if(B[0]==3&&B[1]<3) return 0;if(B[1]==3&&B[0]<3) return 1;
if(B[0]<3&&B[1]<3){
A[0]=1;A[1]=1;playRound(A,B);
return B[1]==2&&B[0]<2;
}else{
A[0]=3;A[1]=3;playRound(A,B);
return B[1]==4&&B[0]<4;
}
}else{
A[0]=8;A[1]=8;playRound(A,B);
if(B[0]==9&&B[1]<9) return 0;if(B[1]==9&&B[0]<9) return 1;
A[0]=9;A[1]=9;playRound(A,B);
if(B[0]==10&&B[1]<10) return 0;if(B[1]==10&&B[0]<10) return 1;
}
}
}
int greaterValue(int N, int W) {return Subtask3::Solve(N,W);}
namespace Subtask4{
int n,A[N],B[N],Ct;
int PP[N]={0,1,1,1,1,1,1,1,1,1,2,1,1,2,3,3,1,3,1,1,2,3,4,2,3,4,4,1,2,3,3,4,1,5,1,2,2,3,5,3,4,5,2,5,2,3,4,5,4,4,6,1,2,3,5,6,3,4,6,5,6,1,4,5,6,1,7,1,2,2,2,3,4,5,7,3,4,7,5,6,7,2,5,6,7,2,2,3,4,5,6,8,3,4,6,8,5,8,6,8};
void calc(int l,int r,int *P,vector<int> Is){
if(l==r) {P[Is[0]]=l;return;}int SS=n/(r-l+1);
++Ct;
Me(A,0);for(int j:Is) A[j]=PP[Ct];playRound(A,B);
vector<int> I1,I2;for(int j:Is) if(B[j]>=PP[Ct]+1) I1.PB(j);else I2.PB(j);
if(!I1.empty()&&!I2.empty()) {
calc(l,l+I2.size()-1,P,I2);calc(l+I2.size(),r,P,I1);return;
}
}
void Solve(int N,int W,int *P){
n=N;vector<int> Is;Is.clear();for(int i=0;i<n;i++) Is.PB(i);calc(1,n,P,Is);
}
}
namespace Subtask5{
int n,A[N],B[N],Ct;
int PP[N]={0,2,3,4,15,17,21,26,35,52,4,5,26,35,53,5,6,35,53,7,53,8,53,9,54,10,11,12,14,16,18,22,27,36,54,2,18,22,28,37,55,2,55,2,3,8,9,10,10,11,13,14,16,19,22,28,37,56,3,28,37,56,3,4,14,16,19,23,28,38,56,4,5,23,28,38,56,5,6,28,38,57,7,38,57,8,57,9,57,10,11,12,13,15,17,19,23,29,38,57};
void calc(int l,int r,int *P,vector<int> Is){
if(l==r) {P[Is[0]]=l;return;}int SS=2*n/(r-l+1);
++Ct;
Me(A,0);for(int j:Is) A[j]=PP[Ct];playRound(A,B);
vector<int> I1,I2;for(int j:Is) if(B[j]>=PP[Ct]+1) I1.PB(j);else I2.PB(j);
if(!I1.empty()&&!I2.empty()) {
calc(l,l+I2.size()-1,P,I2);calc(l+I2.size(),r,P,I1);return;
}
}
void Solve(int N,int W,int *P){
n=N;vector<int> Is;Is.clear();for(int i=0;i<n;i++) Is.PB(i);calc(1,n,P,Is);
}
}
void allValues(int N, int W, int *P) {if(W==N) Subtask4::Solve(N,W,P);else Subtask5::Solve(N,W,P);}
相关文章
- Dependency Injection 和 Service Locator
- 聊聊代码的割裂感
- 手把手教你用Strace诊断问题
- Unicode and UTF-8
- Leetcode刷题记录:构建最大数二叉树
- Leetcode刷题记录:编码并解码短网址
- 一次「Too many open files」故障
- Laravel队列的一些细枝末节
- 关于FIN_WAIT1
- 修改服务的运行权限,解决SVN Post Commit问题
- 再叙TIME_WAIT
- 将iPod中的音乐拷贝到Mac中
- 一个PHP实现的ID生成器
- 实战Pinba
- Mac下使用XLD转换无损音乐Ape
- 关于FIN_WAIT2
- 如何判断GCC的版本
- 白话火焰图
- 记录一个多核CPU负载不均衡问题
- 如何正确发布PHP代码