oToToT的code收藏區

題目連結: http://poj.org/problem?id=1769 一開始用cin有把連結斷開還是吃了個TLE QQ。 回到正題，本題我個人的一開始的想法其實是看看某個線段插到線段樹後可以幹嘛，後來想一想後發現有點DP的fu，狀態大概就是$dp[i]$為最遠轉移到i時的最小值，那新增一條線段的時候其實就是查$[l,r]$之間的最小值，然後把$r$那個點設成先前查到的最小值+1，因為$\displaystyle dp[i] = \min_{l \leq j \leq r}dp[j]+1 $，不過實際在寫的時候要再跟原值取個min，因為有可能r被覆蓋很多次之類的。 #include <cstdio> #include <algorithm> using std::min; const int N = 50000 + 10; const int INF = 1<<30; class SegTree{ private: int nodes[N<<2], size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} void build(int l, int r, int id){ nodes[id] = INF; if(r-l>1){ int mid=(l+r)>>1; build(l, mid, lc(id)); build(mid, r, rc(id)); } } void modify(int ql, int qr, int v, int l, int r, int id){ if(qr <= l o...

題目連結: http://arc079.contest.atcoder.jp/tasks/arc079_b 構造題，我的構造方法是假定有$n$個數且要湊出$k$次，讓最後的結果為$n-2, n-2, n-2, \cdots , n-2, n-1$，則稍微算一下後就會發現原始的數字必為$n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-2, \cdots , n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-2,n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-1 $，因為其實對於每個數他其實就只會扣掉$n$ $\lfloor \frac{k}{n} \rfloor$次，並且加上總次數減掉$\lfloor \frac{k}{n} \rfloor$的$1$，所以全部家負號後就變成這樣了，不過餘數的地方要好好處理一下(平均分給別人)，以免有地方不小心太大。 為了怕有數字超過$10^{16}+1000$這裡$N$直接取50即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); lld k;cin>>k; int n=50; cout<<n<<'\n'; for(int i=0;i<n-1;i++){ lld kn = k/n; if(i<k%n) kn++; cout<<n*kn-(k-kn)+n-2<<' '; } lld kn = k/n; cout<<n*kn-(k-kn)+n-1...

題目連結: http://poj.org/problem?id=3468 裸的線段樹，區間加值、區間查和，不過也可以用BIT做掉，不過我不太會QQ #include <iostream> #include <utility> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 100000 + 5; class SegTree{ private: PLL nodes[N<<2]; int size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} inline void push(int l, int r, int id){ if(r-l>1){ nodes[lc(id)].FF += nodes[id].FF; nodes[rc(id)].FF += nodes[id].FF; } nodes[id].SS += nodes[id].FF * (r-l); nodes[id].FF=0; } inline void pull(int l, int r,int id){ int mid=(l+r)>>1; lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l); lld rr =...

題目連結: http://tioj.infor.org/problems/1316 一開始想錯方向，以為是有一堆開頭跟結尾，然後要選一些之類的...。卡了超久做不出來後，才發現其實它就是一堆線段，然後要選一堆線段，使得同一個位置只能最多被覆蓋到兩次。那其實就直接greedy選右界最靠近左邊的就好了(因為越短，表示你越可以選到後面的)。 這裡寫了個線段樹，來判斷可不可以插入，不過應該可以不用，然後也可以直接$O(N)$的做這個操作XD #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second const int N = 4000 + 5; class SegTre{ private: struct node{ int flag=0, val=0; } nodes[N<<3]; int size; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} inline void push(int l, int r, int id){ if(r-l > 1){ nodes[lc(id)].flag+=nodes[id].flag; nodes[rc(id)].flag+=nodes[id].flag; } nodes[id].val += nodes[id].flag; nodes[id].flag=0; } inline void pull(int id){ ...

