PolarisChiba的code收藏區

題目連結： https://tioj.ck.tp.edu.tw/problems/1827 　　人生第一次寫了持久化資料結構>< ! 不過是參考了cbd的code才順利寫出來的。 　　b[i]的範圍在1e5以內所以不用離散話，二分搜答案，建持久化線段樹。 # include<bits/stdc++.h> using namespace std; const int N = 100000+10; struct node{ int val; node *l,*r; node( int v) { val = v; l = r = NULL; } }*root[N]; node* build( int L, int R) { if (L == R) return ( new node(0) ); int mid = (L+R)>>1; node *v = new node(0); v -> l = build(L,mid); v -> r = build(mid+1,R); return v; } node* modify( int L, int R,node* u, int pos ) { if (L == R) return ( new node(u -> val+1) ); node* v = new node(0); int mid = (L+R)>>1; if ( pos <=mid) { v -> r = u -> r; v -> l = modify(L,mid,u -> l, pos ); } else { v -> l = u -> l; v -> r = modify(mid+1,R,u -> r, pos ); } v -> val = v -> l -> val+v -> r -> val; re

題目連結： https://oj.infor.org/problems/17 　　counting sort. #include<bits/stdc++.h> using namespace std ; int n,a; int sor[ 109 ]; int main () { cin >> n; while(n--) { cin >> a; sor[a]++; } for(int i = 1; i <= 100; i++) while(sor[i] != 0) { cout << i << " "; sor[i]--; } }

題目連結： https://oj.infor.org/problems/18 　　h由小到大w由大到小排序，然後對w最LIS，就可以保證得到的是h1<h2、w1<w2了。 #include<bits/stdc++.h> # define F first # define S second # define pi pair<int,int> # define endl '\n' using namespace std ; int n; bool ok[ 10009 ]; pair< int , int > people[ 10009 ]; int main () { cin >> n; cin >> people[0] .F >> people[0] .S ; cout << 1 << endl; int ans = 1; fill( ok,ok+10009,true); for(int i = 1; i < n; i++) { cin >> people[i] .F >> people[i] .S ; for(int j = 0; j < i; j++) { if( (people[i] .F > people[j] .F && people[i] .S >= people[j] .S ) || (people[i] .F >= people[j] .F && people[i] .S >people[j] .S ) ) ok[i] = false; if(ok[j]) if( (people[j] .F > people[i] .F && people[j] .S >= people[i] .S ) || (people[j] .F >= peopl

題目連結： https://oj.infor.org/problems/15 　　DP，轉移式為dp[i][j] = max(a[i]+...+a[k] - dp[k+1][j], a[j]+...+a[k] - dp[i][k-1])之類的，dp[i][j]代表i~j的解，然後因為N到了1000，所以要欲處理前綴和以O(1)求出區間和。 #include<bits/stdc++.h> using namespace std ; int n; int noodle[ 1009 ]; int dp[ 1009 ][ 1009 ]; int input () { int x = 0; char cha; bool flag = true; while(cha = getchar()) { if(cha == '-') flag = false; if(cha <= '9' && cha >= '0') break; } x = cha - '0'; while(cha = getchar()) { if(cha > '9' || cha < '0') break; x = (x<<3)+(x<<1)+(cha-'0'); } return (flag)?x:-x; } void output (int x) { int res = 0; char cha[100]; if(x < 0) putchar('-'); x = abs(x); if(x == 0) putchar('0'); while(x != 0) { cha[res++] = '0'+(x%10); x /= 10; } for(int i = res-1;

題目連結： https://oj.infor.org/problems/14 　　矩陣快速冪。 #include<stdio.h> #include<algorithm> using namespace std ; typedef long long lld; const lld mmod = 1000000007ll ; lld m,n; lld m1[ 110 ][ 110 ], m2[ 110 ][ 110 ]; lld ans[ 110 ][ 110 ], tp[ 110 ][ 110 ]; inline void matrixtime (lld a[][110],lld b[][110],lld c[][110]) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) { c[i][j] = 0; for(int k = 0; k < m; k++) { c[i][j] += a[i][k]*b[k][j]; c[i][j] %= mmod; } } } inline void qpow (lld n) { for(int i = 0; i < m; i++) for(int j = 0; j < m; j++) ans[i][j] = (i==j); bool flag = false; while(n) { if(n&1) { matrixtime( ans,(!flag)?m1:m2,tp); swap( tp,ans); } if(!flag) matrixtime( m1,m1,m2); else matrixtime( m2,m2,m1); flag ^= 1;

