2015年6月29日 星期一

[CF 555D] Case of a Top Secret

作法:

首先看要如何模擬,可以把繩子的動作分成兩種,第一種是當前繩子往下垂並且物體正在往右邊移,另一種則是當前繩子是往上的並且物體正在往左邊移。把輸入的座標排序就可以用 lower_bound / upper_bound 找出繩子接下來會繞誰轉,就可以模擬了。但直接做會TLE,首先觀察到我們可以先把繩子的長度縮減到比$a[n]-a[1]$還短,其中$a[1],...,a[n]$代表已排序後的釘子座標。接下來考慮模擬時要如何優化,設當前繩子繞著$a[i]$轉,並且是前面所述的第一種狀態,如果他是由第二種狀態轉移過來的,那麼顯然會滿足$a[i]-a[i-1]>L$,其中$L$為當前繩子長度。首先求出他之後會繞著$a[x]$轉,那麼他的長度就會變為$L-(a[x]-a[i])$。如果每次長度都減少了一半以上,那麼模擬的次數就會變成$O(logL)$,會是好的。但如果在這次$L$的長度沒有減少一半以上,那麼不難發現再繞完$x$旋轉的下一步會再去繞$i$旋轉,重複繞這兩個點旋轉直到$L$小於他們之間的距離為止,因此我們可以直接把$L$的長度縮減成$L\% (a[x]-a[i])$,並由他們的商來判斷此時是繞$i$轉還是繞$x$轉。由於此時$(a[x]-a[i])<\frac{L}{2}$,所以$L$也會至少砍半,而對於第二種狀態作法也幾乎一樣,因此這樣就得到了單次詢問$O(lognlogL)$的算法了。

code :



#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
#define LL long long
using namespace std;
const int maxn=200000+10 ;
 
pii p[maxn] ;
int a[maxn],idx[maxn],mp[maxn] ;
main()
{
    int n,Q ; scanf("%d%d",&n,&Q) ;
    for(int i=1;i<=n;i++) scanf("%d",&p[i].F) , p[i].S=i ;
    sort(p+1,p+n+1) ;
    for(int i=1;i<=n;i++) a[i]=p[i].F , idx[i]=p[i].S , mp[p[i].S]=i ;
    while(Q--)
    {
        int x,l,type=1 ; scanf("%d%d",&x,&l) ;
        if(n==1){printf("1\n") ; continue ;}
        x=mp[x] ;
 
        int id=upper_bound(a+1,a+n+1,a[x]+l)-a-1 ;
        l-=a[id]-a[x] ;
        x=id ; type=2 ;
 
        if(l>=a[n]-a[1])
        {
            int q=l/(a[n]-a[1]) ;
            if(q%2) x=1 , type=1 ;
            else x=n , type=2 ;
            l-=q*(a[n]-a[1]) ;
        }
        while(l)
        {
            if(type==1)
            {
                id=upper_bound(a+1,a+n+1,a[x]+l)-a-1 ;
                if(id==x || a[id]==a[x]+l){x=id ; break ;}
                if(a[id]-a[x]>=l/2)
                {
                    l-=(a[id]-a[x]) ;
                    x=id ; type=2 ;
                    continue ;
                }
                int tmp=a[id]-a[x] , q=l/tmp ;
                if(q%2) x=id , type=2 , l-=q*tmp ;
                else l-=q*tmp ;
            }
            else
            {
                id=lower_bound(a+1,a+n+1,a[x]-l)-a ;
                if(id==x || a[id]==a[x]-l){x=id ; break ;}
                if(a[x]-a[id]>=l/2)
                {
                    l-=(a[x]-a[id]) ;
                    x=id ; type=1 ;
                    continue ;
                }
                int tmp=(a[x]-a[id]) , q=l/tmp ;
                if(q%2) x=id , type=1 , l-=q*tmp ;
                else l-=q*tmp ;
            }
        }
        printf("%d\n",idx[x]) ;
    }
}
 

1 則留言:

  1. If you need your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (even if they're dating somebody else now) you gotta watch this video
    right away...

    (VIDEO) Win your ex back with TEXT messages?

    回覆刪除