題目連結: http://tioj.infor.org/problems/1361 卡了超久....寫了支暴搜對答案也看不出個所以然，最後才發現原來沒保證$a \leq b$，所以要判一下... 回到正題，觀察一下後會發現對於$[1, x]$中出現的0的個數，考慮個位時就是看$\lfloor \frac{x}{10^1} \rfloor$，但考慮十位時則是$\lfloor \frac{x}{10^2} \rfloor \times 10$，稍微想一下就可以推出考慮第$i$位時就是看$\lfloor \frac{x}{10^i} \rfloor \times 10^{i-1}$，不過要稍微注意一下邊界，若是不足$10^{i-1}$時要修正回來。 所以對於$[l, r]$做法就是用算$[0, r]-[0, l-1]$ #include <bits/stdc++.h> using namespace std; typedef long long lld; inline int getSum(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int l, r; while(cin>>l>>r){ if(l>r) swap(l, r); cout<<getSum(r)-getSum(l-1)<<'\n'; } return 0; } inline int getSum(int x){ if(x<0) return 0; int r=1; for(lld i=10;i<=x;i*=10){ r += (x/i) * (i/10); if((x%i)<(i/10)) r -= (i/10)-(x%i)-1; } return r; }

題目連結: http://tioj.infor.org/problems/1046 一開始看到的時候不知所措，後來瀚瀚(?講了我才知道。其實只要枚舉最上面那排要怎麼按，下面的所有按鈕就可以知道要怎麼按了，因為一定要把上面的按掉這樣，複雜度$O(2^N)$。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define X first #define Y second const int INF = 1000000; char game[10][10]; int n, m; int dfs1(int); int dfs2(); inline bool check(); inline void click(int,int); int main(){ while(true){ char c; for(n=0;;n++){ c=getchar(); for(m=0;c!='\n';m++){ if(c=='#')break; game[n][m]=c; c=getchar(); } if(c=='#')break; game[n][m]='\0'; if(game[n][0]=='\0') break; } if(c=='#')break; m=strlen(game[0]); int ans = dfs1(0); if(ans >= INF) puts("Another Skeleton in the Ancient Tom...

題目連結: http://tioj.infor.org/problems/1331 看一眼大概就可以發現這就是一個經典的矩陣優化DP的題目，稍微算一下後得到轉移矩陣$ \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix} $，所以要求$a_n$其實就是算$ \begin{bmatrix} a_0 & a_1 \\ \end{bmatrix} \times \begin{bmatrix} 0 & x \\ 1 & y \\ \end{bmatrix}^n = \begin{bmatrix} a_n & a_{n+1} \\ \end{bmatrix}$ ，然後冪次的部分用快速冪解決。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef unsigned long long llu; const llu mod = 1LL<<32; auto A = new llu[2][2]; auto B = new llu[2][2]; auto C = new llu[2][2]; auto F = new llu[2][2]; void mTimes(llu[2][2],llu[2][2],llu[2][2],int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); lld n, a, b, x, y; while(cin>>n, n>=0){ cin>>a>>b>>x>>y; F[0][0]=a; F[0][1]=b; A[0][0]=0; A[0][1]=x; A[1][0]=1; A[1][1]=y; B[0][0]=...

題目連結: http://tioj.infor.org/problems/1145 原本看第一眼覺得跟經典的矩陣安排一樣，結果寫下去才發現比矩陣安排麻煩，因為他不只一種計算方法，所以如果單純算最大值的話，會不符合最佳子結構而不能DP(例如你可能減一個負數反而會變大，但是負數並不是最佳的)。所以我同時存了最大及最小值，這時加法時的最大值必定是兩個最大值相加，同理最小值；減法的話則反過來就好了，然而乘法的話有可能是負的乘負的，正的乘負的...比較複雜，所以我就直接讓他是所有情況取min跟max了。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 50 + 5; const lld INF = 1LL<<40; char str[1000]; vector<int> nums; vector<char> opt; PLL dp[N][N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>str; nums.PB(0); for(int i=0;str[i]!='\0';i++){ if('0'<=str[i] and str[i]<='9'){ nums.back() = nums.back()*10+str[i]-'0'; }else{ opt.PB(str[i]); nums.PB(0); } } int cnt=nums.size();...

