2016年3月20日 星期日

[公告]code風景區暫緩更新 (本文將持續更新直到資奧結束)

【IOI2016結束,本文到此為止
「鑽礦遊戲Digging Game 3」請期待~XD】

2016/8/16
競賽結果:http://pcms.ioi2016.ru/
銀牌第二,有點噢但還算不錯www
感謝大家的鼓勵與支持~ ^_^

2016/8/12
比賽實況連結似乎還沒出來
擔心來不及所以先煩請大家多多關注IOI 2016的官網 (http://ioi2016.ru/)
知道實況連結後要記得互相通知哦~
再次提醒比賽時間為8/14和8/16的14:00~19:00(UTC+8台北 (台灣) 時間)
歡迎大家來幫TWN(台灣隊)加油!

2016/8/11
國際資訊奧林匹亞競賽將於俄羅斯的喀山舉行
分成兩天比賽
比賽時間轉成台灣時區後分別是8/14和8/16的14:00~19:00(UTC+8)
歡迎大家來幫TWN(台灣隊)加油!
比賽有實況哦~實況連結代補充

2016/4/27
官方國手名單公布!!!
http://toi.csie.ntnu.edu.tw/news_show.php?ID=92

2016/4/24
目前情況樂觀,感謝路上好友相伴與支持
每次模擬考都有進步,十分感動!
以第二名的成績結訓,十分滿意!
雖然官方國手名單還沒公佈,但應該不會有問題了

鑽礦遊戲Digging Game 3製作決定!
敬請期待~(學電影用語XD)
歡迎隨時關心遊戲開發進度
另外,歡迎提供遊戲背景音樂,不限檔案格式、不限風格
請寄到我的電子信箱(收到後會回信通知):fsps60312@yahoo.com.tw
並附上署名,將在遊戲結束畫面公開感謝您的大恩大德!
鑽礦遊戲Digging Game 2在這裡,請參考~

接下來的國手培訓
還在拿捏時間的分配
寫遊戲和題目的時間要分配多少呢?

名次曲線:6→4→3→2
分數曲線:319→326→473→330 (最後一次滿分400,其他500)
詳細資料


2016/4/17
第三次模擬考幾乎滿分!
名次上升到第三名,和第四名拉了109分的差距!
國手有望,繼續努力維持前四名!
名次曲線:六→四→三
分數曲線:319→326→473
邪惡表格連結

2016/3/28
第二階段選訓營官方名單 (不按照名次排序)
入選了!繼續努力!


2016/3/20
現在正在準備資訊奧林匹亞競賽
將「暫時」降低文章發布頻率
若造成不便,敬請見諒

Surprise!!!

2016年3月12日 星期六

[CodeChef XORSACK]Hououin Kyouma and Xorsack

中文版

The problem source is not easy to find, so the problem link is provided.

Definitions:
"A number set" is a set of numbers, "Number sets" means a lot of sets of numbers
"$bit_{i}$" is the $i$-th $bit$ of a number or $\oplus($elements of a number set$)$ ($\oplus$ is the sign of $XOR$)
"$X_{i}$" is number $X$'s $bit_{i}$ ($X$'s $i$-th $bit$)

One $bit$ by one $bit$, we can try maintain the number sets satisfy current conditions.

But the number of number sets is too large ($2^N$)!
What can we do?
It doesn't matter, we can save these $N$ numbers. (call it $s$, $s$ can represent all $2^N$ number sets)
At least later we still can get all the number sets, by enumerate "to choose or not to choose"(call it "choosing state") of each elements of $s$.

The first step is maintain all the number sets, whose $bit_{1}=K_{1}$.

Suppose that $K_{1}=0$
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has even number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=0$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We can prove that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$ (Why? Maybe you could figure out by yourself :))

