2016年12月24日 星期六

TIOJ 1726 Dice Wars

  老實說 我這題真的AC得很莫名其妙
本來一點想法也沒有 然後用一些詭異的優化答案就出來了?!

先不管複雜度 說說中心思想

先開n個vector
然後若是第i個位置是k
那麼在第 k 個vector丟入i

若詢問為a,b

那麼就是將所有a所在的位置
都詢問離該點最近的 b 的位置(在b的vector做lower_bound)

所以這樣每步就會是 O( SZ(vec[a]) lg( SZ(vec[b]) ) )
很明顯若是 SZ(vec[a])>SZ(vec[b])
我們可以交換a,b 達到較好的複雜度

最後
有兩個小小技巧
1.
把所有已經回答的詢問存起來
要是以前已經問過 就可以直接回答
2.
如果有連續三個以上一樣的數字
中間的可以全部都不要存

然後我就不會算複雜度了
但是有一種構造方法可以弄成O(n*sqrt(n)*lg(n) )
就是共sqrt(n)個數字 每個數字有sqrt(n)個
詢問種類最多約 sqrt(n)*sqrt(n)/2
每個次詢問是sqrt(n) lg(n)
所以是O(sqrt(n)*sqrt(n)/2*sqrt(n)*lg(n))=O(n*sqrt(n)*lg(n) )

如果有神人會證複雜度務必告訴我

2018/3/8 補證明
我們已經知道每次詢問複雜度是O( SZ(vec[a]) lg( SZ(vec[b]) ) )
假設SZ(vec[a])<=SZ(vec[b])
考量下列兩種情形

1 . SZ(vec[a])<=sqrt(n)
 這時每次詢問都是O( sqrt(n) lg( n ) )
 總詢問q次 所以此部分詢問複雜度是O( q sqrt(n) lg( n ) )

2 . sqrt(n)<=SZ(vec[a])<=SZ(vec[b])
 我們知道大小大於sqrt(n)的vec,最多只有sqrt(n)個
 也就是說,要在此情形詢問vec[a],最多只會問sqrt(n)次
 也就是說,對於vec[a]裡面每一個元素,最多只會問sqrt(n)次
 而總元素數量是n,所以總複雜度就是O( n sqrt(n) lg( n ) )

所以此題的複雜度就是O( (n+q) sqrt(n) lg( n ) )

#include <bits/stdc++.h>
using namespace std;
//type
typedef long long ll;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef priority_queue<pll,vector<pll>,greater<pll> > heap;
typedef vector<int>::iterator iter;
//macro
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define REP(i,n) for(ll i=0;i<(n);i++)
#define REP1(i,a,b) for(ll i=(a);i<=(b);i++)
#define mkp make_pair
#define pb push_back
const int INF=1e9;
const ll MA=1e6+5;
const ll MOD=1e9+7;
//}}}
int n,m;
vector<int> v[60010];
map<pii,int> mp;
int arr[60010];
int main(){
 ios_base::sync_with_stdio(0); cin.tie(0);
 cin>>n>>m;
 int k;
 for(int i=1;i<=n;i++)
  cin>>arr[i];
 for(int i=1;i<=n;i++){
  if(arr[i-1]!=arr[i]||arr[i+1]!=arr[i])
   v[arr[i]].emplace_back(i);
 }
 int a,b;
 while(m--){
  cin>>a>>b;
  if(!SZ(v[a])||!SZ(v[b])){
   cout<<"-1\n";
   continue;
  }
  if(a==b){
   cout<<"0\n";
   continue;
  }
  if(a>b) swap(a,b);
  if(mp.find({a,b})!=mp.end()){
   cout<<mp.find({a,b})->second<< '\n';
   continue;
  }
  if(SZ(v[a])>SZ(v[b])) swap(a,b);
  int mi=INF;
  for(int i=0,si=SZ(v[a]);i<si;i++){
   int x=lower_bound(ALL(v[b]),v[a][i])-v[b].begin();
   if(x!=SZ(v[b])) mi=min(mi,v[b][x]-v[a][i]);
   if(x){
    x--;
    mi=min(mi,v[a][i]-v[b][x]);
   }
  }
  cout<<mi<< '\n';
  if(a>b) swap(a,b);
  mp[{a,b}]=mi;
 }
 return 0;
}

沒有留言:

張貼留言