題目連結: http://tioj.infor.org/problems/1045 原本看到的時候想用線段樹直接揍他，結果寫一寫覺得卡卡的，然後就被嗆說幹嘛用線段樹做了QQ。想了想才發現可以離散化後直接對序列操作，複雜度$O(N^2)$，也就是把序列乘二或除二，然後算一下他的變化量來維護整段的總和。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; #define ALL(x) (x).begin(), (x).end() const int N = 10000 + 1; class Lisan{ private: vector<int> v; public: inline void init(){ v.clear(); } inline void insert(int x){ v.PB(x); } inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v),x)); } inline int inv_get(int x){ return v[x]; } } li; struct Opt{ int pos, l, r, v; }; vector<Opt> op...

題目連結: http://tioj.infor.org/problems/1489 經典(?的雙指針題，每次右界擴充的時候就判斷一下左界的那個字元是不是出現超過一次了，如果超過一次表示他其實不必要。此外透過計算每個字元出現的次數也可以計算是否26個字母都出現過了，作法大概就是發現這個字元出現了，且之前他沒出現過就讓某一個變數增加一。最後判一下該變數是否為26就好了。 #include <bits/stdc++.h> using namespace std; const int INF = 2000000; const int N = 1000000 + 5; char str[N]; int cnt[256], c=0; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n, n){ fill(cnt, cnt+256, 0); c=0; cin>>str; int ansL=0, ansR=INF; int curL=0, curR; for(curR=0;curR<n;curR++){ if(cnt[(unsigned)str[curR]]==0) c++; cnt[(unsigned)str[curR]]++; while(cnt[(unsigned)str[curL]]>1){ cnt[(unsigned)str[curL]]--; curL++; } if(c==26){ if(ansR-ansL > curR-curL){ ansR...

題目連結: http://tioj.infor.org/problems/1272 給定一棵樹，然後要求詢問某個節點的值是偶數或奇數，或者對一整顆子樹加一。不妨把樹壓平後，透過進入時間戳與出去的時間戳，得到一個區間$[in[x], out[x])$，而其實這個區間就是x的子樹，所以發現要對子樹加值就是對那個區間加值，而查詢則是查$in[x]$。把問題轉成單點查詢區間加值後，其實一個BIT就可以做到了。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; class BIT{ private: int arr[N], size=0; inline int lowbit(int x){ return x&-x; } public: void init(int s){ fill(arr, arr+s, 0); size=s; } //1-base (l, r] void add(int l, int r, int v){ add(l, -v); add(r, v); } void add(int s, int v){ while(s){ arr[s]+=v; s-=lowbit(s); } } int query(int x){ int r=0; while(x<size){ ...

題目連結: http://tioj.infor.org/problems/1199 枚舉x並且用快速冪加速次方的地方，就可以做到$O(y log n)$了。 #include <bits/stdc++.h> using namespace std; int qPow(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int a, n, y; while(cin>>a>>n>>y, a or n or y){ int ans=0; for(int i=0;i<=y-1;i++){ if(n==0 and i==0) continue; if(qPow(i, n, y)==a) ans++; } cout<<ans<<'\n'; } return 0; } int qPow(int a, int b, int m){ int r=1; while(b){ if(b&1) r=(r*a)%m; b>>=1; a=(a*a)%m; } return r%m; }

