作法：
一開始大概可以先想到奇偶性的問題：如果走了 $i$ 步停在 $( x , y )$ ，那麼 $i$ 和 $x + y$ 的奇偶性一定要一樣，這件事可以先在讀入條件時過濾掉顯然不可能的解。以下把每個指令都看成一個向量（$U$ 就是 $( 0 , 1 )$ ，以此類推），並且記 $S_i$ 為前 $i$ 個指令的向量和，另外記 $S_L = ( p , q )$ 。首先每個條件告訴我們的東西其實是一個等式： $k ( p , q ) + S_i = ( x , y )$ ，其中如果輸入為 $t , x , y$ 的話，那麼上式的 $ k$ 就等於 $\left \lfloor \frac{t}{L} \right \rfloor$ ，$i$ 等於 $t % L$ 。觀察這條式子可以發現，如果確定好 $( p , q )$ 的值時，就代表現在每個條件都變成了 $S_i = ( ?? , ?? )$ 的型式了，此時處理方法就會變得很簡單：把所有的 $S_i$ 按照 $i$ 值由小到大排序，如果相鄰等式的奇偶性沒有滿足的話就無解，或是相鄰兩個等式要求的 $S_i$ 座標的曼哈頓距離太大了(超過兩式的 $S$ 的下標差值)就無解，反之可以簡單的構造出一組解（先一堆 $U/D$ 再一堆 $R/L$ ，如果還有多的步數就一直加 $LR$ 之類的）。而由上面的處理方法可以反過來得到 $p , q$ 的限制條件，具體來說，首先把所有的等式都改寫成 $S_i = ( a \cdot p + b , c \cdot p + d )$ 這種樣子( 其中$ a = c = -k , b = x , d = y$ )，所以可以用 $5$ 個變數$( i , a , b , c , d )$來代表一個等式(當然 $4$ 個也可以，因為 $a = c$ ，不過我覺得用 $5$ 個比較直觀)。把所有的等式按照 $i$ 由小到大排序，不過還要注意到在這之前還得加上兩個潛在的條件：$S_0 = ( 0 \cdot p + 0 , 0 \cdot q + 0 )$ ，還有 $S_L = ( 1 \cdot p + 0 , 1 \cdot q + 0 )$ 。將等式們排序後，看兩條相鄰的等式 $S_i $和 $S_j$ ，假設他們的$4$個係數分別為$ a1 , b1 , c1 , d1$ 和 $a2 , b2 , c2 , d2$ ，那麼這樣就得到了一個條件：$| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq | j - i |$ ，更一般的可以寫成 $| a \cdot p + b | + | c \cdot q + d | \leq e$ ，也就是現在我們獲得了很多這樣子的關於 $p$ 和 $q$ 的限制條件，要找出一組可能的 $( p , q )$ 或是輸出無解。（對了，如果相鄰兩等式的 $a$ 值一樣的話，條件就會變成 $| b | + | d | \leq e$ ，這個可以直接判掉，所以之後可以不用考慮條件中 $a=0$ 或 $c=0$ 的情形。）
如果考慮對某一個限制條件枚舉 $p$ 的話，顯然 $p$ 要滿足 $| a \cdot p + b | \leq e$ ，所以可以先解出 $p$ 的範圍。當確定 $p$ 的值時，所有的條件就變成 $| c \cdot q + d | \leq f$ 的型式了，於是只要再對每個條件都跑一次，把所有的 $q$ 要滿足的不等式交集起來就好了，但這樣複雜度會爆掉。不過其實可以發現，因為當 $p$ 變動 1 的時候 $a \cdot p + b$ 會變動 $a$ ，所以滿足 $| a \cdot p + b | \leq e$ 的 $p$ 值大概不會超過 $\frac{2e}{a}$ 個（因為當 $p$ 改變那麼多時 $a \cdot p + b$ 就至少會從 $-e$ 跳到 $e$ 了），也就是我們有 $p$ 要枚舉的個數上限了，但這件事還不夠，因為如果 $e$ 很大的話複雜度還是爆掉的。但是事實上 $e$ 不會總是那麼大！觀察所有條件的 $e$ 值的由來，是由兩個相鄰等式的 $S$ 的下標相減得到的，所以就可以得到所有 $e$ 值的總和 $\leq L$ ，所以我們只要取 $e$ 值最小的那個等式枚舉 $p$ 的值就好了。這樣的話假設共有 $x$ 條等式，那麼 $e$ 的最小值 $\leq L / x$ ，所以這樣子的複雜度就會是 $O( x ) \cdot O( L / x ) = O( L )$ ！就成功解決了這個問題了。類似的梗也出現在 CF 526-E Transmitting Levels。
但這樣傳上去之後爛掉了OAO，後來我發現是因為忘記判斷相鄰兩個等式之間的奇偶條件了......也就是當我們得到一條 $| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq | j - i |$ 這樣的條件時，奇偶性的條件其實就會等價於「左式和右式的奇偶性一樣」。我的解決方法是：因為當在枚舉 $p$ 時會再把所有條件跑過一遍，那麼只要在那時候多回傳「 $q$ 是否可以是奇數」和「 $q$ 是否可以是偶數」這兩件事就好了。另外一個小細節是，我們會需要解形如 $a \leq k \cdot x \leq b$ 的等式，其中 $a , b , k$ 給定，這要把 $a$ 和 $b$ 的正負分開處理才可以，因為「 / 」這個運算子是往 $0$ 的方向捨去的。
code :
#include<bits/stdc++.h> #define LL long long #define ABS(x) ((x)>0 ? (x) : (-(x))) #define INF (1LL<<60) using namespace std; const int maxn=200000+10 ; struct pll{LL x,y;}; pll cal(LL k,LL a,LL b) /// a <= kx <= b --> ? <= x <= ? , k>0 { pll p ; p.x = (a>0 ? (a-1)/k+1 : a/k) ; p.y = (b>=0 ? b/k : (b+1)/k-1) ; return p ; } struct P { int id ; LL a,b,c,d ; bool operator < (const P &rhs) const { return id<rhs.id ; } }p[maxn]; struct cond{LL a,b,c,d,e;}con[maxn] ; int ccnt ; pll get_interval(LL x,int &pa) /// parity , 1 : odd ok , 2 : even ok { pll ret=(pll){-INF,INF} ; pa=3 ; for(int i=0;i<ccnt;i++) { if(con[i].a%2) { int z=((con[i].e-x-con[i].d-con[i].b)%2+2)%2 ; if(z==0 && (pa&1)) pa^=1 ; if(z==1 && (pa&2)) pa^=2 ; } LL val=con[i].e-ABS(x*con[i].a+con[i].b) ; pll tmp=cal(con[i].c,-val-con[i].d,val-con[i].d) ; ret.x=max(ret.x,tmp.x) ; ret.y=min(ret.y,tmp.y) ; } return ret ; } int n,L ; void found_ans(LL x,LL y) { for(int i=0;i<n+1;i++) { if(p[i].id==p[i+1].id) continue ; LL x1=x*p[i].a+p[i].b , y1=y*p[i].c+p[i].d ; LL x2=x*p[i+1].a+p[i+1].b , y2=y*p[i+1].c+p[i+1].d ; LL dx=x2-x1 , dy=y2-y1 , dis=p[i+1].id-p[i].id ; dis-=ABS(dx)+ABS(dy) ; while(dx<0) putchar('L') , dx++ ; while(dx>0) putchar('R') , dx-- ; while(dy<0) putchar('D') , dy++ ; while(dy>0) putchar('U') , dy-- ; while(dis) putchar('L') , putchar('R') , dis-=2 ; } } main() { scanf("%d%d",&n,&L) ; for(int i=1;i<=n;i++) { LL t,x,y ; scanf("%I64d%I64d%I64d",&t,&x,&y) ; if((t+x+y)%2){printf("NO\n") ; return 0 ;} LL u=t/L ; int v=t%L ; p[i]=(P){v,-u,x,-u,y} ; } p[0]=(P){0,0,0,0,0} ; p[n+1]=(P){L,1,0,1,0} ; sort(p,p+n+2) ; for(int i=0;i<n+1;i++) { LL a=p[i].a-p[i+1].a , b=p[i].b-p[i+1].b ; LL c=p[i].c-p[i+1].c , d=p[i].d-p[i+1].d ; if(!a) { if(ABS(b)+ABS(d)>p[i+1].id-p[i].id) {printf("NO\n") ; return 0 ;} continue ; } if(a<0) a=-a , b=-b , c=-c , d=-d ; con[ccnt++]=(cond){a,b,c,d,p[i+1].id-p[i].id} ; } int mi=L+1 , mid ; for(int i=0;i<ccnt;i++) if(con[i].e<mi) mi=con[mid=i].e ; pll tmp=cal(con[mid].a,-con[mid].e-con[mid].b,con[mid].e-con[mid].b) ; for(LL i=tmp.x;i<=tmp.y;i++) { int pa ; pll tmp2=get_interval(i,pa) ; if((tmp2.x%2) && !(pa&1)) tmp2.x++ ; if((tmp2.x%2==0) && !(pa&2)) tmp2.x++ ; if(tmp2.y>=tmp2.x && pa){found_ans(i,tmp2.x) ; return 0 ;} } printf("NO\n") ; }
沒有留言:
張貼留言