oToToT的code收藏區

最近一直覺得自己該復健一下。剛好看到這系列，決定來寫一下回復一下手感，順便練練日文，不然真的太久太久沒自己好好做題了，什麼都忘光光了 😥 題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_a 題目大意: 有一個 $L$ 公分的羊羹，其中有 $N$ 個可以切的地方，從左數來第 $i$ 個可以切的位置在 $A_i$ 公分。你要選擇切 $K$ 刀使得產生 $K+1$ 塊的羊羹出來。定義切完後的羊羹的分數為： 切出來的 $K+1$ 塊中長度最小塊的長度。我們想要最大化切出來的分數。答案請輸出最大可能的分數。 挺經典的二分搜題，跟 骨牌遊戲 那種題目有點類似，可以直接對答案二分搜。假設我們知道分數是 $x$ ，那就代表只要當前位置與上一刀距離超過 $x$ 就可以砍一刀下去，而如果砍了 $K$ 刀的話就可以停下來，且代表這個分數是達的到的。根據這件事情我們就可以二分搜出最大的分數 $x$ 使得還可以砍得出 $K$ 刀。 惹..講得有點模糊，但 code 短短的可能可以看一下它 (?) #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, d, k; cin >> n >> d >> k; vector<int> a(n); for (int &a_i : a) cin >> a_i; auto valid = [&] (int m) { int piv = 0, tot = 0; for (int a_i: a) { if (a_i - piv >= m and d - a_i >= m) { tot++; piv ...

題目連結: 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/832/C 煩躁的一題...還因為沒注意到一定要放在整數點卡了一段時間QQ。 作法大概就是對答案二分搜，而驗證的時候，則會發現若是考慮要讓某個人往右的人達到終點，如果直接放在他身上可以，那往他左邊一點可能也可以，所以可以求出一個區間 ；同理往左的也是。這樣就轉化成為先將一堆區間填在數線上，接著詢問一堆區間是否與先前的區間們有碰在一起的地方。而找出對於往右區間的方法這裡是列了$$\frac{x-x^\prime}{s-v}+\frac{10^6-\frac{x-x^\prime}{s-v}\cdot v-x}{s+v} \leq t\\x^\prime \geq 10^6-\frac{v(10^6-x-vt)}{s}-st$$往左的則是$$\frac{x^\prime-x}{s-v}+\frac{x-\frac{x^\prime-x}{s-v}\cdot v}{s+v} \leq t\\x^\prime \leq \frac{v(x-vt)}{s}+st$$ #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second typedef long double llf; typedef long long lld; const int N = 1e6 + 5; int n, s; vector<PII> L, R; lld arr[N]; inline bool isOK(llf); int main(){ cin>>n>>s; for(int i=0;i<n;i++){ PII tp; cin>>tp.FF>>tp.SS; int x; cin>>x; ...

題目連結: http://codeforces.com/problemset/problem/732/D 一開始想爛了，但大方向還算對，原本以為可以直接greedy算，但一直算不太出來(雖然好像還是可)。後來發現其實可以對答案二分搜，然而驗答案的地方我一直寫爛掉，導致這題寫了超久了，但最後AC code其實也沒多複雜，真搞不懂哪裡爛掉。 稍微講一下驗證答案的部分好了，就因為有個簡單的性質就是你若可以今天考，但今天不考之後再考也可以，所以驗證答案的時候都讓每科考試都在最後一次可以考時才考，這樣前面就會有一堆溫書假了。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; int need[N], ok[N]; bitset<N> done; bool isOK(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>ok[i]; for(int i=1;i<=m;i++) cin>>need[i]; int l=1, r=n+1; while(r-l > 1){ int mid = (l+r)>>1; if(isOK(mid, m)) r=mid; else l=mid; } cerr<<ok[r]<<"\n"; if(r==n+1) cout<<"-1\n"; else cout<<r<<'\n'; return 0; } bool isOK(int n, int m){ ...

題目連結: http://tioj.infor.org/problems/1406 右界設太大浪費了3hr debug... 回到正題，應該不難猜出可以對答案二分搜，而驗證答案的時候也很簡單，想法就是如果我有多我就往右運過去，然後如果有人少他就拿走那些，如果還不夠就跟右邊的再要，所以其實就是開個變數存說多多少/少多少，如果是多的話運走的時候要是變成小於零，就讓它變成零，但是如果是少的話就算變成小於零，還是要維持著。最後只要看剩下來的是否大於等於零即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 100000 + 5; int n; PLL arr[N]; inline bool isOK(lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); while(cin>>n){ lld l=0, r=0; for(int i=0;i<n;i++){ cin>>arr[i].FF>>arr[i].SS; r=max(r, arr[i].SS); } r++; while(r-l>1){ lld mid = (l+r)>>1; if(isOK(mid)) l=mid; else r=mid; } cout<<l<<'\n'; } return 0; }...

