2015年4月10日 星期五

[USACO 2014 Gold] Fair Photography

作法:

令 S[ i ][ j ] 代表第 i 種品種在前 j 隻牛裡面出現了幾隻,那麼如果 ( L , R ] 是一個滿足條件的區間,若且唯若:對於所有的品種 i ,要嘛 S[ i ][ L ] = S[ i ][ R ] ,要嘛 S[ i ][ R ] - S[ i ][ L ] = k ,其中 k 為一個不受 i 影響的定值。也就是如果我們考慮把 B 個前綴和包成一個 B 元數組,第 j 個數組的第 i 項就是 S[ i ][ j ] ,那麼我們就是要在這 n+1 個 B 元組裡面找兩個數組 P 和 Q ,使得存在一個 1~B 的子集 A, 滿足當 i ∈ A 時 P[ i ] = Q[ i ] + k , i ∉ A 時 P[ i ] = Q[ i ] 。考慮對一個從「 B 元組和一個 1~B 的子集 A」 映射到 B 元組的函數 f ( P , A ) ,其中:

f ( P , A ) [ i ] = P[ i ] ,當 i ∉ A 。
f ( P , A ) [ i ] = P[ i ] - P[ k ] ,當 i ∈ A ,其中 k 是 A 中最小的數。

那麼可以得到,若 B 元組 P 和 Q 滿足題目的條件,那麼存在一個 A 使得 f( P , A ) = f( Q , A ) 。所以這樣就可以得到一個算法:枚舉所有的 A ,還有所求區間的右端點,每次將新的 B 元組關於 A 的 f 值加入一個查找表中,並且紀錄是在哪個位置出現這個數組的,然後查詢當前右端點的前綴和形成的 B 元組關於 A 的 f  值是否有出現在查找表裡面,有的話就代表找到了一個滿足條件的區間。但這個算法的複雜度會是 O( n * 2^B ) ,會TLE掉。

還要注意到一件事,就是當我們固定區間的右端點時,考慮左端點從這個點開始往左邊跑,會有一些新的品種進到這個區間中,而已經在區間內的品種不會不見,也就是對於一個右端點的所有符合條件的區間中,可能的 A 集合只有 B 種,所以可以只枚舉這 B 種就好了。所以我們的查找表就改成紀錄數組的 f 值,再加上他是用哪個 A 集合轉換過來的。另外同理可以有,對於一個左端點,最多也只有 B 種可能的 A 集合,所以以他為左端點時只要加入 B 個東西進入查找表即可。

一開始我查找表直接用 map< vector<int>,int > 寫,結果有兩筆測資一直TLE,後來改成自己寫 hash 才過,真是麻煩QQ。

code :



#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define M 5000000
using namespace std;
const int maxn=100000+10 , maxb=8+2 ;
 
void getv(const vector<int> &vec,int S,vector<int> &ret)
{
    ret.resize(vec.size()) ;
    for(int i=0,j=-1;i<vec.size();i++)
    {
        if(!(S&(1<<i))) ret[i]=vec[i] ;
        else
        {
            if(j==-1) j=vec[i] ;
            ret[i]=vec[i]-j ;
        }
    }
    ret.push_back(S) ;
}
 
int ri[maxn][maxb],le[maxn][maxb] ;
void getb(int x,int type,int K,vector<int> &ret)
{
    ret.clear() ;
    if(type==1) for(int i=K-1;ri[x][i];i++)
        ret.push_back(ri[x][i]) ;
    else for(int i=K-1;le[x][i];i++)
        ret.push_back(le[x][i]) ;
}
 
struct node
{
    node *nex ;
    vector<int> vec ;
    int data ;
    node(const vector<int> &_vec,int _data)
    {
        nex=NULL ;
        data=_data ;
        vec=_vec ;
    }
}*head[M] ;
 
int insert(const vector<int> &vec,int data)
{
    int h=0 ;
    for(int i=0;i<vec.size();i++) h+=(vec[i]<<(2*i)) ;
    h%=M ; if(h<0) h+=M ;
    for(node *u=head[h];u;u=u->nex)
    {
        bool ok=1 ;
        for(int i=0;i<vec.size();i++) if(vec[i]!=u->vec[i])
            { ok=0 ; break ; }
        if(ok) return u->data ;
    }
    if(data==-1) return -1 ;
    node *v=new node(vec,data) ;
    v->nex=head[h] ; head[h]=v ;
    return -1 ;
}
 
vector<int> pos[maxb] ;
vector<int> sum(maxb),tmp1(maxb),tmp2(maxb) ;
pii p[maxn] ;
 
int n ;
pii tmp[maxb] ;
void cal_lr(int x)
{
    int cnt=0 ;
    for(int i=0;i<maxb;i++)
    {
        int id=lower_bound(pos[i].begin(),pos[i].end()
                           ,x)-pos[i].begin() ;
        if(id!=pos[i].size()) tmp[cnt++]=(pii){pos[i][id],i} ;
    }
    sort(tmp,tmp+cnt) ;
    for(int i=0,j=0;i<cnt;i++)
        j^=(1<<tmp[i].S) , ri[x][i]=j ;
 
    cnt=0 ;
    for(int i=0;i<maxb;i++)
    {
        int id=upper_bound(pos[i].begin(),pos[i].end(),
                           x)-pos[i].begin()-1 ;
        if(id>=0) tmp[cnt++]=(pii){pos[i][id],i} ;
    }
    sort(tmp,tmp+cnt,greater<pii>()) ;
    for(int i=0,j=0;i<cnt;i++)
        j^=(1<<tmp[i].S) , le[x][i]=j ;
}
 
main()
{
    if(fopen("fairphoto.in","r"))
    {
        freopen("fairphoto.in","r",stdin) ;
        freopen("fairphoto.out","w",stdout) ;
    }
    int K ; scanf("%d%d",&n,&K) ;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].F,&p[i].S) ;
    sort(p+1,p+n+1) ;
    for(int i=1;i<=n;i++) pos[p[i].S].push_back(i) ;
    for(int i=1;i<=n;i++) cal_lr(i) ;
 
    int ans=-1 ;
    for(int i=1;i<=n;i++)
    {
        getb(i,1,K,tmp1) ;
        for(auto j : tmp1)
        {
            getv(sum,j,tmp2) ;
            insert(tmp2,p[i].F) ;
        }
        sum[p[i].S]++ ;
        getb(i,2,K,tmp1) ;
        for(auto j : tmp1)
        {
            getv(sum,j,tmp2) ;
            int res=insert(tmp2,-1) ;
            if(res!=-1) ans=max(ans,p[i].F-res) ;
        }
    }
    printf("%d\n",ans) ;
}
 

沒有留言:

張貼留言