作法：
首先考慮一個樸素的算法：對於每個$i$，我們知道存在一些以$i$結尾的子字串是滿足題目要求的，那麼對每個子字串來說，都可以用他的長度去更新所有$i$之後的答案（依照這個長度時下一步應該要比$a[i]$大還是小，或是等於）。具體來說，如果有一個$i$結尾的子字串長度為$L$，並且$s[L]$為$<$，那麼就可以用$L+1$去更新$i$以後的值大於$a[i]$的位子的答案。這裡有個非常不顯然的結論，就是其實對於所有$i$結尾的子字串，我們只需要紀錄最長那個的長度就可以了！（證明補在後面），因此就可以用 DP 算出每個位子結尾的最長子序列長度了。具體來說，當算完$dp[i]$時，如果$s[dp[i]]$為$<$，那麼之後如果遇到有某個$>a[i]$的數，都要把他的答案和$dp[i]+1$取 max 。如果是$<$的話也一樣，因此這就可以用一個區間修改加上單點查詢的線段樹來作了。而因為要輸出解，所以在線段樹上會多紀錄說造成這個最大值的 index 是誰。
再來則是證明為什麼紀錄最長的就可以了，假設以$x$結尾有兩個滿足條件的子序列，長度分別是$L$和$l$，其中$L>l$。記兩個子序列的 index 分別為$i_1,...,i_L$和$j_1,...,j_l$（因此有$i_L=j_l=x$），並且不妨設$s[l]$為$<$（當$s[l]$為$=$時證法幾乎一樣，在此省略），並且此時$x$準備要拿$l+1$去更新$y$的答案。令$z=i_l$，如果$a[z]<a[y]$，那麼在我們前面算到$z$的答案時早就已經拿$l+1$去更新$y$的答案了，因此這個情況下長度$l$的這個子字串是完全沒有用的。反之如果$a[z]\geq a[y]$，由$s[l]$為$<$和$x$要拿長度$l$的子字串去更新$y$的答案可以推出$a[x]<a[y]$，所以有$a[z]\geq a[y]>a[x]$，推得$a[z]>a[x]$，因此考慮子序列$a[i_l],...,a[i_L]$，裡面一定存在相鄰的兩項使得左大於右，也就是存在一個 index $i_u$（$l\leq u < L$），滿足$a[i_u]>a[i_{u+1}]$（這也代表了$s[u]$為$>$）。我們取滿足這個條件的最小的$u$，不難發現$a[z]<a[i_u]$，因此有$a[i_u]>a[z]\geq a[y]$，因此當我們在算完$i_u$的答案時，就會拿$u+1$去更新$y$的答案了，所以在這種情況長度為$l$的子序列也是沒有用的，所以就可以直接不紀錄了。
code :
2015年7月15日 星期三
2015年7月11日 星期六
[POI 13 Stage 3] Palindromes
作法：
考慮把兩個不同的字串$S_1,S_2$接起來會形成回文，不妨設$|S_1|\leq |S_2|$，那麼不難推得他是回文的充要條件為：$S_1$是$S_2$的前綴，並且$S_2$的長度為$|S_2|-|S_1|$的前綴也是回文。因此我們可以考慮先建一個 trie ，那麼就可以得出：對每個字串$S$來說，有幾個字串恰好為$S$的長度為$i$的前綴。並且再用 manacher 處理一個字串的子字串是否為回文的詢問就可以了。但直接建 trie 會 MLE ，因為一個 node 存 26 個子節點太浪費了，於是我苦苦的把子節點的紀錄方式改成用 treap 才過，詳細就參考 code 吧。
code :
考慮把兩個不同的字串$S_1,S_2$接起來會形成回文，不妨設$|S_1|\leq |S_2|$，那麼不難推得他是回文的充要條件為：$S_1$是$S_2$的前綴，並且$S_2$的長度為$|S_2|-|S_1|$的前綴也是回文。因此我們可以考慮先建一個 trie ，那麼就可以得出：對每個字串$S$來說，有幾個字串恰好為$S$的長度為$i$的前綴。並且再用 manacher 處理一個字串的子字串是否為回文的詢問就可以了。但直接建 trie 會 MLE ，因為一個 node 存 26 個子節點太浪費了，於是我苦苦的把子節點的紀錄方式改成用 treap 才過，詳細就參考 code 吧。
code :
2015年7月9日 星期四
[POI 12 Stage 2] Template
作法：
首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。
code :
首先求出每個點的 Z value ，假設$L$是一個答案，那就代表如果只看字串中那些 Z value $\geq L$的位子，這些位置的相鄰位置的差不會超過$L$。因此我們就可以考慮由小到大枚舉$L$，維護好當前有哪些位置的 Z value $\geq L$，並維護相鄰位置的差的最大值，用可以用個 set 做到這件事。每次把新的數移除的時候就看看他的左右兩個數，並拿這兩個數的差來更新當前的相鄰位置差的最大值。不過實際上用個 linked list 就可以了，複雜度降為$O(n)$。
code :
[POI 19 Stage 3] Prefixuffix
作法：
假設長度為$L$的前綴後綴為答案，那麼可以知道一定存在一個$k$，使得$S[1,...,k]$和$S[n-k+1,...,n]$長的一模一樣，並且$S[k+1,...,L]$和$S[n-L+1...n-k]$一模一樣（跟題目條件等價）。前面的條件很好檢查，不管是用 hash 還是 Z value 都可以。至於後面那個條件，這時我們需要知道：給定一個$i$，找出最長的長度$L$使得$S[i,...,n+1-i]$這個字串的長$L$的前綴和長$L$的後綴長的一模一樣。也就是我們關心的是位子關於整個字串中點對稱的長的一模一樣的字串。具體來說就是一些$(x,y)$滿足$S[x,...,y]$和$S[n+1-y,...,n+1-x]$長的一模一樣。我們考慮枚舉$(x,y)$數對的中點，那麼可以先二分搜出以某個點為中點的話滿足條件的$(x,y)$最多可以擴展到哪裡（因為有個性質是$(x,y)$滿足的話$(x+1,y-1)$也滿足）。假設我們二分搜出了$(L,R)$這段區間是滿足的，也就是$S[L,...,R]=S[n+1-R,...,n+1-L]$，並且$(L-1,R+1)$不滿足，令$len[i]$代表最大的「滿足$S[i+1,...,n-i]$的長$len[i]$的前綴和長$len[i]$的」的數，那麼這時就要用$R-L+1$去更新$len[L-1]$，$R-L-1$去更新$len[L]$，以此類推直到更新的值$<0$為止。這樣就可以直接往左往右掃得到每個$len$值了，只要當我們收到「把$a$和$x$取 max ，把$a+1$和$x-2$取 max ，...」時在$a$上紀錄$x+2a$的值，並在掃描過程中維護好這個數的值的最大值就可以了。
code :
假設長度為$L$的前綴後綴為答案，那麼可以知道一定存在一個$k$，使得$S[1,...,k]$和$S[n-k+1,...,n]$長的一模一樣，並且$S[k+1,...,L]$和$S[n-L+1...n-k]$一模一樣（跟題目條件等價）。前面的條件很好檢查，不管是用 hash 還是 Z value 都可以。至於後面那個條件，這時我們需要知道：給定一個$i$，找出最長的長度$L$使得$S[i,...,n+1-i]$這個字串的長$L$的前綴和長$L$的後綴長的一模一樣。也就是我們關心的是位子關於整個字串中點對稱的長的一模一樣的字串。具體來說就是一些$(x,y)$滿足$S[x,...,y]$和$S[n+1-y,...,n+1-x]$長的一模一樣。我們考慮枚舉$(x,y)$數對的中點，那麼可以先二分搜出以某個點為中點的話滿足條件的$(x,y)$最多可以擴展到哪裡（因為有個性質是$(x,y)$滿足的話$(x+1,y-1)$也滿足）。假設我們二分搜出了$(L,R)$這段區間是滿足的，也就是$S[L,...,R]=S[n+1-R,...,n+1-L]$，並且$(L-1,R+1)$不滿足，令$len[i]$代表最大的「滿足$S[i+1,...,n-i]$的長$len[i]$的前綴和長$len[i]$的」的數，那麼這時就要用$R-L+1$去更新$len[L-1]$，$R-L-1$去更新$len[L]$，以此類推直到更新的值$<0$為止。這樣就可以直接往左往右掃得到每個$len$值了，只要當我們收到「把$a$和$x$取 max ，把$a+1$和$x-2$取 max ，...」時在$a$上紀錄$x+2a$的值，並在掃描過程中維護好這個數的值的最大值就可以了。
code :
2015年7月8日 星期三
[POI 19 Stage 2] A Horrible Poem
作法：
考慮枚舉所求子字串的長度$L$，我們知道$L$是給定子字串長度的因數，所以可以只枚舉其因數就可以了。確定$L$之後，假設詢問的區間為$[x,y]$，那麼判斷這個$L$是否可以的方法就只要看$[x,y-L]$和$[x+L,y]$這兩個字串是否一模一樣就可以了，證明並不難。而只要用 hash 就可以$O(1)$判斷了，因此就得到了一個$O(logn)$的解。但這樣傳上去 TLE 了，而只要再注意到：假設詢問的區間中有$x_1$個$a$，那麼分的塊數也一定要是$x_1$的因數，這樣就又縮減一些可能性了。因此我們變成枚舉切的塊數，所有的可能會是某個數的因數，直接用$O(\sqrt{n})$的找因數方法就可以了。
code :
考慮枚舉所求子字串的長度$L$，我們知道$L$是給定子字串長度的因數，所以可以只枚舉其因數就可以了。確定$L$之後，假設詢問的區間為$[x,y]$，那麼判斷這個$L$是否可以的方法就只要看$[x,y-L]$和$[x+L,y]$這兩個字串是否一模一樣就可以了，證明並不難。而只要用 hash 就可以$O(1)$判斷了，因此就得到了一個$O(logn)$的解。但這樣傳上去 TLE 了，而只要再注意到：假設詢問的區間中有$x_1$個$a$，那麼分的塊數也一定要是$x_1$的因數，這樣就又縮減一些可能性了。因此我們變成枚舉切的塊數，所有的可能會是某個數的因數，直接用$O(\sqrt{n})$的找因數方法就可以了。
code :
2015年4月6日 星期一
[POI 18 Stage 3] Meteors
作法：
這題是整體二分的經典題。具體作法是：我們使用BIT作區間加減值和單點查詢的操作，這樣可以在 O( A_i * logm ) 的時間中求出一個人目錢賺到的錢有多少。並且我們遞回處理的問題是：對於 [ L , R ] ，已知有一個 vector 裡面放的人們的答案都落在 [ L , R ] 裡面，求出這些人的確切答案。當 L = R 的時候當然 vector 裡面的人們的答案都是 L ，而如果不是的話，令 mid = ( L + R ) / 2 ，這時後把 BIT 調整到已經進行的操作只有第 1 ~ mid 個，然後把這時候已經達到目標的人丟進一個 vector ，因為他們的答案區間就會是 [ L , mid ] ，而還沒達到目標的就丟進另一個，他們的答案區間會是 [ mid+1 , R ] ，遞回下去處理即可。
另外，要記得開 unsigned long long =ㄦ= 真是太陰險了。
感覺我沒講的很清楚，還是看看 code 吧，應該蠻好懂的。
code :
這題是整體二分的經典題。具體作法是：我們使用BIT作區間加減值和單點查詢的操作，這樣可以在 O( A_i * logm ) 的時間中求出一個人目錢賺到的錢有多少。並且我們遞回處理的問題是：對於 [ L , R ] ，已知有一個 vector 裡面放的人們的答案都落在 [ L , R ] 裡面，求出這些人的確切答案。當 L = R 的時候當然 vector 裡面的人們的答案都是 L ，而如果不是的話，令 mid = ( L + R ) / 2 ，這時後把 BIT 調整到已經進行的操作只有第 1 ~ mid 個，然後把這時候已經達到目標的人丟進一個 vector ，因為他們的答案區間就會是 [ L , mid ] ，而還沒達到目標的就丟進另一個，他們的答案區間會是 [ mid+1 , R ] ，遞回下去處理即可。
另外，要記得開 unsigned long long =ㄦ= 真是太陰險了。
感覺我沒講的很清楚，還是看看 code 吧，應該蠻好懂的。
code :
#include<bits/stdc++.h> #define LL unsigned long long #define lowbit(x) (x&(-x)) using namespace std; const int maxn=300000+10 ; LL bit[maxn] ; void add(int l,int r,LL val) { r++ ; while(l<maxn) bit[l]+=val , l+=lowbit(l) ; while(r<maxn) bit[r]-=val , r+=lowbit(r) ; } LL query(int x) { LL ret=0LL ; while(x) ret+=bit[x] , x-=lowbit(x) ; return ret ; } LL query(const vector<int> &v) { LL ret=0LL ; for(int i=0;i<v.size();i++) ret+=query(v[i]) ; return ret ; } struct P{ int l,r ; LL val; }q[maxn] ; int n,m,nowq=0 ; void adjust(int newq) { while(nowq < newq) { int x=++nowq ; if(q[x].l <= q[x].r) add(q[x].l,q[x].r,q[x].val) ; else add(q[x].l,m,q[x].val) , add(1,q[x].r,q[x].val) ; } while(nowq > newq) { int x=nowq-- ; if(q[x].l <= q[x].r) add(q[x].l,q[x].r,-q[x].val) ; else add(q[x].l,m,-q[x].val) , add(1,q[x].r,-q[x].val) ; } } vector<int> peo[maxn],G[4*maxn] ; int gid ; int ans[maxn] ; LL goal[maxn] ; void solve(const vector<int> &v,int l,int r) { if(l==r) { for(int i=0;i<v.size();i++) ans[v[i]]=l ; return ; } if(v.empty()) return ; int mid=(l+r)/2 ; adjust(mid) ; for(int i=0;i<v.size();i++) { if( query(peo[v[i]]) >= goal[v[i]] ) G[gid].push_back(v[i]) ; else G[gid+1].push_back(v[i]) ; } int tmp=gid ; gid+=2 ; solve(G[tmp],l,mid) ; solve(G[tmp+1],mid+1,r) ; } main() { scanf("%d%d",&n,&m) ; for(int i=1;i<=m;i++) { int x ; scanf("%d",&x) ; peo[x].push_back(i) ; } for(int i=1;i<=n;i++) scanf("%llu",&goal[i]) ; int Q ; scanf("%d",&Q) ; for(int i=1;i<=Q;i++) scanf("%d%d%llu",&q[i].l,&q[i].r,&q[i].val) ; for(int i=1;i<=n;i++) G[0].push_back(i) ; gid=1 ; solve(G[0],1,Q+1) ; for(int i=1;i<=n;i++) { if(ans[i]==Q+1) printf("NIE\n") ; else printf("%d\n",ans[i]) ; } }
[POI 18 Stage 3] Sticks
作法：
如果三角形的三邊長裡面，最大的數確定了，那麼剩下的兩個數必定越大越好。所以只要考慮枚舉每一個數當最大的數，然後找出其他顏色裡小於等於這個數的最大數，對於取出來的數字最大的前兩種顏色拿去和目前枚舉到的這個最大邊檢驗即可。
code :
如果三角形的三邊長裡面，最大的數確定了，那麼剩下的兩個數必定越大越好。所以只要考慮枚舉每一個數當最大的數，然後找出其他顏色裡小於等於這個數的最大數，對於取出來的數字最大的前兩種顏色拿去和目前枚舉到的這個最大邊檢驗即可。
code :
#include<bits/stdc++.h> using namespace std; const int maxn=50+10 ; int get(int x,const vector<int> &v) { int id=upper_bound(v.begin(),v.end(),x)-v.begin()-1 ; return id==-1 ? -1 : v[id] ; } vector<int> v[maxn] ; main() { int n ; scanf("%d",&n) ; for(int i=1;i<=n;i++) { int m ; scanf("%d",&m) ; while(m--) { int x ; scanf("%d",&x) ; v[i].push_back(x) ; } sort(v[i].begin(),v[i].end()) ; } for(int i=1;i<=n;i++) for(int j=0;j<v[i].size();j++) { int x=v[i][j] , m1=-1 , m2=-1 , id1 , id2 ; for(int i2=1;i2<=n;i2++) if(i2!=i) { int tmp=get(x,v[i2]) ; if(tmp>=m1) m2=m1 , m1=tmp , id2=id1 , id1=i2 ; else if(tmp>=m2) m2=tmp , id2=i2 ; } if(m1+m2>x) { printf("%d %d %d %d %d %d\n",i,x,id1,m1,id2,m2) ; return 0 ; } } printf("NIE\n") ; }
2015年4月5日 星期日
[HOJ 158][POI 18 Stage 2] Strongbox
這題我之前在HOJ上就AC過了( 作法在這裡 )，但一樣的 code 丟到 main 上 TLE 了，應該是 main 的主機跑太慢了，所以只好弄個另解=ㄦ=
作法：
參考了這篇的 code 。
由我之前打的那篇可知， d 整除 a_k 和 n ，並且不整除 a_1 ~ a_( k-1 ) 。也就是 d 整除 gcd ( a_k , n ) ，所以我們可以先把 a_k 改成 gcd( a_k , n ) ，不會影響答案。再來則是 d 不整除 a_1 ~ a_( k-1 ) 的條件，如果 a_i 有個質因數 p ，他不整除 a_k ，那麼 d 不整除 a_i 若且唯若 d 不整除 a_i / p ，也就是我們可以把每個 a_i 裡面和 a_k 不相干的部分都砍掉，也就是把 a_i 全部改成 gcd( a_i , a_k ) ，這樣也不會影響答案。
這時候問題就轉化為：現在有一個集合 S ，裡面包含了 a_k 的因數，但不包含 a_1 ~ a_( k-1 ) 的因數，求裡面最小的數 ( 也就是 d )是多少。這裡先介紹兩種找一個數的所有因數的方法，等等兩種都會用到。
假設現在要找 n 的所有因數，第一種就是直接從 1 枚舉到 sqrt( n ) ，如果 n 整除 i 那麼 i 和 n/i 都是 n 的因數，並且這樣不會遺漏。另外一種則是先求出 n 的標準分解式，假設為 p_1 ^ a_1 * p_2 ^ a_2 * ... * p_r ^ a_r ，那麼 n 的所有因數就型如 p_1 ^ b_1 * p_2 ^ b_2 * ... * p_r ^ b_r ，其中 0 <= b_i <= a_i ，所以我們可以對陣列 a_1 ~ a_r 作DFS，枚舉 p_i 要取幾個，就可以得到所有的因數。
回到原題，首先考慮這樣的一個算法：找出 a_1 ~ a_( k-1 ) 每個數的所有因數，把他們都丟進一個 set 裡，最後用第一種方法枚舉 a_k 的因數。但這樣在一開始就太慢了，因為在找出 a_1 ~ a_( k-1 ) 每個數的所有因數時會算到很多重複的數。不過我們知道 a_1 ~ a_( k-1 ) 全部都會是 a_k 的因數 ( 剛剛取過 gcd 了 )，也就是 a_1 ~ a_( k-1 ) 每個數字的樣子都是確定的( 質因數組成確定，但質因數的次方不確定 )，所以我們可以直接對 a_k 套用第二種找因數的方法，當找到了一個 a_k 的因數 u ，並且 u 出現在 a_1 ~ a_( k-1 ) 裡時，我們就知道 u 的每個質因數的次方是多少了，這時候就可以再用另外一個 dfs 找出所有 u 的因數並把它標記刪除了。但這樣還是有很多數被重複算到了，而這裡只需注意到，當 x 被刪除時，代表他的因數也全部都被刪除了，所以當第二次收到「刪除 x 」的指令時就可以不理他了，而這可以用一個 set 來維護，裡面存哪些數字已經被刪掉了。這樣就可以保證每個數頂多被刪除一次。最後再使用第一種找因數的方法，枚舉 a_k 的因數，如果遇到一個因數還沒被刪除，就把它拿去更新答案即可。
code :
作法：
參考了這篇的 code 。
由我之前打的那篇可知， d 整除 a_k 和 n ，並且不整除 a_1 ~ a_( k-1 ) 。也就是 d 整除 gcd ( a_k , n ) ，所以我們可以先把 a_k 改成 gcd( a_k , n ) ，不會影響答案。再來則是 d 不整除 a_1 ~ a_( k-1 ) 的條件，如果 a_i 有個質因數 p ，他不整除 a_k ，那麼 d 不整除 a_i 若且唯若 d 不整除 a_i / p ，也就是我們可以把每個 a_i 裡面和 a_k 不相干的部分都砍掉，也就是把 a_i 全部改成 gcd( a_i , a_k ) ，這樣也不會影響答案。
這時候問題就轉化為：現在有一個集合 S ，裡面包含了 a_k 的因數，但不包含 a_1 ~ a_( k-1 ) 的因數，求裡面最小的數 ( 也就是 d )是多少。這裡先介紹兩種找一個數的所有因數的方法，等等兩種都會用到。
假設現在要找 n 的所有因數，第一種就是直接從 1 枚舉到 sqrt( n ) ，如果 n 整除 i 那麼 i 和 n/i 都是 n 的因數，並且這樣不會遺漏。另外一種則是先求出 n 的標準分解式，假設為 p_1 ^ a_1 * p_2 ^ a_2 * ... * p_r ^ a_r ，那麼 n 的所有因數就型如 p_1 ^ b_1 * p_2 ^ b_2 * ... * p_r ^ b_r ，其中 0 <= b_i <= a_i ，所以我們可以對陣列 a_1 ~ a_r 作DFS，枚舉 p_i 要取幾個，就可以得到所有的因數。
回到原題，首先考慮這樣的一個算法：找出 a_1 ~ a_( k-1 ) 每個數的所有因數，把他們都丟進一個 set 裡，最後用第一種方法枚舉 a_k 的因數。但這樣在一開始就太慢了，因為在找出 a_1 ~ a_( k-1 ) 每個數的所有因數時會算到很多重複的數。不過我們知道 a_1 ~ a_( k-1 ) 全部都會是 a_k 的因數 ( 剛剛取過 gcd 了 )，也就是 a_1 ~ a_( k-1 ) 每個數字的樣子都是確定的( 質因數組成確定，但質因數的次方不確定 )，所以我們可以直接對 a_k 套用第二種找因數的方法，當找到了一個 a_k 的因數 u ，並且 u 出現在 a_1 ~ a_( k-1 ) 裡時，我們就知道 u 的每個質因數的次方是多少了，這時候就可以再用另外一個 dfs 找出所有 u 的因數並把它標記刪除了。但這樣還是有很多數被重複算到了，而這裡只需注意到，當 x 被刪除時，代表他的因數也全部都被刪除了，所以當第二次收到「刪除 x 」的指令時就可以不理他了，而這可以用一個 set 來維護，裡面存哪些數字已經被刪掉了。這樣就可以保證每個數頂多被刪除一次。最後再使用第一種找因數的方法，枚舉 a_k 的因數，如果遇到一個因數還沒被刪除，就把它拿去更新答案即可。
code :
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=250000+10 ; LL getll() { char c=getchar() ; while(c<'0'||c>'9') c=getchar() ; LL x=0 ; while(1) { x=x*10+c-'0' ; c=getchar() ; if(c<'0'||c>'9') return x ; } } LL a[maxn] ; set<LL> st,del ; int cnt=0,num[maxn],num2[maxn] ; LL p[maxn] ; void DEL(int x,LL now) { if(x==cnt) { del.insert(now) ; return ; } if(del.find(now)!=del.end()) return ; DEL(x+1,now) ; for(int i=1;i<=num2[x];i++) { now/=p[x] ; DEL(x+1,now) ; } } void dfs(int x,LL now) { if(x==cnt) { if(st.find(now)!=st.end()) DEL(0,now) ; return ; } if(del.find(now)!=del.end()) return ; dfs(x+1,now) ; for(int i=1;i<=num[x];i++) { now/=p[x] ; num2[x]-- ; dfs(x+1,now) ; } num2[x]=num[x] ; } main() { LL n ; int m ; scanf("%lld%d",&n,&m) ; for(int i=1;i<=m;i++) a[i]=getll() ; a[m]=__gcd(a[m],n) ; for(int i=1;i<m;i++) st.insert(__gcd(a[i],a[m])) ; int sq=(int)sqrtl(a[m]+0.5) ; LL tmp=a[m] ; for(int i=2;i<=sq && i<tmp;i++) if(tmp%i==0) { p[cnt]=i ; num[cnt]=0 ; while(tmp%i==0) num[cnt]++ , tmp/=i ; num2[cnt]=num[cnt] ; cnt++ ; } if(tmp!=1) p[cnt]=tmp , num[cnt]=num2[cnt]=1 , cnt++ ; dfs(0,a[m]) ; LL ans=0LL ; for(int i=1;i<=sq;i++) if(a[m]%i==0) { if(del.find(i)==del.end()) ans=max(ans,n/i) ; if(del.find(a[m]/i)==del.end()) ans=max(ans,n/(a[m]/i)) ; } printf("%lld\n",ans) ; }
[POI 18 Stage 2] Tree Rotations
作法：
對於一個非葉節點，把這個節點的兩個子樹交換的話，會讓逆序數對改變的其實只有「兩個子樹內的形成的逆序數對」數量，也就是「滿足 x 屬於 T1， y 屬於 T2 ，並且 x > y 的二元組 ( x , y )」 數量( 記為 M )，其中 T1 和 T2 代表個節點的兩個子樹。而這兩個子樹形成的總數對數量是 size( T1 ) * size( T2 ) ( 記為 N )，所以這個節點的答案就會是兩個子節點的答案再加上 min ( M , N-M ) 。而在計算 M 的數量的時候，我們需要一個可以查詢一個數在某陀集合裡面大於幾個數的資料結構，所以會用到 treap 。並且我們還需要合併兩個 treap ，用啟發式合併即可。
因為 treap 懶得自己寫，於是借用了這裡的模板XD。
code :
對於一個非葉節點，把這個節點的兩個子樹交換的話，會讓逆序數對改變的其實只有「兩個子樹內的形成的逆序數對」數量，也就是「滿足 x 屬於 T1， y 屬於 T2 ，並且 x > y 的二元組 ( x , y )」 數量( 記為 M )，其中 T1 和 T2 代表個節點的兩個子樹。而這兩個子樹形成的總數對數量是 size( T1 ) * size( T2 ) ( 記為 N )，所以這個節點的答案就會是兩個子節點的答案再加上 min ( M , N-M ) 。而在計算 M 的數量的時候，我們需要一個可以查詢一個數在某陀集合裡面大於幾個數的資料結構，所以會用到 treap 。並且我們還需要合併兩個 treap ，用啟發式合併即可。
因為 treap 懶得自己寫，於是借用了這裡的模板XD。
code :
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=200000+10 ; typedef int type; struct node{ node *l,*r; int fix,size; type data; node(){ l=r=NULL; fix=rand(); size=1; } int lsize(){return l?l->size:0;} int rsize(){return r?r->size:0;} }; struct treap{ node *root; treap(){ root=NULL; } int size() { return root ? root->size : 0 ; } inline void left_rotate(node *&a){ node *b=a->r; a->r=b->l; b->l=a; a=b; b=a->l; b->size=b->lsize()+b->rsize()+1; a->size=a->lsize()+a->rsize()+1; } inline void right_rotate(node *&a){ node *b=a->l; a->l=b->r; b->r=a; a=b; b=a->r; b->size=b->lsize()+b->rsize()+1; a->size=a->lsize()+a->rsize()+1; } void insert(node *&p,type data){ if(!p){ p=new node; p->data=data; }else{ p->size++; if(data<p->data){ insert(p->l,data); if(p->l->fix<p->fix)right_rotate(p); }else if(data>p->data){ insert(p->r,data); if(p->r->fix<p->fix)left_rotate(p); } } } inline void insert(type data){ insert(root,data); } int rank(node *p,type data,int cur){ if(!p) return cur ; if(data==p->data)return p->lsize()+cur+1; else if(data<p->data)return rank(p->l,data,cur); else return rank(p->r,data,cur+p->lsize()+1); } inline int rank(type data){ return rank(root,data,0); } }; struct RET{ int id ; LL val ; }; treap s[maxn] ; int scnt=0 ; int tmp[maxn],tcnt ; void dfs(node *u) { if(!u) return ; dfs(u->l) ; tmp[tcnt++]=u->data ; dfs(u->r) ; } RET solve() { int z ; scanf("%d",&z) ; if(z) { s[scnt++].insert(z) ; return (RET){scnt-1,0} ; } RET r1=solve() ; RET r2=solve() ; int x=r1.id , y=r2.id ; RET ret ; ret.val=r1.val + r2.val ; if(s[x].size() < s[y].size()) swap(x,y) ; int i=0 ; LL cnt=0LL , tot=((LL)s[x].size())*((LL)s[y].size()) ; tcnt=0 ; dfs(s[y].root) ; for(int i=0;i<tcnt;i++) cnt+=s[x].rank(tmp[i]) ; ret.val+=min(cnt,tot-cnt) ; for(int i=0;i<tcnt;i++) s[x].insert(tmp[i]) ; ret.id=x ; return ret ; } main() { srand(time(NULL)) ; int n ; scanf("%d",&n) ; RET ans=solve() ; printf("%lld\n",ans.val) ; }
[POI 18 Stage 2] Difference
作法：
首先可以把其中兩種字母抽出來看，這樣可以求出一個答案，而對所有可能的字母組都求一次答案，並且取這些答案的 max 即可，不難證明這樣會是對的。所以現在問題轉化為如何求一個只有兩種字元的字串的答案。假設他們一個是 a 一個是 b 好了，考慮平面上的點集 ( x_i , y_i ) ，其中 x_i 和 y_i 分別代表前 i 個數裡面有幾個 a 和幾個 b ( 就是一個前綴和的概念 )，而我們的目標是要找到 i , j 使得 | ( x_i - x_j ) - ( y_i - y_j ) | 最大，可以改寫成 | ( x_i - y_i ) - ( x_j - y_j ) |，也就是如果記 f ( x , y ) = x - y ，那麼我們想要求的就是 | f ( i ) - f ( j ) | 的最大值。但 i , j 還必須要有個限制，就是不能有 x_i = x_j 或是 y_i = y_j ( 因為這樣會變成 i+1 ~ j 中只有一種字母 )，所以用雙指標，記錄當前合法的 f ( j ) 的最大和最小值，當算到 ( x_i , y_i ) 的時候用所有剛變合法的 f ( j ) 拿去更新最大和最小值，那麼以 ( x_i , y_i ) 為右端點的答案就會是 | f ( i ) - mi | 或是 | f ( i ) - ma | ，其中 mi 和 ma 分別為當前合法 f 值的最小和最大值，對全部取 max 就可以得到答案了。
code :
首先可以把其中兩種字母抽出來看，這樣可以求出一個答案，而對所有可能的字母組都求一次答案，並且取這些答案的 max 即可，不難證明這樣會是對的。所以現在問題轉化為如何求一個只有兩種字元的字串的答案。假設他們一個是 a 一個是 b 好了，考慮平面上的點集 ( x_i , y_i ) ，其中 x_i 和 y_i 分別代表前 i 個數裡面有幾個 a 和幾個 b ( 就是一個前綴和的概念 )，而我們的目標是要找到 i , j 使得 | ( x_i - x_j ) - ( y_i - y_j ) | 最大，可以改寫成 | ( x_i - y_i ) - ( x_j - y_j ) |，也就是如果記 f ( x , y ) = x - y ，那麼我們想要求的就是 | f ( i ) - f ( j ) | 的最大值。但 i , j 還必須要有個限制，就是不能有 x_i = x_j 或是 y_i = y_j ( 因為這樣會變成 i+1 ~ j 中只有一種字母 )，所以用雙指標，記錄當前合法的 f ( j ) 的最大和最小值，當算到 ( x_i , y_i ) 的時候用所有剛變合法的 f ( j ) 拿去更新最大和最小值，那麼以 ( x_i , y_i ) 為右端點的答案就會是 | f ( i ) - mi | 或是 | f ( i ) - ma | ，其中 mi 和 ma 分別為當前合法 f 值的最小和最大值，對全部取 max 就可以得到答案了。
code :
#include<bits/stdc++.h> #define INF 10000000 #define ABS(x) ( (x)>0 ? (x) : (-(x)) ) using namespace std; const int maxn=1000000+10 ; struct P{int x,y;}; P cal(const P &p,int t) { return t==0 ? (P){p.x,p.y+1} : (P){p.x+1,p.y} ; } vector<int> v[26] ; int tmp[maxn] ; int solve(const vector<int> &v1,const vector<int> &v2) { int cnt=0 , j=0 ; for(int i=0;i<v1.size();i++) { while(j<v2.size() && v2[j]<v1[i]) j++ , tmp[cnt++]=1 ; tmp[cnt++]=0 ; } while(j<v2.size()) tmp[cnt++]=1 , j++ ; int ret=0 ; P p={0,0},p2={0,0} ; for(int i=0,j=0 , mi=0,ma=0;i<cnt;i++) { p=cal(p,tmp[i]) ; if(!p.x || !p.y) continue ; while(j<i) { P np2=cal(p2,tmp[j]) ; if(np2.x==p.x || np2.y==p.y) break ; p2=np2 ; mi=min(mi,p2.x-p2.y) ; ma=max(ma,p2.x-p2.y) ; j++ ; } ret=max(ret,ABS(p.x-p.y-mi)) ; ret=max(ret,ABS(p.x-p.y-ma)) ; } return ret ; } char s[maxn] ; main() { int n ; scanf("%d%s",&n,s+1) ; for(int i=1;i<=n;i++) v[s[i]-'a'].push_back(i) ; int ans=0 ; for(int i=0;i<26;i++) if(!v[i].empty()) for(int j=i+1;j<26;j++) if(!v[j].empty()) ans=max(ans,solve(v[i],v[j])) ; printf("%d\n",ans) ; }
[POI 19 Stage 3] Minimalist Security
作法：
首先可以發現，如果一個點的點權確定了，那麼那個點所在的連通快的全部點權也就確定了，所以可以對每個連通塊分開作，再全部加起來得到答案。對於一個連通塊，如果有奇圈的話，那麼會得到所有奇圈上的點的權重都確定了( 想像一下沿路加減加減，最後得到的值會是兩倍的某點點權 )，當然如果加減得到的值是奇數就是無解。在這種情況下，因為已經確定一個點了，所以可以直接 DFS 求出其他所有點的點權，並加到答案裡，而如果在 DFS 的過程中出現矛盾( 這個點的點權太大或太小 ) 那就趕快回 return false 。而如果沒有奇圈只有偶圈的話，因為偶圈必須要滿足沿著圈走加減加減最後會得到0，這也就代表隨便對某一個點賦一個值的話，合法的偶圈可以保證走完一圈更新完點權之後不會矛盾，而不合法的則沒辦法保證，所以只要在DFS的過程中沿路確定點權，如果遇到一個點和自己形成偶圈，並且點權產生矛盾，那就代表無解。
如果把隨便一個點賦值之後在DFS的過程中沒有出現任何矛盾，那麼如果考慮把這個點的點權加上 t ，那麼會得到其他所有點要嘛會 +t ，要嘛會 -t ，而這就等價於每個點是落在這張二部圖的哪個部分(因為此時沒有奇圈)，所以我們可以算出 t 的範圍，並且因為所有點的點權都是一次函數，而我們要maximize / minimize 的數也是對 t 的一次函數，所以我們只要考慮 t 最大和 t 最小的情形即可。如果求出的 t 的範圍會導致 t 不存在，那也代表無解，否則對最小的 t 和最大的 t 代入點權分別進行一次DFS求答案，就可以得到最大和最小所求值了。
code :
首先可以發現，如果一個點的點權確定了，那麼那個點所在的連通快的全部點權也就確定了，所以可以對每個連通塊分開作，再全部加起來得到答案。對於一個連通塊，如果有奇圈的話，那麼會得到所有奇圈上的點的權重都確定了( 想像一下沿路加減加減，最後得到的值會是兩倍的某點點權 )，當然如果加減得到的值是奇數就是無解。在這種情況下，因為已經確定一個點了，所以可以直接 DFS 求出其他所有點的點權，並加到答案裡，而如果在 DFS 的過程中出現矛盾( 這個點的點權太大或太小 ) 那就趕快回 return false 。而如果沒有奇圈只有偶圈的話，因為偶圈必須要滿足沿著圈走加減加減最後會得到0，這也就代表隨便對某一個點賦一個值的話，合法的偶圈可以保證走完一圈更新完點權之後不會矛盾，而不合法的則沒辦法保證，所以只要在DFS的過程中沿路確定點權，如果遇到一個點和自己形成偶圈，並且點權產生矛盾，那就代表無解。
如果把隨便一個點賦值之後在DFS的過程中沒有出現任何矛盾，那麼如果考慮把這個點的點權加上 t ，那麼會得到其他所有點要嘛會 +t ，要嘛會 -t ，而這就等價於每個點是落在這張二部圖的哪個部分(因為此時沒有奇圈)，所以我們可以算出 t 的範圍，並且因為所有點的點權都是一次函數，而我們要maximize / minimize 的數也是對 t 的一次函數，所以我們只要考慮 t 最大和 t 最小的情形即可。如果求出的 t 的範圍會導致 t 不存在，那也代表無解，否則對最小的 t 和最大的 t 代入點權分別進行一次DFS求答案，就可以得到最大和最小所求值了。
code :
#include<bits/stdc++.h> #define LL long long #define INF (1LL<<60) using namespace std; const int maxn=500000+10 ; struct P{int to,d;}; vector<P> v[maxn] ; int num[maxn],vis[maxn],col[maxn] ; LL val[maxn] ; int tmp[maxn],cnt ; void dfs0(int x) { vis[x]=1 ; tmp[cnt++]=x ; for(int i=0;i<v[x].size();i++) if(!vis[v[x][i].to]) dfs0(v[x][i].to) ; } int fa[maxn],fa_d[maxn] ; int dfs1(int x,int c) { col[x]=c ; for(int i=0;i<v[x].size();i++) if(v[x][i].to!=fa[x]) { if(col[v[x][i].to]==-1) { val[v[x][i].to]=v[x][i].d-val[x] ; fa[v[x][i].to]=x ; fa_d[v[x][i].to]=v[x][i].d ; int res=dfs1(v[x][i].to,c^1) ; if(res!=0) return res ; } else if(col[v[x][i].to]!=c) { if(val[v[x][i].to]+val[x]!=v[x][i].d) return -1 ; } else { LL sum=v[x][i].d + fa_d[x] ; for(int j=fa[x],k=-1;j!=v[x][i].to;j=fa[j]) sum+= k*fa_d[j] , k=-k ; if(sum%2) return -1 ; val[x]=sum/2 ; return x ; } } return 0 ; } int dfs2_cnt ; bool dfs2(int x,LL &sum) { if(val[x]<0 || val[x]>num[x]) return 0 ; else sum+=num[x]-val[x] ; vis[x]=dfs2_cnt ; for(int i=0;i<v[x].size();i++) { if(vis[v[x][i].to]==dfs2_cnt) { if(val[v[x][i].to]+val[x]!=v[x][i].d) return 0 ; } else { val[v[x][i].to]=v[x][i].d-val[x] ; if(!dfs2(v[x][i].to,sum)) return 0 ; } } return 1 ; } bool solve(int x,LL &mi,LL &ma) { cnt=0 ; dfs0(x) ; val[x]=0 ; fa[x]=x ; int res=dfs1(x,0) ; if(res==-1) return 0 ; else if(res>0) { mi=ma=0LL ; dfs2_cnt=2 ; if(!dfs2(res,mi)) return 0 ; ma=mi ; return 1 ; } LL tmi=-INF , tma=INF ; for(int i=0;i<cnt;i++) { if(col[tmp[i]]==0) tmi=max(tmi,-val[tmp[i]]) , tma=min(tma,-val[tmp[i]]+num[tmp[i]]) ; else tmi=max(tmi,val[tmp[i]]-num[tmp[i]]) , tma=min(tma,val[tmp[i]]) ; } if(tmi > tma) return 0 ; val[tmp[0]]+= ( col[tmp[0]]==0 ? tmi : -tmi ) ; dfs2_cnt=2 ; mi=0LL ; dfs2(tmp[0],mi) ; val[tmp[0]]-= ( col[tmp[0]]==0 ? tmi : -tmi ) ; val[tmp[0]]+= ( col[tmp[0]]==0 ? tma : -tma ) ; dfs2_cnt=3 ; ma=0LL ; dfs2(tmp[0],ma) ; if(mi>ma) swap(mi,ma) ; return 1 ; } main() { int n,m ; scanf("%d%d",&n,&m) ; for(int i=1;i<=n;i++) scanf("%d",&num[i]) ; while(m--) { int x,y,d ; scanf("%d%d%d",&x,&y,&d) ; v[x].push_back((P){y,d}) ; v[y].push_back((P){x,d}) ; } memset(col,-1,sizeof(col)) ; LL ans1=0LL , ans2=0LL ; for(int i=1;i<=n;i++) if(!vis[i]) { LL mi,ma ; if(!solve(i,mi,ma)) { printf("NIE\n") ; return 0 ; } ans1+=mi ; ans2+=ma ; } printf("%lld %lld\n",ans1,ans2) ; }
訂閱：
文章 (Atom)