頹coding

題目連結： http://tioj.ck.tp.edu.tw/problems/1604 把時間排序然後dp。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; struct Node{ lld id,st,w; bool operator<(const Node &x)const{ return w < x.w; } }; vector<Node> w; vector<lld> chu[ 1005 ]; lld dp[ 1005 ]; lld *p; int main (){jizz fill(dp,dp+1005,-1); lld s,e,m,a,b;cin >> s >> e >> m >> a >> b; p = new lld[a+b+5]; for(int i = 0 ; i < m ; i++){ for(int j = 0 ; j < a+b ; j++){ lld t;cin >> t; chu[i]. PB (t); w. PB ({i,j,t}); } } bool t = 0; sort(w. begin (),w....

題目連結： http://tioj.ck.tp.edu.tw/problems/1974 不難發現可以利用掃描線的方法，掃過x軸，就能知道選擇x軸第 i 點會垂直經過哪些矩形，這時只要找出那從哪個點 j 水平發射會經過矩形價值總合對大，因為也要考慮到垂直已經算進去的那些矩形，所以可以用線段樹維護區間加值、區間詢問。 # include < iostream > # include < algorithm > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' # define N 100005 # define M (l+r)/2 using namespace std; typedef pair< int , int > Pair; vector< int > vx,vy,ouch[ 2 *N]; int X1[N],X2[N],Y1[N],Y2[N],w[N],n,m; bitset<N> in; struct Node{ int w,tag; }seg[ 11 *N]; inline void pull (int id){ seg[id] .w = max(seg[id << 1] .w ,seg[id << 1|1] .w ); } inline void push (int id){ if(seg[id] .tag == 0)return; seg[id << 1] .w += seg[id] .tag ; seg[id << 1] .tag += seg[id] .tag ; s...

題目連結： http://tioj.ck.tp.edu.tw/problems/2006 隨便亂做就可以了，枚舉每一張牌看是不是聽這張，再枚舉是用哪張牌拆將，接著就greedy作，能湊成三個一組的就湊，不能的就往後配。 # include < bits/stdc++.h > # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define lld long long # define F first # define S second # define MOD 1000000007 using namespace std; typedef pair< int , int > Pair; int cnt[ 405 ],tmp[ 405 ]; int n,m; bool check (){ for(int j = 1; j <= n; j++){ if(cnt[j] < 2)continue; for(int i = 1; i <= n ; i++)tmp[i] = cnt[i]; tmp[j] -= 2; bool flag = 0; for(int i = 1; i <= n-2 ; i++){ tmp[i] %= 3; if(tmp[i] <= tmp[i+1] && tmp[i+2] >= tmp[i]){ tmp[i+1] -= tmp[i]; tmp[i+2] -= tmp[i]; tmp[i] = 0; }else {flag = 1;break;} } if(!(tmp[n]%3) && !(tmp[n-1]%3) && !(tmp[n-2]%3) && !flag )return 1; } re...

題目連結： http://tioj.ck.tp.edu.tw/problems/1768 這題不難，但是我超垃圾沒有想出來。 待補做法。 # include < bits/stdc++.h > # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define lld long long # define F first # define S second # define MOD 1000000007 using namespace std; typedef pair< int , int > Pair; lld a[ 20000005 ]; int n; lld a1,a2; signed main (){jizz cin >>n; for(int i = 1 ; i <= n ; i++)cin >> a[i],a1 += a[i],a2 += i*a[i]; if(a2%a1 == 0)return cout <<0 << ' '<<(a2/a1)-1 <<endl,0; for(int i = 1 ; i < n/2 ; i++){ a2 -= i*a[i]; a2 -= (n-i+1)*a[n-i+1]; a2 += (n-i+1)*a[i]; a2 += i*a[n-i+1]; if(a2%a1 == 0)return cout <<i << ' '<<(a2/a1)-1 <<endl,0; } return 0; }