題目連結： https://oj.infor.org/problems/77 　　聽了AY的解說才會的。 　　將平面分成四塊，題目也就可以轉變成上半塊減左半塊或是右半塊減去下半塊，所以就離線做、離散化，BIT隨便弄一弄就OK了。 #include<bits/stdc++.h> using namespace std ; int n; int a,b,c; typedef pair< int , int > pi; vector<pair< int ,pi> > v; vector< int > lis; int bitx[ 600009 ]; int bity[ 600009 ]; const int N = 600009 ; void update (int x,int i,int t) { if(t == 1) { while(i <= N) { bitx[i] += x; i += i&-i; } } else { while(i <= N) { bity[i] += x; i += i&-i; } } } int sum (int i,int t) { int res = 0; if(t == 1) { while(i > 0) { res += bitx[i]; i -= i&-i; } } else { while(i > 0) { res += bity[i]; i -= i&-i; } } return res; } int main () { cin >> n; while(n--)

題目連結： https://oj.infor.org/problems/2 　　裸的LIS。 #include<bits/stdc++.h> using namespace std ; int n; vector< int > v; int main () { cin >> n; while(n--) { int a; cin >> a; auto i = lower_bound( v. begin ( ),v. end ( ),a); if(i == v. end ( )) v. push_back ( a); else *i = a; } cout << v. size ( ) << endl; }

題目連結： https://oj.infor.org/problems/5 　　由於僅限奇回文，所以隨便觀察性質就出來了？ #include<bits/stdc++.h> using namespace std ; string s; int main () { cin >> s; string ans = s; for(int i = s. size ( )-2; i >= 0; i--) ans += s[i]; cout << ans << endl; }

題目連結： https://oj.infor.org/problems/19 　　由於a XOR b = x 的話，那麼 a XOR x = b，這應該挺顯然的吧？所以就sort後然後算一下有幾個就好了，不過要注意有可能有多個所以要upper_bound減去lower_bound。 #include<bits/stdc++.h> using namespace std ; int n,x; vector< int > a; int main () { cin >> n >> x; while(n--) { int aa; cin >> aa; a. push_back ( aa); } sort( a. begin ( ),a. end ( )); int ans = 0; for(int i = 0; i < a. size ( ); i++) { int d1 = lower_bound( a. begin ( )+i+1,a. end ( ),(a[i]^x))-a. begin ( ); int d2 = upper_bound( a. begin ( )+i+1,a. end ( ),(a[i]^x))-a. begin ( ); ans += d2-d1; } cout << ans << endl; }

題目連結： https://oj.infor.org/problems/8 　　裸的二分匹配圖，每個點的x或y至少要有一個被打到，因此要求最小點涵蓋的大小，又經由koning's theorem可知其大小等於最大匹配的大小，所以就dfs跑一跑或是太閒的話可以用flow寫寫看啦~~ #include<bits/stdc++.h> using namespace std ; int n,k; bool rock[ 509 ][ 509 ]; int my[ 509 ]; bool vis[ 509 ]; bool dfs (int x) { for(int i = 1; i <= n; i++) if(rock[x][i] && !vis[i]) { vis[i] = 1; if(!my[i] || dfs( my[i])) { my[i] = x; return true; } } return false; } int main () { cin >> n >> k; while(k--) { int a,b; cin >> a >> b; rock[a][b] = 1; } int ans = 0; for(int i = 1; i <= n; i++) { memset(vis,0, sizeof (vis)); if(! dfs ( i)) break; else ans++; } cout << ans << endl; }

題目連結： https://oj.infor.org/problems/11 　　用dsu去維護關係即可。 #include<bits/stdc++.h> # define endl '\n' using namespace std ; int n,k; int fa[ 1500009 ]; int sz[ 1500009 ]; inline void init () { for(int i = 0; i <= 3*n; i++) { fa[i] = i; sz[i] = 1; } } inline int find (int x) { return (fa[x]==x)?(fa[x]):(fa[x] = find( fa[x])); } inline bool same (int x,int y) { return ( find ( x) == find( y)); } inline void unite (int x,int y) { if( same ( x,y)) return; if(sz[ find ( x)] < sz[ find ( y)]) swap( x,y); fa[ find ( y)] = find( x); sz[ find ( x)] += sz[ find ( y)]; } int main () { ios_base::sync_with_stdio( 0); cin. tie ( 0); cin >> n >> k; int ans = 0; init( ); while(k--) { int d,x,y; cin >> d >> x >> y; if(x > n || y > n) { ans++; continue; } if(d == 1) {