題目連結: http://arc078.contest.atcoder.jp/tasks/arc078_c 奇怪的二分搜題，賽中的時候我有想出來大概的方向，結果沒刻完QQ，賽後再刻才發現其實還滿討厭的，有一些小小的邊界case要想。 這裡我先二分搜出答案的位數，方法很簡單，就找一個字典序很小的數字10000000(這樣讀到Y就知道原因了)，然後開始搜尋他後面0的個數，因為顯然他的字典序比起來一定都會最小，那只要找到Y跟N之間的分界，那Y那個就會是位數。 第二步則是對每一位二分搜出他正確的值，這裡先讓數字超級巨大，這樣讀到Y或N時就知道原因了，所以就每次都選最一個是N的地方。 不過要注意一下，因為最後一次也還是N，所以要加回1讓他變成Y。 p.s 付個Judge用的code AC Code: #include <bits/stdc++.h> using namespace std; typedef long long lld; int getDigit(); string getVal(int); int main(){ int dig = getDigit(); string val = getVal(dig); long long ans=0; for(int i=0;i<dig;i++) ans=ans*10 + (val[i]-'0'); cout<<"! "<<(ans+1)<<endl<<flush; return 0; } int getDigit(){ int r=10, l=0; while(r-l > 1){ int mid = (l+r)>>1; cout<<"? 1"; for(int i=0;i<mid;i++) cout<<0; cout<<endl<<flu...

題目連結: http://codeforces.com/problemset/problem/782/B 其實本題是對答案二分搜，驗證方法是當你把時間乘上速率後可以得到每個人最遠走到哪，看有沒有交集就知道解是否合法，不過本題有更無腦的方式，那就是對集合點模擬退火(其實是因為我當時看一眼就想到這個做法就沒去想正解了XD #include <bits/stdc++.h> using namespace std; #define N 60000 double pos[N+5], speed[N+5]; int n; inline double getY(double x); int main(){ scanf("%d",&n); for(int i=0;i<n;i++)scanf("%lf",&pos[i]); for(int i=0;i<n;i++)scanf("%lf",&speed[i]); double rr=*max_element(pos,pos+n); double ll=*min_element(pos,pos+n); default_random_engine rEng(time(NULL)); uniform_real_distribution<double> Range(-1,1); uniform_real_distribution<double> expR(0,1); auto Random=bind(Range,rEng); auto expRand=bind(expR,rEng); int step=0; double pace=rr-ll, mini=0.95; double x=max(min(Random()*pace+ll, rr), ll), y=getY(x); while(pace>=1e-7){ ...

題目連結: http://tioj.infor.org/problems/1827 不難發現本題可以對答案二分搜，因為S有單調性，那驗證的時候就是要驗證一個區域是不是有至少k個數小於S，我原本想說用個BIT套treap之類的，但估完複雜度後發現會TLE，實在苦思不知該如何做，直到有人雷了我說誰區間和在用BIT的，我才發現可以用維護前綴和的精神做這題，也就是說每個前綴變成存一棵treap，但是如果每一個前綴都重新插一遍所有東東到treap裡面會發現預處理變成$O(n^2 log(n))$，明顯會TLE，所以不妨用持久化的概念，也就是讓一部分是共用的，有修改到的部分再複製出來就好了，因為複製時最多只會動到一條跟到葉的路徑也就是最多$log(n)$個節點，因此複雜度還是$log(n)$，只是記憶體有點龐大而已。 #include <bits/stdc++.h> using namespace std; #define N 100000 struct treap{ treap *l, *r; int pri,val,size; treap(){l=r=nullptr;size=0;} treap(int x){l=r=nullptr;pri=rand();val=x;size=1;} }; inline int gSize(treap* x){return x?x->size:0;} inline void pull(treap* x){x->size=gSize(x->l)+1+gSize(x->r);} int arr[N+5], n; treap* root[N+5]; bool isOK(int,int,int); void split(treap*,int,treap*&,treap*&); treap* merge(treap*, treap*); int query(treap*,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0);...

