IOI2016Day2. Messy

題目鏈接：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;
}

轉載請聲明！！！