[20220208联考] 差量
前言
又被卷飞了。/jk
题目
这是一道交互题。
有一个长度为 \(n\) 的数组 \(a\)，里面的数字互不相同且都为不超过 \(10^9\) 的正整数，下标从 \(0\) 开始。有以下三种交互操作：
- 询问一个位置的值。
- 询问一个下标集合中元素两两的差的绝对值，返回顺序任意。如询问长度为 \(4\)，则返回长度为 \(\frac{4\times (4-1)}{2}=6\)。
- 回答。
三个操作对应的函数为：
int qry1(int pos)
vector qry2(const vector &S)
void answer(const vector &ret)
需要 #include "difference.h" 头文件。
讲解
嘛，交互题就那点套路，二分、倍增、分治，这道题用二分和分治。具体怎么想出来的，只能说人类智慧。
题解看不懂(我觉得它有问题)，但是卷爷一下就给我讲懂了！卷爷太强了！
为方便讲解，下文的差可能指差的绝对值。
首先我们问出 \(0\) 号位的值，并把全集问一次，可以得到极差。然后二分前缀，找到一个极值，问一下极值的值并与 \(0\) 号位比较即可知道这是最大值还是最小值，令极值位置为 \(jc\)。(我代码用的这个名字，尽管这个名字很蠢)
这里用到了 \(2\) 次 \(1\) 询问和 \(\log_2n\) 次 \(2\) 询问。
令除了 \(0\) 号位和找出来的那个极值的位置组成的集合为 \(S\)，我们询问 \(S\) 和 \(S\cup\{jc\}\)，用后者减去前者即可得到 \(S\) 中所有位置与极值的差，现在的问题就是如何分配这些值。
注意到所有的 \(a_i\) 互不相同，那么这些差的值也一定互不相同，把未成功分配的位置组成很多连续区间，每次将所有这些区间的前半段取出，一轮下来两次询问即可求出它们与极值的差。
显然，一轮操作后每个区间的长度都会减半，所以这里会用到 \(2\log_2n\) 次 \(2\) 询问。
总共使用 \(1\) 询问 \(2\) 次，\(2\) 询问 \(3\log_2n\) 次，可以通过。
由于n很小，所以不管写得多花里胡哨应该都不会TLE。
代码
代码实现难度很低
//12252024832524
#include "difference.h"
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 255;
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
//int qry1(int pos)
//vector qry2(const vector &S)
//void answer(const vector &ret)
vector Query(int l,int r,int ex = 500)
{
vector Q;
for(int i = l;i <= r;++ i) if(i^ex) Q.emplace_back(i);
return qry2(Q);
}
vector operator - (vector A,vector B)
{
sort(A.begin(),A.end()); sort(B.begin(),B.end());
vector ret; int now = 0,lena = A.size();
for(int i = 0,len = B.size();i < len;++ i)
{
while(A[now]^B[i]) ret.emplace_back(A[now++]);
++now;
}
while(now < lena) ret.emplace_back(A[now++]);
return ret;
}
vector operator & (vector A,vector B)
{
vector ret;
sort(A.begin(),A.end()); sort(B.begin(),B.end());
int now = 0,lenb = B.size();
if(!lenb) return ret;
for(int i = 0,len = A.size();i < len;++ i)
{
while(now < lenb-1 && B[now] < A[i]) ++now;
if(A[i] == B[now]) ret.emplace_back(A[i]);
}
return ret;
}
struct node
{
int l,r;
vector val;
};
int ans[MAXN];
void find(int n, int M1, int M2)
{
vector ret,Q; ans[0] = qry1(0);
int m = 0; ret = Query(0,n-1);
for(int i = 0,len = ret.size();i < len;++ i) m = Max(m,ret[i]);
int l = 1,r = n-1,jc = 1;
while(l <= r)
{
int mid = (l+r) >> 1,win = 0;
ret = Query(0,mid);
for(int i = 0,len = ret.size();i < len && !win;++ i) if(ret[i] == m) win = 1;
if(win) jc = mid,r = mid-1;
else l = mid+1;
}
ans[jc] = qry1(jc);
ret = Query(1,n-1) - Query(1,n-1,jc);
vector q[2];
if(1 < jc)
{
if(jc < n-1) q[0].emplace_back(node{1,jc-1,ret-(Query(jc,n-1)-Query(jc+1,n-1))});
else q[0].emplace_back(node{1,jc-1,ret});
}
if(jc < n-1)
{
if(1 < jc) q[0].emplace_back(node{jc+1,n-1,ret-(Query(1,jc)-Query(1,jc-1))});
else q[0].emplace_back(node{jc+1,n-1,ret});
}
bool now = 0,to = 1;
while(!q[now].empty())
{
Q.clear(); bool wow = 0;
for(int i = 0,len = q[now].size();i < len;++ i)
{
if(q[now][i].l == q[now][i].r) ans[q[now][i].l] = q[now][i].val[0];
else
{
int mid = (q[now][i].l + q[now][i].r) >> 1;
for(int j = q[now][i].l;j <= mid;++ j) Q.emplace_back(j);
wow = 1;
}
}
if(!wow) break;
ret = qry2(Q); Q.emplace_back(jc); ret = qry2(Q) - ret;
for(int i = 0,len = q[now].size();i < len;++ i)
if(q[now][i].l ^ q[now][i].r)
{
int mid = (q[now][i].l + q[now][i].r) >> 1;
q[to].emplace_back(node{q[now][i].l,mid,q[now][i].val & ret});
q[to].emplace_back(node{mid+1,q[now][i].r,q[now][i].val - (q[to].back().val)});
}
q[now].clear();
to = now; now ^= 1;
}
for(int i = 1;i < n;++ i)
if(i^jc)
{
if(ans[0] < ans[jc]) ans[i] = ans[jc] - ans[i];
else ans[i] = ans[jc] + ans[i];
}
ret.clear();
for(int i = 0;i < n;++ i) ret.emplace_back(ans[i]);
answer(ret);
}