題目連結: http://tioj.infor.org/problems/1208 不太確定該如何下手時，就先二分搜一陣吧，而且他還特別保證所有項的絕對值都不超過10,000，所以感覺二分搜有機會，那二分搜答案要怎麼驗證呢?其實對於一個數我們有能力可以知道有幾個連續和比他大，因為如果要看x是第幾大，則就是對於每個前綴和$a_i$我們都要找有多少個$a_j$使得$a_i - a_j > x$(其中$i>j$)，移項發現變成找有多少個$a_j+x #include <bits/stdc++.h> using namespace std; #define N 20000 class Treap{ private: struct __node{ __node* l; __node* r; int __pri,__size,__val; __node(){l=NULL;r=NULL;__pri=rand();__size=0;} __node(int x){l=NULL;r=NULL;__pri=rand();__size=1;__val=x;} ~__node(){if(l)delete l;if(r)delete r;l=NULL;r=NULL;} }; __node* __root; inline int __gSize(__node* __x){return (__x==NULL)?0:(__x->__size);} __node* __merge(__node* __x,__node* __y){ if(__x==NULL||__y==NULL)return __x?__x:__y; else if(__x->__pri > __y->__pri){ __x->r ...

題目連結: http://tioj.infor.org/problems/1839 經典的二分搜題，對於每個門都二分搜一次他的開關是哪一個，記錄下來並使他保持開著的狀況，如此便可以往下繼續走下去，一次檢驗出一個門，所以複雜度是$O(n^2 log n)$，不過該怎麼二分搜呢?不妨每次都反轉一串開關(已知道的就不要轉)，看結果有沒有變成跟上一次不一樣(這裡的不一樣指的是說有沒有動到你要問的那個人)，也就是說如果按下去發現原本只能通到i，但現在可以走到i+1之類的，那你剛剛必定按到i了，反之如果現在可以到達i+1你按完之後只能到i那，也是有按到的，所以依此性質就可以二分搜每個門對應到的開關是誰，同時也知道如何開關才好。 p.s沒看到多筆測資害我被梗了一下下ww #include "lib1839.h" #define N 5000 int MAP[N+5], OPENED[N+5]; inline void SWAP(int,int); int main(){ while(1){ int n=Initialize(); for(int i=0;i<n;++i) MAP[i]=-1; for(int i=0;i<n;++i){ int sks = tryCombination(OPENED);if(sks==-1)sks=n; bool preSAME = (sks==i); int l=0, r=n;bool ff=(sks>i); while(r-l>1){ int mid=(l+r)/2; SWAP(l,mid); int kawaii=tryCombination(OPENED);if(kawaii==-1)kawaii=n; bool curSAME = (kawaii==i); ...

題目連結: http://contest.cc.ntu.edu.tw/npsc2011/finalSen_release.zip 不難發現在贏多少匹馬上有單調性，所以可以二分搜答案，驗證的方法用個greedy的方法，就盡量挑能贏他的馬跟他打，也就是最強的跟最強的比，如果打不贏就改成拿最廢的跟他換，大概這樣吧 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 10000 struct hr{ lld a,b; }; lld oppo[N+5]; hr my[N+5]; lld n,k; vector<lld> cur; inline bool isOK(lld); inline int fJiao(); int main(){ int t; scanf("%d",&t); while(t--){ lld l=-1,r=100000000; scanf("%lld%lld",&n,&k); for(int i=0;i<n;i++)scanf("%lld%lld",&my[i].b, &my[i].a); for(int i=0;i<n;i++)scanf("%d",&oppo[i]); sort(oppo, oppo+n,[](lld a,lld b){return a>b;}); bool jj = isOK(r); if(!jj){ puts("-1"); }else{ while(r-l!=1){ ll...

題目連結: http://tioj.infor.org/problems/1562 本題跟 骨牌遊戲 有8成7像，只差在你一定要在最後一格也要有警報器響而已，所以就直接把警報器次數-1，然後就變一模一樣的骨牌遊戲了www #include <stdio.h> typedef long long lld; int n,m; lld arr[1000 + 10]; inline bool test(lld); int main(){ while(scanf("%d %d",&n,&m)!=EOF){ m--; lld l=0,r=0; for(int i=0;i<n;i++){ scanf("%lld",&arr[i]); r+=(lld)arr[i]; l=(l>arr[i])?l:arr[i]; } l-=1; while(r-l != 1){ if(test((r+l)/2)) r=(r+l)/2; else l=(r+l)/2; } printf("%lld\n",r); } } inline bool test(lld maxS){ int k=0; lld plus=0; for(int i=0;i<n;i++){ if(plus + arr[i] > maxS){ plus=arr[i]; k++; if(k>m) return 0;...

