oToToT的code收藏區

題目連結: http://acm.csie.org/ntujudge/problem.php?id=2584 在兩棵樹上找LCS，其實跟原本找LCS的方法一樣，因為他還是可以找到字串的上一個字元，只不過原本的是要看前一個字元就好，這變成要看父親的字元，狀態也稍微改動成$dp[i][j]$是第一顆樹的0~i跟第二顆樹的0~j的LCS長度 #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 = 1000 + 5; string s1, s2; vector<int> G1[N], G2[N]; int dp[N][N], ans; void DFS(int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ ans=0; int n, m; cin>>n>>m; for(int i=1;i<=n;i++) G1[i].clear(); for(int i=1;i<=m;i++) G2[i].clear(); cin>>s1; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G1[u].PB(v); G1[v].PB(u); } cin>>s2; for(int i...

題目連結: http://acm.csie.org/ntujudge/problem.php?id=2789 原本想要用離散化在定義一堆其怪的狀態來做這題，不過越寫越寫不出來。被雷了才知道，原來其實把那堆bit看成一堆線段就好了，那其實退位就是讓目前最低位消失，並在低他一位的地方長出一堆一直到現在這位置，而進位就更不用說了，畢竟原本進位就是均攤$O(1)$了。 #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 template<typename T> using minHeap = priority_queue<T,vector<T>,greater<T>>; vector<PII> work, ans; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ work.clear(); ans.clear(); minHeap<int> pq1, pq2; int n; cin>>n; for(int i=0;i<n;i++){ char c;int k; cin>>c>>k; if(c=='+') pq1.push(k); else if(c=='-') pq2.push(k); } while(...

題目連結: http://acm.csie.org/ntujudge/problem.php?id=903 有趣的好題，想了很久只想的到樹鍊剖分的作法，被雷了才知道更好的做法QQ 對於全子樹加一其實很簡單，就把樹壓扁後把$[in[x], out[x]]$全部加一就好，然後詢問時則單點詢問邊即可。但是另外兩個操作就會變得很難做，所以要用另外一種方式想，考慮一條邊若或被加值，則一定是因為它下面的點有被加值，所以其實對最底下的點加值即可，然後為了怕太上面的人也會被算到，記得超過最頂之後要再減一以免多算，這樣就變成單點加值區間查詢了。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; class BIT1{ #define lowbit(x) ((x)&(-(x))) private: int arr[N], size; inline int query(int x){ int r=0; while(x){ r+=arr[x]; x-=lowbit(x); } return r; } public: inline void init(int x){ fill(arr, arr+size, 0); size=x; } inline int query(int l, int r){ // 1-base (l, r] return query(r)-query(l); } inline void add(int x,...