題目連結: http://tioj.infor.org/problems/1488 經典的DP題，狀態$dp[i][j]$是將矩陣$[i,j]$乘起來所需的最小值，稍微想一下後就會發現轉移就是$ dp[i][j] = \min_{ \forall i \leq k 不過在DP有個麻煩的點就是他的順序，因為要是沒有好的順序就會算出不對的答案，一個解決方法是直接top-down，但是常數會變大，這題又卡的有點緊，可能會TLE。這時其實發現迴圈的第一維枚舉右界，第二維再倒過來求左界，他長度就會是遞增而且前面都已經DP過了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,int> PII; #define FF first #define SS second const int N = 1000 + 5; const lld INF = 1LL<<60; PII mtx[N]; lld dp[5][N][N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int T; cin>>T; lld sm=0; for(int t=0;t<T;++t){ int n;cin>>n; for(int i=0;i<n;++i) cin>>mtx[i].FF>>mtx[i].SS; fill(dp[t][0], dp[t][n]+n, INF); for(int i=0;i<n;++i) dp[t][i][i] = 0; for(int j=0;j<n;++j){ for(int i=j-1;i>=0;--i){ for(int k=i;...

題目連結: http://arc078.contest.atcoder.jp/tasks/arc078_b 考慮一棵樹上的區域，其實有一塊是白的無法到達，一塊是黑的無法到達，另一塊則是大家都可以碰觸到。所以顯然在玩的時候一定是先搶大家都可以碰觸到的地方，會發現離自己越近的點越容易成為自己的顏色。仔細考慮後發現其實BFS一下，並且算個大家的領地大小就會是答案了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 100000 + 5; vector<int> G[N]; bitset<N> visited; int sum1=0, sum2=0; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=0;i<n-1;i++){ int u, v;cin>>u>>v; G[u].PB(v); G[v].PB(u); } queue<PII> BFS; BFS.push({1,1});BFS.push({n,2}); visited[1]=1;visited[n]=1; while(!BFS.empty()){ int cur=BFS.front().FF; int id=BFS.front().SS; BFS.pop(); for(auto i:G[cur]){ ...

題目連結: http://arc078.contest.atcoder.jp/tasks/arc078_c 奇怪的二分搜題，賽中的時候我有想出來大概的方向，結果沒刻完QQ，賽後再刻才發現其實還滿討厭的，有一些小小的邊界case要想。 這裡我先二分搜出答案的位數，方法很簡單，就找一個字典序很小的數字10000000(這樣讀到Y就知道原因了)，然後開始搜尋他後面0的個數，因為顯然他的字典序比起來一定都會最小，那只要找到Y跟N之間的分界，那Y那個就會是位數。 第二步則是對每一位二分搜出他正確的值，這裡先讓數字超級巨大，這樣讀到Y或N時就知道原因了，所以就每次都選最一個是N的地方。 不過要注意一下，因為最後一次也還是N，所以要加回1讓他變成Y。 p.s 付個Judge用的code AC Code: #include <bits/stdc++.h> using namespace std; typedef long long lld; int getDigit(); string getVal(int); int main(){ int dig = getDigit(); string val = getVal(dig); long long ans=0; for(int i=0;i<dig;i++) ans=ans*10 + (val[i]-'0'); cout<<"! "<<(ans+1)<<endl<<flush; return 0; } int getDigit(){ int r=10, l=0; while(r-l > 1){ int mid = (l+r)>>1; cout<<"? 1"; for(int i=0;i<mid;i++) cout<<0; cout<<endl<<flu...

題目連結: http://tioj.infor.org/problems/1513 一開始用unordered_map秒過去，可是傳上去後發現速度似乎有點慘，而且記憶體也比大家高，後來才發現其實把所有數字xor起來就會是答案，因為被關掉的編號一定是出現偶數次，而一個數字xor偶數次後必定就會變成0(也就是那個數字就會消失)。 unordered_map版本 #include <bits/stdc++.h> using namespace std; #define FF first #define SS second int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ unordered_map<unsigned int,int> mm; for(int i=0;i<n;i++){ unsigned int x;cin>>x; mm[x]++; } for(auto i:mm) if(i.SS&1) cout<<i.FF<<'\n'; } return 0; } xor版本 #include <cstdio> int main(){ int n; while(scanf("%d",&n)!=EOF){ unsigned int k=0; for(int i=0;i<n;i++){ unsigned int x;scanf("%u",&x); k^=x; } printf("%u\n",k); }...

