oToToT的code收藏區

題目連結: https://codeforces.com/problemset/problem/1027/F 我好笨QAQ 本題關鍵大概是想到可以把每個考試當做邊來看吧OAO（看了解才知道 假設知道這件事後，那其實就很簡單，當然對於每個連通元件分開處理，明顯的如果邊數較點數多，那一定無法構造出一個合法的結果。 接著當邊數跟點數一樣多的時候，一定存在解，因為他必定可拆成幾個環跟一些連接的邊，那這時這裡的答案就是點的最大值。 還有邊數是點數減一的時候，不難發現他是顆樹，然後答案會是次大值。 邊數是點數減二的時候則不可能出現，所以討論這幾種狀況就可以得到答案了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; using PII = pair<int,int>; #define PB push_back #define FF first #define SS second #define ALL(x) begin(x), end(x) #define SZ(x) (static_cast<int>(std::size(x))) const int N = 2000000 + 5; class LiSan{ private: vector<lld> vv; public: template<typename... Args> void insert(lld x, Args& ...oth){insert(x);insert(oth...);} void insert(lld x){vv.PB(x);} void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } int size() const { return SZ(vv); } int get(lld x){ return static_cast<int>(distance(vv.begin(), lower_bound(ALL(vv), x))); } lld inv_get(in

題目連結: 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; struct PT{ lld x, y;