題目連結: http://tioj.infor.org/problems/1337 本題一樣也是校內補選題，當時在寫的時候我一值莫名其妙唬爛到60分，學長一直rejudge掉我，但我又有其他騙分的方式，所以最後就因為這題我上機變第一www，不過說實在那時寫的是假解，實在不太好 正題：本題雖然可以轉成區間最大值，然後用個線段樹可以應付沒有炸彈的情況，但是若用線段樹很難維護要炸掉誰，所以不妨對答案二分搜，驗證那個答案可不可能的方式就是從左掃到右，發現疊起來值太大時就把右界最遠的線段pop掉，因為他一定後面還會影響到很多人，掃過去看要炸的數量是不是比炸彈多，過多就表示不可能，反之就有可能。不過要特別注意一下，二分搜時上界記得設成n-k，免得不小心因為常數TLE掉。複雜度$O(n log^2 n)$ #include <bits/stdc++.h> using namespace std; #define FF first #define SS second int n,k; struct block{ vector<int> end; int val; }; map<int,block> mm; inline bool test(int); int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++){ int l,r; scanf("%d%d",&l,&r); mm[l].end.push_back(r); mm[l].val++; mm[r].val--; } int uBound=n-k, lBound=-1; while(uBound-lBound!=1){ bool qq = test((uBound+lBound)/2); if(qq) uBound=(uBound+lBound)/2; else lBound=(uBound+lBound)/2; } printf("%d...

題目連結: http://tioj.infor.org/problems/1945 這題看到他詢問的次數後，應該很容易想到我們的上限就是$N+\log_2 N+2$，那那$N$必定是先單點詢問一遍，然後$\log_2 N$就是二分搜誰說謊，值得注意的是，你發現右半塊沒問題後不能又去問左半塊，要直接問左半塊的小孩，不然Query的次數會變成$2 \times N$，如果要確認會不會CE之類的話或詢問太多次，可以複製我下面的標頭檔，大概這樣吧 #include <cstdio> #define N 131072 #include "lib1945.h" int q[N+5]; int arr[N+5]; int sum[N+5]; inline int query(int l,int r){ return (l==0)?sum[r-1]&1:(sum[r-1]-sum[l-1])&1; } inline void check(int l, int r){ if(r-l==1){ int k = Query(1,q+l); if(k!=query(l,l+1)) arr[l]=Query(1,q+l); }else{ int m=(l+r)/2; int fromXian = Query(m-l, q+l); int fromOrigin = query(l,m); if(fromOrigin == fromXian) check(m,r); else check(l,m); } } int main(){ Init(); for(int i=0;i<N;i++) q[i]=i; ...

題目連結: http://tioj.infor.org/problems/1465 本題其實跟 TIOJ 1432 很像，一樣都二分搜答案，上界是序列和，下界是序列中最大值-1，不過他比較麻煩的地方是他在輸出時要把劃分好的結構輸出，所以當我們搜到答案以後，還要再從後面爬一遍，然後看要把分隔符號塞在那，不過為何是從後面爬呢，因為他想要讓前面的人的項數最少，那就是要讓後面的人項數最多，所以就讓後面每個人都拿到極限就好，另外一個值得注意的重點是因為他要讓每個人都抄到書，所以我們還要判斷一下剩下的項數根剩下的人數是否一樣了，若是就要在每個地方加上分隔符號 #include <stdio.h> #include <vector> typedef long long lld; #define PB push_back using std::vector; int n,m; int arr[500 + 10]; inline bool test(int); int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); lld l=0,r=0; for(int i=0;i<n;i++){ scanf("%d",&arr[i]); r+=(lld)arr[i]; l=(l>arr[i])?l:arr[i]; } l-=1; while(r-l != 1){ if(test((r+l)/2)) r=(r+l)/2; else l=(r+l)/2; ...

題目連結: http://tioj.infor.org/problems/1432 本題直接二分搜答案吧，值得注意的是最初始的上界顯然是數列和，但下界要注意的是它是數列中的最大值-1，因為顯然小於最大值-1的數一定會讓他壞掉，然後驗證二分搜就直接跑過去算，大概醬吧XD #include <stdio.h> typedef long long lld; int n,m; lld arr[1000 + 10]; inline bool test(lld); int main(){ scanf("%d %d",&n,&m); while(n!=0 || m!=0){ lld l=0,r=0; for(int i=0;i<n;i++){ scanf("%lld",&arr[i]); r+=(lld)arr[i]; l=(l>arr[i])?l:arr[i]; } l-=1; while(r-l != 1){ if(test((r+l)/2)) r=(r+l)/2; else l=(r+l)/2; } printf("%lld\n",r); scanf("%d %d",&n,&m); } } inline bool test(lld maxS){ int k=0; lld plus=0; for(int i=0;i<n;i++){ if(plus + arr[i] > maxS){ ...