頹coding

題目連結： 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(">\\\\<"); } }

題目連結： http://codeforces.com/contest/862/problem/C 需要構造一個長度為n的序列，其全部xor起來等於k。 可以發現0^1^2^3為0 ，4^5^6^7為0，8^9^10^11為0........。 所以先構造出n%4個數字其xor總和為k，接著再如上所寫的規律一組一組丟進ans。 接著就特判一些東西，會無解的可能情況只有n = 2和k = 0的時候，同理當(n%4 = 2,k = 0)時因為無法構造出2個數字xor = 0，所以先隨便丟一些數字進去再構造即可。 # 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 N 1000000 using namespace std; typedef pair< int , int > Pair; vector< int > ans; bitset< 1000006 > ok; int tmp = ( 1 << 18 )- 1 ,t = 0 ; int main (){jizz int n,k;cin >> n >> k; bool flag = 0; if(n == 2 && !k)return cout << "NO" << endl, 0; if(n%4 == 2 && !k){ fla...

題目連結： http://tioj.ck.tp.edu.tw/problems/1202 可以用Heap維護～ 當時間點到達房子的左界就push進去，超過右界就pop出來。 # 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); # define endl '\n' using namespace std; typedef pair< int , int > Pair; priority_queue<Pair , vector<Pair> ,less<Pair> > pq; vector< int > v,g; struct Ken{ int l,h,r; bool operator < (const Ken &x)const{ return l < x.l; } }a[ 30004 ]; int main (){jizz int n,t; while(cin >> n ,n){ v. clear (); g. clear (); t = 0; while(!pq. empty ())pq. pop (); pq. push ({0,2147483647}); for(int i = 0 ; i < n ; i++){ cin >> a[i] .l >> a[i] .h >> a[i] .r ; g. PB (a[i] .l ),g. PB (a[i] .r ); } sort (a,a+n); sort (g. begin (),g. end ()); for(int i : g){ ...

題目連結： http://tioj.ck.tp.edu.tw/problems/1359 你可以把每個數字加起來在看是少哪個數字，可是這樣會用太多Ask()。 不難觀察出來，把所有數字的第i位有幾個1找出來，那便可以找出丟失的數的那一位是1或0。 與第i位與丟失的數不同的數字便不可能是答案， 因此不用在 Ask()那個數字。 # include < iostream > # include < algorithm > # include < cmath > # include < bitset > # include < queue > # include < vector > # include " lib1359.h " # 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; vector< int > v,v2,v3; bitset< 105 > ok; int main (){ int n = Initialize(); int lo = 31 - __builtin_clz(n-1); int ans = 0; for(int i = 1; i < n ; i++)v. PB (i); for(int i = 0 ; i <= lo ; i++){ int tmp = 0; v2. clear ();v3. clear (); for(int j = 0 ; j < n ; j++)if(!ok[j] && j&(1 << i))tmp++; ...

題目連結： http://tioj.ck.tp.edu.tw/problems/1111 判斷不少的DFS題。 # include < bits/stdc++.h > # define endl '\n' using namespace std; int n; string s[ 505 ]; int ans[ 5 ]; int gx[ 8 ] = {1,0,-1,0,1,1,-1,-1},gy[ 8 ] = {0,1,0,-1,1,-1,1,-1}; bool is (int l,int r,int ll,int rr){ if(ll < 0 || ll >= n || rr < 0 || rr >= n)return 1; return s[l][r] != s[ll][rr]; } int DFS (int x,int y,int st,int f){ if(st == 1){ int tmp = 0; for(int i = 0 ; i < 8 ; i++){ int xx = x+gx[i],yy = y+gy[i]; if(xx < n && xx >= 0 &&yy < n && yy >= 0&&s[xx][yy] == s[x][y] && is(x,y,x-gx[i],y-gy[i])){ tmp += DFS(xx,yy,st+1,i); } } return tmp; }int t = x+gx[f],p = y+gy[f]; if(st == 5){ if(t < n && t >= 0 &&p < n && p >= 0 && s[t][p] == s[x][y])return 0; return 1; }if(t ...