題目連結: http://codeforces.com/problemset/problem/525/E 一個神奇的技巧，砍半枚舉，其實就是一種枚舉的方法，不過因為可能原本$2^N$太大，所以只在兩邊各枚舉一半，變成$2^{\frac{N}{2}+1}$，不過這作法要可以有效率的枚舉出部分在左、部分在右的。像這題的話，我是先算完左半邊後，把可能的值全部塞到一個vector，sort完後，就可以在算右邊時，同時二分搜左邊可能的答案。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define ALL(x) (x).begin(), (x).end() #define PB push_back typedef pair<int,lld> PLI; const int N = 25 + 3; int n, k; lld arr[N], jie[N], S, ans=0; vector<PLI> set1; void dfs(int,int,int,lld); void dfs2(int,int,int,lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>k>>S; for(int i=0;i<n;i++) cin>>arr[i]; jie[0]=1; for(int i=1;i<20;i++) jie[i]=jie[i-1]*i; int mid=n>>1; dfs(0, mid, k, 0); sort(ALL(set1)); dfs2(mid, n, k, 0); cout<<ans<<'\n'; return 0; } void dfs(i...

題目連結: http://tioj.infor.org/problems/1161 考慮把力量跟敏捷當成兩維把所有技能繪製在平面上，接著用掃描線的概念，從左掃到右，那這時其實就是要對當前的點集尋找第k小，然後跟自己的值加上去。也可以想像成枚舉其中一維的最大值來做計算。而維護點集第k小，其實開個heap維護他的size是k就好了。(我原本寫平衡樹但一直MLE) #include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; #define FF first #define SS second const int INF = 2e9; const int N = 1000000 + 5; int n, k; PII arr[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ cin>>n>>k; for(int i=0;i<n;i++) cin>>arr[i].FF>>arr[i].SS; sort(arr,arr+n); int ans=INF; priority_queue<int> pq; for(int i=0;i<n;i++){ pq.push(arr[i].SS); while((int)pq.size() > k)pq.pop(); if((int)pq.size() == k) ans=min(ans, arr[i].FF+pq.top()); } cout<<an...

題目連結: http://tioj.infor.org/problems/1351 $\sqrt{n}$把數字分解掉，再記錄一下就好了 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ int x;cin>>x; int sx = ceil(sqrt(x)); vector<int> fac; for(int i=1;i<sx;i++){ if(x%i==0){ fac.PB(i); fac.PB(x/i); } } if(sx*sx==x) fac.PB(sx); lld sm=0; for(auto i:fac) sm+=i; cout<<sm*fac.size()<<'\n'; } return 0; }

題目連結: http://arc077.contest.atcoder.jp/tasks/arc077_c 賽中完全沒頭緒，最後是被雷了才知道這題怎麼做的XD想法大概是我們在算cost的時候其實就是算$\sum_{i=1}^{n}(R_i-L_i)$，那顯然等價於$\sum_{i=1}^{n}R_i-\sum_{i=1}^{n}L_i$(注意若其中$R_i #include <bits/stdc++.h> using namespace std; typedef long long lld; const int INF = 2000000000; const int N = 100000 + 10; lld arr[N], cnt[N], sm[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m;cin>>n>>m; for(int i=0;i<n;i++) cin>>arr[i]; lld sumL=0, sumR=0; for(int i=0;i<n-1;i++) sumL+=arr[i]; for(int i=1;i<n;i++) sumR+=arr[i]+m*(arr[i-1]>arr[i]); for(int i=1;i<n;i++){ if(arr[i-1]>arr[i]){ cnt[arr[i-1]+1]+=1; cnt[m+1]-=1; cnt[1]+=1; cnt[arr[i]+1]-=1; sm[arr[i-1]+1]+=arr[i-1]; sm[m+1]-=arr[i-1]; sm[1]+=arr[i-1]-m; sm[arr...

