IOI2016Day2. Messy
程序员文章站
2022-07-02 14:29:58
题目链接:http://uoj.ac/problem/239 题目大意: 这是一道交互题,交互库维护了一个数据结构,可以存储n为二进制串,一开始你可以向空的数据结构中插入若干二进制串, 接下来这个数据结构会将其中存储的二进制串进行改变。 改变的方法是生成一个0到n-1的排列pi,将原来的二进制串a0 ......
题目链接:http://uoj.ac/problem/239
题目大意:
这是一道交互题,交互库维护了一个数据结构,可以存储n为二进制串,一开始你可以向空的数据结构中插入若干二进制串,
接下来这个数据结构会将其中存储的二进制串进行改变。
改变的方法是生成一个0到n-1的排列pi,将原来的二进制串a0a1a2..an-1变成ap0ap1..apn-1。
接着你可以进行询问,每次询问一个串是否在这个数据结构当中,要求你在不超过w次插入和r次询问中求出排列p
分析:读完题后看看数据范围,w=r=896=128*7=nlog^2(n),提示我们用分治算法
加数:
我们需要在开始一次性把所有数加完。
考虑加哪些数?结合分治,我们把l,r分为(l,mid)(mid+1,r)如果我们把左边的数加入库中,分治时如果我们找到一个数在出现
就说明他是在(l,mid)范围内,否则在(mid+1,r)中,可以完成分治。
对于这个操作我们具体讲讲:根据上面所说,我们只对(l,mid)进行操作,枚举i(l<=i<=mid)我们使(l,i-1)(i+1,mid)为0,其他位置
都为1,把他们都加入库中,这样我们每一层1的个数都不同,所以所有数加入过后不会影响最后分治。
查找 :
我们对(0,n-1)进行分治,每次可以判断一个位置上的数在哪个区间,一直递归到底层可得最后答案。
附上交互代码 :
#include<bits/stdc++.h> #include "messy.h" using namespace std; const int N=350; int ans[N],used[N],len; inline void add(int l,int r) { if(l>=r) return ; string str=""; for(int i=0;i<len;i++) str+='0'; for(int i=0;i<l;i++) str[i]='1'; for(int i=r+1;i<len;i++) str[i]='1'; int mid=(l+r)>>1; for(int i=l;i<=mid;i++) { str[i]='1'; add_element(str); str[i]='0'; } add(l,mid);add(mid+1,r); } int temp[N]; inline void solve(int l,int r) { if(l>=r) return ; string str=""; for(int i=0;i<len;i++) str+='0'; for(int i=0;i<l;i++) str[ans[i]]='1'; for(int i=r+1;i<len;i++) str[ans[i]]='1'; int cnt1=0,cnt2=0,mid=(l+r)>>1; for(int i=l;i<=r;i++) { int o=ans[i]; str[o]='1'; if(check_element(str)) { cnt1++; temp[l+cnt1-1]=ans[i]; } else { cnt2++; temp[mid+cnt2]=ans[i]; } str[o]='0'; } for(int i=l;i<=r;i++) ans[i]=temp[i]; solve(l,mid);solve(mid+1,r); } vector<int> cnt; vector<int> restore_permutation(int n, int w, int r) { len=n; memset(used,0,sizeof(used)); add(0,len-1); compile_set(); for(int i=0;i<len;i++) ans[i]=i; solve(0,len-1); for(int i=0;i<len;i++) temp[ans[i]]=i; for(int i=0;i<len;i++) cnt.push_back(temp[i]); return cnt; }
转载请声明!!!
下一篇: IOI2016Day2. Paint