頹coding

題目連結： 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; }