oToToT的code收藏區

題目連結: https://codeforces.com/problemset/problem/1017/E 比賽unrated了，不知道好險還是好慘，前面做題真的做超慢，然後到現在還是不知道為什麼C那樣做就好了。 不過這題其實滿有趣的。 可以發現這題其實要問的就是兩個東東他們的凸包是否相同(允許旋轉及位移，但不能鏡射)，原因就是會發現結束的時候，一個engine構成的power field一定會變成一個凸多邊形，然後現在考慮若是拆掉凸多邊形上任意一個頂點，那他必定會縮進去(沒有兩個點在相同的位置)，所以我們一定要用另外一個engine來補，才可以讓他不會縮進去，也因此其實就是每個頂點都要在一樣的位置。 那要怎麼做呢？當然，先求出凸包之後，拿到的凸包顯然會按(順/逆)(看實作)時鐘的方式排序點，所以我們其實就是要求，兩個凸包是否有某種旋轉操作(abc->bca->cab...)使他們相同。 我原先是用booth's algorithm幫兩個東東都求出最小字典序的旋轉，再來一個一個比較是否一樣，但也有其他作法。 字串相關的作法就是將其中一個凸包複製一次貼在自己後面(abc->abcabc)，然後hash或kmp直接求是否另一個凸包出現在裡面。 不過其實暴力枚舉一個東東旋轉後的長相然後判斷相等就可以過了，因為其實整數點上的凸包大小最多只有$\sqrt{C}$，所以直接枚舉的複雜度也才$\sqrt{C} \times \sqrt{C} = C$。 但這題最難的點，我覺得其實要怎麼把凸包變成一個序列，且他可以拿來判斷旋轉位移後可以一樣，但鏡射不行，原本我的想法只有判斷所有邊的長度跟所有角的角度是否一樣，但是卻被 Hack 掉了，後來才發現我需要把角跟邊擺在一起才可以成立，不然鏡射的話他拿的邊順序及角順序也可以一樣，但實際卻長得不一樣。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) #define SZ(x) (static_cast<int>((x).size())) using lld = int64_t; ...

題目連結: http://tioj.infor.org/problems/1497 本題是個裸後綴陣列題，基本上只要你懂它就寫得出來，不過我好像寫這題寫了一整天，倒最後是參考 這篇 的$O(n \log ^2 n)$的作法才刻了出來，不過後來還是有寫一份radix sort的版本，但效率不知為何很差就是了... $O(n \log ^2 n)$的作法 #include <bits/stdc++.h> using namespace std; #define N 100000 #define PB push_back struct sfx{ int index; int r,nr; }; char str[N + 10]; int len; int mapping[N + 10]; sfx sa[N + 10]; bool cmp(sfx a,sfx b){ if(a.r==b.r){ return a.nr<b.nr; }else{ return a.r<b.r; } } void SA(); int main(){ gets(str); len = strlen(str); SA(); for(int i=0;i<len;i++){ printf("%d\n",sa[i].index); } return 0; } void SA(){ for(int i=0;i<len;i++){ sa[i].index = i; sa[i].r=str[i]; sa[i].nr=(i+1>=len)?-1:str[i+1]; } sort(sa,sa+len,cmp)...