[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:

[POI 12 Stage 2]Template

這裡提供了另外一個做法，選個喜歡的去實現吧～

可以發現，能用來當模板的字串一定只能同時是主串的前綴和後綴
回顧$KMP$中失配函數$fail$ (有人稱作$next$) 的定義：(以下字串中的編號皆由$0$開始)
字串$S$的$fail[i]$代表$S$的最長前綴長度，使得這個前綴和$S_{0\sim i-1}$的後綴 (結尾是$i-1$的子串) 完全相符

於是，可以當作答案的前綴的長度就只能是$N$、$fail[N]$、$fail[fail[N]]$、......了 ($N$為主串長度)
把這些候選人依序存起來，$f_{0}=N$、$f_{1}=fail[N]$、$f_{2}=fail[fail[N]]$、......、$f_{n}=0$

於是，我們可以從$f_{n-1}$開始枚舉候選人 ($f_{n}=0$代表空串，是不合法的)，看看和$S_{0\sim f_{i}-1}$匹配的點中，相鄰點間的最大距離有沒有超過$f_{i}$，沒有的話答案就是$f_{i}$

注意，和這個作法不一樣的是，這些點代表的是字串尾端的位置 (也就是代表以這個點為結尾的子串)，而不是字串開頭的位置

與其找出所有和$S_{0\sim f_{i}-1}$匹配的點，不如改成只保留和$S_{0\sim f_{i}-1}$匹配的點

做法是：
先將所有$fail$的邊反向建圖，我們就得到了一棵根為$0$的樹
可以發現，對於任何一個節點$u$，和以$u$為根的子樹中任何一個節點$v$，$S_{v-u\sim v-1}$和$S_{0\sim u-1}$匹配

當枚舉到$f_{i}$這個候選人，就將$f_{i+1}$所有不包含$f_{i}$的子樹中涵蓋的點全部刪除 (因為這些點和$S_{0\sim f_{i+1}}$匹配，但不和$S_{0\sim f_{i}}$匹配)
這樣每一個點都只會被刪掉一次，沒有重複也沒有遺漏 (除了$N$這個最後的點)

利用雙向鏈表可以實現$O(1)$刪點並維護相鄰點間的最大距離

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

code:

[POI 12 Stage 2]Template

這裡提供了另外一個做法，選個喜歡的去實現吧～

可以發現，能用來當模板的字串一定只能是主串的某個前綴

於是，我們可以枚舉前綴，然後看看這個前綴和字串中的哪些地方吻合
如果這些吻合的位置相鄰間的最大距離不超過這個前綴的長度，答案就是這個前綴的長度了

要怎麼得到這個前綴和字串中的哪些地方吻合呢？
就是$Z\ Value\geq$這個前綴長度的位置啦

$O(N)$將$Z\ Value$求出後，利用基數排序$O(N)$將它們由小到大排好
然後由短到長枚舉前綴，將$Z\ Value$太小的點刪掉
然後看看剩餘的點，相鄰間的最大距離是不是不超過這個前綴的長度

用雙向鏈表可以實現$O(1)$刪點並維護相鄰點間的最大距離

你問我為甚麼不需要考慮這個前綴是不是也是主串的後綴 (才能剛好覆蓋完整串)？
如果不是的話，鏈表中$N+1$這個點和前一個點的距離就爆掉啦～ ($>$目前前綴長度)

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

code:

[POI 14 Stage 1]Offices

仔細想想，可以發現最大辦公大樓數量就是補圖的連通塊數量，每棟辦公大樓的大小就是這些連通塊的大小

所以把補圖建出來就好了

等等，$N$到100000...

可以發現，我們只須在意連通性，因此如果$A$能走到$B$和$C$，就不必考慮$B$有沒有邊連向$C$了
也就是說，我們只需要挑出幾條代表性的邊，讓連通性保持不變就好了

實作上可以每次挑一個沒走過的點$u$開始bfs，遍歷所有未走過的點，和$u$有連邊的時候跳過，否則加入queue裡面並標記已走過

這做法看似不太高效，但是因為這是稀疏圖，跳過的次數不會超過$M$次，如果將鄰接表和未走過的點都用set維護的話，時間複雜度可以達到$O((N+M)\log N)$

就這樣傳上去獲得了39分+一堆RE
記憶體超限= =

因此我把雙向邊當作單向邊來存，這樣記憶體就少一半了

獲得了88分+一堆OK(?)
沒跟我解釋為啥沒滿分= =

自己生10W點200W邊的測資，開了工作管理員測一下記憶體
只見記憶體用量慢慢往上飆
就在最後一刻
閃了一個65180KB
答案就跑出來了Orz
可是記憶體限制64MB......

至於後來我怎麼成功把記憶體降到20MB並獲得滿分
請看我的code吧XD

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

code:

[TIOJ 1841][POI 21 Stage 1]好．傳囉！ Nice Boat！

(題號打錯所以只好重發文章@@，順便套用剛學的latex語法)
因為HOJ在我寫完這題之後的submissions都沒有動靜(聽說HOJ快要壽終正寢了，好難過QAQ)，所以現在來寫TIOJ了XD

這題題目敘述有點雜，還誤會題目意思打錯code，花了不少時間才理解成功@@
就是，給你一個數列，求最長區間的長度，使得這個區間的任意前綴和後綴和都$\geq 0$

首先，區間的任意前綴和後綴和都是區間和，可以用數列的前綴和(不是區間的)相減求得
假設一開始的$0$也算進去的話，我們可以把這些前綴和畫成有$N+1$個點的折線圖

而假設有一個區間符合題目的條件，把它對應到折線圖上面
那麼仔細思考就可以發現，在折線圖的這個區間裡面，區間左端是最低點，右端是最高點，中間不會允許任何一個點突破兩端的極值(不然就會有區間前綴或後綴和$<0$了)

為了方便說明，定義規則1為區間中間的值必須$\leq$右端點，規則2為區間中間的值必須$\geq$左端點
我們可以先預處理出每個左端點$u$符合規則2中最右邊的右端點$R[u]$，可以用單調對列實現。可以證明，在左端點到$R[u]$之間的所有點，都會是符合規則2的右端點
再來，對於每個左端點，可以維護一個符合規則1的右端點的集合，這一樣可以用單調對列從右到左掃實現
這樣，當左端點維護到$u$時，我們就可以在這個集合裡面進行二分搜，在符合規則1的右端點之中找出最大且$\leq R[u]$的點$v$，那麼$[u,v]$就是符合題目要求中左端點是$u$的最長區間了
在這些計算結果中，取最大的區間長度即可

時間複雜度：$O(N\log N)$

code:

[HOJ 257][POI 19 Stage 3][Interactive]Bidding

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這題的題目敘述爛掉了......
總之，你覺得少一個字的地方就填N吧(?)
可以發現，pot的石頭數一定是(2^a)*(3^b)
因此，在<30000的範圍pot可能的數字最多O(logN)個
再加上stack，可能的狀態數不超過O(NlogN)個
這樣就可以實現記憶化搜索了
如果不能動任何一步讓對手輸，你就輸了
反之，你就贏了
詳情請參考code

要注意的是，本題的#include "interactive/257.h"之前一定要有#include<cstdio>或#include<stdio.h>，不然會編譯錯誤說你沒定義scanf和printf
=ㄦ=

code:

[HOJ 163][POI 18 Stage 1]數列排序

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

這種題目很多都和逆序對數有關(我也不知道為甚麼XD)，可以發現，操作a可以視為將b操作的基準點往前移一格，那剩下的就是考慮要依序在哪幾點進行b操作了
首先，先決定一點(這點怎麼決定等一下再說www)，把1移到那個地方，接著會說明，如果有解，對剩下的2,3,...N存在一系列操作使得任意操作都不會動到1
接下來往逆序數對思考吧，可以發現，操作b在任何情況下都不改變逆序對數的奇偶性，操作a就只有N是偶數的情況下才會改變逆序對數的奇偶性
若數列已經排序好，逆序對數為零(偶數)，因此如果N是偶數，而逆序對數是奇數的話，無解
反之，如果N是奇數，逆序對數是奇數，則想成先把「排序好的序列做一次操作a」的情況弄出來(因為這時逆序對數是奇數)，再做N-1次操作a還原
這等價於先把1放在N這個位置
如果逆序對數是奇數，就把1放在1這個位置
然後就可以透過好多次「對不同位置進行操作b(多次操作a和一次操作b的組合)」依序把2,3,...N-2排好了(當然，1是不能動的，要永遠待在1或N這個位置)
咦?如果這時候N-1和N的位置反過來了怎麼辦?
這是不可能發生的，因為前面的預處理已經將逆序對數弄成偶數了，上述情況的逆序對數是奇數哦XD~
然後，就不小心做完了(?)
記錄下每一個操作，轉換成題目要求的格式輸出，就很開心的WA了(?)
哦，因為我把'a'打成'A'了XDD

code:

[HOJ 162][POI 17 Stage 1]找因數

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

先備知識: 質數判定法
假設這n個數的乘積是N好了
總之，先用輾轉相除法把這n個數分解成更多個兩兩互質的數，但是乘積還是等於N，這個分解完的數列就壓縮存在S裡面，請注意，這個互質的性質很重要
然後就是對S裡面的每個數做質因數分解算次方數，最後就可以直接找k了
由於數字很大，有時不能直接對他做質因數分解
首先可以設想一個很大很大的數字M，用10^6以內的質數試除完畢，剩下一個數，叫它A好了
先用上網查的(XD)質數判定法判斷A是不是質數，如果是，就結束了
因為次數是很重要的資訊，所以先開根號看看是不是某個質數平方，如果是，就結束了
如果上述方法都失敗，就代表A一定是兩個>10^6的相異質數P和Q相乘，這時候其實不用找出P和Q是甚麼，可以直接用A和A+1來代表這兩個質數
為甚麼呢?
上面有提到，經過處理，S裡面每兩個數都會互質，因此不會有另外一個數的因數也包含P、Q或A
又因為A一定是大於10^6的奇數(不然就會在前面的試除過程被解決掉了)，所以A和A+1這兩個key一定不會被其他人用到
既然這麼好康，當然不客氣就把A和A+1當作P和Q了XD
現在，我們成功把這個很大很大的數質因數分解了！(其實只知道次方啦，不過這樣就夠了XD)
接下來的步驟就很明朗了
找出最大的k和次方數等於k的質數個數
至於「第二行請輸出 k 最大時 d 有多少種可能」，仔細想想就會發現可以套用一下計算因數個數的技巧，它其實就是「2^(符合條件的質數個數)-1」
要注意的是這中間涉及很多溢位問題，要設計一個方法支持(long long)*(long long)%(long long)這個運算
我原本直接貼大數模板結果TLE了QQ
不過後來的方式時間效率還不錯啦XD
耶！

code:

[HOJ 158][POI 18 Stage 2]猜密碼

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

仔細想就會發現，如果x和y都是密碼，那麼任何(ax+by)%N (a、b為任意非負整數) 的形式也都會是密碼
PW是一個已知密碼，所以每隔Gcd(PW,N)就會出現循環(假如我們用0和1代表是不是密碼)
如果有任何一個猜錯的密碼被Gcd(PW,N)整除，那答案就是1了
再來就是怎麼算這長度為Gcd(PW,N)的01序列
現在我們把視野範圍縮小到這長度為Gcd(PW,N)的01序列，可以發現，如果f是密碼，那麼任何整除Gcd(f,Gcd(PW,N))的數也都會是密碼，因此我們可以從小到大枚舉這個Gcd(f,Gcd(PW,N))，也就是gap，找到第一個不和非密碼數們衝突的gap，然後就可以知道這個01序列就是每隔gap的長度就會出現一個1的形式了
雖然可以直接算出N/gap，可是繼承先前的思路我是先算出n/gap再乘上N/n XD
對了，那個lower_bound的優化很重要

code: