頹coding

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