題目連結： http://codeforces.com/problemset/problem/877/E 既然是對子樹做操作，那我們可以把樹壓平，並用線段樹區間改值、區間詢問。 # include < bits/stdc++.h > # define PB push_back # define N 200005 # define M (l+r)/2 # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; struct Node{ int w; bool tag; }seg[ 4 * N]; int n,t; int b[N],a[N]; vector< int > v[N]; int in[N],out[N]; void DFS (int now){ in[now] = ++t; a[t] = b[now]; for(int i : v[now]) DFS (i); out[now] = t; } void pull (int id){ seg[id] .w = seg[id << 1] .w + seg[id << 1 | 1] .w ; } void push (int id, int l ,int r){ if(seg[id] .tag == 0 || l == r)return; seg[id << 1] .w = M-l+1-seg[id << 1] .w ; seg[id <<1 | 1] .w = r-M-seg[id <<1 |1] .w ; seg[id << 1] .tag ^= 1; seg[id <<1 | 1] .tag ^= 1; seg[id] .tag = 0; } void build (int l,int r,int id){ if(l == r){ seg[id] .w = a[l]; retu...

題目連結： http://codeforces.com/problemset/problem/609/F 可以用青蛙的位置建一顆線段樹，存青哇所能吃到的位置的最大值。 對於這隻蚊子，先二分搜找到最後一隻位置小於蚊子的青蛙，接著區間搜尋哪一隻青蛙是可以吃到且是最左邊的。 開個multiset存哪幾隻蚊子先前沒被吃掉，如果有青蛙可以吃的距離有增加，就找multiset內有沒有蚊子可以被吃掉。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # include < set > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' # define N 200005 # define M (l+r)/2 # define INF 2147483647 using namespace std; typedef pair< int , int > Pair; int n,m; Pair x[N]; int seg[ 4 *N],sol[N],ans[N]; multiset<Pair> s; void pull (int id){ seg[id] = max(seg[id<<1],seg[id<<1|1]); } void build (int l,int r, int id){ if(l == r){ seg[id] = x[sol[l]] .F +x[sol[l]] .S ; return; } build...

題目連結： http://codeforces.com/problemset/problem/600/E 題目為為子樹的眾數問題。 不難發現樹壓扁可以轉成序列區間眾數，因此再用莫隊去做。 # include < bits/stdc++.h > # define PB push_back # define F first # define S second # define lld long long # define N 100005 # define debug cout << "a" <<endl; using namespace std; typedef pair< int , int > Pair; struct Query{ int l,r,lid,id; bool operator < (const Query &x)const{ return lid == x .lid ? r < x .r : lid < x .lid ; } }q[N]; int n; int color[N]; vector< int > v[N],g; int in[N],out[N],sz[N],mx,t; lld h[N],ans[N],sum; void DFS (int now,int fa){ in[now] = t++; g. PB (color[now]); for(int i : v[now]){ if(i != fa) DFS (i,now); } out[now] = t-1; } void add (int x){ ++sz[x]; h[sz[x]] += x; mx = max(mx,sz[x]); } void sub (int x){ h[sz[x]] -= x; sz[x]--; if(!h[mx])mx--; } void MO (){ int L = 0,R = 0; add(g[L]); for(i...

題目連結： http://tioj.ck.tp.edu.tw/problems/1996 求最短路徑的題目，邊權只有0,8,16這三種。 當邊權為0時可以直接將兩點合併成一點，當邊權為8就建起一條邊，當邊權為16就開一個新的點變成連兩次邊權8。 因為邊權都只剩8，所以BFS找最短路即可。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # include " lib1996.h " # define lld long long # define PB push_back # define INF 2147483647 # define N 6000005 using namespace std; typedef pair< int , int > Pair; struct DJS{ int p[N]; void Init(){for(int i = 0 ; i < N ; i++)p[i] = i;} inline int query (int x){return p[x] == x ? x : p[x] = query(p[x]);} void unite (int x,int y){ x = query(x);y = query(y); p[x] = y; } }djs; int dis[N]; vector< int > v[N]; void init (int n,int m,int A[],int B[],int K[]){ djs. Init (); fill(dis,dis+N,INF); int t = n+1; for(int i = 0 ; i < m ; i++)if(!K[i])djs. unite (A[i],B[i]); ...

題目連結： http://tioj.ck.tp.edu.tw/problems/1995 記憶體卡的超級緊。 有兩種做法，第一種是實作3Byte的整數，然後排序詢問，BIT維護前綴最大值。 不難發現第二種做法就是做Sparse Table，不難發現將該層的回答先回答，之後就可以直接覆蓋掉，這樣不難發現Sparse Table的空間複雜度可以壓到O(n)。 # include " lib1995.h " # define lo (x,y) 31-__builtin_clz(y-x+1) using namespace std; int s1[ 2500000 ],n,m; int l[ 1000006 ],r[ 1000006 ]; bitset< 1000006 > ok; int main (){ scanf("%d %d",&n,&m); for(int i = 0 ; i < m ; i++) scanf ("%d %d",&l[i],&r[i]),l[i]--,--r[i]; for(int i = 0 ; i < n ; i++) scanf ("%d",&s1[i]); for(int i = 0 ; i < m ; i++)if( lo (l[i],r[i]) == 0)l[i] = s1[l[i]],ok[i] = 1; for(int i = 1; (1 << i) <= n ; i++){ for(int j = 0 ; j+(1 << i) <= n ; j++) s1[j] = ( max (s1[j],s1[j+(1<<(i-1))])); for(int j = 0 ; j < m ; j++) if( lo (l[j],r[j]) == i && !ok[j]) l[j] = max(s1[l[j]],s1[r[j]-(1<...

題目連結： http://tioj.ck.tp.edu.tw/problems/1561 裸次短路徑。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; struct Ken{ int to,w; }; vector<Ken> v[ 105 ]; Pair dis[ 105 ]; int main (){jizz int n,m; while(cin >> n >> m){ fill(dis,dis+105,(Pair){1e9,1e9}); for(int i = 0 ; i < 105 ; i++)v[i]. clear (); while(m--){ int a,b,c;cin >> a >> b >> c; v[a]. PB ({b,c}); v[b]. PB ({a,c}); } int st,ed;cin >> st >> ed; priority_queue<Pair,vector<Pair> , greater<Pair> > pq; ...

題目連結： http://tioj.ck.tp.edu.tw/problems/1997 可以紀錄dp[n][k]代表前n個切了k刀，轉移式 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+t*a[i]，當j是奇數t = -1，反之t = 1。 # include < iostream > # define lld long long # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; typedef pair< int , int > Pair; lld dp[ 1000006 ][ 7 ]; int fa[ 1000006 ][ 7 ]; int main (){jizz int n,k;cin >> n >> k;k--; for(int i = 1 ; i <= n ; i++){ int a,t;cin >> a; dp[i][0] = dp[i-1][0]+a; for(int j = 1 ; j <= k && j < i ; j++){ t = (j&1 ? -1 : 1); if(j == i-1){ fa[i][j] = i; dp[i][j] = dp[i-1][j-1]+t*a; } else if(dp[i-1][j]+t*a >= dp[i-1][j-1]+t*a){ fa[i][j] = fa[i-1][j]; dp[i][j] = dp[i-1][j]+t*a; }else{ fa[i][j] = i; dp[i][j] = dp[i-1][j-1]+t*a; } ...