題目連結： http://tioj.infor.org/problems/1990 可以直接利用索引值交換，來取代陣列中的值的交換。 # 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; int r[ 1000006 ],c[ 1000006 ]; int main (){jizz int n,m;cin >> n >> m; s = new string*[n+1]; for(int i = 1 ; i <= n ; i++){ s[i] = new string[m+1]; r[i] = i; for(int j = 1; j <= m ; j++){ c[j] = j; cin >> s[i][j]; } } int q;cin >>q; while(q--){ char cc;cin >> cc; if(cc == 'S'){ int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y...

題目連結： http://tioj.infor.org/contests/55/problems/1993 背包問題，但是需要用bitset壓常數。 # 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; bitset< 100005 > ok; int main (){jizz int t;cin >> t; while(t--){ ok. reset (); int n,h;cin >> n >> h; ok[0] = 1; for(int i = 0 ; i < n ; i++){ int a,b,c;cin >> a >> b >> c; ok = (ok << a)|(ok << b)|(ok << c); } int ans = 0; for(int i = 0 ; i <= h ; i++)if(ok[i])ans = i; if(!ans)cout <<"no solution" << endl; ...

題目連結： http://tioj.infor.org/problems/1991 不難發現答案可以利用前綴和來維護，既然是二維的那就用前綴和的前綴和來維護。 一個記放橫的答案，另一個記放直的答案。 因為陣列難先開好，所以把座標Hash掉。 # 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 r,c; bitset< 1000006 > box; int a[ 1000006 ],b[ 1000006 ]; inline int h (int x,int y){ if(x < 1 || x > r || y < 1 || y > c)return 1000005; return c*(x-1)+y; } int main (){jizz cin >> r >> c; for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ bool o;cin >> o; box[ h (i,j)] = o; } } for(int i = 1; i <= r; i++){ for(int j =...

題目連結： http://tioj.infor.org/problems/1994 裸裸的遞迴下去，判斷朝向哪一邊即可～ 我的code挺暴力的>< # 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 a[ 2050 ][ 2050 ]; void make (int x,int y,int l,int r,int sta){ if(r - l == 3){ if(sta == 1)a[x][y] = l,a[x+1][y] = l+1,a[x+1][y+1] = r-1,a[x][y+1] = r; if(sta == 2)a[x][y] = l,a[x+1][y] = r,a[x+1][y+1] = r-1,a[x][y+1] = l+1; if(sta == 3)a[x][y] = r-1,a[x+1][y] = r,a[x+1][y+1] = l,a[x][y+1] = l+1; if(sta == 4)a[x][y] = r-1,a[x+1][y] = l+1,a[x+1][y+1] = l,a[x][y+1] = r; return; } int t = (r-l+1)/4; int p = sqrt(r-l+1)/2; if(sta ...

題目連結： http://tioj.infor.org/problems/1388 dp[l][r]代表區間(l,r)的最佳解，而(r-l+1)的奇偶將判斷他們是要用加的還是減的。 # include < iostream > # define lld long long # define jizz cin.tie(0);ios_base::sync_with_stdio(0); # define endl '\n' using namespace std; lld dp[ 105 ][ 105 ]; int main (){jizz int n; while(cin >> n){ fill(&dp[0][0],&dp[105][105],0); for(int i = 1; i <= n ; i++)cin >> dp[i][i]; for(int j = 2; j <= n ; j++){ for(int i = j-1 ; i >= 1 ; i--){ for(int k = i ; k < j ; k++){ dp[i][j] = max(dp[i][j],((j-i+1)&1 ? dp[i][k]*dp[k+1][j] : dp[i][k]+dp[k+1][j])); } } } cout << dp[1][n] << endl; } return 0; }

題目連結： http://tioj.infor.org/problems/1699 莫隊算法的經典題，區間眾數。 對數值離散化之後，開陣列紀錄數字 x 出現了幾次，以及有幾種數字出現了 y 次。 # 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 Query{ int l,r,k,id,lid; bool operator < (const Query & x) const{ return lid == x.lid ? r < x.r : lid < x.lid; } }q[ 1000005 ]; bitset< 1000005 > as; int n,m,t,a[ 50005 ],ans; int num[ 50005 ],cnt[ 50005 ]; void add (int x){ cnt[num[x]]--; num[x]++; cnt[num[x]]++; ans = max(ans,num[x]); } void sub (int x){ cnt[num[x]]--; num[x]--; cnt[num[x]]++; if(!cnt[ans])ans--; } void MO (){ sort(q,q+...

題目連結： http://tioj.infor.org/problems/1279 從數字最大的那格一路選下來會是最佳解。 # 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 gx[] = {0,1,0,-1},gy[] = {1,0,-1,0}; struct Ken{ int w,x,y; bool operator<(const Ken &_)const{ return _.w > w; } }; priority_queue<Ken> pq; bitset< 1005 > ok[ 1005 ]; int a[ 1005 ][ 1005 ]; int main (){jizz int n,m;cin >> n >> m; lld ans = 0; for(int i = 0 ; i < n ; i++){ for(int j = 0 ;j < m ; j++){ cin >> a[i][j]; pq. push ({a[i][j],i,j}); ans += a[i][j]; } } while(...

題目連結： http://tioj.infor.org/problems/1546 不難發現做什麼操作的順序並不重要，一定有一位必輸，因此只要把可以做幾次操作算出來再mod N即可。 因為a xor b xor b 會等於 a ，所以可以觀察出[a][b]項 其實就是 [0][0] xor [a][0] xor [0][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; int u[ 10004 ],l[ 10004 ]; lld ans,p,q; inline lld count (int x){ if(x >= q)return q-p+1; if(x < p)return 0; return x-p+1; } inline int num (int x,int y){ if(x == 0)return u[y]; if(y == 0)return l[x]; return u[0]^l[x]^u[y]; } int main (){jizz int n,m;cin >> n >> m >> p >> q; ans = m*m-2*m+1; for(int i = 0 ; i < m ; i++)cin >> u[i]...

題目連結： http://tioj.infor.org/problems/1172 nth_element() 可以將第n個放在陣列第n個位置而他的左方是比他的，右方是比他大的。 而d陣列具有單調性，所以我們可以用二分的方法去做。 d[i]在左邊就用左邊的陣列去做，右邊亦然。 # include " lib1172.h " # include < algorithm > using namespace std; int aa[ 1000005 ],b[ 105 ],r[ 105 ]; void find (int l,int r,int ll,int rr){ if(l == r || rr == ll)return; nth_element(aa+l,aa+b[(ll+rr)/2],aa+r,[](int x,int y){return comp(x,y);}); find(l,b[(ll+rr)/2],ll,(ll+rr)/2); find(b[(ll+rr)/2]+1,r,(ll+rr)/2+1,rr); } void query (int n,int d[],int l,int ans[]){ for(int i = 0 ; i < n ; i++)aa[i] = i; for(int j = 0 ; j < l ; j++)b[j] = d[j]; find(0,n,0,l); for(int i = 0; i < l; i ++)ans[i] = aa[d[i]]; }

題目連結： http://tioj.infor.org/problems/1694 題目要求區間的逆序數對量，可以寫莫隊，並用BIT維護[L+-1,R+-1]的情況。 我因為ans[]只開到23000而吃了7次MLEＱＱ # 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 N 23000 using namespace std; typedef pair< int , int > Pair; int a[N+ 5 ],n,Q,cur_ans; int ans[ 200005 ]; struct Query{ int l,r,id,Lid; bool operator<(const Query &x)const{ return Lid == x.Lid ? r < x.r : Lid < x.Lid; } }q[ 200005 ]; struct BIT{ int b[N+5]; void update(int x,int e){ while(x <= n){ b[x]+=e; x += x&-x; } } int query (int x){ int tmp = 0; while(x){ tmp += b[x]; ...