題目連結: http://tioj.infor.org/problems/1448 / http://poj.org/problem?id=1182 經典的並查集應用，想法大概就跟並查集的大多數用途一樣，考慮把每個動物X分三種類型$X_A, X_B, X_C$，代表若X為A的情況或X為B的情況...，那要兩種動物$X, Y$為同一種的話合併的話，顯然就是合併$X_A \equiv Y_A, X_B \equiv Y_B, X_C \equiv Y_C$，吃的話則是$X_A \equiv Y_B, X_B \equiv Y_C, X_C \equiv Y_A$，這樣的話要判斷是否為假話的話就變容易了，仔細想想會發現不可能有一種動物$X$，他在某次操作後$X_A \equiv X_B \lor X_B \equiv X_C \lor X_C \equiv X_A$，所以只要操作前看看沒有要合併的人他的集合是不是原本就一樣就好。 p.s POJ上範圍不太一樣，這裡是TIOJ的範圍(而且動態配置貌似POJ會TLE) #include <bits/stdc++.h> using namespace std; #define FAKE ans++;continue; const int N = 500000; class DJS{ private: int *arr; public: void init(int T){ arr=new int[T]; for(int i=0;i<T;i++) arr[i]=i; } void merge(int a, int b){ arr[query(a)]=query(b); } int query(int x){ if(arr[x]!=x) arr[x]=query(arr[x]); retur...

題目連結: http://arc077.contest.atcoder.jp/tasks/arc077_b 我賽中的時候蠢蠢的，一直想說要$\binom{n+1}{k}-\sum^{n+1}_{i=1}{\binom{p-1}{i} \times \binom{n+1-q}{n+1-i}}$，後來才發現其實那就等價於$\binom{n+1}{k}-\binom{n-q+p}{k-1}$，其中$p,q$為重複的那兩個數的位置。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 100000 + 5; const int mod = 1000000007; int arr[N], pos[N]; lld moni[N], cmb[2][N]; lld qPow(lld,lld); lld C(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, p, q;cin>>n; for(int i=1;i<=n+5;i++) moni[i]=qPow(i, mod-2); for(int i=0;i<=n;i++) cin>>arr[i]; fill(pos, pos+1+n, -1); for(int i=0;i<=n;i++){ if(pos[arr[i]]==-1) pos[arr[i]]=i; else{ p=pos[arr[i]]; q=i; break; } } cmb[0][0]=1; cmb[1][0]=1; for(int i=1;i<=n+1;i++){ ...

題目連結: http://tioj.infor.org/problems/1368 我這題想了好久好久，然後某天突然感覺這題可以這樣做XD 這題我的作法是，找到對於每一個元素，往左跟往右找到第一個比他小的數字，以兩者為範圍，算high值，最後再取max即。，而往又跟往左找第一個比他小的數字其實一個stack就可以做到了，只要維護stack裡由底往上是遞增就好。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,int> PII; #define FF first #define SS second const int N = 100000 + 5; lld arr[N], preS[N]; int rr[N], ll[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=1;i<=n;i++) cin>>arr[i]; arr[n+1]=0; for(int i=1;i<=n;i++) preS[i] = preS[i-1]+arr[i]; stack<int> ss; for(int i=1;i<=n;i++){ while(!ss.empty() and arr[ss.top()] > arr[i]){ rr[ss.top()]=i-1; ss.pop(); } ss.push(i); } while(!ss.empty()){ ...

題目連結: http://tioj.infor.org/problems/1390 看到n這麼小就合理猜個狀態壓縮DP，稍微想個兩下應該可以發現轉移式$dp[S] = \max\limits_{i,j \in S}(dp[S-not \_ left[i][j]] + val[i][j])$，也就是說對於一個集合，找到使得他最大的一組i,j。 #include <bits/stdc++.h> using namespace std; const int N = 15+1; int n, val[N][N], lef[N][N]; int dp[1<<N]; bitset<(1<<N)> dped; inline bool inS(int,int); int f(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); while(cin>>n){ dped.reset(); fill(dp, dp+(1<<(n+1)), 0); dped[0]=1; for(int i=0;i<n;i++) dped[1<<i]=1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>val[i][j]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>lef[i][j]; cout<<f((1<<n) - 1)<<'\n'; } return 0; } inline bool inS(int x, int S){ return ...

題目連結: http://tioj.infor.org/problems/1202 一開始看到的時候總覺得線段樹可以秒過，不過想說應該不需要，應該有線性的作法，所以這題我一直以為是某種單調隊列，直到我想了超久後才發現他無法好好維護單調性的(或者說他沒有單調性)，因此原本要回去刻線段樹，越刻越覺得操作很神奇，仔細想想後才發現自己根本在寫heap，把他想成heap之後就很簡單了XD。 就先把過期的建築拔掉，再把每棟建築依照左界丟進去，之後得到最大的高度，最後再取個unique即可。 #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 30000 + 5; struct BB{ int l, r, h; bool operator<(const BB& x)const{ return h<x.h; } }; vector<BB> buildings; vector<int> points; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n, n){ points.clear(); buildings.clear(); for(int i=0;i<n;i++){ int a,b,c; cin>>a>>b>>c; buildings.PB({a,c,b}); ...

題目連結: http://tioj.infor.org/problems/1385 本題有空白!!!裸的Edit Distance題，不過要注意要吃一整行，不要只讀一段進來，不然會WA。稍微解釋一下DP式，$dp[i][j]$代表用a的前i個字元轉換成b的前j個字元所需的最少次數，那轉移就會是$dp[i][j] = \begin{cases} dp[i-1][j-1],& \text{if } a[i-1] = b[j-1]\\ \min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1, & \text{otherwise} \end{cases}$，因為如果$a[i]==b[j]$那顯然不需要作修改，而若不同，則看看用插入、刪除或取代哪個比較好。 #include <bits/stdc++.h> using namespace std; const int N = 1000 + 5; int dp[N][N]; int main(){ string a, b; getline(cin, a); getline(cin, b); int lenA=a.size(), lenB=b.size(); for(int i=0;i<=lenA;i++) dp[i][0] = i; for(int i=0;i<=lenB;i++) dp[0][i] = i; for(int i=1;i<=lenA;i++){ for(int j=1;j<=lenB;j++){ if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]})+1; } } ...

題目連結: http://tioj.infor.org/problems/1493 本題要求在樹上對一個節點單點加值或是問一個節點及其子樹的和，顯然直接照著做會TLE，所以不妨考慮把樹壓扁後的序列，修改一個節點的值就是對序列作單點修改，問子樹的話也會剛好是一個連續的區間，所以就直接作區間詢問就好。單點修改，區間查詢就是一個BIT支援的操作，所以就開三個BIT把三種果實維護好即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int, int> PII; #define FF first #define SS second const int N = 1000000 + 5; vector<int> g[N]; int st[N], ed[N], timer=1; void dfs(int,int); struct BIT{ int arr[2*N]; inline int lowbit(int x){ return x&(-x); } void add(int w, int c){ while(w<=timer){ arr[w]+=c; w+=lowbit(w); } } int query(int l, int r){ return query(r-1) - query(l-1); } int query(int w){ int r=0; while(w){ r+=arr[w]; w-=lowbit(w); } return r;...