So, what we should do is replace $s$ with $\{{elements\ (in\ original\ s),\ whose\ bit_{1}=0},s'\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

What if $K_{1}=1$?
We can know, whether we choose each number (in $s$), whose $bit_{1}=0$, does not matter.
The key point is, how to pick up all the number sets, which has odd number of elements satisfy $bit_{1}=1$. ($bit_{1}$ of all the number sets would $=1$ only if we do this)
Consider all elements (in $s$), whose $bit_{1}=1$, $v_{1},v_{2},v_{3},...,v_{n}$
We just know that $s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$ can exactly represent all number sets that contain even number of elements, whose $bit_{1}=1$
Why not make each number sets, which originally doesn't contain $v_{1}$, contains $v_{1}$,
and make each number sets, which originally contains $v_{1}$, does not contains $v_{1}$?

Therefore, what should we do was just replace $s$ with $\{\{$elements (in original $s$), whose $bit_{1}=0\},s'$ after modify its $v_{1}$'s choosing state$\}$
Then, we can continue to maintain all the number sets, satisfy $(bit_{i}=K_{i},\forall 1\leq i\leq 2)$, $(bit_{i}=K_{i},\forall 1\leq i\leq 3)$..., and so on!

The problem is, how to modify all number sets' $v_{1}$'s choosing state in $s'$?
We can know that choosing the same number twice, has the effect equals to not to choose the number.
Therefore, we just force it to choose an extra number, $v_{1}$.
For implementation, just let $K\oplus v_{1}$! (But I use another variable, $now$, to represent the changes of $K$)

The answer is $No$ if $v_{1}$ does not exist when we need it.
Or there's nothing going wrong until the last $bit$ is considered (That means there are still number sets satisfy the conditions), the answer is $Yes$

Time complexity: $O(31N)$ (My code enumerates $31$ $bit$s)

code:

[CodeChef XORSACK]Hououin Kyouma and Xorsack

English version

這題目不好找,附上題目連結

說明:
$bit_{i}$為某數字或某數字集合$\oplus$起來的數字,它的第$i$個$bit$ ($\oplus$為$XOR$的符號)
$X_{i}$為數字$X$的$bit_{i}$

我們可以嘗試一個$bit$一個$bit$慢慢維護符合目前條件的數字集合們

可是數字集合的數量實在太多了 ($2^N$),該怎麼辦呢?
沒關係,我們先存下這$N$個數字 (稱$s$,$s$代表了這$2^N$種數字集合),這樣至少以後會知道枚舉$s$裡面每個數字的選或不選就可以得到每一種數字集合

第一步就是維護出所有會讓$bit_{1}=K_{1}$的數字集合

假設$K_{1}=0$
我們知道,$s$中$bit_{1}=0$的那些數字選或不選都沒有影響
重點是要怎麼挑出那些包含偶數個$bit_{1}=1$的數字的集合 (因為這樣它們的$bit_{1}$才會$=0$)
考慮$s$中$bit_{1}=1$的數字為$v_{1},v_{2},v_{3},...,v_{n}$
可以證明,$s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$恰可以代表所有選擇偶數個$bit_{1}=1$的數字的集合!(想一想,為甚麼XD)

因此,我們只要將$s$取代成$\{{原本s裡面bit_{1}=0的數字},s'\}$,就可以繼續維護$(bit_{i}=K_{i},\forall 1\leq i\leq 2)$、$(bit_{i}=K_{i},\forall 1\leq i\leq 3)$...的數字集合!

如果$K_{1}=1$呢?
我們知道,$s$中$bit_{1}=0$的那些數字選或不選都沒有影響
重點是要怎麼挑出那些包含奇數個$bit_{1}=1$的數字的集合 (因為這樣它們的$bit_{1}$才會$=1$)
考慮$s$中$bit_{1}=1$的數字為$v_{1},v_{2},v_{3},...,v_{n}$
剛剛我們知道了,$s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$恰可以代表所有選擇偶數個$bit_{1}=1$的數字的集合
那麼,把所有沒選到$v_{1}$的集合改成有選到$v_{1}$,選到$v_{1}$的集合改成沒選到$v_{1}$就好了!

因此,我們只要將$s$取代成$\{\{原本s裡面bit_{1}=0的數字\},修改v_{1}選擇狀態後的s'\}$,就可以繼續維護$(bit_{i}=K_{i},\forall 1\leq i\leq 2)$、$(bit_{i}=K_{i},\forall 1\leq i\leq 3)$...的數字集合!

問題來了,要怎麼修改$s'$中所有集合的$v_{1}$選擇狀態?
我們知道,同一個數字選兩次等於沒選
因此,我們就強迫多選一個數字$v_{1}$,實作上將$K\oplus v_{1}$就好了!(不過我是另外用一個變數$now$來儲存$K$的變化)

當發現需要$v_{1}$它卻不存在時,答案為$No$
否則如果算到最後一個$bit$仍然還沒出錯 (代表還是存在符合條件的數字選擇方案),答案為$Yes$

時間複雜度:$O(31N)$ (枚舉了$31$個$bit$)

code:

[Codeforces 631E]Product Sum

Link

Definitions:
$SUM[i]=\sum_{k=1}^{i}A_{k}$

For each element, $A_{i}$, how does the characteristic of the array change if we move $A_{i}$ to position $j$?
It changes $A_{i}(j-i)+SUM[i]-SUM[j]$!

Enumerate $i$ and $j$, we get an $O(N^{2})$ solution.
How to speed up?

Treat $j$ as coordinate $x$.
Then we can treat $SUM[j]$ as a function $f(x)$, $A_{i}*j+SUM[i]-A_{i}*i$ as a line $ax+b$ ($a=A_{i},b=SUM[i]-A_{i}*i$)

What we should find is $\max\{(ax+b)-f(x)\}$, where $f(x)$ is a fixed function, $ax+b$ is a line depend on which $A_{i}$ we choose.

Now we have a new way to enumerate: $x$
Enumerate $x$, and find the line whose $ax+b$ is maximum.
Actually, we can use $deque$ to maintain the $convex\ hull$ of these lines.
For each $x$, we just find the corresponding point on the $convex\ hull$, $(x,y)$, $y$ is what we want to get (maximum $ax+b$).

On this picture, black straight lines are $ax+b$ we want to pick to form the $convex\ hull$, the green one.

How to build the $convex\ null$?
Well, this is a long story... Learn it!
(keywords: $monotone\ queue$,$slope\ optimization$)
(hints: sort the lines by their slopes, $a$)

By enumerating $x$ in increasing order, we can reach linear time complexity with the help of monotonicity of $x$, get the maximum $ax+b$ for every $x$.
Update maximum $ax+b-SUM[x]$, this is how much we can increase the characteristic of the array.
Initial characteristic of the array is $\sum_{i=1}^{N}A_{i}*i$

Time complexity:$O(N\log N)$ (remember that $sorting$ was required)

p.s. Actually, we can avoid $sorting$ to reach $O(N)$, that is, only allow element move toward one direction, then these $ax+b$ become rays (instead of lines), enumerate $x$ in that directions, and dynamic maintain the $convex\ hull$. Please remenber that it's required to do the same thing on another direction.
p.s. For $O(N)$ implementation, you can see this.

code:

2016年3月10日 星期四

[Codeforces g100520F][ASC 45]Flights

題目敘述
傳code

說明:
$SUM[i]$為城市$i$連出去的道路數字總和

可以注意到首都是和所有城市相連的
所以一定可以讓$SUM[1]$ (首都的數字總和) 最大,有個方法是把數字$(M-N+2)\sim(M)$分配給連到首都的道路

先不用確定$(M-N+2)\sim(M)$要分配給哪些道路
我們可以先把其他城市之間的道路隨便給一個數字
然後算好每個城市 (不包括首都$1$) 連出去的道路數字總和
將這些城市依照目前的道路數字總和排序
假設排序後的城市為$\{c_{1},c_{2},c_{3},...,c_{N-1}\}$

發現了嗎?
對於城市$c_{i}$,將$c_{i}$和首都相連的道路的數字設定成$M-N+1+i$
可以發現,我們可以保證$SUM[c_{i}]<SUM[c_{i+1}]<SUM[1],\forall i\in [1,N-2]$

時間複雜度:$O(M+N\log N)$

code:

[TIOJ 1692]Problem B 道路巡邏問題 [Interactive]

題目敘述

題解:

我們可以先把奇點兩兩再連一條邊
這樣整張圖的每個點都是偶點了!

因此,可以直接利用經典的方法求出一個$Euler\ Circuit$
然後把後來加進去的邊移除 ($Euler\ Circuit$有可能因此斷掉)
答案就是$Euler\ Circuit$斷開成的這幾條路徑了
(圖有沒有連通甚麼的請自行考慮~~~)

時間複雜度:$O(V+E)$

CBD提供了另外一個做法

code:

[Codeforces 651E]Table Compression

Link

For simplicity, let's assume all values are different.
For each row, we can connect edges from cells of larger values to cells of smaller values.
Considering time and memory usage, we only add edges between cells of adjacent values. (So $sorting$ is required)
For each column, we do the same thing.

Therefore, we get a $DAG$ ($Directed\ Acyclic\ Graph$), whose root is the cell of the largest value.
Each cell becomes a node in the graph.
We can know that if there is an edge from $a$ to $b$, the value of $a$ must be larger than $b$
So, the low bound of maximum number in the compressed table is the height of the whole graph.
How to reassign values of each cell?
Let's reassign each cell's (Call the cell $u$) value to the height of the subgraph, whose root is $u$.
Now that the low bound is reached.

How to calculate the height of a subgraph?
Let $DP[u]$ be the height of the subgraph, whose root is $u$.
Then we can conclude the following recursive formula:
$DP[u]=\max(DP[v]+1,v$ is a child node of $u)$
Specially, if $u$ has no child node, $DP[u]=1$
$Memorized\ Search$ can be used to obtain amortized time complexity $O(1)$.

Now it's possible to have pairs of cells of same values.
We can know:
If two cells of same value are on the same horizontal position, or same vertical position
After compression, both cells' values should still be the same.
So we can treat both cells as one single cell. (A single node in the graph)
$Disjoint\ Sets$ can be used to perform the implementation.

Time complexity:$O(NM(\log M+\log N))$ ($sorting$ of $N$ rows and $M$ columns)

code:

2016年3月9日 星期三

[POI 11 Stage 2]The Tournament

題目連結

我們先看看怎麼在時間內找出一個會贏的人

入度為$0$的點嗎?不是,如果整張圖是一個環就GG了
入度為$0$的$SCC$ ($Strongly\ Connected\ Component$) 嗎?
對了,就是它!

可以發現,位於同一個$SCC$內的點,不是全部有可能當冠軍,就是全部不可能當冠軍
因此,我們只須找出哪些$SCC$有可能直接或間接打敗所有其他$SCC$

先不管時間複雜度,我們來構造一個算法找出所有答案
先讓那些入度為$0$的$SCC$加入$queue$裡面,並標記為答案
然後,每次從$queue$弄出一個可能當冠軍的$SCC$ (稱作$u$)
枚舉還沒被標記答案的$SCC$ (稱作$nxt$),只要發現$nxt$可以打敗$u$ (換句話說,$(從u連到nxt的邊數)<(u的大小)*(nxt的大小)$,也就是$u$無法壓倒性勝利$nxt$),那麼$nxt$也可以當冠軍了!
把所有變成新冠軍的$SCC$加入$queue$裡面,並標記為答案

於是我們有了一個$O(N^{2})$的作法
真的是$O(N^{2})$嗎?

跟你說,如果你把還沒被標記答案的$SCC$用$set$來維護
傳上去就$AC$了

然後就會想問為甚麼
為甚麼?

可以發現,在枚舉還沒被標記答案的$SCC$時,只有兩種情況:
1. 當冠軍,從$set$中移除並加入$queue$
2. 被壓倒性勝利惹QAQ,繼續待在$set$裡面

時間複雜度取決於情況2.會發生多少次
可以發現,情況2.發生的次數不會超過圖上邊的數量 (想一想,為甚麼XD) (提示:要壓倒性勝利代表至少有一條從$u$連向$nxt$的邊)

時間複雜度:$O((N+M)+(N\log N+M))$ ($M$是邊數)

code:

2016年3月8日 星期二

[Codeforces g100016B]Command Post (中文:圈地問題) (優化後的code)

這題目不好找,附上題目連結

題解在這裡
性質證明在這裡

可以發現,$A[n][i][i-k]$、$A[n][i][i+N+1+k]$ ($k\geq 0$),矩陣中的這些位置永遠是無意義的狀態
因此,我們可以直接把索引值$\mod N$
也就是,原來的$A[n][i][j]$會變成$A[n][i\mod N][j\mod N]$
特別的,這時$A[n][i][i+N]$會變成$A[n][i][i]$

這樣我們$2000*2000$的矩陣就可以瘦身成$1000*1000$了!
記憶體用量減為$\frac{1}{4}$

時間複雜度:$O(N^{2}\log N\log K)$

code:

[Codeforces g100016B]Command Post (中文:圈地問題)

題目敘述
傳code

建議先將所有觀察站位置複製,變成$2N$個觀察站
處理環狀模型會方便許多

由於最後圍籬會形成一個多邊形,我們先枚舉觀察站位置,並強迫在這個地方蓋觀察站
因此這個位置就一定是多邊形的一個頂點,這樣剩下來的觀察站就有特定順序了 (問題變成非環形),依序給它們編號$1\sim N-1$ (也就是,假設枚舉到第$i$個觀察站,那麼第$j$個觀察站的編號就是$j-i$)

說明:
$G[i]$為編號$i$的觀察站位置所在的角度 (參見原題定義)

先來考慮一個很樸素的$DP$
$DP[n][i]$代表在觀察站位置$1\sim i$選$n$個蓋觀察站 (有個限制是觀察站$i$一定要蓋),對圓心而言所能覆蓋的最大面積 (就是兩兩點間的弦+它們的兩條半徑形成的很多三角形的面積的總和)
因此我們就有以下遞推式:
$DP[n][i]=\max_{j=0}^{i-1}(DP[n-1][j]+\frac{\sin(G[i]-G[j])}{2},G[i]-G[j]\leq\pi)$
邊界條件:
$DP[0][0]=0$

乍看之下很像斜率優化$DP$?
其實不然
因為它無法表示成一條條的直線QAQ

不過這個$DP$有一個性質
令$j_{i}$為第一個$j$使得$DP[n-1][j]+\frac{\sin(G[i]-G[j])}{2}$最大,$G[i]-G[j]\leq\pi$
則我們有$j_{i}\leq j_{i+1}$
限於篇幅,性質證明請看這裡

因此當我們算出$j_{k}$時,同時間也知道了$j_{i}\leq j_{k},\forall i\leq k$和$j_{i}\geq j_{k},\forall i\geq k$

利用這個性質,我們可以按照$n$慢慢遞增的順序計算$DP$
然後對於$DP[l\sim r]$,假設目前知道了$l_{b}\leq j_{l\sim r}\leq r_{b}$
那麼我們可以取$mid=\left\lfloor\frac{l+r}{2}\right\rfloor$,暴力枚舉$l_{b}\sim r_{b}$,算出$j_{mid}$ (因為我們已經知道$l_{b}\leq j_{mid}\leq r_{b}$)
於是
對於$DP[l\sim mid-1]$,我們知道了$l_{b}\leq j_{l\sim mid-1}\leq j_{mid}$
對於$DP[mid+1\sim r]$,我們知道了$j_{mid}\leq j_{mid+1\sim r}\leq r_{b}$
將這兩個子問題遞迴計算即可

可以證明,整體時間複雜度為$O(N\log N)$ (證明略去,但還是建議讀者自行把code打出來並證明一下,不會很難的)
因此算到$n=K$需要$O(KN\log N)$的時間

所以我們得到了$O(KN^{2}\log N)$的算法

當然,這樣還不夠快

可以發現,我們的計算方向是$n$遞增
因此與其每枚舉一個觀察站位置就花$O(KN\log N)$的時間去計算
不如全部的枚舉情況一起算(?)

令$A[n][i][j]$為觀察站$i+1\sim j$中選$n$個時,最大面積是多少 (觀察站$i$和$j$是強迫要選的)
因此,我們有了$A[a+b][i][j]=\max_{k=i+1}^{j-1}(A[a][i][k]+A[b][k][j])$
注意到,這很像矩陣乘法
只是這裡將元素的相乘變成相加,相加變成取最大值
而且利用前述性質的拓展 (請讀者自行思考怎麼拓展性質,不會很困難的),這個特殊的矩陣乘法可以做到$O(N^{2}\log N)$!
或許我們可以利用快速冪(?)

我們可以先算出$A[1]$
利用$A[1]*A[1]$我們可以算出$A[2]$
利用$A[2]*A[2]$我們可以算出$A[4]$
利用$A[4]*A[4]$我們可以算出$A[8]$
......
任何$2$的冪次方都可以藉由$O(\log X)$次矩陣乘法算出來!

非$2$的冪次方怎麼辦呢?
以$19$次方為例
我們可以先用$A[1]$和$A[2]$相乘算出$A[3]$
然後再用$A[3]$和$A[16]$算出$A[19]$!
一般的
把數字轉換成二進位 (例如$19$就是$10011$)
右邊數來第$x$位是$1$就把矩陣乘上$A[2^{x-1}]$
任何冪次方都可以藉由$O(\log X)$次矩陣乘法算出來!

呵呵,我們講到哪裡了?
對啊,這樣把$A[K]$算出來
然後枚舉$i$找出最大的$A[K][i][i+N]$ (因為要完整環繞一圈變成多邊形)
就知道最大面積多少了!

可是題目要我們輸出方案
簡單!(拍桌)
記錄下中間結果再逆推回去就好啦!

時間複雜度:$O(N^{2}\log N\log K)$

p.s.你以為這麼容易嗎?XD
p.s.這份code會MLE (還沒結束?!),我們必須有效利用未使用的儲存空間,將記憶體用量減為$\frac{1}{4}$

code:

[Codeforces g100016B]Command Post (中文:圈地問題) (性質證明)

這題目不好找,附上題目連結

題解在這裡
優化後的code在這裡

先看這張圖
我們要證明的是這張圖代表的情況是不可能發生的
也就是$j_{k}=j>i=j_{k+1}$

由於$DP[k]$是從$DP[j]$轉移過來而不是$DP[i]$
因此$DP[j]+a+b+c+e+h\geq DP[i]+c+d+e+g+h$
同理
由於$DP[k+1]$是從$DP[i]$轉移過來而不是$DP[j]$
因此$DP[i]+g+h+i\geq DP[j]+b+e+f+h+i$

將上式整理一下
我們得到:
$DP[j]+a+b-d-g\geq DP[i]$
$DP[i]\geq DP[j]+b+e+f-g$

$\Rightarrow DP[j]+a+b-d-g\geq DP[j]+b+e+f-g$
$\Rightarrow a-d\geq e+f$
$\Rightarrow a\geq d+e+f$

可以發現,$\triangle a$和$\triangle def$互為$AA$相似
可是$\triangle a$的對應邊卻比$\triangle def$還短
因此我們得到$a<d+e+f$
矛盾,因此假設錯誤
$j_{k}$不可能$>j_{k+1}$

[BZOJ 1096][ZJOI2007]仓库建设

題目敘述

如果想輕鬆看懂這個題解,請先了解如何使用單調隊列優化$DP$以及如何利用單調隊列實現斜率優化

假設$DP[i]$是在第$i$座工廠建設倉庫,第$1\sim i-1$座工廠選擇性建設倉庫的條件之下,保護工廠$1\sim i$的貨物的最小總花費
那麼答案就是$DP[N]$了

我們可以得到以下遞推式:
$DP[i]=\min(DP[j]+\sum_{k=j+1}^{i}(P_{k}(X_{i}-X_{k}))+C_{i},0\leq j<i)$

事實上,如果我們預處理一些前綴和
$PROD[i]=\sum_{k=1}^{i}P_{k}$
$COST[i]=\sum_{k=1}^{i}(P_{k}(X_{N}-X{k}))$

那麼以上遞推式可以變成以下形式:
$DP[i]=\min(DP[j]+(COST[i]-COST[j])-(PROD[i]-PROD[j])(X_{N}-X_{i}),0\leq j<i)$

於是我們得到了一個$O(N^{2})$的作法
當然,這樣還不夠快

將上式整理一下,我們得到:
$DP[i]=\min(-PROD[j]X_{i}+DP[j]-COST[j]+PROD[j]X_{N}+COST[i]-PROD[i]X_{N}+PROD[i]X_{i},0\leq j<i)$

令:
$a=-PROD[j]$
$b=DP[j]-COST[j]+PROD[j]X_{N}$
$c=COST[i]-PROD[i]X_{N}+PROD[i]X_{i}$
$x=X_{i}$

則上式變成$DP[i]=\min(ax+b+c,0\leq j<i)$,其中$c$是只跟$i$有關的數字,可以當作常數
因此問題就變成了給定$x$求$ax+b$的最小值 ($ax+b$在模型上為一條直線)
其中$a$和$b$都只和$j$有關,也就是每個$j$代表一條斜直線

注意到$x$是單調遞增的,斜率$a$隨著$j$變大也有單調性 (單調遞減)

因此可以直接套用單調隊列實現的斜率優化$DP$

時間複雜度:$O(N)$

code:

2016年3月7日 星期一

[UVa 11802]All Your Bases Belong to Us

題目連結

這題問你有幾種進位法,使的$N!$後面有$K$個$0$

假設你已經知道十進位的時候要怎麼算後面幾個$0$
可以發現,當要計算$B$進位時
我們可以先把$B$質因數分解
假設$B$分解後變成$2^{p_{1}}*3^{p_{2}}*5^{p_{3}}*7^{p_{4}}*...$
$N!$分解後變成$2^{q_{1}}*3^{q_{2}}*5^{q_{3}}*7^{q_{4}}*...$
(每個$q_{i}$可在$O(\log N)$的時間內算出來)

那麼$B$進位時$N!$就有$\min_{i=1}^{\infty}\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$個$0$了
別被那個$\infty$嚇到,因為$i$到一個數字以後$p_{i}$就全部都是$0$了,也就是可以忽略

現在題目給你$N$和$K$,問你有幾種$B$
也就是有幾種$B$讓$\min_{i=1}^{\infty}\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor=K$

可以發現,每一項$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都有一個下限$K$,但又不能全部$>K$
換句話說,就是至少要有一個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor=K$,其他的可以是$\geq K$的隨意值

我們可以使用排容原理
算出讓每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都$\geq K$的$B$有幾種
再減掉讓每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都$>K$的$B$有幾種

可以發現每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都是獨立的 (想一想,為甚麼XD)
因此將每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$的合法情況數量乘起來就好 (別忘了$mod$一下)

合法情況數量怎麼算呢?
可以發現$q_{i}$是固定的,我們只需調整$p_{i}$即可
讓$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor\geq K$的最大$p_{i}$就是$\left\lfloor\frac{q_{i}}{K}\right\rfloor$
讓$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor>K$的最大$p_{i}$就是$\left\lfloor\frac{q_{i}}{K+1}\right\rfloor$

答案就是$\prod_{i=1}^{\infty}(\left\lfloor\frac{q_{i}}{K}\right\rfloor+1)-\prod_{i=1}^{\infty}(\left\lfloor\frac{q_{i}}{K+1}\right\rfloor+1)$
一樣,別被那個$\infty$嚇到,只要發現$\left\lfloor\frac{q_{i}}{K}\right\rfloor=0$時直接跳出迴圈即可

這樣會不會超時啊......
題目保證$\frac{N}{K}<500$
因此當質因數枚舉到$\geq 502$時,$q_{i}=\sum_{k=1}^{\infty}\left\lfloor\frac{N}{502^{k}}\right\rfloor<\sum_{k=1}^{\infty}\frac{N}{502^{k}}=\frac{N}{502(1-\frac{1}{502})}=\frac{N}{501}<K$
於是$\left\lfloor\frac{q_{i}}{K}\right\rfloor$就$=0$了

時間複雜度:$O(Q*91\log N)$ ($\leq 500$的質數有$91$個)

code:
#include<cstdio>
#include<cassert>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
LL N,K;
vector<LL>P;
int main()
{
//    freopen("in.txt","r",stdin);
    P.push_back(2LL),P.push_back(3LL);
    for(int i=2,j;;i++)
    {
        P.push_back(P[i-1]);
        do
        {
            P[i]+=2LL;
            for(j=0;P[j]*P[j]<=P[i]&&P[i]%P[j]!=0LL;j++);
        }while(P[i]%P[j]==0LL);
        if(P[i]>=500LL)break;
    }
//    printf("%d\n",(int)P.size());
//    for(const LL &v:P)printf("%lld\n",v);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%lld%lld",&N,&K);
        LL ans1=1LL,ans2=1LL;
        for(int i=0;;i++)
        {
            assert(i<(int)P.size());
            LL power=0LL;
            {LL n=N;while(n)(power+=(n/=P[i]));}
            const LL &up=power/K,&down=power/(K+1LL);
            if(up==0LL)break;
            (ans1*=(up+1LL))%=MOD;
            (ans2*=(down+1LL))%=MOD;
        }
        static int kase=1;
        printf("Case %d: %lld\n",kase++,(ans1-ans2+MOD)%MOD);
    }
    return 0;
}

2016年3月6日 星期日

質數的線性篩法

我們希望每個合數只被篩到一次
可以發現,對於每一個合數$N$
設它的最小質因數為$P$
一定有$\frac{N}{P}\geq P$
而且$P\leq \frac{N}{P}最小的質因數$
因此,我們可以從小到大枚舉$Q$ ($\frac{N}{P}$)
所有$\leq Q最小的質因數$的質數$P$去更新$PQ$
實作上枚舉$P$的時候發現$P$整除$Q$時跳出迴圈即可

code:

[SPOJ COT3]COT3 - Combat on a tree (優化後的code)

請先參考這裡的題解

優化1:
$trie$的新節點從動態宣告改成靜態宣告 ($replacement\ new$)

優化2:
$trie$單字結尾的訊息使用鏈表來儲存,做到$O(1)$合併
原本是用$vector$儲存,啟發式合併做到整體均攤$O(N\log N)$,現在變成了$O(N)$
你覺得這沒有差?
嘿嘿嘿
還是要做這個優化才能卡進時限喔XD

時間複雜度:$O(N\log^{2}N)$

code:

[SPOJ COT3]COT3 - Combat on a tree

題目連結

如果要看懂這個題解,請先了解組合賽局的$SG$函數和$Nim$和的性質

這題的盤面感覺很複雜
不妨先假設所有點都是白色的吧

還是好複雜?
不妨先從一個點來討論吧

一個點的$SG\ value$當然就是$1$囉

然後拓展到兩個點
$SG\ value$變成$2$了

拓展到三個點
如果三個點成鏈狀,$SG\ value$當然就是$3$了
如果是櫻桃形的,$SG\ value$可以照以下方式算出 ($\oplus$是$XOR$的符號)
可以得到$SG\ value=mex\{0,1,1\}=2$

一般的,我們可以用以下方式來算出以任何一個點為根的子樹的$SG\ value$ (注意這裡假設每個點都是白色的)
(之後將通通以這張圖做參考)
注意到選了$4$這個節點之後,整棵樹分裂成了$4$個子遊戲
選了$4$之後整個盤面的$SG\ value$就是這些子遊戲的$SG\ value$的$Nim$和 ($\oplus$)
我們只要枚舉$11$種選擇,就可以算出這個盤面的$SG\ value$
也就是$mex\{選了i之後整個盤面的SG\ value,1\leq i\leq 11\}$

利用記憶化搜索,再加上一些避免重複計算的小技巧,可以做到時間複雜度$O(N^{2})$
很可惜的,這樣當然還不夠好

說明:
子樹$u$為以$u$為根的子樹
$SG(xxx)$為盤面為$xxx$的$SG\ value$

如果現在要算$SG(子樹1)$,而且正在枚舉子樹$4$的點
可以發現,$SG(子樹1選擇8後的盤面)=SG(子樹4選擇8後的盤面)\oplus SG(子樹3)\oplus SG(子樹2)$
因為正在枚舉子樹$4$的點,所以$SG(子樹3)\oplus SG(子樹2)$可以視為常數!

這樣,如果我們用某種資料結構存下計算$SG(子樹4)$時的中間結果 (也就是$SG(子樹4選擇u後的盤面)$)
如果這個資料結構支持在短時間內
1. 將全部資料$\oplus$一個數字
2. 算出全部資料的$mex$
3. 插入一個數字

再套用啟發式合併,就解決了
$copy-on-write$的二元$trie$,搭配懶惰標記,剛好符合所有需求!
實作上並不是那麼的困難,就不細講了
提示:把每個數字轉換成二進位,然後當作$01$字串來看
另外,我的啟發式合併有點隱形,請參考函數Node *Merge(Node *a,Node *b,const int depth)

這樣就做完了嗎?
好像還沒耶

我們假設每個點都是白色的
現在有些點可能是黑色的

其實......仔細想想,那些黑色的點直接忽略就好了
具體實現要用什麼樣的方式忽略
請參考下面的code吧

你認為這份code就可以拿去AC了嗎?
好像還沒耶哈哈
這份code常數過大會導致TLE,優化的方法和code在這裡

時間複雜度:$O(N\log^2N)$

code:

2016年3月5日 星期六

[Codeforces 317D]Game with Powers

題目連結

如果要看懂這個題解,請先了解組合賽局的$SG$函數和$Nim$和的性質

不曉得您有沒有看出,$2$的冪次方組成的數字可以當作是獨立的子遊戲呢?
同理
$3$的冪次方組成的數字也可以當作獨立的子遊戲
$4$的冪次方就不能了,因為$4$已經被歸類在$2$的冪次方
$5$的冪次方可以
$6$的冪次方也可以
......

好像知道了甚麼
我們只要算出這些子遊戲的$SG\ value$,然後$\oplus$起來就好了嘛XD ($\oplus$是$XOR$的符號)
可以發現,如果某個子遊戲裡面只有一個數字,那麼它的$SG\ value$就一定是$1$了
我們只要關心以$2\sim\sqrt{N}$為底的子遊戲,它的$SG\ value$怎麼算就好了

可以發現,每個子遊戲最多包含$30$個數字
而這個遊戲的底數是甚麼並不重要,我們只需關心剩下的數字分別是幾次方
因此,可以簡單地用$bitmask$+離散記憶化搜索 (我使用了$map$) 來計算
可是,這樣還不夠快

可以發現,我們要求$SG\ value$的狀態,表示成$bitmask$永遠是一堆$1$組成
因此,可以先將$2^{1}-1$、$2^{2}-1$、$2^{3}-1$、$2^{4}-1$、...、$2^{30}-1$的答案在本機先算好 (參見// for(int i=0;i<=30;i++)printf("%d %d\n",(1<<i)-1,GetSG((1<<i)-1));),然後直接寫進程式碼就好了

要記得排除$\sqrt{N}\sim N$中已經被算進前面的子遊戲的數字
如果算出來有奇數個數字,就把答案$\oplus 1$
還有
$1$自己也是一個獨立的子遊戲,要再把答案$\oplus 1$

答案為$0$時先手敗,否則先手勝

時間複雜度:$O(\sqrt{N}\log N)$ (經過本機的預計算,$SG\ value$的取得可以當作$O(1)$了)

code:

[Codeforces g100365F][ASC 34]Coins Game

原文題目敘述 (第7頁)
傳code

題目敘述:
桌上擺了N*M個硬幣 (位置從 (1,1) 到 (N,M) ),一開始知道哪些硬幣頭朝上,哪些數字朝上
每一回合必須選一個頭朝上的硬幣 (假設這個硬幣的位置是 (i,j) ),再選個位置 (a,b),其中0<=a<i且0<=b<j,然後把 (a,b)、(a,j)、(i,b)、(i,j) 這四個位置的硬幣都翻轉
注意到,當a=0或b=0的時候,有些要翻轉的位置是不存在的,所以在這些位置的翻轉操作是無效的
當玩到最後每個硬幣都是數字朝上,沒有步可以動了,就輸了

故事背景:
某校的學生餐廳是孳殉懊淋霹啞界聞名的 (以下簡稱學餐)
有時食物吃下去會發現又酸又澀的酒味,然後就知道,又要拉肚子一整天了
還有一次吃高麗菜結果被魚刺卡喉嚨,馬上緊急送醫 (造成食道傷口,還好沒傷到喉嚨)
我們從此對學餐感到恐慌,因此合力爭取到晚餐不吃學餐的權利 (不過預算只有100元,而且午餐還是無法倖免)
然後這是某次培訓時想出來的遊戲
因為需要很多很多的硬幣鋪在桌上,所以想要申請經費補助
但是管經費的說他為了讓我們不吃學餐幫我們墊錢 (100元*4人*21天),郵局帳戶見底了,所以拒絕請求
我們只好寫程式用電腦來模擬這個硬幣遊戲了
後來覺得太無聊,寫了AI來對打
注意到,國手雖然很可憐每天都要被逼著吃學餐,可是他們寫出來的AI都是無懈可擊的
請問誰會贏?
(真實事件改編)
(N<=50,M<=50)

以下是題解

如果要看懂這個題解,請先了解組合賽局的$SG$函數和$Nim$和的性質

首先,每個頭朝上的硬幣可以視為一個獨立的遊戲
提示:想想$Nim$和的性質,翻轉硬幣相當於$XOR$ (還是一頭霧水?請參考這裡)

因此,我們就可以用$O(N^{2}M^{2}\log(NM))$的時間預處理出每個位置的$SG\ value$ (因為我計算$mex$的方法牽涉到排序,其實利用基數排序還可以把$\log$去掉),然後就可以算出整個盤面的$SG\ value$了!

題目要求當先手贏的時候要輸出一種必勝策略
只要用$O(N^{2}M^{2})$的時間枚舉$i$、$j$、$i_{1}$和$j_{1}$,找到一組解讓$SG(i,j)\oplus SG(i_{1},j)\oplus SG(i,j_{1})\oplus SG(i_{1},j_{1})=$整個盤面的$SG\ value$就好了 ($\oplus$是$XOR$的符號)
對了,還有一個條件
你只能考慮一開始的盤面中位置$(i,j)$的硬幣是頭朝上的$(i,j)$

時間複雜度:$O(N^{2}M^{2}\log(NM)+N^{2}M^{2})$

code:

[Codeforces 603C]Lieges of Legendre

題目連結

題目敘述

給你N堆石頭 (原題中的cow) 和數字$K$,我們來玩一個遊戲
操作1:拿掉任一堆的任一顆石頭
操作2:選個$2n$顆石頭的石頭堆,換成$K$個各有$n$顆石頭的石頭堆
不能動就輸了,請問先手勝還是後手勝?

題解

如果要看懂這個題解,請先了解組合賽局的$SG$函數和$Nim$和的性質

可以發現,每堆牛都可以視作獨立的遊戲 (想一想,為甚麼XD)
又可以發現,當$K$是偶數時,可以視作$K=0$,當$K$是奇數時,可以視作$K=1$
因為在算$Nim$和 ($XOR$) 的時候會兩兩對消

我們當然可以使用$O(a_{i})$的記憶化搜索算出每個$a_{i}$的$SG$函數值
也就是code中被註解掉的//int GetSG(const int n)
注意到
因為操作最多兩種,因此$SG$函數值只會在$[0,2]$的範圍內

再來怎麼加速呢?
找規律吧

會發現
當$K\mod 2=0$,$SG(i)=\{0,1,2,0,1,0,1,...\}$,後面皆是$01$循環
當$K\mod 2=1$,$SG(i)=\{0,1,0,1,2,0,2,0,1,...\}$,後面奇數項均為$0$,偶數項均為$1$或$2$

要判斷$K\mod 2=1$時$SG(x)$ ($x\mod 2=0$) 是$1$還是$2$,只要算算看$SG(\frac{x}{2})$是不是$1$即可
這樣複雜度為$O(\log x)$

時間複雜度:$O(\sum_{i=1}^{N}\log a_{i})$

看不懂?可參考Coding Beans的題解

code:

2016年3月4日 星期五

[HDU 4787]GRE Words Revenge

操作有兩種:
1. 學一個單字
2. 讀一篇文章,問你有幾個子字串是背過的單字 (只要位置或長度不同就是不同的子字串)

如果先學完所有單字,然後給要你讀幾篇文章問你答案,可以怎麼做呢?

首先對所有單字建立$AC$自動機,然後讓每篇文章在$AC$自動機裡面轉移
每走到一個點,就把答案加上「沿著失配邊可以走到的單字結尾數量」
可以對「將所有失配邊反向形成的樹」建立樹壓平序列

把樹壓平就是對樹做一次$dfs$,把每個點的進入和離開時間記錄下來即可
這樣任何一棵子樹都可以用一個區間表示了

用線段樹來維護這個樹壓平序列
每個單字結尾相當於把整個子樹都$+1$ (實作上將樹壓平序列對應的區間$+1$),可以使用線段樹的區間修改
「沿著失配邊可以走到的單字結尾數量」相當於樹壓平序列上對應點的值,可以使用線段樹的單點查詢
這樣讓大小$N$的$AC$自動機讀入長度$L$的文章,時間複雜度為$O(L\log N)$

現在,需要動態新增字串 (單字)
可是$AC$自動機的失配邊只能離線建立
怎麼辦呢?

解決方案:
$BIT$ ($Binary\ Indexed\ Tree$) 套$AC$自動機

當新增第$N$個字串時,$BIT$的第$N$個元素就是第$N-lowbit(N)+1$個到第$N$個字串組成的$AC$自動機
讀文章時,$BIT$查詢$\log N$個自動機把答案加起來即可

加字串到$BIT$前需要先判斷這個單字有無背過,否則會重複計算

時間複雜度:$O(10^{5}\log 10^{5}+(5*10^{6})\log^{2}10^{5})$

code:

[POJ 3415]Common Substrings (題解二)

請先參考題解一

上一篇有提到我們讓$B$在$A$的後綴自動機裡面進行轉移時,每走一步就要往失配邊回溯直到$max\_len<K$為止
那我們能不能把這個過程加速呢?

我們可以套用$O(\log N)$尋找$LCA$ ($Lowest\ Common\ Ancestor$) 的思想
考慮使用倍增的方法,我們對於每個點預先算好往失配邊走$1$步、走$2$步、走$4$步、走$8$步......會答案加多少
然後就可以盡量跨大步,同時維持$max\_len>=K$
這樣最多跨$\log\left|A\right|$步,形同在$O(\log\left|A\right|)$的時間複雜度內走完失配邊!
注意,還需要做一些加加減減的小細節才是要求的答案

預處理可以做到$O(\left|A\right|\log\left|A\right|)$
我的作法是先將所有失配邊反向形成的樹建出來,然後用$dfs$的方式以類似$LCA$的預處理方式算出需要的資料

這樣就做完了嗎?
好像還沒耶

注意到這裡的字元集大小是$52$ (題目沒說會全部小寫)!
這樣最多會需要$2*10^{5}*52$的時間和空間來初始化並建立後綴自動機
對這題的時限來說實在太大了

因此必須使用更省時間空間的方案
我自己實作了$list$

時間複雜度:$O(\left|A\right|\log\left|A\right|+\left|B\right|\log\left|A\right|)$

code:

[POJ 3415]Common Substrings (題解一)

這題,我們已經知道在枚舉$B$的前綴$B_{p}$時,如何求出$B_{p}$最長的後綴,使得這個後綴同時也是$A$的子字串
方法就是讓$B$在$A$的後綴自動機裡面轉移,同時維護目前答案的長度 (稱作$len$)

那要怎麼求出節點$u$代表的最長字串在$A$裡面出現幾個地方呢?
就是「代表$A$的前綴的節點集合」中,有幾個可以直接或間接透過失配邊走到$u$囉~

這些資訊可以利用$queue$先進行預處理,我們得到一個儲存答案的陣列$count$

於是在$B$進行轉移時,我們每走一步,就將目前找到的最長屬於$A$子字串的後綴$S$,沿著失配邊枚舉$S$的後綴集合,然後把它們在$A$中出現的次數全部加進答案裡面
實作上可以將沿著失配邊走的路徑上的每個節點的$count$乘上一個權重,再加起來
權重就是這個節點代表的字串集合中有幾個長度$\geq K$且$\leq \left|S\right|$,透過$len$和每個節點的$max\_len$資訊可以$O(1)$計算出來

這篇先講到這裡,並給出實現目前算法的code
下一篇說明怎麼讓時間複雜度再降低

時間複雜度:$O(\left|A\right|+\left|A\right|\left|B\right|)$

code:

[公告]code風景區瀏覽量破五千囉!

非常感謝大家的支持,讓code風景區自1/7開站以來瀏覽量首度破五千!
為了讓以後的文章更好,有任何改善建議請隨時留言或寄信給小莫,小莫會盡量在短時間內立即回覆並試用!

相信code風景區的進步,大家有目共睹
從引入latex語法 (感謝CBD)、字體調整、版面和文章結構、時間複雜度分析、圖片輔助說明 (感謝教室白板)、code中加入註解 (感謝程式設計社學長)、......
對code風景區來說都是一大躍進!

因為有你們,code風景區才能變得更好

請踴躍留言
請踴躍留言
請踴躍留言

因為很重要所以說三次

另外,小莫還發現一件事,不藏私地告訴大家:
將「code風景區設為首頁,連結到各大OJ都方便!
真的是這樣啦不騙你XD
不然至少也加進我的最愛列嘛www (然後那些OJ的連結就可以全部刪掉了(?) )

對了
如果覺得「code風景區」同時有英文和中文,輸入不方便的話
現在Google搜尋「code scenic」也可以找到「code風景區囉~

Email:fsps60312@yahoo.com.tw

以下為code風景區瀏覽量破五千時的網頁畫面:

2016年3月3日 星期四

[Codeforces 547E]Mike and Friends

如果要看懂這個題解,必須先了解「後綴陣列和其衍生的$height$陣列」的性質

這裡的詢問很特別,要你算出第$l$到第$r$隻熊會打給第$k$隻熊幾次
我們可以反向思考,怎麼求出第$k$隻熊會被哪幾隻熊打電話呢?

說明:
$phone[i]$為第$i$隻熊的電話代表的字串

可以考慮把所有熊的電話號碼接起來 (稱新字串為$S$),中間用空字元隔開
如果我們對$S$建立它的後綴陣列和其衍生的$height$陣列
那麼對於第$k$隻熊,會打電話給它的就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間$_{(tag\ 1)}$了
利用後綴陣列來代出這個區間中的每個點分別對應到$S$的哪些位置,就能知道是哪幾隻熊打幾次電話給它了!

可是一個一個代出是哪隻熊打的電話,再篩選出第$l$到第$r$隻熊,實在太花時間了
我們可以考慮離線作法
可以發現,對於$height$陣列的一個區間$[l_{h},r_{h}]$,我們可以用「($height$中區間$[1,r_{h}]$有幾隻是第$l$到第$r$隻熊)$-$($height$中區間$[1,l_{h}-1]$有幾隻是第$l$到第$r$隻熊)」來算出$height$中區間$[l_{h},r_{h}]$有幾隻是第$l$到第$r$隻熊

因此,我們可以把所有的詢問分割成一個個形如「$height$中區間$[1,x]$有幾隻是第$l$到第$r$隻熊」的子問題,將這些子問題依照$x$排序,然後讓$i$由小到大跑,將$height[i]$在$S$上對應到的位置加進線段樹中維護
這樣對於每個子問題,$i$跑到$x$時,就可以直接利用線段樹的區間查詢,求出$[l,r]$有幾隻熊了

每個詢問的答案就是它對應到的兩個子問題答案相減

$Tags$:
$_{tag\ 1}$:將每隻熊的電話號碼由長到短排序,$height$由大到小排序,然後就可以在$x$遞減的情況下,利用$disjoint\ sets$維護$height$上高度$\geq x$的連通塊,當$x$等於第$k$熊的電話號碼長度時,就可以直接利用$disjoint\ sets$求出所在連通塊的左界和右界,也就是$height$陣列中連續高度$\geq \left|phone[k]\right|$的區間

時間複雜度:$O((\sum_{i=1}^{N}\left|phone[i]\right|)\log(\sum_{i=1}^{N}\left|phone[i]\right|)+Q\log(\sum_{i=1}^{N}\left|phone[i]\right|))$

code:

[Codeforces 547E]Cyclical Quest

題目就是給你字串$S$,然後再給你一堆$A_{i}$,問你$S$有幾個子字串和$A_{i}$循環等價

可以考慮對$S$製作後綴自動機
然後對每個$i$ ($1\leq i\leq N$)
把$A_{i}$複製一遍接在後面 (稱新字串為$B$)
讓$B$在自動機裡面進行轉移
可以立即得到當前$B$的前綴屬於$S$的子字串的最長後綴 (請參考這裡)
如果後綴長度$\geq \left|A_{i}\right|$,就把這點標記起來,代表如果某個代表$S$前綴的點可以透過失配邊直接或間接指到這點,那麼這個點代表的$S$前綴的後綴就是符合條件的子字串
當然,因為要找出盡量多符合條件的$S$子字串,所以如果目前節點往失配邊走,代表的字串長度還是$\geq \left|A_{i}\right|$,就得往失配邊走

可以發現
後綴自動機的所有失配邊反向後會形成一棵根為$0$的樹
而答案就是這些被標記的點和其子節點們之中有幾個代表$S$的前綴

我們可以先把這棵樹壓平 ($dfs$並存下進入和離開時間即可),讓每棵子樹都可以用一個區間來表示
然後用線段樹來維護,可以先預處理,用單點修改將所有代表$S$前綴的點加入
然後要求$u$和其子節點們之中有幾個代表$S$的前綴時,只要線段樹查詢子樹對應的區間的總和就好了

要注意被標記的點中有可能出現某個點是另外一個點的子節點的情況
為了避免重複計算
我們先把標記的點依照$dfs$後序排序 (設序列變成$\{v_{1},v_{2},v_{3},...\}$),這樣如果$v_{a}$是$v_{b}$的子節點,那麼$v_{a+1},v_{a+2},...,v_{b-1}$也都會是$v_{b}$的子節點
用$stack$維護互不屬於父子關係的節點們即可

時間複雜度:$O(\left|S\right|+\sum_{i=1}^{N}\left|A_{i}\right|)$

code:

2016年3月1日 星期二

[Codeforces 163E]e-Government

這題給你一個字串集合$\{A_{i}\}$ ($1\leq i\leq N$)
然後是$Q$個操作,分為三種
1. 將$A_{i}$從集合中移除
2. 將$A_{i}$加回集合中
3. 給你字串$S$,問你$S$中可以數出幾個$\{A_{i}\}$的元素?
例如$\{A_{i}\}=\{"a","aa","aaa"\}$,$S="aaaa"$,你應該回答$9$

我們可以先把$\{A_{i}\}$建成$AC$自動機,然後讓$S$在裡面進行轉移
每走一個點,就將沿著失配邊可以走到的所有單字結尾的計數器都$+1$
走完時,每個單字結尾的計數器數值加起來就是答案了

當然,真的這麼做會TLE,每走一步就沿失配邊遍歷每個可以走到的單字結尾實在太花時間了

可以發現,將所有的失配邊反向可以形成一棵根節點為$0$的樹
於是我們就可以建立這棵樹的壓扁序列,這樣每棵子樹就都能剛好對應到一個區間了

那要怎麼做到快速的將沿著失配邊可以走到的所有單字結尾的計數器都$+1$呢?
反向思考,為甚麼我們不先把所有點的$+1$次數都算好?

於是,我們可以將每個以單字結尾為根的子樹全部$+1$
可以透過用線段樹維護樹壓扁序列,實現區間修改來達成

於是,要怎麼取得某個節點沿著失配邊走會遇到幾個單字結尾呢?
就是線段樹的單點查詢啦!

於是操作3.我們可以做到時間複雜度$O(\left|S\right|\log(\sum_{i=1}^{N}\left|A_{i}\right|))$!

那麼操作1.和2.呢?
移除單字相當於將以對應的單字結尾為根的子樹裡的每個點全部$-1$
那麼加回單字當然就是將子樹裡的每個點全部$+1$了
將樹壓扁序列對應的區間做適當的區間修改即可
時間複雜度$O(\log(\sum_{i=1}^{N}\left|A_{i}\right|))$

總時間複雜度:$O(\sum_{i=1}^{N}\left|A_{i}\right|+(\sum S)\log(\sum_{i=1}^{N}\left|A_{i}\right|)+Q\log(\sum_{i=1}^{N}\left|A_{i}\right|))$

code: