oToToT的code收藏區

題目連結: https://codeforces.com/contest/1051/problem/F 煩人的題目，一開始看到題的時候，忘記字串可以$(N, O(logN))$比較大小，然後想了想，想出一個什麼suffix array上二分搜之類的超噁比大小作法XD 後來發現可以$O(logN)$比大小之後，又因為hash碰撞卡了一段時間，才發現我p, q打反XD 總之，這題應該可以想到一個簡單的DP狀態$dp[i]$代表把後i個弄好的方法數，哪也很明顯的如果$s_i \neq \text{'0'}$，那就是找到一個區間的$j(i \le j \leq n)$使得$L \leq s_i...s_j \leq R$然後明顯$dp[i]=\sum_{j} dp[j]$，因為我們顯然只能把$s_i$跟那些人接在一起，而若$s_i = \text{'0'}$的情況也類似，所以現在變成我們要找到那些j，不過很明顯可以發現若a跟b差不多大，那他們的位數應該也差不多，所以我們只要去比較位數差不多的那個substring，就可以得知他是不是比較大了。 #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; const int qs[] = { 1002939109, 1020288887, 1028798297, 1038684299, 1041211027, 1051762951, 1058585963, 1063020809, 1094763083, 1106384353, 1120154459, 1140593173, 1147930723, 1172520109, 1183835981, 1187659051, 1241251303, 1247184097, 1255940849, 1272759031, 1287027493, 1288511629, 1294632499, 1312650799, 1314753281, 1320080669, 1321970357, 1333133947, ...

題目連結: 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)))); } 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; ...

題目連結: http://codeforces.com/problemset/problem/909/C 我不會DP QAQ 本題狀態可以訂成$dp[i][j]$代表到第$i$個statement時有$j$個intent的方法數，那轉移想了想後就可以得到，如果前面是for statement，那顯然現在的東西就只能擺在跟他同一個intent，而若前一個是普通的statement，則我們可以擺到intent比較小的任意一個位置。而這樣的話複雜度會變成$O(N^3)$，但是其實我們可以透過預處理前綴和以達到$O(N^2)$的複雜度。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int MOD = 1000000007; const int N = 5000 + 5; bool arr[N]; lld dp[N][N], sum[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ string ss; cin>>ss; if(ss[0]=='s') arr[i] = 1; else arr[i] = 0; } auto psum = [](int l, int r){ // 0-base [l, r] if(l) return sum[r]-sum[l-1]; else return sum[r]; }; dp[0][0] = 1; for(int i=1;i<=n;i++){ if(arr[i-1]){ sum[0] = dp[i-1][0]; for...

題目連結: http://codeforces.com/contest/912/problem/E 記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數，大約只有$10^6~10^7$種左右，所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數，但是因為如果真的把全部都長出來了會太大，所以我們還可以二分搜第k大會是誰，這樣就只要知道比某個數小的數字有幾個就好了，而計算這個的方法很簡單，就枚舉一邊，再二分搜另外一邊即可。 #include <bits/stdc++.h> using namespace std; typedef uint64_t llu; #define PB push_back #define ALL(x) begin(x), end(x) const llu C = 1000000000000000000LL; llu primes[20], p1[10], p2[10]; vector<llu> num1, num2; inline llu calc(llu); void dfs(int,llu,llu[],int,vector<llu>&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>primes[i]; sort(primes, primes+n); int n1 = 0, n2 = 0; for(int i=0;i<n;i+=2) p1[n1++] = primes[i]; for(int i=1;i<n;i+=2) p2[n2++] = primes[i]; dfs(0, 1, p1, n1, num1); dfs(0, 1, p2, n2, num2); sort(A...

題目連結: http://codeforces.com/problemset/problem/839/D 超級無敵久沒寫blog了，記錄一下這題好了，我過然數學還是不太好QQ 首先我們可能會想要對每個gcd都計算答案，那這時候我們可能會想知道有可能對這個gcd有貢獻的人會有誰，所以不妨先計算好有多少個數字含有因數$i$。那接著我們就直接計算總長度，對於每個因數$i$計算$\sum_{j=0}^{cnt[i]} j\cdot \binom{cnt[i]}{j}$但是這樣會重複計算到太多人，所以要扣掉他的2倍、3倍....的答案，而要算答案的時候則再乘上$i$即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; const int C = 1000000 + 5; const int MOD = 1000000007; int arr[N], cnt[C]; lld ans[C], two[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; two[0] = 1; for(int i=1;i<n;i++) two[i] = two[i-1]*2 % MOD; for(int i=0;i<n;i++){ cin>>arr[i]; cnt[arr[i]]++; } for(int i=1;i<=C;i++) for(int j=2;j*i<=C;j++){ cnt[i] += cnt[i*j]; } lld ret = 0; for(int i=C;i>=2;i--){ if(cnt[i]==0)...

題目連結: http://codeforces.com/problemset/problem/894/D 看了題解又問了人才會這題QAQ 本題作法我覺得好暴力(?，首先要觀察出這題第$i$條邊固定連接$ \lfloor \frac{i+1}{2} \rfloor $跟$i+1$的話，那給定的這棵樹就一定會是一棵完滿二元樹，深度必定為$\log_2(n)$，接著我們要預處理這棵樹，把每個點到其子樹們（包含自己）的距離算出來並排序好（這裡可以用merge sort的merge方法把兩棵子樹merge好），那我們要查詢的時候就只要往上走，並把我另外一邊的子樹可以走到的節點們通通加起來就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define SZ(x) ((int)(x).size()) #define ALL(x) begin(x), end(x) typedef pair<lld,int> PLI; #define FF first #define SS second const int N = 1000000 + 5; vector<lld> dis[N], sum[N]; lld len[N]; void build(int,int); lld go(int,lld,int); PLI get_val(int,lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, q; cin>>n>>q; for(int i=2;i<=n;i++) cin>>len[i]; build(1, n); while(q--){ int w, l; cin>>w>>l; cout<...

題目連結: http://codeforces.com/problemset/problem/675/C 想了很久才知道方向錯了QAQ 作法是枚舉每個人往右邊推過去(可以證明只要枚舉所有人往右走就一定是好的)，那仔細觀察就會發現我們要省幾個就是看我們走過來有幾個前綴為零，而枚舉每一個人做開頭的時候其實我們就是問一直把最後的放到前面，也就是把前面加值，最後一個減值接著再查一下有幾個0就好了XD #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 100000 + 5; map<lld,int> cnt; lld arr[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; lld cur = 0; for(int i=0;i<n;i++){ cin>>arr[i]; cur += arr[i]; cnt[cur]++; } int ans = n-cnt[0]; cnt[0]--; for(int i=n-1;i>=0;i--){ cur -= arr[i]; ans = min(ans, n-cnt[cur]); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/798/D 很久以前比賽的時候沒寫出來，最近又再想還是想不到，只好去看題解QQ 大致的想法是，會發現對於$a$我們其實只要在$a$的任意排列的裡面選$a_{2i}$跟$a_{2i+1}$中比較大的人的index，那加起來就一定會夠。但是如果只是無腦的這樣挑很有可能$b$不會符合，所以不妨想想我們把$a$排序一下，並且一定選第一個，接著看相對映的$b$哪個index比較大，就挑他，這樣的話因為$b$一定是好的(跟前面講的一樣)，而$a$若是每次都挑到比較小的那個也不會爛，因為我們已經挑了最大的那個(可以想像成$a$是從$0$開始挑比較大的，$b$是從$1$開始挑比較大的之類的)。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; int a[N], b[N], p[N], ans[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<n;i++) cin>>b[i]; for(int i=0;i<n;i++) p[i]=i; sort(p, p+n, [](int x, int y){ return a[x] > a[y]; }); cout<<n/2+1<<'\n'; ans[0] = p[0]; for(int i=1;i<n;i+=2){ if(b[p[i]] > b[p[i+1]]) ans[(i+1)/2] = p[i]; else ans[(i+1)/2] = p[i+1]; } ...

題目連結: http://codeforces.com/problemset/problem/877/E 把樹壓扁後題目就轉化成有一個01序列，並且有兩種操作：查詢區間和跟把區間的bit反轉。稍微想一下會發現線段樹可以好好做他，所以就用線段樹維護一下就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,bool> PIB; #define FF first #define SS second const int N = 200000 + 5; class SegTree{ private: PIB nodes[N<<2]; int n; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} inline void push(int l, int r, int id){ if(!nodes[id].SS) return; nodes[id].FF = r-l - nodes[id].FF; if(r-l > 1){ nodes[lc(id)].SS ^= nodes[id].SS; nodes[rc(id)].SS ^= nodes[id].SS; } nodes[id].SS = 0; } inline void pull(int l, int r, int id){ int val = 0, mid = (l+r)>>1; if(nodes[lc(id)]...

題目連結: http://codeforces.com/problemset/problem/731/D 我覺得我的作法感覺不太對(?但還是講一下好了 我的做法是先把大小關係建成一張DAG，而這樣的話會發現題目變成說可不可以找到一種拓樸排序方法使得序列會是循環的字串，而又已經知道循環其實就只有可能中間斷開一個而已，所以我們不妨找到中間斷開的那個關係，並追本朔源到最前面的那個，從他開始拓樸排序，看會不會是好的。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 500000 + 5; const int C = 1000000 + 5; class DJS{ private: vector<int> arr; public: inline void init(int n){ arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ int u = query(a), v = query(b); arr[max(u, v)]=min(u, v); } } djs; vector<int> G[C], cur; int in[C]; inline void kill(){cout<<"-1\n...

題目連結: http://codeforces.com/problemset/problem/761/E 一開始以為邊長只能是一www 會發現節點才30個，那我們可以簡單的安排每個深度的邊長$2^{55-d_i}$這樣的話，因為$\sum_{i=0}^{n-1}2^i #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 30 + 5; lld dx[]={0, 0, 1, -1}, dy[]={1, -1, 0, 0}; int inv[]={1, 0, 3, 2, 5}; vector<int> G[N]; PLL ans[N]; int dep[N]; void dfs(int,int,int,PLL); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } bool flag = false; for(int i=1;i<=n;i++) if(G[i].size() > 4){ flag = true; } if(flag){ cout<<"NO\n"; return 0; } cout<<...

題目連結: http://codeforces.com/problemset/problem/735/C 我覺得這其實滿有趣的(?，我自己是半猜出跟費式數列有關，感覺好像是要找到最大的$i$使得$\sum_{j=0}^{i}F_j \leq n$，但一直不知道為什麼。看了題解才知道原來其實就是我們想想看如果要贏$n$場比賽，那勢必自己要贏$n-1$場，並且找一個贏過$n-2$場的人來打會最好，所以就得到$F_n = F_{n-1}+F_{n-2}$的費式數列公式了XDD。 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long long n; cin>>n; long long prepre = 0, pre=1, cnt = 0; int ans; for(ans=0;cnt<n;ans++){ long long cur = prepre+pre; prepre=pre; pre=cur; cnt+=prepre; cerr<<cnt<<'\n'; } cout<<ans-1<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/383/D 某種進階版的加減問題(?，原本的加減問題DP式大概長得像$dp[i][j] = dp[i-1][j+a_i]+dp[i-1][j-a_i]$之類的，而現在變成可以從任意時間點開始的話就除了原本的方法，還多了兩種:$dp[i][a_i]$跟$dp[i][-a_i]$ #include <bits/stdc++.h> using namespace std; const int C = 10000 + 5; const int N = 1000 + 5; const int MOD_BASE = 1000000007; #define dp(i, j) way[(i)][(j)+C] int way[N][2*C]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; for(int j=10000;j>=-10000;j--){ if(j+x <= 10000) dp(i, j) += dp(i-1, j+x); if(j-x >= -10000) dp(i, j) += dp(i-1, j-x); dp(i, j) %= MOD_BASE; } dp(i, x)++; dp(i, -x)++; } int sum = 0; for(int i=1;i<=n;i++) sum = (sum+dp(i, 0))%MOD_BASE; cout<<sum<<'\n'; return 0; } ...

題目連結: http://codeforces.com/contest/842/problem/C 一直以為因數個數會太多，所以只打算枚舉質因數.... 但其實直接枚舉因數，然後看看哪個因數個數有超過n-1個之類的就好，枚舉完後把他插進去，讓下面的人來看。(頭痛，有點不知所云OAO #include <bits/stdc++.h> using namespace std; #define PB push_back const int C = 200000 + 5; const int N = 200000 + 5; vector<int> frac[C], G[N]; int arr[N], ans[N], cnt[C]; void sieve(int); void dfs(int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); sieve(C); int n; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=1;i<n;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } dfs(1, 1, 0, 0); for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; return 0; } void sieve(int n){ for(int i=2;i<n;i++) for(int j=i;j<n;j+=i){ frac[j].PB(i); } } void dfs(int...

題目連結: http://codeforces.com/problemset/problem/735/D IOICamp的時候有提到這題，不過我其實已經忘了結論了www 去翻了一下才知道原來是跟哥德巴赫猜想有關，其猜想簡而言之就是說對於任意一個大於二的偶數，都可以拆成兩個質數相加。所以我們這題的做法就是先看看給定的數是不是質數，如果是當然就輸出1，接下來看他是不是偶數，是的話那根據歌德巴赫猜想，答案應該會是2，而對於一個奇數，我們要先看看他減二是不是質數，是的話輸出2，不是的話輸出3，因為對於一個奇數他一定是拆成一個質數加一個偶數，然後偶數拆成兩個質數，但要是拆出來的偶數是二，那答案就變成2了。 p.s. 附個維基上哥德巴赫猜想的條目 https://zh.wikipedia.org/wiki/哥德巴赫猜想 #include <bits/stdc++.h> using namespace std; bool isprime(int n){ for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return 1; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; if(isprime(n)) cout<<1<<'\n'; else if(n%2==0 or isprime(n-2)) cout<<2<<"\n"; else cout<<3<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/864/E 只感覺應該是DP，而且東東的順序會有影響，但是完全不知道該用何種順序來DP，看了tutorial才知道原來要按照消失時間來DP。 tutorial中其實並未給出證明，不過下面有人表示「如果你不先挑那些會先消失的人，那很有可能他待會就消失了(當然挑他要是有助益的)」，想了想我自己是覺得說，如果你可以先挑比較晚消失的人，再挑比較早消失的人，那你也一定可以先挑早消失再挑晚消失的，但反過來的挑法就不一定了。 那所以就按照那個順序排好序後，這題就變得類似於背包問題了，所以我們就可以跟背包一樣，用加入東東的方是想，每次加入一個物品就是在那些可行的範圍中往後加值之類的。 #include <bits/stdc++.h> using namespace std; const int N = 100 + 5; const int M = 2000 + 5; struct Obj{ int t, d, p; int id; inline bool operator<(const Obj &x) const { return d < x.d; } } arr[N]; int sum[M]; vector<int> ori[M]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ cin>>arr[i].t>>arr[i].d>>arr[i].p; arr[i].id = i+1; } sort(arr, arr+n); for(int i=0;i<n;i++){ for(int j=arr[i].d-1;j>...

題目連結: http://codeforces.com/problemset/problem/802/M 沒敘述的題目www 但其實應該不難猜到就是輸出前k小數字的和。 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); priority_queue<int,vector<int>,greater<int>> pq; int n, k; cin>>n>>k; for(int i=0;i<n;i++){ int x; cin>>x; pq.push(x); } int ans = 0; for(int i=0;i<k;i++){ ans += pq.top(); pq.pop(); } cout<<ans<<'\n'; return 0; }

題目連結: http://codeforces.com/problemset/problem/721/C 莫名其妙吃了MLE，只好把int改short, long long改int = = 本題的做法滿DP的，我狀態直接訂成$dp[i][j]$代表起點到$i$號節點，經過$j$個中繼點所需的最短時間，而DP的順序就按照圖的拓樸排序順序DP就可以好好DP了，不過要注意的是起點有可能不會是拓樸排序的第一個點，所以要稍微判一下... #include <cstdio> #include <vector> #include <utility> #include <stack> #include <queue> using namespace std; typedef long long lld; #define PB push_back typedef pair<short,int> PSI; typedef pair<short,short> PSS; #define FF first #define SS second const int N = 5000 + 5; const int INF = 1<<30; short in[N]; int dp[N][N]; PSS ori[N][N]; vector<PSI> G[N]; int main(){ short n, m;int t; scanf("%hd%hd%d",&n,&m,&t); fill(dp[0], dp[n]+n+1, INF); for(int i=0;i<m;i++){ short u, v; int c; scanf("%hd%hd%d",&u,&v,&c); G[u].PB({v, c}); in[v]++; ...

題目連結: http://codeforces.com/contest/855/problem/C 賽中看到一堆大大們都寫出來的題目，但是自己怎麼寫都寫不出來就是了QQ，一定是因為我DP太爛的緣故 總之這題很明顯就是個樹DP題，狀態這裡是定成$$ dp[i][x][0] := 第i個節點放[1,k-1]種類且有x個k的方法數 \\ dp[i][x][1] := 第i個節點放k且有x個k的方法數 \\ dp[i][x][2] := 第i個節點放[k+1,M]且有x個k的方法數 $$轉移的話就算滿好想的了，大致就是0號可以從0,1,2轉來；2只能從0轉來；ㄉ可以從0, 2轉來，而怎麼轉就直接枚舉其中一邊有幾個就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; const int N = 100000 + 5; const int K = 10 + 2; const int MOD_BASE = 1e9+7; int n, m, k, x; lld dp[N][K][3]; vector<int> G[N]; void dfs(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } cin>>k>>x; dfs(1, 1); lld ans = 0; for(int i=0;i<=x;i++){ ans=(ans+dp[1][i][0])%MOD_BASE;...