网站你懂我意思正能量app,做购物网站能赚钱吗,wordpress 调试php代码,wordpress头像代码正题
题目链接:http://pjudge.ac/problem/21651 题目大意
有一个1∼n1\sim n1∼n的排列#xff0c;每次你可以询问 iii和jjj的大小关系i,j,ki,j,ki,j,k的中位数
现在要求在222次111操作和2n2n2n次222操作内得到这个排列。 50≤n≤510550\leq n\leq 5\times 10^550≤n≤5105…正题
题目链接:http://pjudge.ac/problem/21651 题目大意
有一个1∼n1\sim n1∼n的排列每次你可以询问
iii和jjj的大小关系i,j,ki,j,ki,j,k的中位数
现在要求在222次111操作和2n2n2n次222操作内得到这个排列。
50≤n≤5×10550\leq n\leq 5\times 10^550≤n≤5×105 解题思路
首先我们发现在询问中位数的情况下我们是完全不能够区分1,21,21,2和n−1,nn-1,nn−1,n的那么两次操作111肯定是用于区分这两个东西上的。
那么我们假设我们现在已经得到了两个数字[l,r][l,r][l,r]此时我们通过询问中位数l,r,xl,r,xl,r,x。
若lxrlxrlxr此时我们可以得到xxx。得到xlxlxl或者xrxrxr
再进一步如果我们不知道l,rl,rl,r的值呢。此时如果我们在询问中得到了两个kkk那么说明kkk一定是lll或者rrr的值也就是lll和rrr我们能得到两次如果有一个只得到了一次那么说明l1l1l1或者l2l2l2也就是在边界附近的两格。
而如果我们已经确定了一个xlxlxl此时肯定也有前一个ylylyl因为lll被得到了两次那么我们令lxlxlx然后再重新处理一次yyy。
不难发现这样最多扩展nnn次每次会重新处理一个数字也就是2n2n2n次询问。 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#include guess.h
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N5e510;
int v[N];
vectorint now,ans;
vectorint q;
void Clear(int l,int r){for(int il;ir;i)if(v[i])ans[v[i]-1]i,v[i]0;q.clear();return;
}
int Ask2(int x,int y,int z)
{return query2(x-1,y-1,z-1);}
int Ask1(int x,int y)
{return query1(x-1,y-1);}
vectorint solve(int n,int m){int x1,y2,L0,R0,flag0;ans.resize(n);for(int i3;in;i)now.push_back(i);for(int ii0;iinow.size();ii){
// if(ans[now[ii]-1])continue;int inow[ii],kAsk2(x,y,i);if(v[k]){if(flag-1){if(kR){ans[y-1]k;yi;now.push_back(v[k]);v[k]0;}else{ans[x-1]k;xi;now.push_back(v[k]);v[k]0;}}else if(flag){LRkAsk2(i,v[k],x);now.push_back(y);yi;if(kflag)swap(x,y),R;
// now.push_back(v[k]);v[k]0;
// Clear(L1,R-1);for(int i0;iq.size();i)now.push_back(q[i]);memset(v,0,sizeof(v));q.clear();flag-1;}else{if(!flag)now.push_back(x);flagk;xi;for(int i0;iq.size();i)now.push_back(q[i]);memset(v,0,sizeof(v));q.clear();}}else v[k]i,q.push_back(i);}Clear(3,n-2);int av[2],bv[n-1];if(flag!-1){int k1Ask2(a,b,x);if(k1n-1)swap(x,y);}if(Ask1(x,a))ans[x-1]1,ans[a-1]2;else ans[a-1]1,ans[x-1]2;if(Ask1(y,b))ans[y-1]n-1,ans[b-1]n;else ans[b-1]n-1,ans[y-1]n;return ans;
}
