网站建设首页模板,网站服务器选购,网站制作成本多少钱,网联科技网站建设题目
t(t100)组样例#xff0c;长为n(n2000)的序列
交互题#xff0c;每次你可以询问一个区间[l,r]的逆序对数#xff0c;代价是
要在的代价内问出最大元素的位置#xff0c;输出其位置
思路来源
neal Codeforces Round 890 (Div. 2) supported by Constructo…题目
t(t100)组样例长为n(n2000)的序列
交互题每次你可以询问一个区间[l,r]的逆序对数代价是
要在的代价内问出最大元素的位置输出其位置
思路来源
neal Codeforces Round 890 (Div. 2) supported by Constructor Institute D (交互分治) 附加强 - 知乎
题解
赛中开题顺序大失败没看这个sb题
赛后用一种不超过的搞过去了也就是分治左右区间
找到左区间和右区间的极大值的位置
然后询问两次决定是左更大还是右更大 看见neal这个最优次数不超过补一下
感觉有点哈夫曼树贪心的意思也有点启发式NTT的合并方式 实际就是当还有x个位置都可以成为答案时
把他们按位置增序维护在链表里
每次遍历链表找到位置最接近的两个数询问
复杂度
构造
根据这个尝试去构造对应的hack方法
于是想到的最接近3n方次数的构造方法是 先把n和n-1放两边n-2放中间然后递归左右 n9时数组形如 9 4 6 3 7 2 5 1 8 证明 代码
#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,ll PI;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ll long long
#define ull unsigned ll
const int N2e310;
int t,n,dp[N][N];
int cal(int l,int r){if(lr)return 0;if(~dp[l][r])return dp[l][r];printf(? %d %d\n,l,r);fflush(stdout);int v;scanf(%d,v);return dp[l][r]v;
}
void out(int x){printf(! %d\n,x);fflush(stdout);
}
int main(){sci(t);while(t--){sci(n);vectorintnow(n);iota(now.begin(),now.end(),1);rep(i,1,n){rep(j,i,n){dp[i][j]-1;}}while(SZ(now)1){int disn,p-1,szSZ(now)-1;rep(i,0,sz-1){int wnow[i1]-now[i];if(wdis)disw,pi;}int xcal(now[p],now[p1]),ycal(now[p],now[p1]-1);if(xy)now.erase(now.begin()p);else now.erase(now.begin()(p1));}out(now[0]);}return 0;
}