題目連結: http://tioj.infor.org/problems/1226 我原本以為本題就裸裸的邊作拓樸排序邊算每個點所會花到的時間就好，後來一直WA後才發現原來那樣做是錯的，因為一個點可以被走過很多次，所以有些邊要再乘以路徑數，所以還要多紀錄一下路徑數再好好算才對。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int mod = 32768; const int V = 1005; int inDg[V], ans[V], cnt[V]; vector<PII> g[V]; vector<string> names; bitset<V> visited; void init(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; for(int _=1;_<=t;_++){ cout<<"Game #"<<_<<'\n'; int n, v, e;cin>>n>>v>>e; init(v); for(int i=0;i<n;i++){ string ss;cin>>ss; names.PB(ss); } for(int i=0;i<e;i++){ int st, ed, w;cin>>st>>ed>...

題目連結: http://tioj.infor.org/problems/1407 跟 TIOJ 1387 一樣，只是把N改大一點。不過如果C在大一點就要好好的對餘數作單調隊列優化。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define PB push_back #define FF first #define SS second vector<PII> stones; int dp[1000005]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, t;cin>>n; for(int i=0;i<n;i++){ int w,m,c,j;cin>>w>>m>>c; for(j=1;j<=c;c-=j, j<<=1) stones.PB({w*j, m*j}); if(c) stones.PB({w*c, m*c}); } for(int i=1;i<=t;i++) dp[i]=0; cin>>t; for(int i=1;i<=int(stones.size());i++) for(int j=t;j-stones[i-1].FF>=0 && j>=1;j--) dp[j] = max(dp[j-stones[i-1].FF] + stones[i-1].SS, dp[j]); int ans=0; for(int i=1;i<=t;i++) ans = max(ans, dp[i]); cout<<ans...

題目連結: http://tioj.infor.org/problems/1387 經典的多重背包優化，其實本題可以裸著當背包寫就好了，不過我還是寫了一個logC的優化。這優化的想法大概是想說你並不需要完整的C組，而只要把他分成2的冪次跟餘數即可有所有數量的可能了。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define PB push_back #define FF first #define SS second vector<PII> stones; int dp[10005]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, t;cin>>n; for(int i=0;i<n;i++){ int w,m,c,j;cin>>w>>m>>c; for(j=1;j<=c;c-=j, j<<=1) stones.PB({w*j, m*j}); if(c) stones.PB({w*c, m*c}); } for(int i=1;i<=t;i++) dp[i]=0; cin>>t; for(int i=1;i<=int(stones.size());i++) for(int j=t;j-stones[i-1].FF>=0 && j>=1;j--) dp[j] = max(dp[j-stones[i-1].FF] + stones[i-1].SS, dp[j]); int ans=0; for(int i=1;i<=t;i++) ans = ...

題目連結: http://tioj.infor.org/problems/1014 n小小的，所以應該不難猜到這題可以狀態壓縮DP。狀態我這裡是寫$dp[S][i] = 已打S，且最後一個打的是i所需的最小時間$，那轉移就是$ dp[S][i] = \displaystyle \min_{j \in S-\{i\}}(dp[S-i][j] + |i-j| + (t[i] - ((dp[S-i][j] + |i-j|) \mod t[i])) \mod t[i]) $ #include <bits/stdc++.h> using namespace std; const int N = 16; const int INF = 2000000000; bool dped[(1<<N)+5][N+5]; int n, t[N+5]; int dp[(1<<N)+5][N+5]; int f(int,int); bool inS(int,int); int main(){ cin>>n; for(int i=0;i<n;i++) cin>>t[i]; for(int i=0;i<n;i++){ dped[1<<i][i] = 1; dp[1<<i][i] = i+1 + (t[i]-((i+1)%t[i]))%t[i]; } int ans=INF; for(int i=0;i<n;i++) ans = min(ans, f((1<<n)-1, i)); cout<<ans<<'\n'; return 0; } bool inS(int S, int e){ return S & (1<<e); } int f(int S, int i){ if(...