題目連結： http://codeforces.com/contest/962/problem/C 　　用位元的手法亂做。 #include<bits/stdc++.h> using namespace std ; int main () { string a; cin >> a; reverse( a. begin ( ),a. end ( )); int len = a. size ( ); int ans = 1e9; for(int i = 1; i < (1<<len); i++) { int t= 0, o = 0, p = -1; vector<int> aa; aa. clear ( ); for(int j = 0; j < len; j++) { if(i&(1<<j)) { t += pow(10,o)*(a[j]-'0'); o++; aa. push_back ( j); } } if(a[aa. back ( )] == '0') continue; int tt = sqrt(t); if(tt*tt == t) { //cout << i << endl; ans = min( ans,len-o); } } if(ans == 1e9) cout << -1; else cout << ans << endl; }

題目連結： http://codeforces.com/contest/962/problem/D 　　用map亂做。 　　好感嘆我當時竟然寫得出來......。 #include<bits/stdc++.h> # define int long long using namespace std ; map< int ,priority_queue< int ,vector< int >,greater< int > > > m,ss; int n; vector<pair< int , int > > s; signed main () { cin >> n; for(int i = 0; i < n; i++) { int a; cin >> a; m[a]. push ( i); } for(auto i:m) { //cout << i .first << endl; while(i .second . size ( )) { if(i .second . size ( ) == 1) { ss[i .first ]. push ( i .second . top ( )); break; } //cout << i .second . top ( ) << " "; i .second . pop ( ); int p = i .second . top ( ); i .second . pop ( ); //cout << p << endl; m[i .first *2]. push ( p); } } s. clear ( );

題目連結： http://codeforces.com/contest/964/problem/C 　　我最近DEBUG能力明顯下降，思緒不清晰......。 　　以ｋ個做為一個循環，用1+x+x^2+...甚麼的那個公式，然後亂做就好了。 #include<bits/stdc++.h> # define int long long # define MOD 1000000009ll using namespace std ; int n,a,b,k; string s; inline int add (int aa,int bb) { aa += bb; aa %= MOD; if(aa<0) aa += MOD; return aa; } inline int mul (int aa,int bb) { aa *= bb; aa %= MOD; return add( aa,0); } inline int fast (int a,int b=MOD-2) { int res = 1; while(b) { if(b&1) res = mul( res,a); b >>= 1; a = mul( a,a); } return res; } signed main () { cin >> n >> a >> b >> k >> s; int ans = 0, neg = 0; for(int i = 0; i < k; i++) { neg = (s[i] == '+')?1:-1; ans = add( ans,neg* fast ( a,n-i)* fast ( b,i)); } int inv_a = fast( a); a = mul( fast ( inv_a,k), fast ( b,k)); int _ = (n+1)/k; if(a == 1) ans

題目連結： http://codeforces.com/contest/964/problem/D 　　觀察到偶數個點的時候，由於共有奇數個邊，但每次都只能拔掉偶數個邊，所以一定NO，而奇數則一定可以，從葉子做上來，假設拔掉了一個點，考慮其其中一個子樹，若其根的deg為奇數，則這點拔掉前為偶數，所以會先拔掉這個點才對；若為偶數，那就從這個點往下拔，由於不會出現第一種case，所以一定會拔光，因此奇數一定YES。 　　謹記遇到樹的時候要從子樹開始做之類的。 #include<bits/stdc++.h> using namespace std ; const int N = 200000 + 9 ; int n; vector< int > G[N]; int deg[N]; bool done[N]; void split (int u,int f) { cout << u << '\n'; done[u] = 1; for(auto i:G[u]) deg[i] ^= 1; for(auto i:G[u]) if(i != f && !deg[i] && !done[i]) split( i,u); } void dfs (int u,int f) { for(auto i:G[u]) if(i != f) dfs( i,u); if(!deg[u]) split( u,f); } int main () { cin >> n; for(int i = 1; i <= n; i++) { int a; cin >> a; if(a == 0) continue; G[i]. push_back ( a); G[a]. push_back ( i); deg[i] ^= 1; deg[a] ^= 1; } if(n %2 == 0) cout << "NO\n"; else cout << "YES\n&qu

題目連結： http://codeforces.com/contest/965/problem/C 　　在這裡抱怨應該沒關係吧，反正完全沒人看XD，這場從各種意義上都是一個轉折點啊(笑)，掉到了歷史上最低分了，之前所積累的心血兩次就全沒了，真的一無所有了，不過換個角度想，也不用怕再失去了(吧)。 　　原本我以為會是個凸函數，所以弄了個三分搜來寫，然後就錯了，最後推測有可能是因為圖形並非凸函數吧。 　　正解的關鍵是D<=1000，然後由於要算Arkady最多能拿多少，所以就將他視為另外一個人，因此人數就變成了t*k+1了。 #include<bits/stdc++.h> # define int long long using namespace std ; int n,k,M,D; signed main () { cin >> n >> k >> M >> D; int ans = 0, d = 1; for(int i = 1; i <= D; i++) { ans = max( ans, min ( M,n/d)*i); d += k; } cout << ans << endl; }