題目連結： http://tioj.ck.tp.edu.tw/problems/1998 可以把字串處理成數字，先排序左界，二分搜找最後一個小於等於該數字的位置，所有左界小於等於詢問的數字便在此位置的前綴，因此只要維護前綴最大值即可。 # include < bits/stdc++.h > # define PB push_back # define F first # define S second # define lld long long # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair<lld,lld> Pair; lld tmp,t,p; string s; vector<Pair> v; bool find (lld t){ int l = 0,r = v. size (); while(r-l != 1){ int M = (l+r)/2; if(v[M] .F > t)r = M; else l = M; } return v[l] .F <= t && v[l] .S >= t; } int main (){jizz int n,m;cin >> n >> m; for(int i = 0 ; i < n ;i ++){ cin >>s; tmp = 0,t = 0; for(int i = 0 ; i < s. size (); i++){ if(s[i] == '.')t <<= 8,t += tmp,tmp = 0; else if(s[i] >= '0' && s[i] <= '9')tmp *= 10,t...

題目連結： http://tioj.ck.tp.edu.tw/problems/1420 要看這個地雷有沒有和別的地雷有重疊到的地方，其實就是看這個地雷的周圍24塊，並用disjoint set維護。 # include < bits/stdc++.h > # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); using namespace std; typedef pair< int , int > Pair; bitset< 50004 > is; int n,m,c; int gx[ 24 ] = {0,0,1,-1,1,1,-1,-1,2,2,2,2,2,-2,-2,-2,-2,-2,1,0,-1,1,0,-1}, gy[ 24 ] = {1,-1,0,0,-1,1,-1,1,0,1,2,-1,-2,0,1,2,-1,-2,2,2,2,-2,-2,-2}; struct DJS{ int p[50004]; void init(){for(int i = 0 ; i < 50004 ; i++)p[i] = i;} int query (int x){return p[x] == x ? x : p[x] = query(p[x]);} void unite (int x,int y){x = query(x);y = query(y);p[x] = y;} int count (){ int ans = 0; for(int i = 1 ; i <= c; i++ ){ int tmp = query(i); if(!is[tmp])ans++; is[tmp] = 1; } return ans; } }djs; map<Pair, int > mp; int X[ 50004 ],Y...

題目連結： http://tioj.ck.tp.edu.tw/problems/1721 用stack維護嚴格遞減。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # include < stack > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int a[ 100005 ],ans[ 100005 ]; int main (){jizz int n; while(cin >> n){ stack<Pair> s; fill(ans,ans+100005,0); for(int i = 1 ; i <= n ;i++)cin >> a[i]; for(int i = 1 ; i <= n ; i++){ while(!s. empty () && s. top () .F < a[i])s. pop (); if(!s. empty ())ans[i] += (i-s. top () .S ); else ans[i] += i-1; s. push ({a[i],i}); } while(!s. empty ())s. pop ...

題目連結： http://codeforces.com/contest/510/problem/C 先比較字串，對字元間的大小關係建一張圖，如果'a' < 'b'那'a'就連一條邊給'b'。 接著就找該圖的拓墣排序即可。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; string s[ 105 ],ans; bitset< 30 > g[ 30 ]; int in[ 30 ]; bool topu (){ queue<int> q; for(int i = 0 ; i < 26 ; i++)if(!in[i])q. push (i),ans+='a'+i; while(!q. empty ()){ int t = q. front ();q. pop (); for(int i = 0 ; i < 26 ; i++){ if(g[t][i] && (--in[i]) == 0){ q. push (i),ans += 'a'+i; } } } return an...

題目連結： http://tioj.ck.tp.edu.tw/problems/1445 裸次小生成樹。 用Kruskal做最小生成樹，然後LCA維護路徑最大值來枚舉所有可以換得邊。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int ,lld> Pair; struct Edge{ int from,to; lld w; bool operator<(const Edge &x)const{ return w < x.w; } }E[ 500005 ]; struct DJS{ int p[1005]; void init(){for(int i = 0 ; i < 1005; i++)p[i] = i;} int query (int x){return p[x] == x?x:p[x] = query(p[x]);} void unite (int x,int y){ x = query(x); y = query(y); p[x] = y; } bool same (int x,int y){return query(x) == query(y);} }djs; lld mst,smst; vector<Pair> v...

