oToToT的code收藏區

題目連結: https://codeforces.com/contest/1051/problem/F 煩人的題目，一開始看到題的時候，忘記字串可以$(N, O(logN))$比較大小，然後想了想，想出一個什麼suffix array上二分搜之類的超噁比大小作法XD 後來發現可以$O(logN)$比大小之後，又因為hash碰撞卡了一段時間，才發現我p, q打反XD 總之，這題應該可以想到一個簡單的DP狀態$dp[i]$代表把後i個弄好的方法數，哪也很明顯的如果$s_i \neq \text{'0'}$，那就是找到一個區間的$j(i \le j \leq n)$使得$L \leq s_i...s_j \leq R$然後明顯$dp[i]=\sum_{j} dp[j]$，因為我們顯然只能把$s_i$跟那些人接在一起，而若$s_i = \text{'0'}$的情況也類似，所以現在變成我們要找到那些j，不過很明顯可以發現若a跟b差不多大，那他們的位數應該也差不多，所以我們只要去比較位數差不多的那個substring，就可以得知他是不是比較大了。 #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; const int qs[] = { 1002939109, 1020288887, 1028798297, 1038684299, 1041211027, 1051762951, 1058585963, 1063020809, 1094763083, 1106384353, 1120154459, 1140593173, 1147930723, 1172520109, 1183835981, 1187659051, 1241251303, 1247184097, 1255940849, 1272759031, 1287027493, 1288511629, 1294632499, 1312650799, 1314753281, 1320080669, 1321970357, 1333133947, ...

題目連結: http://tioj.infor.org/problems/1998 可以發現其實每個IP都是一個32-bit的東東，所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1，而我們要詢問一堆IP是不是在一堆區間內，其實就直接把那些區間當作區間加值，那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大，要先離散化掉就是了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int M = 200000 + 5; const int N = 300000 + 5; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } } lisan; ...

題目連結: http://codeforces.com/problemset/problem/835/D 先觀察到一件事，是k回文的他一定也是k-1回文，這樣的話就只要知道一個子字串他最大是幾回文就好了，而這可以DP，狀態是$dp[i][j]$代表$i~j$最大可以是幾回文，而轉移也很顯然的就是$dp[i][j] = dp[i][mid]+1$，如果$i~mid == mid~r$的話，否則的話就是0，而要判斷兩個子字串是否相等其實用個hash就好了，只不過我真的不太會寫hash，搞了好久QQ #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 5000 + 5; class Hash{ private: const lld p = 127, q = 1208220623; int sz; lld prefix[N], power[N]; public: void init(const string &x){ sz = x.size(); prefix[0]=0; for(int i=1;i<=sz;i++) prefix[i]=((prefix[i-1]*p)%q+x[i-1])%q; power[0]=1; for(int i=1;i<=sz;i++) power[i]=(power[i-1]*p)%q; } lld query(int l, int r){ // 1-base (l, r] return (prefix[r] - (prefix[l]*power[r-l])%q + q)%q; } }; // dp[4][9] : ...

題目連結: http://tioj.infor.org/problems/1214 原本以為可以拿個中序前序之類的來判，但感覺還是慘慘的。後來才知道原來其實可以把一整棵樹的形狀hash起來，這樣的話就可以直接看hash值來判了，不過要怎麼hash呢?這裡的作法是先定義葉節點的hash值，而其他非葉節點則將他所有子樹的hash值平方後加起來，這樣只要根一樣的話那hash出來的值就會一樣(但有可能有碰撞)，但是這題給的是棵無根樹，若沒有用一些好方法定根，那hash出來的值就很有可能不一樣，這裡利用樹的一個特殊的性質－一顆樹的重心最多只有兩顆，所以用重心當根判一下就可以有$O(n)$的複雜度了。 #include <bits/stdc++.h> using namespace std; typedef unsigned long long llu; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100 + 5; const int mod = 44478311; vector<int> G1[N], G2[N]; int sz1[N], sz2[N]; inline void init(int); int GetCentroid(vector<int>[],int[],int,int,int); llu Hash(vector<int>[],int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n, n){ init(n); for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; ...