頹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