題目連結： http://tioj.ck.tp.edu.tw/problems/1163 最小生成樹＋利用LCA找路徑最大值。 原本我以為我寫LCA一定會寫出很多BUG然後在那邊狂刷，結果沒想到只WA一兩次而已。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' # define maxn 30004 using namespace std; typedef pair< int , int > Pair; struct Edge{ int from,to,w; bool operator<(const Edge& x)const{ return w<x.w; } }E[ 50005 ]; struct DJS{ int p[maxn]; void init(){ for(int i = 0 ;i < maxn ; i++)p[i] = i; } int query (int x){ return p[x] == x? x : p[x] = query(p[x]); } void unite (int x,int y){ x = p[x];y = p[y]; p[y] = x; } bool same (int x,int y){ return query(x) == ...

題目連結： http://codeforces.com/contest/864/problem/E 類似背包的dp，dp[i][j] = max(dp[i][j-1],dp[i-1][j],dp[i-1][j-item[i].t]+item[i].p)。 最後再遞迴找是從哪裡轉移過來的。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; struct Ken{ int t,d,p,id; bool operator<(const Ken &x)const{ return d < x.d; } }item[ 105 ]; int dp[ 105 ][ 2005 ],ans; pair< int , Pair> f[ 105 ][ 2005 ]; vector< int > v; void solve (int x,int y){ if(f[x][y] .F == 0)return; ans++; v. PB (f[x][y] .F ); solve(f[x][y] .S .F ,f[x][y] .S .S ); } int main (){jizz int n;cin >> n; for(int i = 1 ; i <= n ;...

題目連結： http://tioj.ck.tp.edu.tw/problems/1337 因為答案具有單調性，所以可以對答案二分搜。 驗證答案的時候可以從左掃過去，如果這一點的隕石數量大於當前防護罩數量的話就需要把隕石打掉，打掉右界最大值的那一顆隕石會是最佳解（用priority_queue維護），最後檢查隕石數量有沒有大於上限即可。 因為數值範圍太大所以要離散化。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # define lld long long # define PB push_back # define F first # define S second # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; typedef pair< int , int > Pair; int n,k; vector< int > v; vector<Pair> l; int b[ 200005 ]; bool check (int x){ priority_queue<int, vector<int> , less<int> > pq; fill(b,b+200005,0); int p = 0,t = 0,m = k; for(int i = 0 ; i < v. size () ; i++){ while(p < n && l[p] .F == i)t++,b[l[p] .S ]++,pq. push (l[p] .S ),p++; if(b[i])t -= b[i]; in...

題目連結： https://zerojudge.tw/ShowProblem?problemid=b902 手機打code CE好多次>< 先討論當情況是一奇一偶時，可以證明先手必勝。一奇一偶拿了之後可能會變成兩偶、兩奇、一奇一偶。因為兩奇只能變成一奇一偶，那你又會回歸到原本的一奇一偶，這樣一直做下去遲早會變成(1,0)的情況，所以先手必勝。 接著是兩奇的情況，如上所述只能變成一奇一偶，所以先手必輸。 接著是兩偶的情況，兩偶可能會變成一奇一偶或兩偶（透過第二種操作），一奇一偶必輸，所以如果要贏只能變成兩偶的情形，那兩偶拿到最後一定會變成兩個一樣的數字，因為當兩偶以及兩數相等時先手必勝（這很好想吧），所以只要判斷能做多少次第二種操作的奇偶性即可知道誰必勝。 # include < iostream > using namespace std; long long g (long long a,long long b){ return b ? a/b+ g (b,a%b) : 0; } int main (){ int o;cin>>o; while(o--){ long long n,m;cin >>n>>m; int t=0; if(n&1)t++; if(m&1)t++; if(t == 0 && g(n,m)&1) puts (">//<"); else if(t==1) puts (">//<"); else puts(">\\\\<"); } }