srO Charlie Orz
[CF1354G]Find a Gift
\(【题目描述】\)
这是一道交互题。你有一排 \(n(n\leq 10^3)\) 个箱子，编号为 \(1\rightarrow n\)，每个箱子可能装有一个礼物或石头（保证礼物的数量 \(k\leq \lfloor \frac{n}{2}\rfloor\)），装有石头的箱子重量相等，且严格大于装有礼物的箱子，但装有礼物的箱子重量可能不相等。你可以进行不超过 \(50\) 次询问，每次询问给出两个箱子编号的不相交集合 \(A,B\)，表示询问 \(A\) 中的箱子重量之和与 \(B\) 中的箱子重量之和的大小关系。现要求找出编号最小的装有礼物的箱子编号。
\(【考点】\)
随机化、二分、倍增
\(【做法】\)
一道挺有思维难度的题（对于我来讲交互题都这样
首先 \(50\) 次询问以及 \(n\leq 1000\) 可以想到 \(5\log\) 左右的做法，一般使用二分或倍增。可以发现，想要确定一个箱子的状态，必须用一个已知为石头的箱子去与之比较。
假设我们确定了 \(1\) 号箱子是石头，就可以用它和 \(2\) 号箱子比较，推算出 \(2\) 号箱子的情况，若还是石头，我们可以用 \([1,2]\) 箱子去推出 \([3,4]\) 箱子的情况……直到发现 \([1,p],[p+1,2p]\) 重量不相等，然后就可以将答案确定在 \([p+1,2p]\) 中。于是可以利用 \([1,p]\) 全是石头的性质，二分出第一个礼物的位置。除去确定 \(1\) 号箱子，一共需要 \(2\log\) 左右的次数。
回到一开始的问题，如何确定 \(1\) 号箱子是石头。题目中限定了 \(k\leq \lfloor \frac{n}{2}\rfloor\)，即至少有一半为石头，此时大概还剩 \(3\log\) 次操作，可以直接Roll \(3\log\) 个箱子与 \(1\) 号作比较，若Roll出了一个石头就可以确定 \(1\) 号箱子的状态概率至少为 \(1-\frac{1}{2^{30}}\).
\(【代码】\)
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define go(i,u) for(int i=head[u];i;i=a[i].nxt)
#define f fflush(stdout)
using namespace std;
int n,k,t;
char s[10];
int query(int l1,int r1,int l2,int r2)
{
printf("? %d %d\n",r1-l1+1,r2-l2+1);
rep(i,l1,r1) printf("%d ",i);
puts("");
rep(i,l2,r2) printf("%d ",i);
puts(""),f;
scanf("%s",s+1);
if(s[1]=='F') return 1;
if(s[1]=='S') return 2;
return 3;
}
int main()
{
srand((int)time(0));
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
bool q=true;
rep(i,1,20){//roll 20个箱子与1比较
int r=rand()%(n-1)+2;
if(query(1,1,r,r)==2){
q=false;break;
}
}
if(!q){
printf("! 1\n"),f;
continue;
}
int now=1,pos=1;
while((now<<1)<=n){//倍增比较[1,now]与[now+1,now*2]
if(query(1,now,now+1,now<<1)==1) break;
now<<=1;
}
int l=now+1,r=min((now<<1),n);
while(l<r){//二分找[now+1,now*2]的第一个1
int mid=(l+r)>>1;
if(query(l,mid,1,mid-l+1)==3) l=mid+1;
else r=mid;
}
printf("! %d\n",l),f;
}
return 0;
}
[WC2018]通道
\(【题目描述】\)
给出 \(n(n\leq 10^5)\) 个点，点与点之间有 \(3\) 类连边，边都有长度，每类边分别构成一棵树。现要找出两个点 \(x,y\)，使得他们在三棵树上的距离之和最大。
\(【考点】\)
边分治、虚树、随机化
\(【做法】\)
一眼随机化
可以模拟退火，但是时间复杂度可能不太能接受。
考虑一下一棵树的情况，就是两遍大法师找到直径两端点。那扩展到三棵树，同样以一个点为根，进行狂暴大法师，找到一个深度最深的点，以他为根，反复循环大法师，直到超时为止。然后借助模拟退火优化的小trick，换几个根多跑几遍，记录全局最优解。
\(【代码】\)
#include<bits/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define go(i,u,t) for(int i=head[t][u];i;i=a[t][i].nxt)
using namespace std;
const int N=5e5+50;
struct edge{
int to,val,nxt;
}a[3][N<<1];
int head[3][N],dis[3][N],root=1,cnt[3],n,ans;
bool vis[N];
inline int read()
{
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=(x<<1)+(x<<3)+ch-48;
ch=getchar();
}
return x;
}
inline void print(int x)
{
if(x>9) print(x/10);
putchar((x%10)|48);
}
namespace kuangbaodfs{
void dfs(int u,int fa,int t)
{
go(i,u,t){
int v=a[t][i].to;
if(v!=fa){
dis[t][v]=dis[t][u]+a[t][i].val;
dfs(v,u,t);
}
}
}
inline int Dis(int x){return dis[0][x]+dis[1][x]+dis[2][x];}
void solve()
{
int T=10;
root=((int)rand()*(int)rand())%n+1;//注意这里rand()的范围只有32767
while(T--){
dis[0][root]=dis[1][root]=dis[2][root]=0;
rep(t,0,2) dfs(root,0,t);
int now=0;
rep(i,1,n){
if(Dis(now)<Dis(i)){
now=i,ans=max(ans,Dis(i));
}
}
root=now;
}
}
}
using namespace kuangbaodfs;
void add(int u,int v,int w,int t)
{
++cnt[t];
a[t][cnt[t]].to=v;
a[t][cnt[t]].val=w;
a[t][cnt[t]].nxt=head[t][u];
head[t][u]=cnt[t];
}
signed main()
{
double st=clock();
n=read();
int u,v,w;
rep(t,0,2){
rep(i,1,n-1){
u=read(),v=read(),w=read();
add(u,v,w,t);
add(v,u,w,t);
}
}
while((clock()-st)/CLOCKS_PER_SEC<3.5) solve();
printf("%lld\n",ans);
return 0;
}
[CF1114E]Arithmetic Progression
\(【题目描述】\)
这是一道交互题。交互库有一个长度为 \(n(n\leq 10^6)\) 的乱序等差数列 \(a(a_i\leq 10^9)\)，最多可以进行 \(60\) 次以下询问：
- 给定一个 \(i\)，询问 \(a_i\) 的值
- 给定一个 \(x\)，询问是否存在 \(a_i>x\)
现要求出这个等差数列的首项和公差。
\(【考点】\)
数学（？
\(【做法】\)
首先可以通过二分，使用第二个操作 \(30\) 次找到末项。接着roll \(30\) 个数搞操作1，求出它们与末项的差的 \(\gcd\)
于是就做完了，感性理解一下发现成功率很高，严谨证明大概为 \(1-\frac{1}{10^9}\)
\(【代码】\)
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
using namespace std;
const int N=1e6+50;
int n,t=60;
bool vis[N];
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
inline bool que(int x)
{
printf("> %d\n",x);
fflush(stdout);
int p;
scanf("%d",&p);
return p;
}
int main()
{
srand((int)time(0));
scanf("%d",&n);
int l=0,r=1e9;
while(l<r){
int mid=(l+r)>>1;
t--;
if(que(mid)) l=mid+1;
else r=mid;
}
int g=0,x,cnt=0;
rep(i,1,t){
if(cnt==n) break;
int r=((int)rand()*(int)rand())%n+1;//还是注意rand()的范围
while(vis[r]) r=rand()%n+1;
vis[r]=true,cnt++;
printf("? %d\n",r);
fflush(stdout);
scanf("%d",&x);
g=gcd(g,l-x);
}
printf("! %d %d\n",l-(n-1)*g,g);
return 0;
}
[CF1305F]Kuroni and the Punishment
\(【题目描述】\)
给定一个长为 \(n(n\leq 2\times 10^5)\) 的序列 \(a\)，每次可以将一个数+1或-1，求使得所有数都不互质的最小操作次数。
\(【考点】\)
随机化
\(【做法】\)
首先一种合法方案就是将所有数变成偶数。因此操作次数的上限即为 \(n\)，也就是说，有一半以上的数变化量不超过1。因此，我们在序列中随机roll \(50\) 个数，设当前数为 \(x\)，将 \(x,x+1,x-1\) 的质因数全部存到一个集合里面，最终集合里面至多有 \(600\) 个质数，且必有一个是最终整个序列 \(gcd\) 的因数，因此直接算每个质数作为 \(gcd\) 的因数的情况下，序列中所有数的变化量之和，去最小即可。
\(【代码】\)
#include<bits/stdc++.h>
#define IT set<ll>::iterator
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
using namespace std;
typedef long long ll;
const int N=2e5+50,M=2e6+50;
const ll inf=1e18;
int n,ed;
ll a[N],s[N];
bool vis[M];
set<ll> prime;//set自动去重
void work(ll x)
{
if(x<=0) return ;
for(ll i=2;i*i<=x;++i){
if(x%i==0){
if(!vis[i]) vis[i]=true,prime.insert(i);
while(x%i==0) x/=i;
}
}
if(x!=1) prime.insert(x);
}
inline ll Run(ll x)
{
ll cnt=0;
rep(i,1,n){
ll t=a[i]/x*x;
if(t) cnt+=min(a[i]-t,t+x-a[i]);
else cnt+=t+x-a[i];
}
return cnt;
}
int main()
{
srand((int)time(0));
scanf("%d",&n);
rep(i,1,n) scanf("%lld",&a[i]);
rep(t,1,50){
int p=((int)rand()*(int)rand())%n+1;
work(a[p]),work(a[p]+1),work(a[p]-1);
}
ll ans=inf;
// rep(i,1,ed) printf("%lld ",prime[i]);
// puts("");
for(IT it=prime.begin();it!=prime.end();++it){
// printf("%lld\n",Run(prime[i]));
ans=min(ans,Run(*it));
}
if(ans==inf) printf("%d\n",n);
else printf("%lld\n",ans);
return 0;
}
[JSOI2016]炸弹攻击
\(【题目描述】\)
二维平面上有 \(n(n\leq 10)\) 个圆和 \(m(m\leq 10^3)\) 个点，求一个圆心任意、半径不超过 \(R\) 的圆，使其不予任何给定的圆相交，且覆盖点的个数最多。
\(【考点】\)
计算几何、模拟退火
\(【做法】\)
一眼退火
如果直接拿覆盖点数作为估价函数，价值相等的点太多，不好搞，因此可以考虑设估价函数 \(f(x)=c-kr_0\)，其中 \(c\) 表示覆盖点数，\(r_0\) 表示再增加多少半径能够覆盖到下一个点，\(k\) 是一个 \(>0\) 的常数。经过一番尝试，最终确定 \(k=14.14\) 时最优.
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define eps 1e-6
using namespace std;
const int N=1e3+50,M=15;
const double T=5e8,ed=1e-10,del=0.998,inf=1e9;
double x[M],y[M],r[M],p[N],q[N];
int n,m,ans,cnt;
double R,X,Y,val;
inline double Rand(){return rand()%100000/100000.0;}
inline double dis(double x,double y,double xx,double yy){
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
double work()
{
cnt=0;
double nowr=inf;
rep(i,1,n) nowr=min(nowr,dis(x[i],y[i],X,Y)-r[i]);
nowr=max(nowr,0.0);
nowr=min(R,nowr);
double minr=inf;
rep(i,1,m){
double d=dis(p[i],q[i],X,Y);
minr=min(minr,d-nowr);
if(nowr-d>=-eps) ++cnt;
}
minr=max(minr,0.0);
return -minr*14.14+(double)cnt;
}
void SA()
{
X=0,Y=0;
val=-inf;
for(double t=T;t>=ed;t*=del){
double tx=X,ty=Y;
X=X+(rand()*2-RAND_MAX)*t;
Y=Y+(rand()*2-RAND_MAX)*t;
// printf("SS:%lf %lf\n",X,Y);
double nw=work();
if(nw>val){
// printf("%d %lf %lf\n",cnt,X,Y);
val=nw,ans=cnt;
}
else{
if(exp((nw-val)/t)<=Rand()) X=tx,Y=ty;
}
}
}
int main()
{
srand(114514);
scanf("%d%d%lf",&n,&m,&R);
rep(i,1,n) scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
rep(i,1,m) scanf("%lf%lf",&p[i],&q[i]);
double st=clock();
while((clock()-st)/CLOCKS_PER_SEC<0.85) SA();
printf("%d\n",ans);
return 0;
}
[CF1305F]Subway Pursuit
\(【题目描述】\)
你有一辆发怒/fn的火车，你要抓住他，每次可以选择一个区间 \([l,r]\)，询问火车是否在这个区间内，若 \(l=r\) 且回答“是”，那么就抓住了火车，算成功，否则火车会往左或往右移动至多 \(k(k\leq 10)\) 步（火车移动范围为 \([1,10^{18}]\)）。你需要在 \(4500\) 次询问内找到这辆火车。
\(【考点】\)
随机化、二分
\(【做法】\)
考虑对整个范围进行二分，每次算上可能移动的 \(k\) 步即可（例如二分出可能区间为 \([l,mid]\)，则下次询问 \([l-k,mid+k]\)），当区间长度到达一个阈值 \(B\) 的时候，区间不再会递减，此时直接盲猜一个位置，然后放区间长度 \(+20\)
- 取 \(B=40\) 时，临近阈值的几次区间长度变化最坏情况为： \(60\rightarrow 50\rightarrow 45\rightarrow 43\rightarrow 42\rightarrow 41\)，这样盲猜的次数只有 \(800\) 次左右。
- 取 \(B=50\) 时，临近阈值的几次区间长度变化最坏情况为：\(70\rightarrow 55\rightarrow 48\)，大约可以猜 \(1400+\) 次，因此取 \(B=50\) 更优
\(【代码】\)
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
using namespace std;
typedef long long ll;
ll n,k;
char s[100];
bool query(ll l,ll r)
{
printf("%lld %lld\n",l,r);
fflush(stdout);
scanf("%s",s+1);
if(s[1]=='Y') return true;
return false;
}
int main()
{
scanf("%lld%lld",&n,&k);
ll l=1,r=n;
while(1){
while(r-l>50){
ll mid=(l+r)>>1;
if(query(l,mid)) r=mid;
else l=mid+1;
l=max(1ll,l-k);
r=min(n,r+k);
}
ll pos=(ll)rand()*rand()*rand()*rand()%(r-l+1)+l;
if(query(pos,pos)) break;
l=max(1ll,l-k),r=min(n,r+k);
}
return 0;
}
[CF1061F]Lost Root
\(【题目描述】\)
这是一道交互题。交互库有一个 \(n(n\leq 1500)\) 个节点的满 \(k(k\leq n)\) 叉树，你需要找到这棵树的根，你可以进行以下操作至多 \(60n\) 次：给出三个点 \(a,b,c\)，询问 \(b\) 是否在路径 \((a,b)\) 上。
\(【考点】\)
随机化
\(【做法】\)
满 \(k\) 叉树启发我们先找到叶子，然后根据根在两个非同一大子树内的叶子的中点，找到根。具体而言，可以先问出路径上的所有点，然后对于所有点诶个问与叶子的距离，共花费 \(n+h^2\) 次询问。
接下来问题变成了找叶子，我们先随便roll两个点 \(u,v\)，然后枚举点 \(w\)，若 \(v\) 在路径 \((u,w)\) 上，直接 \(v\leftarrow w\)，最后 \(v\) 肯定是一个叶子，共花费 \(n\) 次询问，然后再用同样的方法找另一个叶子，只要叶子之间的距离为 \(2h-1\)，也就是不在同一个大子树上，就可以直接找到根了。这样一次花费共 \(2n\) 次询问，成功的概率至少为 \(\frac{1}{2}\)，随便跑个 \(19\) 次左右即可，成功率为 \(1-\frac{1}{2^{19}}\)
\(【代码】\)
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define go(i,u) for(int i=head[u];i;i=a[i].nxt)
using namespace std;
const int N=1e3+5e2+50;
int n,k,h;
int query(int x,int p,int y)
{
printf("? %d %d %d\n",x,p,y);
fflush(stdout);
char s[10];
scanf("%s",s+1);
return s[1]=='Y';
}
int get_dis(int x,int y)//全局查找两点距离
{
int cnt=2;
rep(i,1,n){
if(i!=x&&i!=y) cnt+=query(x,i,y);
}
return cnt;
}
inline int find_leaf()
{
int u=rand()%n+1,v=rand()%n+1,w;
v=rand()%n+1;
rep(i,1,n){
w=rand()%n+1;
w=rand()%n+1;
if(query(u,v,w)) v=w;
}
return v;
}
int s[N],ed;
int get_dis_plus(int x,int y)//知道链上的节点后查找两点距离
{
int cnt=2;
rep(i,1,ed){
if(s[i]!=x&&s[i]!=y) cnt+=query(x,s[i],y);
}
return cnt;
}
int get_ans(int x,int y)
{
ed=0;
rep(i,1,n){
if(i!=x&&i!=y&&query(x,i,y)) s[++ed]=i;
}
rep(i,1,ed){
if(get_dis_plus(x,s[i])==h) return s[i];
}
return 114514;
}
int main()
{
srand((int)time(0));
scanf("%d%d",&n,&k);
h=log(n)/log(k)+1;
rep(i,1,19){
int A=find_leaf(),B=find_leaf();
if(A!=B&&get_dis(A,B)==2*h-1){
printf("! %d\n",get_ans(A,B));
fflush(stdout);
return 0;
}
}
int r=rand()%n+1;
printf("! %d\n",r);
return 0;
}