[关闭]
@yang12138 2023-05-12T10:31:12.000000Z 字数 63810 阅读 552

CPC Code Template

未分类

String

KMP

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. class KMP {
  6.   private:
  7.     static const int LEN = 100000 + 10;
  8.     static int next[LEN];
  10.     template<class T>
  11.     static void GetNext(const T* const s, int n) {
  12.         next[0] = -1;
  13.         for (int i = 1; i < n; i++) {
  14.             next[i] = next[i-1];
  15.             while (next[i] >= 0 && s[next[i]+1] != s[i]) next[i] = next[next[i]];
  16.             if (s[next[i]+1] == s[i]) next[i]++;
  17.         }
  18.     }
  20.   public:
  21.     // match t on s
  22.     template<class T>
  23.     static int Gao(const T* const s, int n, const T* const t, int m) {
  24.         GetNext(t, m);
  25.         int pos = -1, ans = 0;
  26.         for (int i = 0; i < n; i++) {
  27.             while (pos >= 0 && s[i] != t[pos+1]) pos = next[pos];
  28.             if (s[i] == t[pos+1]) pos++;
  29.             if (pos == m-1) return i - m + 1;
  30.         }
  31.         return -2;
  32.     }
  33. };
  34. int KMP::next[KMP::LEN];
  36. int a[1000010], b[10010];
  38. int main() {
  39.     int T;
  40.     scanf("%d", &T);
  41.     while (T--) {
  42.         int n, m;
  43.         scanf("%d%d", &n, &m);
  44.         assert(n <= 100000);
  45.         for (int i = 0; i < n; i++) scanf("%d", a+i);
  46.         for (int i = 0; i < m; i++) scanf("%d", b+i);
  47.         printf("%d\n", KMP::Gao(a, n, b, m)+1);
  48.     }
  49.     return 0;
  50. }

Manacher

  2. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  7. class Manacher {
  8.   public:
  9.     static int Gao(const char* const str, int n) {
  10.         int m = 0;
  11.         t[m++] = '!';
  12.         for (int i = 0; i < n; i++) {
  13.             t[m++] = '@';
  14.             t[m++] = str[i];
  15.         }
  16.         t[m++] = '@';
  18.         int center = 0, radius = 0;
  19.         ll ans = 0;
  20.         int len = 0;
  21.         for (int i = 0; i < m; i++) {
  22.             if (i < center + radius)
  23.                 r[i] = min(r[2 * center - i], center + radius - i);
  24.             while (t[i - r[i] - 1] == t[i + r[i] + 1]) r[i]++;
  25.             if (i + r[i] > center + radius) center = i, radius = r[i];
  27.             ans += (r[i] + 1) / 2;
  28.             len = max(len, r[i]);
  29.         }
  30.         // return ans;
  31.         return len;
  32.     }
  34.   private:
  35.     static const int LEN = 2000000 + 10;
  36.     static char t[LEN];
  37.     static int r[LEN];
  38. };
  39. char Manacher::t[Manacher::LEN];
  40. int Manacher::r[Manacher::LEN];
  42. char in[800010];
  44. int main() {
  45.     scanf("%s", in);
  46.     printf("%d\n", Manacher::Gao(in, strlen(in)));
  47.     return 0;
  48. }

Suffix Array

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  5. struct SA {
  6.     static const int N = 1e5 + 10;
  8.     // a_i >= 0
  9.     void GetSA(const int* a, int n) {
  10.         int up = 0;
  11.         for (int i = 0; i < n; i++) up = max(up, a[i]);
  12.         up++;
  14.         int *rk1 = rk[0], *rk2 = rk[1];
  15.         std::fill(cnt, cnt + up, 0);
  16.         for (int i = 0; i < n; i++) cnt[rk1[i] = a[i]]++;
  17.         for (int i = 0; i+1 < up; i++) cnt[i+1] += cnt[i];
  18.         for (int i = n - 1; i >= 0; i--) sa[--cnt[rk1[i]]] = i;
  20.         for (int d = 1; d <= n; d <<= 1) {
  21.             int p = 0;
  22.             for (int i = n - d; i < n; i++) id[p++] = i;
  23.             for (int i = 0; i < n; i++) if (sa[i] >= d) id[p++] = sa[i] - d;
  25.             std::fill(cnt, cnt + up, 0);
  26.             for (int i = 0; i < n; i++) cnt[rk2[i] = rk1[id[i]]]++;
  27.             for (int i = 0; i+1 < up; i++) cnt[i+1] += cnt[i];
  28.             for (int i = n - 1; i >= 0; i--) sa[--cnt[rk2[i]]] = id[i];
  30.             rk2[sa[0]] = 0;
  31.             for (int i = 1; i < n; i++) {
  32.                 if (sa[i-1] + d < n && sa[i] + d < n && rk1[sa[i-1]] == rk1[sa[i]]
  33.                         && rk1[sa[i-1]+d] == rk1[sa[i]+d])
  34.                     rk2[sa[i]] = rk2[sa[i-1]];
  35.                 else rk2[sa[i]] = rk2[sa[i-1]] + 1;
  36.             }
  37.             swap(rk1, rk2);
  38.             up = n;
  39.             if (rk2[sa[n-1]] == n) break;
  40.         }
  42.         height[0] = 0;
  43.         for (int i = 0, p = 0; i < n; i++) {
  44.             if (rk1[i] == 0) continue;
  45.             int j = sa[rk1[i]-1];
  46.             while (i + p < n && j + p < n && a[i+p] == a[j+p]) p++;
  47.             height[rk1[i]] = p;
  48.             p = max(0, p-1);
  49.         }
  50.     }
  52.     void GetSA(const char* s) {
  53.         int n = strlen(s);
  54.         int* a = new int[n];
  55.         for (int i = 0; i < n; i++) a[i] = s[i];
  56.         GetSA(a, n);
  57.     }
  59.     int cnt[N], id[N];
  60.     int sa[N];          // index from 0 ~ n-1
  61.     int rk[2][N];       // index from 0 ~ n-1
  62.     int height[N];      // index from 1 ~ n-1, largest common prefix of suffix_sa[i] and suffix_sa[i-1]
  63. } sagetter;
  65. void solve() {
  67.     string s;
  68.     cin >> s;
  69.     sagetter.GetSA(s.c_str());
  70.     int* sa = sagetter.sa;
  71.     int* h = sagetter.height;
  72.     for (int i = 0; i < s.size(); i++) {
  73.         printf("sa %d string %s height %d\n", sa[i], s.substr(sa[i], s.size()).c_str(), h[i]);
  74.     }
  76. }
  78. int main() {
  79.     int T = 1;
  80.     // scanf("%d", &T);
  81.     while (T--) solve();
  82.     return 0;
  83. }

AC-AutoMachine

  2. // codeforeces 633C
  3. // link: https://codeforces.com/problemset/problem/633/C
  5. #include <bits/stdc++.h>
  7. using namespace std;
  9. struct Node {
  10.     static const int SIZE = 26;
  11.     int ch[SIZE];
  12.     int val, fail, dep;
  13.     int endpoint;
  14.     Node() {
  15.         fail = 0, endpoint = -1;
  16.         memset(ch, 0, sizeof(ch));
  17.     }
  18. };
  20. struct ACAuto {
  21.     static const int N = 1e6+10;
  22.     Node t[N];
  23.     int counter = 1;
  25.     // A - Z, a - z
  26.     static int transform(char ch) {
  27.         if (ch >= 'A' && ch <= 'Z') return ch - 'A';
  28.         return ch - 'a';
  29.     }
  31.     void Insert(const char* s, int index) {
  32.         int root = 0;
  33.         for (int i = 0; s[i]; i++) {
  34.             int v = transform(s[i]);
  35.             if (!t[root].ch[v]) t[root].ch[v] = counter++;
  36.             root = t[root].ch[v];
  37.             t[root].val = v;
  38.             t[root].dep = i + 1;
  39.         }
  40.         t[root].endpoint = index;
  41.     }
  43.     void BFS() {
  44.         typedef pair<int, int> pii;
  45.         queue<pii> que;
  46.         que.push(pii(0, 0));
  47.         while (!que.empty()) {
  48.             pii p = que.front(); que.pop();
  49.             int u = p.first, pre = p.second;
  50.             for (int i = 0; i < Node::SIZE; i++) {
  51.                 if (t[u].ch[i]) que.push(pii(t[u].ch[i], u));
  52.             }
  53.             if (u == 0) continue;
  54.             if (t[u].dep == 1) {
  55.                 t[u].fail = 0;
  56.                 continue;
  57.             }
  58.             int fail = t[pre].fail;
  59.             int val = t[u].val;
  60.             while (fail && t[fail].ch[val] == 0) fail = t[fail].fail;
  61.             t[u].fail = t[fail].ch[val];
  62.         }
  63.     }
  65.     void Init(const vector<const char*>& stringlist) {
  66.         for (int i = 0; i < stringlist.size(); i++) Insert(stringlist[i], i);
  67.         BFS();
  68.     }
  70.     int* Solve(const char* s) {
  71.         int root = 0, n = strlen(s), pos = 0;
  72.         int* dp = new int[n + 1];
  73.         memset(dp, -1, sizeof(int)*(n+1));
  74.         dp[0] = 0;
  75.         for (int i = 0; i < n; i++) {
  76.             int v = transform(s[i]);
  77.             while (pos && t[pos].ch[v] == 0) pos = t[pos].fail;
  79.             pos = t[pos].ch[v];
  80.             // printf("pos[%d]=%d\n", i+1, pos);
  81.             {
  82.                 int fail = pos;
  83.                 while (fail) {
  84.                     if (t[fail].endpoint >= 0 && dp[i+1-t[fail].dep] >= 0) {
  85.                         dp[i+1] = t[fail].endpoint;
  86.                         break;
  87.                     }
  88.                     fail = t[fail].fail;
  89.                 }
  90.             }
  91.             // printf("dp[%d]=%d\n\n", i+1, dp[i+1]);
  92.         }
  93.         assert(dp[n] >= 0);
  94.         return dp;
  95.     }
  97. } acauto;
  99. char buffer[1000000 + 100000 + 10];
  100. char text[10010];
  101. int pos[100010];
  102. int len[100010];
  104. void DFS(int index, const int* dp) {
  105.     if (index == 0) return ;
  106.     // printf("index: %d, dp: %d, pos: %d, len: %d\n", index, dp[index], pos[dp[index]], len[dp[index]]);
  107.     DFS(index - len[dp[index]], dp);
  108.     printf("%s ", buffer + pos[dp[index]]);
  109. }
  111. void solve() {
  112.     int n;
  113.     scanf("%d%s", &n, text);
  115.     vector<const char*> stringlist;
  116.     int m;
  117.     scanf("%d", &m);
  118.     stringlist.reserve(m);
  119.     for (int i = 0; i < m; i++) {
  120.         scanf("%s", buffer+pos[i]);
  121.         stringlist.push_back(buffer+pos[i]);
  122.         len[i] = strlen(buffer+pos[i]);
  123.         pos[i+1] = pos[i] + len[i] + 1;
  124.         reverse(buffer+pos[i], buffer+pos[i]+len[i]);
  125.     }
  127.     acauto.Init(stringlist);
  128.     // cout << "init succ" << endl;
  129.     const int* dp = acauto.Solve(text);
  130.     // cout << "solve succ" << endl;
  131.     for (int i = 0; i < m; i++)
  132.         reverse(buffer+pos[i], buffer+pos[i]+len[i]);
  134.     DFS(n, dp);
  135.     printf("\n");
  136. }
  138. int main() {
  139.     solve();
  140.     return 0;
  141. }

String Hash

  2. // https://www.luogu.com.cn/problem/P3370
  4. #include <bits/stdc++.h>
  5. using namespace std;
  7. template <int P, int MOD>
  8. struct StringHash {
  9.  public:
  10.     StringHash() {}
  11.     StringHash(const char* s, int n) { Init(s, n); }
  13.     void Init(const char* s, int n) {
  14.         assert(1LL * P * INV % MOD == 1);
  15.         inv = hash = vector<int>(n);
  17.         int pw = 1;
  18.         for (int i = 0; i < n; i++) {
  19.             hash[i] = ((i ? hash[i-1] : 0) + 1LL * pw * (int)s[i]) % MOD;
  20.             inv[i] = i ? (1LL * inv[i-1] * INV % MOD) : 1;
  21.             pw = 1LL * pw * P % MOD;
  22.         }
  23.     }
  25.     int GetHash(int l, int r) const {
  26.         assert(r >= l - 1 && l >= 0 && r < (int)hash.size());
  27.         if (l > r) return 0;
  28.         if (l == 0) return hash[r];
  29.         return 1LL * (hash[r] - hash[l-1] + MOD) * inv[l] % MOD;
  30.     }
  32.  private:
  33.     constexpr static int PowMod(int a, int n) {
  34.         int ans = 1;
  35.         while (n) {
  36.             if (n & 1) ans = 1LL * ans * a % MOD;
  37.             a = 1LL * a * a % MOD;
  38.             n >>= 1;
  39.         }
  40.         return ans;
  41.     }
  43.     constexpr static int INV = PowMod(P, MOD - 2);
  44.     vector<int> hash, inv;
  45. };
  47. typedef StringHash<1009, 1000000007> Hasher;
  48. // typedef StringHash<2003, 1000000009> Hasher2;
  50. const int N = 1e5 + 10;
  51. char buf[N];
  53. int main() {
  54.     int n;
  55.     scanf("%d", &n);
  56.     set<int> st;
  57.     for (int i = 0; i < n; i++) {
  58.         scanf("%s", buf);
  59.         Hasher h(buf, strlen(buf));
  60.         st.insert(h.GetHash(0, strlen(buf)-1));
  61.     }
  62.     printf("%d\n", (int)st.size());
  64.     return 0;
  65. }

Min Representation

  2. // http://acm.hdu.edu.cn/showproblem.php?pid=3374
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 1e6+10;
  12. char s[N];
  14. typedef std::function<bool(char, char)> LessFunc;
  16. void solve(LessFunc leq) {
  17.     int n = strlen(s);
  19.     int i = 0, j = 1, k = 0;
  20.     while (k < n) {
  21.         // printf("i %d, j %d, k %d\n", i, j, k);
  22.         if (leq(s[(j+k)%n], s[(i+k)%n])) {
  23.             if (i+k+1 >= n) break;
  24.             (i += k+1) %= n;
  25.             k = 0;
  26.         } else if (leq(s[(i+k)%n], s[(j+k)%n])) {
  27.             if (j+k+1 >= n) break;
  28.             (j += k+1) %= n;
  29.             k = 0;
  30.         } else {
  31.             k++;
  32.         }
  33.         if (i == j) {
  34.             (j += 1) %= n;
  35.             if (j == 0) break;
  36.         }
  37.     }
  39.     printf("%d %d", i+1, n / (k == n ? abs(i-j) : n));
  40. }
  42. bool solve() {
  43.     if (scanf("%s", s) == 1) {
  44.         solve([](char a, char b) { return a < b; });
  45.         printf(" ");
  46.         solve([](char a, char b) { return a > b; });
  47.         printf("\n");
  48.         return true;
  49.     }
  50.     return false;
  51. }
  53. int main() {
  54.     while (solve());
  55.     return 0;
  56. }

Network Flow

Max Flow

  2. // author: yang12138
  4. // https://atcoder.jp/contests/abc274/tasks/abc274_g
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  11. static const int INF = 1e9;
  13. struct NetFlow {
  14.     struct Edge {
  15.         int to, cap, rev;
  16.         Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
  17.     };
  18.     vector<vector<Edge>> G;
  19.     vector<int> iter, level;
  21.     NetFlow(int V) : G(V), iter(V), level(V) {}
  23.     void AddEdge(int u, int v, int cap) {
  24.         G[u].push_back(Edge(v, cap, (int)G[v].size()));
  25.         G[v].push_back(Edge(u, 0, (int)G[u].size()-1));
  26.     }
  28.     void BFS(int s) {
  29.         fill(level.begin(), level.end(), -1);
  30.         level[s]=0;
  31.         queue<int> que;
  32.         que.push(s);
  33.         while (!que.empty()) {
  34.             int v = que.front();
  35.             que.pop();
  36.             for(int i = 0; i < G[v].size(); i++) {
  37.                 Edge& e=G[v][i];
  38.                 if(level[e.to] < 0 && e.cap > 0)
  39.                     level[e.to] = level[v] + 1, que.push(e.to);
  40.             }
  41.         }
  42.     }
  44.     int DFS(int s, int t, int f) {
  45.         if (s == t) return f;
  46.         for (int& i = iter[s]; i < (int)G[s].size(); i++) {
  47.             Edge& e = G[s][i];
  48.             if (level[s] < level[e.to] && e.cap > 0) {
  49.                 int d = DFS(e.to, t, min(f, e.cap));
  50.                 if (d > 0) {
  51.                     e.cap -= d, G[e.to][e.rev].cap += d;
  52.                     return d;
  53.                 }
  54.             }
  55.         }
  56.         return 0;
  57.     }
  59.     int MaxFlow(int s, int t) {
  60.         int flow = 0;
  61.         while (BFS(s), level[t] >= 0) {
  62.             fill(iter.begin(), iter.end(), 0);
  63.             int f = 0;
  64.             while(f = DFS(s,t,INF)) flow += f;
  65.         }
  66.         return flow;
  67.     }
  68. };
  70. const int N = 305;
  71. char str[N][N];
  72. int up[N][N], lef[N][N];
  74. void solve() {
  75.     int n, m;
  76.     scanf("%d%d", &n, &m);
  78.     auto GetNum = [&](int i, int j) { return (i - 1) * m + j; };
  80.     int s = 0, t = 2 * n * m + 1;
  81.     NetFlow nf(t + 1);
  82.     for (int i = 1; i <= n; i++) {
  83.         scanf("%s", str[i] + 1);
  84.         for (int j = 1; j <= m; j++) {
  85.             if (str[i][j] == '.') {
  86.                 up[i][j] = (i - 1 >= 1 && str[i-1][j] == '.') ? up[i-1][j] : i;
  87.                 lef[i][j] = (j - 1 >= 1 && str[i][j-1] == '.') ? lef[i][j-1] : j;
  89.                 nf.AddEdge(GetNum(up[i][j], j), GetNum(i, lef[i][j]) + n * m, INF);
  90.                 // printf("%d %d up %d lef %d\n", i, j, up[i][j], lef[i][j]);
  91.             }
  93.             nf.AddEdge(s, GetNum(i, j), 1);
  94.             nf.AddEdge(GetNum(i, j) + n * m, t, 1);
  95.         }
  96.     }
  97.     printf("%d\n", nf.MaxFlow(s, t));
  98. }
  100. int main() {
  101.     int T = 1;
  102.     // scanf("%d", &T);
  103.     while (T--) solve();
  104.     return 0;
  105. }

Min Cost Flow

  1. // http://codeforces.com/contest/1510/problem/B
  3. #include <bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. typedef pair<int, int> pii;
  9. struct Edge {
  10.     int to, cap, cost, rev;
  11.     Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {}
  12. };
  14. struct CostFlow {
  16.     static const int V = (1 << 11) + 10;
  17.     static const int INF = 1e9;
  19.     CostFlow(): n_(0) {}
  21.     void Reset() {
  22.         for (int i = 0; i < n_; i++) G[i].clear();
  23.         n_ = 0;
  24.     }
  26.     void AddEdge(int from, int to, int cap, int cost) {
  27.         G[from].push_back(Edge(to, cap, cost, G[to].size()));
  28.         G[to].push_back(Edge(from, 0, -cost, G[from].size() - 1));
  29.     }
  31.     void SetMax(int n) { n_ = n + 1; }
  33.     vector<Edge> G[V];
  34.     int h[V], dist[V];
  35.     int preV[V], preE[V];
  36.     int n_;
  38.     // 初始边权有正有负时不能用
  39.     int MinCostFlow(const int s, const int t, int max_flow, int* real_flow = nullptr) {
  40.         priority_queue<pii, vector<pii>, greater<pii> > que;
  41.         int res = 0;
  42.         memset(h, 0, sizeof(h[0])*n_);
  43.         while (max_flow) {
  44.             // printf("max_flow %d\n", max_flow);
  45.             for (int i = 0; i < n_; i++) dist[i] = INF;
  46.             dist[s] = 0;
  47.             que.push(pii(0, s));
  48.             while (!que.empty()) {
  49.                 pii p = que.top();
  50.                 que.pop();
  51.                 int v = p.second;
  52.                 if (dist[v] < p.first) continue;
  53.                 for (int i = 0; i < G[v].size(); i++) {
  54.                     const Edge& e = G[v][i];
  55.                     if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
  56.                         dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
  57.                         preV[e.to] = v, preE[e.to] = i;
  58.                         que.push(pii(dist[e.to], e.to));
  59.                     }
  60.                 }
  61.             }
  62.             if (dist[t] == INF) return res;
  63.             for (int i = 0; i < n_; i++) h[i] += dist[i];
  64.             int cur_flow = max_flow;
  65.             for (int i = t; i != s; i = preV[i]) {
  66.                 cur_flow = min(cur_flow, G[preV[i]][preE[i]].cap);
  67.             }
  68.             // printf("cur_flow %d dist[t]\n", cur_flow, dist[t]);
  69.             if (real_flow) *real_flow += cur_flow;
  70.             max_flow -= cur_flow;
  71.             res += cur_flow * h[t];
  72.             for (int i = t; i != s; i = preV[i]) {
  73.                 Edge& e = G[preV[i]][preE[i]];
  74.                 e.cap -= cur_flow, G[i][e.rev].cap += cur_flow;
  75.             }
  76.         }
  77.         return res;
  78.     }
  80.     int MinCostMaxFlow(const int s, const int t, int* real_flow = nullptr) {
  81.         return MinCostFlow(s, t, INF, real_flow);
  82.     }
  84.     const vector<Edge>* GetG() { return G; }
  86. } min_cost_flow;
  88. void solve() {
  89.     int d, n;
  90.     scanf("%d%d", &d, &n);
  91.     char buffer[20];
  92.     vector<int> st(n);
  93.     for (int i = 0; i < n; i++) {
  94.         scanf("%s", buffer);
  95.         for (int j = 0; j < d; j++) {
  96.             if (buffer[j] == '1') st[i] |= (1 << j);
  97.         }
  98.     }
  99.     sort(st.begin(), st.end());
  100.     vector<int> bits(1 << d);
  101.     vector<int> lastb(1 << d);
  102.     for (int i = 1; i < (1 << d); i++) {
  103.         bits[i] = bits[i/2] + (i&1);
  104.         if (i&1) lastb[i] = 0;
  105.         else lastb[i] = lastb[i/2]+1;
  106.     }
  108.     int s = 0, t = 2*n+1;
  109.     for (int i = 0; i < n; i++) {
  110.         for (int j = 0; j < i; j++) {
  111.             if ((st[i] | st[j]) == st[i]) {
  112.                 min_cost_flow.AddEdge(j+1, i+1+n, 1, -bits[st[j]]);
  113.             }
  114.         }
  115.         min_cost_flow.AddEdge(s, i+1, 1, 0);
  116.         min_cost_flow.AddEdge(i+1+n, t, 1, -1);
  117.     }
  119.     vector<int> in(1 << d, 0);
  120.     vector<int> vis(1 << d, 0);
  121.     vector<int> nex(1 << d);
  122.     int bs = 0;
  124.     for (auto i: st) in[i] = 1, bs += bits[i];
  126.     min_cost_flow.SetMax(t);
  127.     int flow = 0;
  128.     int cost = min_cost_flow.MinCostMaxFlow(s, t, &flow);
  129.     cost += n-1 + bs;
  131.     for (int i = 1; i <= n; i++) {
  132.         for (const Edge& e : min_cost_flow.GetG()[i]) {
  133.             if (e.to >= n+1 && e.to <= 2*n && e.cap == 0) {
  134.                 nex[st[i-1]] = st[e.to-n-1];
  135.                 break;
  136.             }
  137.         }
  138.     }
  140.     vector<char> ans;
  142.     int reset = 0, rcnt = 0;
  143.     for (int i = 1; i < (1 << d); i++) {
  144.         if (!in[i]) continue;
  145.         if (vis[i]) continue;
  146.         if (reset) ans.push_back('R'), rcnt++;
  147.         int pre = 0, cur = i;
  148.         while (cur) {
  149.             vis[cur] = 1;
  150.             int tmp = (pre ^ cur);
  151.             while (tmp) {
  152.                 ans.push_back('0' + lastb[tmp]);
  153.                 tmp ^= (1 << lastb[tmp]);
  154.             }
  155.             pre = cur, cur = nex[cur];
  156.         }
  157.         reset = 1;
  158.     }
  159.     /*
  160.     printf("reset cnt: %d, flow: %d\n", rcnt, flow);
  161.     printf("cost: %d, ans size: %d\n", cost, int(ans.size()));
  162.     */
  163.     printf("%d\n", ans.size());
  164.     for (auto i: ans) printf("%c ", i);
  165.     printf("\n");
  166.     assert(rcnt == n-1-flow);
  167.     assert(cost == ans.size());
  168. }
  170. int main() {
  171.     int T = 1;
  172.     // scanf("%d", &T);
  173.     while (T--) solve();
  174. }

Global Min Cut

  2. // https://acm.hdu.edu.cn/showproblem.php?pid=6081
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 3005;
  11. const int INF = 1e9;
  13. struct Edge {
  14.     int u, v, w;
  15.     void scan() { scanf("%d%d%d", &u, &v, &w); }
  16. };
  18. struct DisjointSet {
  19.     int fa[N], n;
  20.     void Init(int n) {
  21.         this->n = n;
  22.         for (int i = 1; i <= n; i++) fa[i] = -1;
  23.     }
  24.     int FindFa(int u) {
  25.         return (fa[u] < 0) ? u : (fa[u] = FindFa(fa[u]));
  26.     }
  27.     bool Merge(int u, int v) {
  28.         u = FindFa(u), v = FindFa(v);
  29.         if (u == v) return true;
  30.         if (fa[u] + fa[v] == -n) return false;
  31.         fa[u] += fa[v];
  32.         fa[v] = u;
  33.         return true;
  34.     }
  35. } ds;
  37. bool solve() {
  38.     int n, m;
  39.     if (scanf("%d%d", &n, &m) != 2) return false;
  40.     vector<Edge> edges(m);
  41.     for (auto& edge : edges) edge.scan();
  43.     int ans = INF;
  44.     int unchange = 0;
  45.     const int LIMIT = 2000;
  46.     do {
  47.         random_shuffle(edges.begin(), edges.end());
  48.         ds.Init(n);
  50.         bool flag = false;
  51.         for (const auto& edge : edges) {
  52.             if (!ds.Merge(edge.u, edge.v)) {
  53.                 flag = true;
  54.                 break;
  55.             }
  56.         }
  57.         if (!flag) {
  58.             ans = 0;
  59.             break;
  60.         }
  62.         int tans = 0;
  63.         for (const auto& edge : edges) {
  64.             if (ds.FindFa(edge.u) != ds.FindFa(edge.v)) {
  65.                 tans += edge.w;
  66.             }
  67.         }
  69.         if (ans <= tans) unchange++;
  70.         else ans = tans, unchange = 0;
  72.         // printf("tans %d, ans %d\n", tans, ans);
  73.     } while (unchange <= LIMIT);
  75.     printf("%d\n", ans);
  76.     return true;
  77. }
  79. int main() {
  80.     while (solve());
  81.     return 0;
  82. }

KM Algorithm

  2. // https://acm.hdu.edu.cn/showproblem.php?pid=2255
  3. // https://acm.hdu.edu.cn/showproblem.php?pid=6346
  5. // KM algorithm
  6. // MaxWeightMatch of bipartite graph
  8. #include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  13. const int N = 505;
  14. const int INF = 2e9;
  16. int A[N], B[N], slack[N];
  17. int w[N][N];
  19. // all rig
  20. int match[N], repl[N];
  21. bool vis[N];
  23. int nx, ny;
  25. ll KM() {
  26.     assert(nx >= 1 && ny >= 1 && nx <= ny);
  28.     std::fill(match + 1, match + ny + 1, -1);
  30.     for(int x = 1; x <= nx; x++) {
  31.         int currig = 0;
  32.         match[currig] = x;
  34.         std::fill(vis, vis + ny + 1, false);
  35.         std::fill(slack + 1, slack + ny + 1, INF);
  37.         while (match[currig] != -1) {
  38.             vis[currig] = true;
  39.             int curlef = match[currig], nexrig = -1;
  40.             ll d = INF;
  41.             for (int y = 1; y <= ny; y++) {
  42.                 if (!vis[y]) {
  43.                     ll t = A[curlef] + B[y] - w[curlef][y];
  44.                     if (t < slack[y]) slack[y] = t, repl[y] = currig;
  45.                     if (slack[y] < d) d = slack[y], nexrig = y;
  46.                 }
  47.             }
  48.             for (int y = 0; y <= ny; y++) {
  49.                 if (vis[y]) A[match[y]] -= d, B[y] += d;
  50.                 else slack[y] -= d;
  51.             }
  52.             currig = nexrig;
  53.         }
  55.         while (currig) {
  56.             int nexrig = repl[currig];
  57.             match[currig] = match[nexrig];
  58.             currig = nexrig;
  59.         }
  60.     }
  61.     ll ans = 0;
  62.     for (int i = 1; i <= ny; i++) {
  63.         if (match[i] > 0) ans += B[i] + A[match[i]];
  64.     }
  65.     return ans;
  66. }
  68. void solve(int cas) {
  69.     int n;
  70.     scanf("%d", &n);
  71.     for (int i = 1; i <= n; i++) {
  72.         for (int j = 1; j <= n; j++) {
  73.             scanf("%d", &w[i][j]);
  74.             w[i][j] *= -1;
  75.         }
  76.     }
  77.     nx = ny = n;
  78.     printf("Case #%d: %lld\n", cas, -KM());
  79. }
  81. int main() {
  82.     int T, t = 0;
  83.     scanf("%d", &T);
  84.     while (T--) solve(++t);
  86.     return 0;
  87. }

Data Structure

  2. // https://www.luogu.com.cn/problem/P1501
  3. // https://www.luogu.com.cn/problem/P2147
  4. // https://www.luogu.com.cn/problem/P3690
  6. #include <bits/stdc++.h>
  8. using namespace std;
  9. typedef long long ll;
  10. typedef pair<int, int> pii;
  12. const int N = 1e5+10;
  13. const int MOD = 51061;
  15. int ch[N][2], f[N];
  17. struct Value {
  18.     int mul = 0, add = 0, val = 0, sum = 0, sz = 0, tag = 0;
  20.     Value() {}
  22.     Value(int mul, int add, int tag = 0): mul(mul), add(add), tag(tag) {}
  24.     void PushDown(Value& rhs) const {
  25.         if (mul != 1) {
  26.             rhs.mul = 1LL * rhs.mul * mul % MOD;
  27.             rhs.add = 1LL * rhs.add * mul % MOD;
  28.             rhs.val = 1LL * rhs.val * mul % MOD;
  29.             rhs.sum = 1LL * rhs.sum * mul % MOD;
  30.         }
  31.         if (add) {
  32.             (rhs.add += add) %= MOD;
  33.             (rhs.val += add) %= MOD;
  34.             (rhs.sum += 1LL * rhs.sz * add % MOD) %= MOD;
  35.         }
  36.         if (tag) rhs.tag ^= 1;
  37.     }
  39.     void PushUp(const Value& lhs, const Value& rhs) {
  40.         sz = lhs.sz + rhs.sz + 1;
  41.         sum = (lhs.sum + rhs.sum + val) % MOD;
  42.     }
  44.     void Reset() {
  45.         mul = 1, add = 0, tag = 0;
  46.     }
  48. } val[N];
  50. int Get(int x) { return ch[f[x]][1] == x; }
  52. bool IsSplayRoot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }
  54. void PushDown(int x) {
  55.     if (val[x].tag) swap(ch[x][0], ch[x][1]);
  56.     if (ch[x][0]) val[x].PushDown(val[ch[x][0]]);
  57.     if (ch[x][1]) val[x].PushDown(val[ch[x][1]]);
  58.     val[x].Reset();
  59. }
  61. void PushUp(int x) { val[x].PushUp(val[ch[x][0]], val[ch[x][1]]); }
  63. void Update(int x) { if (!IsSplayRoot(x)) Update(f[x]); PushDown(x); }
  65. void Rotate(int x) {
  66.     assert(f[x]);
  67.     int y = f[x], k = Get(x);
  68.     // link y and ch[x][!k]
  69.     if (ch[x][!k]) f[ch[x][!k]] = y;
  70.     ch[y][k] = ch[x][!k];
  71.     // link f[y] and x
  72.     if (!IsSplayRoot(y)) ch[f[y]][Get(y)] = x;
  73.     f[x] = f[y];
  74.     // link x and y
  75.     ch[x][!k] = y, f[y] = x;
  76.     PushUp(y), PushUp(x);
  77. }
  79. void Splay(int x) {
  80.     Update(x);
  81.     for (int fa = f[x]; !IsSplayRoot(x); fa = f[x]) {
  82.         if (!IsSplayRoot(fa) && !IsSplayRoot(f[fa]))
  83.             Rotate(Get(fa) == Get(x) ? fa : x);
  84.         Rotate(x);
  85.     }
  86. }
  88. int Access(int x) {
  89.     int p = 0;
  90.     while (x) {
  91.         Splay(x), ch[x][1] = p, PushUp(x);
  92.         p = x, x = f[x];
  93.     }
  94.     return p;
  95. }
  97. void MakeRoot(int x) { val[Access(x)].tag ^= 1; }
  99. void Link(int x, int y) { MakeRoot(x), Splay(x), f[x] = y; }
  101. void Split(int x, int y) { MakeRoot(x), Access(y), Splay(x); }
  103. void Cut(int x, int y) { Split(x, y), Splay(y), ch[y][0] = f[x] = 0; }
  105. int FindRoot(int x) {
  106.     Access(x), Splay(x);
  107.     while (ch[x][0]) PushDown(x), x = ch[x][0];
  108.     Splay(x);
  109.     return x;
  110. }
  112. void solve() {
  113.     int n, q;
  114.     scanf("%d%d", &n, &q);
  115.     for (int i = 1; i <= n; i++) {
  116.         val[i].mul = val[i].val = val[i].sz = val[i].sum = 1;
  117.     }
  118.     for (int i = 1; i < n; i++) {
  119.         int u, v;
  120.         scanf("%d%d", &u, &v);
  121.         Link(u, v);
  122.     }
  123.     char s[10];
  124.     while (q--) {
  125.         int u1, v1, u2, v2, c;
  126.         scanf("%s%d%d", s, &u1, &v1);
  127.         if (s[0] == '+') {
  128.             scanf("%d", &c);
  129.             Split(u1, v1);
  130.             Value(1, c).PushDown(val[u1]);
  131.         } else if (s[0] == '-') {
  132.             scanf("%d%d", &u2, &v2);
  133.             Cut(u1, v1);
  134.             Link(u2, v2);
  135.         } else if (s[0] == '*') {
  136.             scanf("%d", &c);
  137.             Split(u1, v1);
  138.             Value(c, 0).PushDown(val[u1]);
  139.         } else {
  140.             Split(u1, v1);
  141.             printf("%d\n", val[u1].sum);
  142.         }
  143.     }
  144. }
  146. int main() {
  147.     int T = 1;
  148.     // scanf("%d", &T);
  149.     while (T--) solve();
  150.     return 0;
  151. }
  2. // https://loj.ac/p/2230
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 1e5+10;
  12. int ch[N][2], f[N];
  14. struct Value {
  15.     int tag = 0;
  16.     int splay_size = 0, subtree_size = 0, virtualson_size = 0;
  18.     Value() {}
  20.     void PushDown(Value& rhs) const {
  21.         if (tag) rhs.tag ^= 1;
  22.     }
  24.     void PushUp(const Value& lhs, const Value& rhs) {
  25.         splay_size = lhs.splay_size + rhs.splay_size + 1;
  26.         subtree_size = lhs.subtree_size + rhs.subtree_size + 1 + virtualson_size;
  27.     }
  29.     void Reset() { tag = 0; }
  31. } val[N];
  33. int Get(int x) { return ch[f[x]][1] == x; }
  35. bool IsSplayRoot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }
  37. void PushDown(int x) {
  38.     if (val[x].tag) swap(ch[x][0], ch[x][1]);
  39.     if (ch[x][0]) val[x].PushDown(val[ch[x][0]]);
  40.     if (ch[x][1]) val[x].PushDown(val[ch[x][1]]);
  41.     val[x].Reset();
  42. }
  44. void PushUp(int x) { val[x].PushUp(val[ch[x][0]], val[ch[x][1]]); }
  46. void Update(int x) { if (!IsSplayRoot(x)) Update(f[x]); PushDown(x); }
  48. void Rotate(int x) {
  49.     assert(f[x]);
  50.     int y = f[x], k = Get(x);
  51.     // link y and ch[x][!k]
  52.     if (ch[x][!k]) f[ch[x][!k]] = y;
  53.     ch[y][k] = ch[x][!k];
  54.     // link f[y] and x
  55.     if (!IsSplayRoot(y)) ch[f[y]][Get(y)] = x;
  56.     f[x] = f[y];
  57.     // link x and y
  58.     ch[x][!k] = y, f[y] = x;
  59.     PushUp(y), PushUp(x);
  60. }
  62. void Splay(int x) {
  63.     Update(x);
  64.     for (int fa = f[x]; !IsSplayRoot(x); fa = f[x]) {
  65.         if (!IsSplayRoot(fa) && !IsSplayRoot(f[fa]))
  66.             Rotate(Get(fa) == Get(x) ? fa : x);
  67.         Rotate(x);
  68.     }
  69. }
  71. int Access(int x) {
  72.     int p = 0;
  73.     while (x) {
  74.         Splay(x);
  75.         val[x].virtualson_size += val[ch[x][1]].subtree_size - val[p].subtree_size;
  76.         ch[x][1] = p, PushUp(x);
  77.         p = x, x = f[x];
  78.     }
  79.     return p;
  80. }
  82. void MakeRoot(int x) { val[Access(x)].tag ^= 1; }
  84. void Link(int x, int y) {
  85.     MakeRoot(x), Splay(x);
  86.     MakeRoot(y), Splay(y);
  87.     f[x] = y, val[y].virtualson_size += val[x].subtree_size;
  88. }
  90. void Split(int x, int y) { MakeRoot(x), Access(y), Splay(x); }
  92. void Cut(int x, int y) { Split(x, y), Splay(y), ch[y][0] = f[x] = 0; }
  94. int FindRoot(int x) {
  95.     Access(x), Splay(x);
  96.     while (ch[x][0]) PushDown(x), x = ch[x][0];
  97.     Splay(x);
  98.     return x;
  99. }
  101. int GetTreeSize(int x) {
  102.     MakeRoot(x), Splay(x);
  103.     return val[x].subtree_size;
  104. }
  106. void solve() {
  107.     int n, q;
  108.     scanf("%d%d", &n, &q);
  109.     for (int i = 1; i <= n; i++) val[i].subtree_size = 1;
  110.     while (q--) {
  111.         char op[4];
  112.         int x, y;
  113.         scanf("%s%d%d", op, &x, &y);
  114.         if (op[0] == 'A') {
  115.             Link(x, y);
  116.         } else {
  117.             Cut(x, y);
  118.             printf("%lld\n", 1LL * GetTreeSize(x) * GetTreeSize(y));
  119.             Link(x, y);
  120.         }
  121.     }
  122. }
  124. int main() {
  125.     int T = 1;
  126.     // scanf("%d", &T);
  127.     while (T--) solve();
  128.     return 0;
  129. }

Pairing Heap

  2. #include <bits/stdc++.h>
  3. using namespace std;
  5. template <typename T>
  6. struct PairingHeap {
  7.  public:
  8.     static const int N = 3e5+10;
  10.     PairingHeap() { Reset(N - 1); }
  12.     void Reset(int n) {
  13.         root = 0;
  14.         std::memset(val, sizeof(val[0]) * (n + 1), 0);
  15.         std::fill(son, son + n + 1, 0);
  16.         std::fill(pre, pre + n + 1, 0);
  17.         std::fill(bro, bro + n + 1, 0);
  18.     }
  20.     const T& GetVal(int u) const { return val[u]; }
  22.     bool InHeap(int u) const { return u == root || pre[u] != 0; }
  24.     bool Empty() const { return root ? false : true; }
  26.     T Top() const {
  27.         assert(!Empty());
  28.         return val[root];
  29.     }
  31.     void Push(int u, T x) {
  32.         assert(son[u] == 0 && pre[u] == 0 && bro[u] == 0);
  33.         val[u] = x;
  34.         root = Merge(root, u);
  35.     }
  37.     void Pop() {
  38.         assert(!Empty());
  39.         int tmp = Merges(son[root]);
  40.         ResetNode(root);
  41.         root = tmp;
  42.     }
  44.     void Update(int u, T x) {
  45.         assert(x < val[u]);
  46.         val[u] = x;
  47.         if (u == root) return ;
  48.         assert(pre[u]);
  49.         if (son[pre[u]] == u) son[pre[u]] = bro[u];
  50.         else bro[pre[u]] = bro[u];
  51.         if (bro[u]) pre[bro[u]] = pre[u];
  52.         root = Merge(root, u);
  53.     }
  55.  private:
  56.     void ResetNode(int u) { son[u] = pre[u] = bro[u] = 0; }
  58.     void MakeRoot(int u) { pre[u] = bro[u] = 0; }
  60.     int Merge(int u, int v) {
  61.         MakeRoot(u), MakeRoot(v);
  62.         if (u == 0 || v == 0) return u ^ v;
  63.         if (val[u] > val[v]) swap(u, v);
  64.         bro[v] = son[u];
  65.         if (son[u]) pre[son[u]] = v;
  66.         son[u] = v;
  67.         pre[v] = u;
  68.         return u;
  69.     }
  71.     int Merges(int u) {
  72.         if (u == 0) return 0;
  73.         int v = bro[u], w = bro[v];
  74.         return Merge(Merge(u, v), Merges(w));
  75.     }
  77.     T val[N];
  78.     int son[N], pre[N], bro[N], root;
  79. };
  81. int main() {
  82.     return 0;
  83. }

Skip List

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  5. struct SkipListNode;
  6. struct SkipListLevel {
  7.     SkipListNode* forward = nullptr;
  8.     int span;
  9. };
  11. struct SkipListNode {
  12.     int score;
  13.     int obj;
  14.     SkipListLevel *level;
  15. };
  17. const int MAX_LEVEL = 20;
  19. int RandomLevel() {
  20.     int level = 1;
  21.     while (level < MAX_LEVEL && rand() % 2 == 0) level++;
  22.     return level;
  23. }
  25. SkipListNode* CreateSkipListNode(int level, int score, int obj) {
  26.     SkipListNode* node = new SkipListNode;
  27.     node->score = score;
  28.     node->obj = obj;
  29.     node->level = new SkipListLevel[level];
  30.     return node;
  31. }
  33. struct SkipList {
  34.     SkipListNode* header_;
  35.     int level_;
  36.     int len_;
  38.     SkipList() {
  39.         header_ = CreateSkipListNode(MAX_LEVEL, 0, 0);
  40.         level_ = len_ = 0;
  41.     }
  43.     void Insert(int score, int obj) {
  44.         SkipListNode *update[MAX_LEVEL];
  45.         int rank[MAX_LEVEL];
  47.         SkipListNode* x = header_;
  48.         for (int i = level_ - 1; i >= 0; i--) {
  49.             rank[i] = (i == level_ - 1) ? 0 : rank[i + 1];
  50.             while (x->level[i].forward && (x->level[i].forward->score < score ||
  51.                         x->level[i].forward->score == score &&
  52.                         x->level[i].forward->obj < obj)) {
  53.                 rank[i] += x->level[i].span;
  54.                 x = x->level[i].forward;
  55.             }
  56.             update[i] = x;
  57.         }
  59.         int newlevel = RandomLevel();
  60.         if (newlevel > level_) {
  61.             for (int i = level_; i < newlevel; i++) {
  62.                 update[i] = header_;
  63.                 update[i]->level[i].span = len_;
  64.                 rank[i] = 0;
  65.             }
  66.         }
  68.         x = CreateSkipListNode(newlevel, score, obj);
  69.         for (int i = 0; i < newlevel; i++) {
  70.             x->level[i].forward = update[i]->level[i].forward;
  71.             update[i]->level[i].forward = x;
  73.             x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
  74.             update[i]->level[i].span = rank[0] - rank[i] + 1;
  75.         }
  76.         for (int i = newlevel; i < level_; i++) update[i]->level[i].span++;
  78.         level_ = max(level_, newlevel);
  79.         len_++;
  80.     }
  82.     int Delete(int score, int obj) {
  83.         SkipListNode *update[MAX_LEVEL];
  84.         int rank[MAX_LEVEL];
  85.         SkipListNode* x = header_;
  86.         for (int i = level_ - 1; i >= 0; i--) {
  87.             while (x->level[i].forward && (x->level[i].forward->score < score ||
  88.                         x->level[i].forward->score == score &&
  89.                         x->level[i].forward->obj < obj)) {
  90.                 // rank[i] += x->level[i].span;
  91.                 x = x->level[i].forward;
  92.             }
  93.             update[i] = x;
  94.         }
  96.         if (!(x->level[0].forward && x->level[0].forward->score == score &&
  97.                 x->level[0].forward->obj == obj)) return -1;
  98.         x = x->level[0].forward;
  100.         for (int i = 0; i < level_; i++) {
  101.             if (update[i]->level[i].forward == x) {
  102.                 update[i]->level[i].forward = x->level[i].forward;
  103.                 update[i]->level[i].span += x->level[i].span - 1;
  104.             } else {
  105.                 update[i]->level[i].span--;
  106.             }
  107.         }
  108.         len_--;
  109.         return 0;
  110.     }
  112.     // rank from 1
  113.     int GetByRank(int rank, int& score, int& obj) const {
  114.         if (rank <= 0 || rank > len_) return -1;
  115.         SkipListNode* x = header_;
  116.         for (int i = level_ - 1; i >= 0 && rank; i--) {
  117.             while (x->level[i].forward && rank >= x->level[i].span) {
  118.                 rank -= x->level[i].span;
  119.                 x = x->level[i].forward;
  120.             }
  121.         }
  122.         score = x->score;
  123.         obj = x->obj;
  124.         return 0;
  125.     }
  127.     int GetByScore(int score, int& obj) const {
  128.         SkipListNode* x = header_;
  129.         for (int i = level_ - 1; i >= 0; i--) {
  130.             while (x->level[i].forward && x->level[i].forward->score < score) {
  131.                 x = x->level[i].forward;
  132.             }
  133.         }
  134.         if (x->level[0].forward && x->level[0].forward->score == score) {
  135.             obj = x->level[0].forward->obj;
  136.             return 0;
  137.         }
  138.         return -1;
  139.     }
  141.     void Dump() const {
  142.         SkipListNode* x = header_->level[0].forward;
  143.         printf("size: %d\n", len_);
  144.         while (x) {
  145.             printf("(%d, %d)\n", x->score, x->obj);
  146.             x = x->level[0].forward;
  147.         }
  148.     }
  149. };
  151. int main() {
  153.     SkipList sl;
  154.     while (1) {
  155.         int type;
  156.         int score, obj;
  157.         scanf("%d", &type);
  158.         if (type == 1) {
  159.             scanf("%d%d", &score, &obj);
  160.             sl.Insert(score, obj);
  161.             sl.Dump();
  162.         } else if (type == 2) {
  163.             int rank;
  164.             scanf("%d", &rank);
  165.             int ret = sl.GetByRank(rank, score, obj);
  166.             printf("ret=%d, rank %d: (%d, %d)\n", ret, rank, score, obj);
  167.         } else if (type == 3) {
  168.             scanf("%d", &score);
  169.             int ret = sl.GetByScore(score, obj);
  170.             printf("ret=%d, (%d, %d)\n", ret, score, obj);
  171.         } else if (type == 4) {
  172.             scanf("%d%d", &score, &obj);
  173.             int ret = sl.Delete(score, obj);
  174.             printf("ret=%d\n", ret);
  175.             sl.Dump();
  176.         }
  177.     }
  179.     return 0;
  180. }

Splay

  2. // https://loj.ac/p/104
  3. // https://loj.ac/p/105
  5. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  11. const int N = 1e6+10;
  12. const int INF = 1e9;
  14. struct SplayNode {
  15.     int weight = 0;
  16.     int cnt = 0, sum = 0;
  17.     int rev = 0;
  18.     SplayNode* ch[2] = {};
  19.     SplayNode* fa = nullptr;
  21.     int Get() const { return this == fa->ch[1]; }
  23.     void Maintain();
  25.     void Rotate();
  27.     SplayNode* Splay();
  29.     SplayNode* Insert(int x);
  31.     // x must exist
  32.     SplayNode* Delete(int x);
  34.     // x must exist
  35.     int Rank(int x) const;
  37.     // 1 <= k <= root->sum
  38.     SplayNode* Kth(int k);
  40.     int Pre(int x) const;
  42.     int Suc(int x) const;
  44.     SplayNode* GetMax() {
  45.         return this->ch[1] ? this->ch[1]->GetMax() : this;
  46.     }
  48.     void PushDown();
  50.     void Traverse(vector<int>&);
  51. } nodes[N];
  53. SplayNode* NewNode() {
  54.     static int counter = 0;
  55.     return nodes + (counter++);
  56. }
  58. void SplayNode::Maintain() {
  59.     /*
  60.     assert(!ch[0] || (weight > ch[0]->weight && ch[0]->cnt));
  61.     assert(!ch[1] || (weight < ch[1]->weight && ch[1]->cnt));
  62.     */
  63.     sum = (ch[0] ? ch[0]->sum : 0) + (ch[1] ? ch[1]->sum : 0) + cnt;
  64. }
  66. void SplayNode::Rotate() {
  67.     assert(this->rev == 0);
  68.     // cerr << "Rorate " << this << endl;
  69.     SplayNode* f = this->fa;
  70.     assert(f);
  71.     int flag = this->Get();
  73.     if (f->fa) {
  74.         f->fa->ch[f->Get()] = this;
  75.     }
  76.     this->fa = f->fa;
  78.     f->ch[flag] = this->ch[flag ^ 1];
  79.     if (this->ch[flag ^ 1]) this->ch[flag ^ 1]->fa = f;
  81.     this->ch[flag ^ 1] = f;
  82.     f->fa = this;
  84.     f->Maintain();
  85.     this->Maintain();
  86. }
  88. SplayNode* SplayNode::Splay() {
  89.     // cerr << "Splay " << this << endl;
  90.     while (this->fa) {
  91.         this->Rotate();
  92.     }
  93.     return this;
  94. }
  96. SplayNode* SplayNode::Insert(int x) {
  97.     // cerr << "Insert " << this << ' ' << x << endl;
  98.     this->sum++;
  99.     if (x == this->weight) {
  100.         this->cnt++;
  101.         return this;
  102.     }
  103.     int flag = (x > this->weight);
  104.     if (this->ch[flag])
  105.         return this->ch[flag]->Insert(x);
  107.     SplayNode* resp = NewNode();
  108.     resp->weight = x;
  109.     resp->cnt = 1, resp->sum = 1;
  110.     this->ch[flag] = resp;
  111.     resp->fa = this;
  112.     return resp;
  113. }
  115. SplayNode* SplayNode::Delete(int x) {
  116.     // cerr << "Delete " << this << ' ' << x << endl;
  117.     this->sum--;
  118.     if (x == this->weight) {
  119.         assert(this->cnt >= 1);
  120.         this->cnt--;
  121.         return this;
  122.     }
  123.     assert(this->ch[x > this->weight]);
  124.     return this->ch[x > this->weight]->Delete(x);
  125. }
  127. int SplayNode::Rank(int x) const {
  128.     if (this->weight == x) return this->ch[0] ? this->ch[0]->sum : 0;
  129.     if (this->weight > x) return this->ch[0] ? this->ch[0]->Rank(x) : 0;
  130.     return (this->ch[0] ? this->ch[0]->sum : 0) + this->cnt + (this->ch[1] ? this->ch[1]->Rank(x) : 0);
  131. }
  133. SplayNode* SplayNode::Kth(int k) {
  134.     this->PushDown();
  136.     if (this->ch[0] && this->ch[0]->sum >= k)
  137.         return this->ch[0]->Kth(k);
  138.     k -= (this->ch[0] ? this->ch[0]->sum : 0);
  140.     if (this->cnt >= k) return this;
  141.     return this->ch[1]->Kth(k - this->cnt);
  142. }
  144. int SplayNode::Pre(int x) const {
  145.     if (x <= this->weight) return this->ch[0] ? this->ch[0]->Pre(x) : -INF;
  146.     return max(this->weight, this->ch[1] ? this->ch[1]->Pre(x) : -INF);
  147. }
  149. int SplayNode::Suc(int x) const {
  150.     if (x >= this->weight) return this->ch[1] ? this->ch[1]->Suc(x) : INF;
  151.     return min(this->weight, this->ch[0] ? this->ch[0]->Suc(x) : INF);
  152. }
  154. void SplayNode::PushDown() {
  155.     if (this->rev) {
  156.         if (this->ch[0]) this->ch[0]->rev ^= 1;
  157.         if (this->ch[1]) this->ch[1]->rev ^= 1;
  158.         swap(this->ch[0], this->ch[1]);
  159.         this->rev = 0;
  160.     }
  161. }
  163. void SplayNode::Traverse(vector<int>& res) {
  164.     this->PushDown();
  165.     if (this->ch[0]) this->ch[0]->Traverse(res);
  166.     res.push_back(this->weight);
  167.     if (this->ch[1]) this->ch[1]->Traverse(res);
  168. }
  170. struct SplayTree {
  171.     SplayNode* root = nullptr;
  173.     void Insert(int x) {
  174.         if (root == nullptr) {
  175.             root = NewNode();
  176.             root->weight = x;
  177.             root->cnt = root->sum = 1;
  178.         } else {
  179.             root = root->Insert(x)->Splay();
  180.         }
  181.     }
  183.     void Delete(int x) {
  184.         root = root->Delete(x)->Splay();
  185.         if (root->cnt == 0) {
  186.             if (root->ch[0] == nullptr) {
  187.                 root = root->ch[1];
  188.                 root->fa = nullptr;
  189.             } else if (root->ch[1] == nullptr) {
  190.                 root = root->ch[0];
  191.                 root->fa = nullptr;
  192.             } else {
  193.                 root->ch[0]->fa = nullptr;
  194.                 SplayNode* s = root->ch[0]->GetMax();
  195.                 s->Splay();
  196.                 assert(s->ch[1] == nullptr);
  197.                 s->ch[1] = root->ch[1];
  198.                 root->ch[1]->fa = s;
  199.                 s->Maintain();
  200.                 root = s;
  201.             }
  202.         }
  203.     }
  205.     int Rank(int x) { return root->Rank(x); }
  206.     SplayNode* Kth(int x) { return root->Kth(x); }
  207.     int Pre(int x) { return root->Pre(x); }
  208.     int Suc(int x) { return root->Suc(x); }
  209.     void Traverse(vector<int>& res) { root->Traverse(res); }
  210. };
  212. void solve() {
  213.     int n, m;
  214.     scanf("%d%d", &n, &m);
  216.     SplayTree tr;
  217.     for (int i = 0; i <= n+1; i++) tr.Insert(i);
  218.     while (m--) {
  219.         int l, r;
  220.         scanf("%d%d", &l, &r);
  222.         tr.root = tr.Kth(l-1 + 1)->Splay();
  223.         tr.root = tr.Kth(r+1 + 1)->Splay();
  224.         assert(tr.root->ch[0]);
  225.         assert(tr.root->ch[0]->ch[1]);
  226.         tr.root->ch[0]->ch[1]->rev ^= 1;
  228.     }
  230.     vector<int> ans;
  231.     tr.Traverse(ans);
  232.     assert(ans.size() == n+2);
  233.     for (int i = 1; i <= n; i++) {
  234.         if (i > 1) printf(" ");
  235.         printf("%d", ans[i]);
  236.     }
  237.     printf("\n");
  238. }
  240. int main() {
  241.     int T = 1;
  242.     // scanf("%d", &T);
  243.     while (T--) solve();
  244.     return 0;
  245. }

Treap

  2. #include <bits/stdc++.h>
  4. using namespace std;
  6. struct TreapNode {
  7.     static const int SIZE = 1e5 + 10;
  8.     static int counter;
  10.     TreapNode *son[2], *fa;
  11.     int val, rank, size, id;
  12.     void Reset() {
  13.         son[0] = son[1] = fa = nullptr;
  14.         rank = rand();
  15.     }
  16.     TreapNode() { Reset(); }
  17.     void PushUp() {
  18.         size = 1;
  19.         if (son[0]) size += son[0]->size;
  20.         if (son[1]) size += son[1]->size;
  21.     }
  22.     void print() const {
  23.         printf("id: %d, val: %d\n", id, val);
  24.     }
  25. } nodes[TreapNode::SIZE];
  26. int TreapNode::counter = 0;
  28. TreapNode* CreateTreapNode(int val, int id) {
  29.     TreapNode* node = &nodes[TreapNode::counter++];
  30.     node->val = val;
  31.     node->id = id;
  32.     node->size = 1;
  33.     return node;
  34. }
  36. struct Treap {
  37.     TreapNode* head;
  39.     void Reset() {
  40.         for (int i = 0; i < TreapNode::counter; i++) nodes[i].Reset();
  41.         TreapNode::counter = 0;
  42.         head = CreateTreapNode(INT_MIN, 0);
  43.         head->rank = -1;
  44.     }
  46.     Treap() { Reset(); }
  48.     static int SonType(TreapNode* x) {
  49.         return x->fa->son[1] == x;
  50.     }
  52.     static void GenChildren(TreapNode* fa, TreapNode* son, int type) {
  53.         fa->son[type] = son;
  54.         if (son) son->fa = fa;
  55.     }
  57.     // if exist already, ingore
  58.     void Insert(int val, int id) {
  59.         TreapNode* x = CreateTreapNode(val, id);
  60.         TreapNode* cur = head;
  61.         while (1) {
  62.             // if (cur->val == val) return;
  63.             cur->size++;
  64.             int flag = cur->val < val;
  65.             if (cur->son[flag] == nullptr) { cur->son[flag] = x, x->fa = cur; break; }
  66.             else cur = cur->son[flag];
  67.         }
  68.         assert(x->fa);
  70.         while (x->rank < x->fa->rank) {
  71.             int flag = SonType(x);
  72.             TreapNode* fa = x->fa;
  73.             assert(fa->fa);
  74.             GenChildren(fa->fa, x, SonType(fa));
  75.             GenChildren(fa, x->son[flag^1], flag);
  76.             GenChildren(x, fa, flag^1);
  77.             fa->PushUp();
  78.             x->PushUp();
  79.         }
  80.     }
  82.     // todo
  83.     void Delete(int val) {
  84.     }
  86.     const TreapNode* SeekUpperBound(int val) {
  87.         TreapNode* cur = head;
  88.         TreapNode* ans = nullptr;
  89.         while (cur) {
  90.             if (cur->val > val) ans = cur, cur = cur->son[0];
  91.             else cur = cur->son[1];
  92.         }
  93.         // assert(ans);
  94.         return ans;
  95.     }
  97.     const TreapNode* SeekLowerBound(int val) {
  98.         TreapNode* cur = head;
  99.         TreapNode* ans = nullptr;
  100.         while (cur) {
  101.             if (cur->val < val) ans = cur, cur = cur->son[1];
  102.             else cur = cur->son[0];
  103.         }
  104.         // assert(ans);
  105.         return ans;
  106.     }
  108.     // from 1
  109.     const TreapNode* GetByRank(int rank) {
  110.         rank++;
  111.         TreapNode* cur = head;
  112.         if (rank > cur->size) return nullptr;
  113.         while (cur) {
  114.             if (cur->son[0]) {
  115.                 if (cur->son[0]->size >= rank) { cur = cur->son[0]; continue; }
  116.                 rank -= cur->son[0]->size;
  117.             }
  118.             if (rank == 1) return cur;
  119.             rank--;
  120.             cur = cur->son[1];
  121.         }
  122.         return nullptr;
  123.     }
  125. } treap;
  127. void SolveHDU4585() {
  128.     int n;
  129.     while (~scanf("%d", &n) && n) {
  130.         treap.Reset();
  131.         treap.Insert(1000000000, 1);
  132.         treap.Insert(-1000000000, 1);
  133.         int id, val;
  134.         while (n--) {
  135.             scanf("%d%d", &id, &val);
  136.             treap.Insert(val, id);
  137.             const TreapNode* lower = treap.SeekLowerBound(val);
  138.             const TreapNode* upper = treap.SeekUpperBound(val);
  139.             if (val - lower->val <= upper->val - val) {
  140.                 printf("%d %d\n", id, lower->id);
  141.             } else {
  142.                 printf("%d %d\n", id, upper->id);
  143.             }
  144.         }
  145.     }
  146. }
  148. void SolveUVA10107() {
  149.     int n, counter = 0;
  150.     while (~scanf("%d", &n)) {
  151.         counter++;
  152.         treap.Insert(n, 0);
  153.         if (counter & 1) {
  154.             printf("%d\n", treap.GetByRank(counter/2 + 1)->val);
  155.         } else {
  156.             printf("%lld\n", (0LL + treap.GetByRank(counter/2)->val + treap.GetByRank(counter/2+1)->val)/2);
  157.         }
  158.     }
  159. }
  161. int main() {
  163.     SolveUVA10107();
  164.     // SolveHDU4585();
  166.     return 0;
  167. }

Graph Theory

2-SAT

  2. // https://atcoder.jp/contests/abc210/tasks/abc210_f
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. struct SCC {
  11.     static const int N = 30000 * 22 * 2 * 2 + 100;
  12.     vector<int> G[N];
  13.     vector<int> rG[N];
  14.     bool vis[N];
  15.     int id[N];
  16.     vector<int> cmp[N];
  18.     SCC() {
  19.         memset(vis, 0, sizeof(vis));
  20.     }
  22.     // a --> b
  23.     // !a || b
  24.     // a -> b and !b -> !a
  25.     void Infer(int u, int v) {
  26.         AddEdge(u, v);
  27.         AddEdge(v^1, u^1);
  28.     }
  30.     void AddEdge(int u, int v) {
  31.         G[u].push_back(v);
  32.         rG[v].push_back(u);
  33.     }
  35.     void dfs(int u, vector<int>& orders) {
  36.         vis[u] = 1;
  37.         for (const int v : G[u]) {
  38.             if (!vis[v]) dfs(v, orders);
  39.         }
  40.         orders.push_back(u);
  41.     }
  43.     void rdfs(int u, int k) {
  44.         vis[u] = 1;
  45.         id[u] = k, cmp[k].push_back(u);
  46.         for (const int v : rG[u]) {
  47.             if (!vis[v]) rdfs(v, k);
  48.         }
  49.     }
  51.     void run(int n) {
  52.         vector<int> orders;
  53.         for (int i = 0; i < n; i++) {
  54.             if (!vis[i]) dfs(i, orders);
  55.         }
  56.         reverse(orders.begin(), orders.end());
  57.         std::fill(vis, vis+n, false);
  59.         int k = 0;
  60.         for (const int u : orders) {
  61.             if (!vis[u]) {
  62.                 rdfs(u, ++k);
  63.             }
  64.         }
  65.     }
  67. } scc;
  69. const int M = 2e6 + 10;
  70. int mip[M];
  71. vector<int> primes;
  73. void init() {
  74.     mip[1] = 1;
  75.     for (int i = 2; i < M; i++) {
  76.         if (mip[i] == 0) mip[i] = i, primes.push_back(i);
  77.         for (const int p : primes) {
  78.             int u = p * i;
  79.             if (u >= M) break;
  80.             mip[u] = p;
  81.             if (i % p == 0) break;
  82.         }
  83.     }
  84. }
  86. vector<int> GetPrimeFactors(int n) {
  87.     vector<int> res;
  88.     while (n > 1) {
  89.         int p = mip[n];
  90.         res.push_back(p);
  91.         while (n % p == 0) n /= p;
  92.     }
  93.     return res;
  94. }
  96. vector<pii> X[M];
  98. void solve() {
  99.     init();
  101.     int n;
  102.     scanf("%d", &n);
  103.     int cur = n;
  104.     for (int i = 0; i < n; i++) {
  105.         int a, b;
  106.         scanf("%d%d", &a, &b);
  107.         for (const int p : GetPrimeFactors(a)) {
  108.             X[p].push_back(pii(i << 1, cur++ << 1));
  109.         }
  110.         for (const int p : GetPrimeFactors(b)) {
  111.             X[p].push_back(pii(i << 1 | 1, cur++ << 1));
  112.         }
  113.     }
  115.     for (int i = 2; i < M; i++) {
  116.         const auto& xp = X[i];
  117.         int sz = xp.size();
  118.         if (sz <= 1) continue;
  120.         for (int i = 0; i < sz; i++) {
  121.             if (i+1 < sz) {
  122.                 scc.Infer(xp[i].first, xp[i+1].second);
  123.                 scc.Infer(xp[i].second, xp[i+1].second);
  124.             }
  125.             scc.Infer(xp[i].second, xp[i].first ^ 1);
  126.         }
  127.     }
  129.     scc.run(2*cur);
  130.     // topo order of x > topo order of !x <==> x is ture
  131.     for (int i = 0; i < cur; i++) {
  132.         if (scc.id[i << 1] == scc.id[i << 1 | 1]) {
  133.             printf("No\n");
  134.             return ;
  135.         }
  136.     }
  137.     printf("Yes\n");
  138. }
  140. int main() {
  141.     int T = 1;
  142.     // scanf("%d", &T);
  143.     while (T--) solve();
  144.     return 0;
  145. }

Cut Point

  2. // author: yang12138
  3. // https://www.luogu.com.cn/problem/P3388
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 1e5+10;
  11. const int M = 1e5+10;
  13. vector<pii> G[N];
  15. int low[N], ord[N], cnt = 0;
  16. bool vise[M];
  18. void DFS(int u, int f, vector<int>& ans) {
  19.     ord[u] = low[u] = ++cnt;
  20.     bool flag = 0;
  21.     int son = 0;
  22.     for (auto [v, eid] : G[u]) {
  23.         if (vise[eid]) continue;
  24.         vise[eid] = 1;
  25.         if (!low[v]) {
  26.             DFS(v, u, ans);
  27.             low[u] = min(low[u], low[v]);
  28.             if (low[v] >= ord[u]) flag = 1;
  29.             son++;
  30.         } else {
  31.             low[u] = min(low[u], ord[v]);
  32.         }
  33.     }
  34.     if (f ? flag : (son > 1)) {
  35.         ans.push_back(u);
  36.     }
  37. }
  39. void solve() {
  40.     int n, m;
  41.     scanf("%d%d", &n, &m);
  42.     for (int i = 0; i < m; i++) {
  43.         int u, v;
  44.         scanf("%d%d", &u, &v);
  45.         G[u].push_back(pii(v, i));
  46.         G[v].push_back(pii(u, i));
  47.     }
  48.     vector<int> ans;
  49.     for (int i = 1; i <= n; i++)
  50.         if (!low[i])
  51.             DFS(i, 0, ans);
  52.     sort(ans.begin(), ans.end());
  53.     printf("%d\n", (int)ans.size());
  54.     for (int i : ans) printf("%d ", i);
  55.     printf("\n");
  56. }
  58. int main() {
  59.     int T = 1;
  60.     // scanf("%d", &T);
  61.     while (T--) solve();
  62.     return 0;
  63. }

Edge BCC

  2. // author: yang12138
  3. // https://www.luogu.com.cn/problem/P2860
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 1e5+10;
  11. const int M = 1e5+10;
  13. vector<pii> G[N];
  14. vector<int> G2[N];
  15. vector<pii> edges;
  17. int low[N], ord[N], cnt = 0;
  18. bool vise[M];
  19. int id[N], deg[N];
  21. void DFS(int u, int f) {
  22.     ord[u] = low[u] = ++cnt;
  23.     for (auto [v, eid] : G[u]) {
  24.         if (vise[eid]) continue;
  25.         vise[eid] = 1;
  26.         if (!low[v])
  27.             DFS(v, u), low[u] = min(low[u], low[v]);
  28.         else
  29.             low[u] = min(low[u], ord[v]);
  30.     }
  31.     if (low[u] < ord[u]) {
  32.         G2[u].push_back(f);
  33.         G2[f].push_back(u);
  34.     }
  35. }
  37. void DFS2(int u, int k) {
  38.     id[u] = k;
  39.     for (auto v : G2[u])
  40.         if (!id[v]) DFS2(v, k);
  41. }
  43. void solve() {
  44.     int n, m;
  45.     scanf("%d%d", &n, &m);
  46.     for (int i = 0; i < m; i++) {
  47.         int u, v;
  48.         scanf("%d%d", &u, &v);
  49.         G[u].push_back(pii(v, i));
  50.         G[v].push_back(pii(u, i));
  51.         edges.push_back(pii(u, v));
  52.     }
  53.     DFS(1, 0);
  55.     int k = 0;
  56.     for (int i = 1; i <= n; i++)
  57.         if (!id[i]) DFS2(i, ++k);
  59.     int ecnt = 0;
  60.     for (auto [u, v] : edges) {
  61.         if (id[u] != id[v])
  62.             deg[id[u]]++, deg[id[v]]++, ecnt++;
  63.     }
  64.     assert(ecnt == k - 1);
  65.     int ans = 0;
  66.     for (int i = 1; i <= k; i++) {
  67.         ans += (deg[i] == 1);
  68.     }
  69.     printf("%d\n", k == 1 ? 0 : (ans + 1) / 2);
  70. }
  72. int main() {
  73.     int T = 1;
  74.     // scanf("%d", &T);
  75.     while (T--) solve();
  76.     return 0;
  77. }

Tree

Divide And Conquer 1

  2. // http://poj.org/problem?id=1741
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 1e4 + 10;
  11. const int INF = 1e9;
  13. vector<pii> G[N];
  14. bool is_centroid[N];
  15. int D;
  17. int GetSubTreeSize(int u, int f) {
  18.     int ans = 1;
  19.     for (const auto pir : G[u]) {
  20.         int v = pir.first;
  21.         if (is_centroid[v] || v == f) continue;
  22.         ans += GetSubTreeSize(v, u);
  23.     }
  24.     return ans;
  25. }
  27. int SearchCentroid(int u, int f, const int size, pii& res) {
  28.     int maxsize = 0, sum = 0;
  29.     for (const auto pir : G[u]) {
  30.         int v = pir.first;
  31.         if (is_centroid[v] || v == f) continue;
  32.         int tmp = SearchCentroid(v, u, size, res);
  33.         maxsize = max(maxsize, tmp);
  34.         sum += tmp;
  35.     }
  36.     maxsize = max(maxsize, size - 1 - sum);
  37.     if (maxsize < res.first) res = pii(maxsize, u);
  38.     return sum + 1;
  39. }
  41. void GetPaths(int u, int f, int d, vector<int>& paths) {
  42.     paths.push_back(d);
  43.     for (const auto pir : G[u]) {
  44.         int v = pir.first;
  45.         if (is_centroid[v] || v == f) continue;
  46.         GetPaths(v, u, d + pir.second, paths);
  47.     }
  48. }
  50. int Calc(vector<int>& ds) {
  51.     sort(ds.begin(), ds.end());
  52.     int l = 0, r = ds.size() - 1;
  53.     int ans = 0;
  54.     while (l < r) {
  55.         while (r > l && ds[l] + ds[r] > D) r--;
  56.         if (r <= l) break;
  57.         ans += r - l;
  58.         l++;
  59.     }
  60.     return ans;
  61. }
  63. void DivideAndConquer(int u, int& ans) {
  65.     int size = GetSubTreeSize(u, 0);
  67.     pii res(INF, 0);
  68.     SearchCentroid(u, 0, size, res);
  69.     const int root = res.second;
  70.     assert(root);
  72.     is_centroid[root] = 1;
  74.     vector<int> paths = {0};
  75.     for (const auto pir : G[root]) {
  76.         int v = pir.first;
  77.         if (!is_centroid[v]) {
  78.             DivideAndConquer(v, ans);
  79.             vector<int> tmp;
  80.             GetPaths(v, 0, pir.second, tmp);
  81.             paths.insert(paths.end(), tmp.begin(), tmp.end());
  82.             ans -= Calc(tmp);
  83.         }
  84.     }
  85.     ans += Calc(paths);
  87.     is_centroid[root] = 0;
  88. }
  90. bool solve() {
  91.     int n;
  92.     scanf("%d%d", &n, &D);
  93.     if (n == 0 && D == 0) return false;
  95.     for (int i = 1; i <= n; i++) G[i].clear();
  97.     for (int i = 1; i < n; i++) {
  98.         int u, v, w;
  99.         scanf("%d%d%d", &u, &v, &w);
  100.         G[u].push_back(pii(v, w));
  101.         G[v].push_back(pii(u, w));
  102.     }
  104.     int ans = 0;
  105.     DivideAndConquer(1, ans);
  106.     printf("%d\n", ans);
  108.     return true;
  109. }
  111. int main() {
  112.     while (solve());
  113.     return 0;
  114. }

Divide And Conquer 2

  1. #include <bits/stdc++.h>
  3. using namespace std;
  5. typedef pair<int, int> pii;
  6. typedef bitset<100010> BitSet;
  8. const int N = 3005;
  10. vector<int> G[N];
  11. int sz[N], is_centroid[N], w[N];
  13. int FindTreeSize(int u, int f) {
  14.     int ret = 1;
  15.     for (int v : G[u]) {
  16.         if (v == f || is_centroid[v]) continue;
  17.         ret += FindTreeSize(v, u);
  18.     }
  19.     return ret;
  20. }
  22. pii FindRoot(int u, int f, int ssz) {
  23.     sz[u] = 1;
  24.     pii ret(N, 0);
  25.     int ma = 0;
  26.     for (int v : G[u]) {
  27.         if (v == f || is_centroid[v]) continue;
  28.         ret = min(ret, FindRoot(v, u, ssz));
  29.         sz[u] += sz[v];
  30.         ma = max(ma, sz[v]);
  31.     }
  32.     ma = max(ma, ssz - sz[u]);
  33.     return min(ret, pii(ma, u));
  34. }
  36. void DP(int u, int f, BitSet& pre) {
  37.     BitSet cur = (pre << w[u]);
  38.     for (int v : G[u]) {
  39.         if (v == f || is_centroid[v]) continue;
  40.         DP(v, u, cur);
  41.     }
  42.     pre |= cur;
  43. }
  45. void DFS(int u, BitSet& ret) {
  46.     int root = FindRoot(u, 0, FindTreeSize(u, 0)).second;
  47.     assert(root);
  49.     BitSet bs;
  50.     bs[0] = 1;
  51.     DP(root, 0, bs);
  52.     ret |= bs;
  54.     is_centroid[root] = 1;
  55.     for (int v : G[root]) {
  56.         if (!is_centroid[v]) {
  57.             DFS(v, ret);
  58.         }
  59.     }
  60.     is_centroid[root] = 0;
  61. }
  63. void solve() {
  64.     int n, m;
  65.     scanf("%d%d", &n, &m);
  66.     for (int i = 1; i <= n; i++) {
  67.         G[i].clear();
  68.         sz[i] = is_centroid[i] = 0;
  69.     }
  70.     for (int i = 1; i < n; i++) {
  71.         int u, v;
  72.         scanf("%d%d", &u, &v);
  73.         G[u].push_back(v);
  74.         G[v].push_back(u);
  75.     }
  76.     for (int i = 1; i <= n; i++) {
  77.         scanf("%d", w + i);
  78.     }
  80.     BitSet ret;
  81.     DFS(1, ret);
  82.     for (int i = 1; i <= m; i++) printf("%d", int(ret[i]));
  83.     printf("\n");
  84. }
  86. int main() {
  87.     int T;
  88.     scanf("%d", &T);
  89.     while (T--) solve();
  90.     return 0;
  91. }

Steiner Tree

  2. // https://www.luogu.com.cn/problem/P6192
  3. // n points, m edges, k key points
  4. // O(n3^k) + O(2^kmlogn)
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  11. const int N = 105;
  12. const int K = 10;
  13. const int INF = 1e9;
  15. int key_point[K];
  16. vector<pii> G[N];
  18. priority_queue<pii, vector<pii>, greater<pii>> que;
  20. void Dijkstra(int* dis) {
  21.     while (!que.empty()) {
  22.         pii t = que.top(); que.pop();
  23.         int u = t.second;
  24.         if (dis[u] < t.first) continue;
  25.         for (auto e : G[u]) {
  26.             int v = e.first, w = e.second;
  27.             if (dis[v] > dis[u] + w) {
  28.                 dis[v] = dis[u] + w;
  29.                 que.push(pii(dis[v], v));
  30.             }
  31.         }
  32.     }
  33. }
  35. int dis[1 << K][N];
  37. void solve() {
  38.     int n, m, k;
  39.     scanf("%d%d%d", &n, &m, &k);
  41.     for (int i = 1; i <= m; i++) {
  42.         int u, v, w;
  43.         scanf("%d%d%d", &u, &v, &w);
  44.         G[u].push_back(pii(v, w));
  45.         G[v].push_back(pii(u, w));
  46.     }
  48.     for (int s = 1; s < (1 << k); s++) fill(dis[s] + 1, dis[s] + n + 1, INF);
  49.     for (int i = 0; i < k; i++) {
  50.         scanf("%d", key_point + i);
  51.         dis[1 << i][key_point[i]] = 0;
  52.     }
  54.     for (int s = 1; s < (1 << k); s++) {
  55.         for (int i = 1; i <= n; i++) {
  56.             for (int mask = (s & (s - 1)); mask; mask = ((mask - 1) & s)) {
  57.                 dis[s][i] = min(dis[s][i], dis[mask][i] + dis[mask ^ s][i]);
  58.             }
  59.             if (dis[s][i] < INF)
  60.                 que.push(pii(dis[s][i], i));
  61.         }
  62.         Dijkstra(dis[s]);
  63.     }
  64.     printf("%d\n", dis[(1 << k) - 1][key_point[0]]);
  65. }
  67. int main() {
  68.     int T = 1;
  69.     // scanf("%d", &T);
  70.     while (T--) solve();
  71.     return 0;
  72. }

Tree-Chain Split

  2. // https://www.spoj.com/problems/QTREE/en/
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. #define lson (root << 1)
  11. #define rson (root << 1 | 1)
  13. const int N = 1e4 + 10;
  15. struct Edge {
  16.     int u, v, w;
  17.     void scan() { scanf("%d%d%d", &u, &v, &w); }
  18. } E[N];
  20. struct SegTree {
  21.     int val[N << 2];
  23.     SegTree() {
  24.         Clear();
  25.     }
  27.     void Clear() {
  28.         memset(val, 0, sizeof(val));
  29.     }
  31.     void Update(int root, int l, int r, int pos, int v) {
  32.         if (l == r) {
  33.             val[root] = v;
  34.             return ;
  35.         }
  36.         int m = (l + r) / 2;
  37.         if (pos <= m) Update(lson, l, m, pos, v);
  38.         else Update(rson, m+1, r, pos, v);
  39.         val[root] = max(val[lson], val[rson]);
  40.     }
  42.     int Query(int root, int l, int r, int a, int b) {
  43.         if (l == a && r == b) return val[root];
  44.         int m = (l + r) / 2;
  45.         if (b <= m) return Query(lson, l, m, a, b);
  46.         else if (a > m) return Query(rson, m+1, r, a, b);
  47.         return max(Query(lson, l, m, a, m), Query(rson, m+1, r, m+1, b));
  48.     }
  49. } bt;
  51. vector<pii> G[N];
  53. int fa[N], sz[N], son[N], dep[N];
  54. int top[N], rk[N], cnt = 0;
  56. void dfs1(int u, int f, int d) {
  57.     fa[u] = f, dep[u] = d;
  58.     son[u] = -1, sz[u] = 1;
  59.     for (const auto pir : G[u]) {
  60.         int v = pir.first;
  61.         if (v == f) continue;
  62.         dfs1(v, u, d + 1);
  63.         if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
  64.     }
  65. }
  67. int n;
  68. void dfs2(int u, int t) {
  69.     top[u] = t, rk[u] = ++cnt;
  70.     if (son[u] != -1) dfs2(son[u], t);
  71.     for (const auto pir : G[u]) {
  72.         int v = pir.first;
  73.         if (v == fa[u] || v == son[u]) continue;
  74.         dfs2(v, v);
  75.     }
  77.     for (const auto pir : G[u]) {
  78.         int v = pir.first;
  79.         if (v == fa[u]) continue;
  80.         bt.Update(1, 1, n, rk[v], pir.second);
  81.     }
  82. }
  84. int Query(int u, int v) {
  85.     // if (u == v) return 0;
  86.     int ans = 0;
  87.     while (top[u] != top[v]) {
  88.         if (dep[top[u]] < dep[top[v]]) swap(u, v);
  89.         ans = max(ans, bt.Query(1, 1, n, rk[top[u]], rk[u]));
  90.         u = fa[top[u]];
  91.     }
  92.     if (u != v) {
  93.         if (dep[u] > dep[v]) swap(u, v);
  94.         ans = max(ans, bt.Query(1, 1, n, rk[u]+1, rk[v]));
  95.     }
  96.     return ans;
  97. }
  99. void solve() {
  100.     scanf("%d", &n);
  101.     for (int i = 1; i <= n; i++) G[i].clear();
  102.     cnt = 0, bt.Clear();
  104.     for (int i = 1; i < n; i++) {
  105.         E[i].scan();
  106.         G[E[i].u].push_back(pii(E[i].v, E[i].w));
  107.         G[E[i].v].push_back(pii(E[i].u, E[i].w));
  108.     }
  110.     dfs1(1, 0, 0);
  111.     dfs2(1, 1);
  113.     char s[10];
  114.     int a, b;
  115.     while (1) {
  116.         scanf("%s", s);
  117.         if (s[0] == 'D') break;
  118.         scanf("%d%d", &a, &b);
  120.         if (s[0] == 'C') {
  121.             int u = E[a].u, v = E[a].v;
  122.             if (u != fa[v]) swap(u, v);
  123.             assert(u == fa[v]);
  124.             bt.Update(1, 1, n, rk[v], b);
  125.         } else {
  126.             printf("%d\n", Query(a, b));
  127.         }
  128.     }
  129. }
  131. int main() {
  132.     int T = 1;
  133.     scanf("%d", &T);
  134.     while (T--) solve();
  135.     return 0;
  136. }

Virtual Tree

  2. // author: yang12138
  3. // https://oi-wiki.org/graph/virtual-tree/
  4. // https://www.luogu.com.cn/record/75047671
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  11. const int N = 3e5+10;
  12. const int INF = 1e9;
  14. int fa[N][20];
  15. int wi[N][20];
  16. int dep[N];
  17. vector<pii> G[N];
  18. int id[N], cnt = 0;
  20. int GetLCA(int u, int v) {
  21.     if (dep[u] < dep[v]) swap(u, v);
  22.     int d = dep[u] - dep[v];
  23.     for (int i = 19; i >= 0; i--) {
  24.         if ((d >> i) & 1)
  25.             u = fa[u][i];
  26.     }
  27.     if (u == v) return u;
  28.     for (int i = 19; i >= 0; i--) {
  29.         if (fa[u][i] != fa[v][i])
  30.             u = fa[u][i], v = fa[v][i];
  31.     }
  32.     return fa[u][0];
  33. }
  35. int GetMinWi(int f, int u) {
  36.     int d = dep[u] - dep[f];
  37.     int ans = INF;
  38.     for (int i = 19; i >= 0; i--) {
  39.         if ((d >> i) & 1) {
  40.             ans = min(ans, wi[u][i]);
  41.             u = fa[u][i];
  42.         }
  43.     }
  44.     assert(u == f);
  45.     return ans;
  46. }
  48. void DFS(int u, int f, int d, int w) {
  49.     fa[u][0] = f, dep[u] = d, wi[u][0] = w, id[u] = ++cnt;
  50.     for (int i = 1; i < 20; i++) {
  51.         fa[u][i] = fa[fa[u][i-1]][i-1];
  52.         wi[u][i] = min(wi[u][i-1], wi[fa[u][i-1]][i-1]);
  53.     }
  54.     for (auto [v, w1] : G[u]) {
  55.         if (v != f) DFS(v, u, d + 1, w1);
  56.     }
  57. }
  59. vector<pii> G2[N];
  60. void AddEdge(int u, int v) {
  61.     G2[u].push_back(pii(v, GetMinWi(u, v)));
  62. }
  64. bool is[N];
  65. ll DP(int u, vector<int>& vs) {
  66.     vs.push_back(u);
  67.     ll dp = 0;
  68.     for (auto [v, w] : G2[u]) {
  69.         ll tdp = DP(v, vs);
  70.         dp += is[v] ? w : min(1LL*w, tdp);
  71.     }
  72.     return dp;
  73. }
  75. int sta[N];
  76. ll Solve(vector<int>& h) {
  77.     sort(h.begin(), h.end(), [](int a, int b) { return id[a] < id[b]; });
  78.     int top = 0;
  79.     sta[top++] = 1;
  80.     for (const int i : h) {
  81.         is[i] = 1;
  82.         assert(i != 1);
  83.         int lca = GetLCA(sta[top - 1], i);
  84.         if (lca != sta[top - 1]) {
  85.             while (id[lca] < id[sta[top - 2]]) {
  86.                 AddEdge(sta[top - 2], sta[top - 1]);
  87.                 top--;
  88.             }
  89.             AddEdge(lca, sta[top - 1]);
  90.             if (id[lca] != id[sta[top - 2]]) {
  91.                 sta[top - 1] = lca;
  92.             } else {
  93.                 top--;
  94.             }
  95.         }
  96.         sta[top++] = i;
  97.     }
  98.     for (int i = 0; i + 1 < top; i++)
  99.         AddEdge(sta[i], sta[i + 1]);
  101.     vector<int> vs;
  102.     ll ans = DP(1, vs);
  103.     for (int i : vs) G2[i].clear();
  104.     for (int i : h) is[i] = 0;
  105.     return ans;
  106. }
  108. void solve() {
  109.     int n;
  110.     scanf("%d", &n);
  111.     for (int i = 1; i < n; i++) {
  112.         int u, v, w;
  113.         scanf("%d%d%d", &u, &v, &w);
  114.         G[u].push_back(pii(v, w));
  115.         G[v].push_back(pii(u, w));
  116.     }
  117.     DFS(1, 0, 0, 0);
  119.     int m;
  120.     scanf("%d", &m);
  121.     while (m--) {
  122.         int k;
  123.         scanf("%d", &k);
  124.         vector<int> h(k);
  125.         for (int i = 0; i < k; i++) scanf("%d", &h[i]);
  126.         printf("%lld\n", Solve(h));
  127.     }
  128. }
  130. int main() {
  131.     int T = 1;
  132.     // scanf("%d", &T);
  133.     while (T--) solve();
  134.     return 0;
  135. }

Math

Fast Walsh Transform

  2. // author: yang12138
  4. // ref: https://oi-wiki.org/math/poly/fwt/
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  10. // C = A \oplus B
  11. // FWT(C) = FWT(A) * FWT(B)
  13. // sig(i & j) ^ sig(i & k) = sig(i & (j ^ k))
  14. // xor: A'(i) = \sum_{j}((-1)^sig(i & j) * A_j)
  16. // or: A'(i) = \sum_{i=j|i}A_j
  17. // and: A'(i) = \sum_{i=j&i}A_j
  19. void FWT(vector<ll>& a, int flag) {
  20.     int n = a.size();
  21.     assert((n & (n - 1)) == 0);
  22.     for (int w = 2; w <= n; w <<= 1) {
  23.         for (int i = 0; i < n; i += w) {
  24.             for (int j = i; j < i + w / 2; j++) {
  25.                 ll u = a[j], v = a[j + w / 2];
  26.                 if (flag == 1) {
  27.                     // xor
  28.                     a[j] = u + v, a[j + w / 2] = u - v;
  29.                     // or
  30.                     // a[j] = u, a[j + w / 2] = u + v;
  31.                     // and
  32.                     // a[j] = u + v, a[j + w / 2] = v;
  33.                 } else {
  34.                     // xor
  35.                     a[j] = (u + v) / 2, a[j + w / 2] = (u - v) / 2;
  36.                     // or
  37.                     // a[j] = u, a[j + w / 2] = v - u;
  38.                     // and
  39.                     // a[j] = u - v, a[j + w / 2] = v;
  40.                 }
  41.             }
  42.         }
  43.     }
  44. }
  46. void solve() {
  47.     srand(time(nullptr));
  48.     int n;
  49.     cin >> n;
  50.     vector<ll> a(n), b(n);
  51.     for (int i = 0; i < n; i++) a[i] = rand() % 100000;
  52.     for (int i = 0; i < n; i++) b[i] = rand() % 100000;
  54.     auto Print = [](const vector<ll>& a) {
  55.         for (ll i : a) printf("%lld ", i);
  56.         printf("\n");
  57.     };
  59.     vector<ll> c(n);
  60.     for (int i = 0; i < n; i++) {
  61.         for (int j = 0; j < n; j++) {
  62.             c[i ^ j] += a[i] * b[j];
  63.         }
  64.     }
  65.     printf("baoli result\n");
  66.     Print(c);
  68.     FWT(a, 1);
  69.     FWT(b, 1);
  70.     vector<ll> d(n);
  71.     for (int i = 0; i < n; i++) d[i] = a[i] * b[i];
  72.     FWT(d, -1);
  74.     printf("FWT result\n");
  75.     Print(d);
  77.     bool succ = true;
  78.     for (int i = 0; i < n; i++)
  79.         succ &= (c[i] == d[i]);
  80.     printf("test %s\n", succ ? "succ" : "fail");
  81. }
  83. int main() {
  84.     int T = 1;
  85.     // scanf("%d", &T);
  86.     while (T--) solve();
  87.     return 0;
  88. }

Fast Fourier Transform

  2. // https://acm.hdu.edu.cn/showproblem.php?pid=1402
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. typedef std::complex<double> Complex;
  9. const double pi = acos(-1.0);
  11. void DFT(vector<Complex>& a, const int opt) {
  12.     int n = a.size();
  13.     if (n <= 1) return ;
  14.     assert(!(n & (n - 1)));
  16.     for (int i = 0, j = 0; i < n - 1; i++) {
  17.         if (i < j) swap(a[i], a[j]);
  18.         int k = n >> 1;
  19.         while (j >= k) j -= k, k >>= 1;
  20.         j += k;
  21.     }
  23.     for (int i = 2; i <= n; i <<= 1) {
  24.         Complex wn = exp(Complex(0, opt * 2.0 * pi / i));
  25.         for (int j = 0; j < n; j += i) {
  26.             Complex w(1, 0);
  27.             for (int k = 0; k < i / 2; k++) {
  28.                 Complex u = a[j + k];
  29.                 Complex v = w * a[j + k + i / 2];
  30.                 a[j + k] = u + v;
  31.                 a[j + k + i / 2] = u - v;
  32.                 w = w * wn;
  33.             }
  34.         }
  35.     }
  37.     if (opt == -1) {
  38.         for (int i = 0; i < n; i++) a[i] /= n;
  39.     }
  40. }
  42. vector<int> FFT(const vector<int>& a, const vector<int>& b) {
  43.     int len = 1;
  44.     while (len < max(a.size(), b.size())) len <<= 1;
  45.     len <<= 1;
  46.     vector<Complex> ca(len), cb(len);
  47.     for (int i = 0; i < a.size(); i++) ca[i] = Complex(a[i], 0);
  48.     for (int i = 0; i < b.size(); i++) cb[i] = Complex(b[i], 0);
  50.     DFT(ca, 1);
  51.     DFT(cb, 1);
  52.     vector<Complex> cc(len);
  53.     for (int i = 0; i < len; i++) cc[i] = ca[i] * cb[i];
  54.     DFT(cc, -1);
  56.     vector<int> c(len);
  57.     for (int i = 0; i < len; i++) c[i] = int(cc[i].real() + 0.5);
  58.     return c;
  59. }
  61. const int N = 1e6 + 10;
  62. char s[N], t[N];
  63. bool solve() {
  64.     if (scanf("%s%s", s, t) != 2) return false;
  66.     int n = strlen(s), m = strlen(t);
  67.     vector<int> a(n), b(m);
  68.     for (int i = 0; i < n; i++) a[i] = s[n - 1 - i] - '0';
  69.     for (int i = 0; i < m; i++) b[i] = t[m - 1 - i] - '0';
  70.     auto c = FFT(a, b);
  71.     c.resize(c.size() + 5);
  72.     int cn = c.size();
  73.     for (int i = 1; i < cn; i++) {
  74.         c[i] += c[i - 1] / 10;
  75.         c[i - 1] %= 10;
  76.     }
  78.     bool pri = false;
  79.     for (int i = cn - 1; i >= 0; i--) {
  80.         if (pri || c[i]) {
  81.             pri = true;
  82.             printf("%d", c[i]);
  83.         }
  84.     }
  85.     if (!pri) printf("0");
  86.     printf("\n");
  87.     return true;
  88. }
  90. int main() {
  91.     while (solve());
  92.     return 0;
  93. }

Number-Theoretic Transform

  2. // https://acm.hdu.edu.cn/showproblem.php?pid=1402
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. typedef long long ll;
  7. typedef pair<int, int> pii;
  9. template<int MOD>
  10. struct ModInt {
  11.   public:
  12.     constexpr ModInt() {}
  13.     constexpr ModInt(int _x) : x(_x) { Ajust(); }
  14.     constexpr ModInt(ll _x) : x(_x % MOD) { Ajust(); }
  15.     constexpr inline int value() const { return x; }
  16.     constexpr inline int inv() const { return Pow(MOD - 2).value(); }
  17.     constexpr inline ModInt operator + (const ModInt& rhs) const { return ModInt(x + rhs.value()); }
  18.     constexpr inline ModInt operator - (const ModInt& rhs) const { return ModInt(x - rhs.value()); }
  19.     constexpr inline ModInt operator * (const ModInt& rhs) const { return ModInt(1LL * x * rhs.value()); }
  20.     constexpr inline ModInt operator / (const ModInt& rhs) const { return ModInt(1LL * x * rhs.inv()); }
  21.     constexpr inline ModInt operator % (const ModInt& rhs) const { return ModInt(x % rhs.value()); }
  22.     constexpr inline ModInt& operator += (const ModInt& rhs) { return (*this = ModInt(x + rhs.value())); }
  23.     constexpr inline ModInt& operator -= (const ModInt& rhs) { return (*this = ModInt(x - rhs.value())); }
  24.     constexpr inline ModInt& operator *= (const ModInt& rhs) { return (*this = ModInt(1LL * x * rhs.value())); }
  25.     constexpr inline ModInt& operator /= (const ModInt& rhs) { return (*this = ModInt(1LL * x * rhs.inv())); }
  26.     constexpr inline ModInt& operator %= (const ModInt& rhs) { return (*this = ModInt(x % rhs.value())); }
  27.     ModInt Pow(ll n) const {
  28.         ll ans = 1, p = x;
  29.         while (n) {
  30.             if (n & 1) ans = ans * p % MOD;
  31.             p = p * p % MOD;
  32.             n >>= 1;
  33.         }
  34.         return ModInt(ans);
  35.     }
  37.   private:
  38.     constexpr inline void Ajust() {
  39.         if (x >= 2 * MOD || x < -MOD) x %= MOD;
  40.         if (x >= MOD) x -= MOD;
  41.         else if (x < 0) x += MOD;
  42.     }
  44.     int x = 0;
  45. };
  47. constexpr int MOD = 998244353;
  48. typedef ModInt<MOD> mint;
  49. constexpr mint g = 3;
  51. void DFT(vector<mint>& a, int opt) {
  52.     int n = a.size();
  53.     if (n <= 1) return ;
  54.     assert(!(n & (n - 1)));
  56.     for (int i = 0, j = 0; i < n - 1; i++) {
  57.         if (i < j) swap(a[i], a[j]);
  58.         int k = n / 2;
  59.         while (j >= k) j -= k, k /= 2;
  60.         j += k;
  61.     }
  63.     for (int i = 2; i <= n; i <<= 1) {
  64.         mint wn = g.Pow(1LL * (MOD - 1) / i * ((opt < 0) ? (MOD - 2) : 1));
  65.         for (int j = 0; j < n; j += i) {
  66.             mint w = 1;
  67.             for (int k = j; k < j + i / 2; k++) {
  68.                 mint u = a[k], v = w * a[k + i / 2];
  69.                 a[k] = u + v, a[k + i / 2] = u - v;
  70.                 w *= wn;
  71.             }
  72.         }
  73.     }
  74.     if (opt < 0) {
  75.         mint invn = mint(n).inv();
  76.         for (int i = 0; i < n; i++) a[i] *= invn;
  77.     }
  78. }
  80. const int N = 1e6 + 10;
  81. char s[N], t[N];
  83. bool solve() {
  84.     if (scanf("%s%s", s, t) != 2) return false;
  86.     int n = strlen(s), m = strlen(t);
  87.     int len = 1;
  88.     while (len < n + m - 1) len <<= 1;
  90.     vector<mint> a(len), b(len);
  91.     for (int i = 0; i < n; i++) a[n - 1 - i] = s[i] - '0';
  92.     for (int i = 0; i < m; i++) b[m - 1 - i] = t[i] - '0';
  94.     DFT(a, 1);
  95.     DFT(b, 1);
  96.     for (int i = 0; i < len; i++) a[i] *= b[i];
  97.     DFT(a, -1);
  99.     a.resize(a.size() + 5);
  100.     for (int i = 1; i < a.size(); i++) {
  101.         a[i] += a[i - 1].value() / 10;
  102.         a[i - 1] %= 10;
  103.     }
  105.     bool pri = false;
  106.     for (int i = a.size() - 1; i >= 0; i--) {
  107.         if (pri || a[i].value() || i == 0) {
  108.             printf("%d", a[i].value());
  109.             pri = true;
  110.         }
  111.     }
  112.     printf("\n");
  113.     return true;
  114. }
  116. int main() {
  117.     while (solve());
  118.     return 0;
  119. }

Chinese Remainder Theorem

  2. // http://acm.hdu.edu.cn/showproblem.php?pid=3579
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  9. typedef vector<ll> vii;
  11. void AddMod(ll& a, ll b, ll mod) {
  12.     a += b;
  13.     if (a >= mod) a -= mod;
  14. }
  16. ll MulMod(ll a, ll b, ll mod) {
  17.     a %= mod, b %= mod;
  18.     if (a > b) swap(a, b);
  19.     ll ans = 0;
  20.     while (a) {
  21.         if (a & 1) AddMod(ans, b, mod);
  22.         AddMod(b, b, mod);
  23.         a >>= 1;
  24.     }
  25.     return ans;
  26. }
  28. void Exgcd(ll a, ll b, ll& x, ll& y) {
  29.     if (b == 0) {
  30.         x = 1, y = 0;
  31.     } else {
  32.         Exgcd(b, a % b, x, y);
  33.         // b*x+(a%b)*y = 1
  34.         // b*x+(a-a/b*b)*y=1
  35.         // b*(x-a/b*y)+a*y=1
  36.         ll t = y;
  37.         y = x - a / b * y;
  38.         x = t;
  39.     }
  40. }
  42. ll MulInv(ll a, ll mod) {
  43.     a %= mod;
  44.     ll x, y;
  45.     Exgcd(a, mod, x, y);
  46.     assert(a * x + mod * y == 1);
  47.     x %= mod;
  48.     if (x < 0) x += mod;
  49.     return x;
  50. }
  52. ll ChineseRemainderTheorem(const vii& mods, const vii& xs) {
  53.     assert(mods.size() == xs.size() && mods.size());
  54.     const int n = mods.size();
  56.     ll M = 1;
  57.     for (const ll mod : mods) M *= mod;
  59.     ll ans = 0;
  60.     for (int i = 0; i < n; i++) {
  61.         ll mi = M / mods[i];
  62.         AddMod(ans, MulMod(mi * MulInv(mi, mods[i]), xs[i], M), M);
  63.     }
  64.     return ans;
  65. }
  67. ll ChineseRemainderTheoremCoprimeVersion(const vii& mods, const vii& xs) {
  68.     auto Process = [](ll x1, ll mod1, ll x2, ll mod2, ll& x, ll& mod) -> bool {
  69.         ll g = __gcd(mod1, mod2);
  70.         if ((x1 - x2) % g) return false;
  71.         mod1 /= g, mod2 /= g;
  72.         mod = mod1 * mod2 * g;
  73.         x = MulMod(x2 - x1 + mod, MulInv(mod1, mod2) * mod1, mod);
  74.         AddMod(x, x1, mod);
  75.         return true;
  76.     };
  77.     assert(mods.size() == xs.size() && mods.size());
  78.     const int n = mods.size();
  79.     ll x = xs[0], mod = mods[0];
  80.     for (int i = 1; i < n; i++) {
  81.         if (!Process(x, mod, xs[i], mods[i], x, mod)) return -1;
  82.     }
  83.     if (x == 0) x = mod;
  84.     return x;
  85. }
  87. ll solve() {
  88.     int n;
  89.     scanf("%d", &n);
  90.     vii mods(n), xs(n);
  91.     for (int i = 0; i < n; i++)
  92.         scanf("%lld", &mods[i]);
  93.     for (int i = 0; i < n; i++)
  94.         scanf("%lld", &xs[i]);
  95.     return ChineseRemainderTheoremCoprimeVersion(mods, xs);
  96. }
  98. int main() {
  99.     int T = 1, t = 0;
  100.     scanf("%d", &T);
  101.     while (T--) {
  102.         printf("Case %d: %lld\n", ++t, solve());
  103.     }
  104.     return 0;
  105. }

Prime Count

  2. // http://acm.hdu.edu.cn/showproblem.php?pid=5901
  4. // author: yang12138
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  11. namespace primecount {
  13. // 240MB
  14. const int N = 70000;
  15. const int M = 700;
  16. const int PM = 1e7 + 10;
  18. int phi[N][M];
  19. int p[PM / 20], pcnt = 0;
  20. int pc[PM];
  22. void init() {
  23.     for (int i = 2; i < PM; i++) {
  24.         if (!pc[i]) p[++pcnt] = i;
  25.         for (int j = 1; j <= pcnt; j++) {
  26.             int u = i * p[j];
  27.             if (u >= PM) break;
  28.             pc[u] = 1;
  29.             if (i % p[j] == 0) break;
  30.         }
  31.     }
  33.     for (int i = 1; i < N; i++) phi[i][0] = i - 1;
  34.     for (int i = 1; i < N; i++) {
  35.         for (int j = 1; j < M; j++) {
  36.             phi[i][j] = phi[i][j-1];
  37.             if (i >= p[j] * p[j]) 
  38.                 phi[i][j] -= phi[i / p[j]][j-1] - (j - 1);
  39.         }
  40.     }
  41.     for (int i = 2; i < PM; i++)
  42.         pc[i] = pc[i-1] + !pc[i];
  43. }
  45. ll Phi(ll n, int m) {
  46.     if (n <= 1) return 0;
  47.     if (n < N && m < M) return phi[n][m];
  48.     if (m == 0) return n - 1;
  49.     ll ans = Phi(n, m - 1);
  50.     if (n / p[m] >= p[m]) {
  51.         ans -= Phi(n / p[m], m - 1) - (m - 1);
  52.     }
  53.     return ans;
  54. }
  56. int Sqrt(ll n) {
  57.     int k = sqrt(n + 0.01);
  58.     while (1LL * k * k > n) k--;
  59.     while (1LL * (k + 1) * (k + 1) <= n) k++;
  60.     return k;
  61. }
  63. int Cbrt(ll n) {
  64.     int k = cbrt(n + 0.01);
  65.     while (1LL * k * k * k > n) k--;
  66.     while (1LL * (k + 1) * (k + 1) * (k + 1) <= n) k++;
  67.     return k;
  68. }
  70. // 2 ~ n
  71. // 1e11 350ms
  72. // 1e12 2s
  73. ll PrimeCount(ll n) {
  74.     if (n < PM) return pc[n];
  76.     int a = pc[Sqrt(n)], b = pc[Cbrt(n)];
  77.     ll ans = Phi(n, b);
  78.     for (int i = b + 1; i <= a; i++) {
  79.         ans -= PrimeCount(n / p[i]);
  80.     }
  81.     ans += 1LL * b * (a - b) + 1LL * (a - b) * (a - b - 1) / 2;
  82.     return ans;
  83. }
  85. } // namespace primecount
  87. void solve() {
  88.     ll n;
  89.     scanf("%lld", &n);
  90.     printf("%lld\n", primecount::PrimeCount(n));
  91. }
  93. int main() {
  94.     primecount::init();
  95.     int T = 1;
  96.     scanf("%d", &T);
  97.     while (T--) solve();
  98.     return 0;
  99. }

Simplex

  2. // http://acm.hdu.edu.cn/showproblem.php?pid=6248
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const double eps = 1e-8;
  11. const double inf = 1e18;
  13. int dcmp(const double x) {
  14.     return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);
  15. }
  17. /*
  18.    target = v + sum(c_i*x_i), i in non_basic
  19.    x_i = b_i - sum(A_{ij}*x_j), i in basic, j in non_basic
  20. */
  22. struct Simplex {
  23.  public:
  24.     Simplex(int n, int m): n(n), m(m), size(n + m + 2), A(size, vector<double>(size, 0)), x(size, 0) {
  25.         for (int i = 1; i <= n; i++) non_basic.insert(i);
  26.         for (int i = 1; i <= m; i++) basic.insert(n + i);
  27.     }
  28.     ~Simplex() {}
  30.     // variable 1 ~ n
  31.     // restrict n + 1 ~ n + m
  33.     void AddRestricts(const vector<vector<double>>& restricts) {
  34.         assert(restricts.size() == m);
  35.         assert(restricts[0].size() == n + 1);
  36.         for (int i = 0; i < m; i++) {
  37.             for (int j = 0; j <= n; j++) {
  38.                 A[1 + n + i][j] = restricts[i][j];
  39.             }
  40.         }
  41.     }
  43.     void SetTarget(const vector<double>& target) {
  44.         assert(target.size() == n + 1);
  45.         for (int i = 0; i <= n; i++) A[0][i] = target[i];
  46.     }
  48.     const vector<double>& GetVariable() { return x; }
  50.     double GetAns() { return A[0][0]; }
  52.     // -1 no answer, -2 unlimited answer, 0 nomral answer
  53.     int Run() {
  54.         // print();
  56.         if (!Fesible()) {
  57.             // printf("fuck, infesible\n");
  58.             const auto real_target = A[0];
  59.             std::fill(A[0].begin(), A[0].end(), 0);
  60.             // target = -x_0
  61.             // x_i = b_i - sum(A_{ij}*x_j) + x_0
  62.             A[0][size - 1] = -1;
  63.             int idx = -1;
  64.             for (const int i : basic) {
  65.                 A[i][size - 1] = -1;
  66.                 if (idx == -1 || A[i][0] < A[idx][0]) idx = i;
  67.             }
  68.             non_basic.insert(size - 1);
  69.             Pivot(size - 1, idx);
  70.             assert(Fesible());
  72.             RunSimplex();
  73.             if (dcmp(x[size - 1]) != 0) return -1;
  75.             if (basic.count(size - 1)) {
  76.                 for (const int i : non_basic) {
  77.                     if (dcmp(A[size - 1][i]) != 0) {
  78.                         Pivot(i, size - 1);
  79.                         break;
  80.                     }
  81.                 }
  82.             }
  83.             non_basic.erase(size - 1);
  84.             A[0] = real_target;
  86.             for (const int i : basic) {
  87.                 if (dcmp(A[0][i]) != 0) {
  88.                     for (const int j : non_basic) {
  89.                         A[0][j] -= A[0][i] * A[i][j];
  90.                     }
  91.                     A[0][0] += A[0][i] * A[i][0];
  92.                 }
  93.             }
  94.         }
  95.         assert(Fesible());
  97.         // print();
  98.         return RunSimplex();
  99.     }
  101.     void print() const {
  102.         printf("target = %.3f + ", A[0][0]);
  103.         bool start = true;
  104.         for (const int j : non_basic) {
  105.             if (!start) printf(" + ");
  106.             start = false;
  107.             printf("%.3f*x(%d)", A[0][j], j);
  108.         }
  109.         printf("\n");
  110.         for (const int i : basic) {
  111.             printf("x(%d) = %.3f - (", i, A[i][0]);
  112.             bool start = true;
  113.             for (const int j : non_basic) {
  114.                 if (!start) printf(" + ");
  115.                 start = false;
  116.                 printf("%.3f*x(%d)", A[i][j], j);
  117.             }
  118.             printf(")\n");
  119.         }
  120.         printf("\n");
  121.     }
  123.  private:
  124.     const int n, m, size;
  125.     vector<vector<double>> A;
  126.     vector<double> x;
  128.     std::set<int> basic, non_basic;
  130.     // e nonbasic, l basic
  131.     void Pivot(int e, int l) {
  132.         assert(dcmp(A[l][e]) != 0);
  133.         // printf("Pivot e %d, l %d\n", e, l);
  134.         A[e][0] = A[l][0] / A[l][e];
  135.         for (const int i : non_basic) {
  136.             if (i == e) continue;
  137.             A[e][i] = A[l][i] / A[l][e];
  138.         }
  139.         A[e][l] = 1.0 / A[l][e];
  141.         for (const int i : basic) {
  142.             if (i == l) continue;
  143.             A[i][0] -= A[i][e] * A[e][0];
  144.             for (const int j : non_basic) {
  145.                 if (j == e) continue;
  146.                 A[i][j] -= A[i][e] * A[e][j];
  147.             }
  148.             A[i][l] = -A[i][e] * A[e][l];
  149.         }
  151.         A[0][0] += A[0][e] * A[e][0];
  152.         for (const int i : non_basic) {
  153.             if (i == e) continue;
  154.             A[0][i] -= A[0][e] * A[e][i];
  155.         }
  156.         A[0][l] = -A[0][e] * A[e][l];
  158.         non_basic.erase(e), non_basic.insert(l);
  159.         basic.erase(l), basic.insert(e);
  160.     }
  162.     int Choose(int& e, int& l) {
  163.         e = l = -1;
  164.         for (const int i : non_basic) {
  165.             if (dcmp(A[0][i]) > 0) {
  166.                 e = i;
  167.                 break;
  168.             }
  169.         }
  170.         if (e == -1) return -1;
  172.         for (const int i : basic) {
  173.             if (dcmp(A[i][e]) > 0) {
  174.                 if (l == -1 || dcmp(A[i][0] / A[i][e] - A[l][0] / A[l][e]) < 0) {
  175.                     l = i;
  176.                 }
  177.             }
  178.         }
  180.         if (l == -1) return -2;
  181.         return 0;
  182.     }
  184.     int RunSimplex() {
  185.         int e = -1, l = -1, ret = 0;
  186.         do {
  187.             ret = Choose(e, l);
  188.             // printf("Choose ret %d, e %d, l %d\n", ret, e, l);
  189.             if (ret == -1) {
  190.                 // finish
  191.                 for (const int i : non_basic) x[i] = 0;
  192.                 for (const int i : basic) x[i] = A[i][0];
  193.                 ret = 0;
  194.                 break;
  195.             } else if (ret == -2) {
  196.                 // unlimited answer
  197.                 for (const int i : non_basic) x[i] = 0;
  198.                 for (const int i : basic) x[i] = 0;
  199.                 x[e] = inf;
  200.             } else {
  201.                 // ret == 0
  202.                 Pivot(e, l);
  203.             }
  204.         } while (ret == 0);
  205.         return ret;
  206.     }
  208.     bool Fesible() const {
  209.         for (const int i : basic) {
  210.             if (dcmp(A[i][0]) < 0) return false;
  211.         }
  212.         return true;
  213.     }
  214. };
  216. void solve(const int cas) {
  217.     int n, m;
  218.     scanf("%d%d", &n, &m);
  219.     vector<int> a(n);
  220.     for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  222.     vector<int> idx(1 << n, 0);
  223.     int cnt = 0;
  224.     for (int i = 0; i < (1 << n); i++) {
  225.         int sum = 0;
  226.         for (int j = 0; j < n; j++) {
  227.             sum += ((i >> j) & 1) * a[j];
  228.         }
  229.         if (sum <= m) idx[i] = ++cnt;
  230.     }
  232.     int v = cnt, e = 2 * n;
  233.     Simplex solver(v, e);
  235.     vector<vector<double>> restricts(e, vector<double>(v + 1));
  236.     vector<double> target(v + 1);
  238.     restricts[0][0] = 1.0;
  239.     for (int i = 1; i <= v; i++) restricts[0][i] = 1.0;
  240.     restricts[1][0] = -1.0;
  241.     for (int i = 1; i <= v; i++) restricts[1][i] = -1.0;
  243.     for (int i = 0; i + 1 < n; i++) {
  244.         for (int mask = 0; mask < (1 << n); mask++) {
  245.             if (((mask >> i) & 1) && idx[mask]) {
  246.                 restricts[2*i+2][idx[mask]] += 1.0;
  247.                 restricts[2*i+3][idx[mask]] -= 1.0;
  249.                 if (i == 0) {
  250.                     target[idx[mask]] = 1.0;
  251.                 }
  252.             }
  253.             if (((mask >> (i + 1)) & 1) && idx[mask]) {
  254.                 restricts[2*i+2][idx[mask]] -= 1.0;
  255.                 restricts[2*i+3][idx[mask]] += 1.0;
  256.             }
  257.         }
  258.     }
  259.     for (int mask = 0; mask < (1 << n); mask++) {
  260.         if (((mask >> 0) & 1) && idx[mask]) {
  261.             target[idx[mask]] = 1.0;
  262.         }
  263.     }
  265.     solver.AddRestricts(restricts);
  266.     solver.SetTarget(target);
  268.     solver.Run();
  269.     printf("Case #%d: %.8f\n", cas, max(0.0, solver.GetAns()));
  270. }
  272. int main() {
  273.     int T = 1, t = 0;
  274.     scanf("%d", &T);
  275.     while (T--) solve(++t);
  276.     return 0;
  277. }

Gaussian Elimination

  2. // http://www.51nod.com/Challenge/Problem.html#problemId=1549
  4. #include <bits/stdc++.h>
  6. using namespace std;
  8. const int N = 505;
  9. const double eps = 1e-8;
  11. int Gauss(vector<vector<double>> x, vector<double>& ans) {
  12.     int n = x.size();
  13.     for (int i = 0; i < n; i++) {
  14.         int p = i;
  15.         for (int j = i+1; j < n; j++)
  16.             if (fabs(x[j][i]) > fabs(x[p][i])) p = j;
  17.         if (fabs(x[p][i]) < eps) return -1;
  18.         swap(x[i], x[p]);
  19.         for (int j = 0; j < n; j++) {
  20.             if (i == j) continue;
  21.             double factor = x[j][i] / x[i][i];
  22.             for (int k = i; k <= n; k++) {
  23.                 x[j][k] -= x[i][k] * factor;
  24.             }
  25.         }
  26.     }
  27.     ans.resize(n);
  28.     for (int i = 0; i < n; i++) {
  29.         ans[i] = x[i][n] / x[i][i];
  30.         for (int j = 0; j < n; j++) {
  31.             assert(i == j || fabs(x[i][j]) < eps);
  32.         }
  33.     }
  34.     return 0;
  35. }
  37. void solve() {
  38.     // star <= 10 -> 不掉星
  39.     // 连胜三局 && star <= 70 -> extra star
  41.     int from;
  42.     double p;
  43.     cin >> from >> p;
  45.     int n = 97;
  46.     vector<vector<double>> x(3*n, vector<double>(3*n+1, 0.0));
  48.     auto ID = [](int star, int win) {
  49.         return win * 97 + star;
  50.     };
  52.     int tot = 3*n;
  53.     for (int star = 0; star <= 95; star++) {
  54.         for (int win = 0; win <= 2; win++) {
  55.             int row = ID(star, win);
  56.             x[row][row] = 1.0;
  57.             x[row][tot] = 1.0;
  58.             if (win == 2 && star <= 70) {
  59.                 x[row][ID(star+2, 2)] -= p;
  60.             } else {
  61.                 x[row][ID(star+1, min(2, win+1))] -= p;
  62.             }
  63.             if (star <= 10) {
  64.                 x[row][ID(star, 0)] -= 1.0-p;
  65.             } else {
  66.                 x[row][ID(max(0, star-1), 0)] -= 1.0-p;
  67.             }
  68.         }
  69.     }
  70.     x[ID(96, 0)][ID(96, 0)] = 1.0;
  71.     x[ID(96, 1)][ID(96, 1)] = 1.0;
  72.     x[ID(96, 2)][ID(96, 2)] = 1.0;
  74.     vector<double> ans;
  75.     int ret = Gauss(x, ans);
  76.     assert(ret == 0);
  77.     printf("%.10f\n", ans[ID(96-from, 0)]);
  78. }
  80. int main() {
  81.     solve();
  82.     return 0;
  83. }

Linear Basis

  2. // http://acm.hdu.edu.cn/showproblem.php?pid=3949
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef vector<ll> vii;
  11. const int B = 60;
  13. bool Contain(ll v, int b) { return (v >> b) & 1; }
  15. vii LinearBasis(vii v) {
  16.     vii ans;
  17.     for (int i = B - 1, r = 0; i >= 0 && r < v.size(); i--) {
  18.         int pos = -1;
  19.         for (int j = r; j < v.size(); j++) {
  20.             if (Contain(v[j], i)) { pos = j; break; }
  21.         }
  22.         if (pos == -1) continue;
  23.         swap(v[r], v[pos]);
  24.         for (int j = r + 1; j < v.size(); j++)
  25.             if (Contain(v[j], i)) v[j] ^= v[r];
  26.         for (ll& t : ans)
  27.             if (Contain(t, i)) t ^= v[r];
  28.         ans.push_back(v[r++]);
  29.     }
  30.     return ans;
  31. }
  33. void print(ll v) {
  34.     for (int i = B - 1; i >= 0; i--) {
  35.         printf("%d", Contain(v, i) ? 1 : 0);
  36.     }
  37.     printf("\n");
  38. }
  40. void solve() {
  41.     int n;
  42.     scanf("%d", &n);
  43.     vii v(n);
  44.     for (int i = 0; i < n; i++) scanf("%lld", &v[i]);
  46.     vii v2 = LinearBasis(v);
  47.     bool sub = v2.size() < v.size();
  48.     // for (auto i : v2) print(i);
  50.     int Q;
  51.     scanf("%d", &Q);
  52.     while (Q--) {
  53.         ll k;
  54.         scanf("%lld", &k);
  55.         k -= sub;
  56.         if (k == 0) {
  57.             printf("0\n");
  58.             continue;
  59.         }
  60.         if (k >= (1LL << v2.size())) {
  61.             printf("-1\n");
  62.             continue;
  63.         }
  64.         ll ans = 0;
  65.         for (int i = 0; i < v2.size(); i++) {
  66.             if (Contain(k, i)) ans ^= v2.end()[-i-1];
  67.         }
  68.         printf("%lld\n", ans);
  69.     }
  70. }
  72. int main() {
  73.     int T = 1, t = 0;
  74.     scanf("%d", &T);
  75.     while (T--) {
  76.         printf("Case #%d:\n", ++t);
  77.         solve();
  78.     }
  79.     return 0;
  80. }

Others

Digit DP

  2. // http://www.51nod.com/Challenge/Problem.html#problemId=1232
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int MOD = 2520;
  12. ll dp[20][MOD + 1][50];
  13. int idx[MOD + 1];
  14. int c[MOD + 1][10];
  15. int num[20];
  17. ll DP(int len, int left, int lcm, bool flag) {
  18.     if (len == 0) return lcm && (left % lcm == 0);
  20.     ll& tdp = dp[len][left][idx[lcm]];
  21.     if (flag && tdp >= 0) return tdp;
  23.     ll ans = 0;
  24.     for (int i = flag ? 9 : num[len]; i >= 0; i--) {
  25.         ans += DP(len-1, (left*10+i) % MOD , c[lcm][i], flag || (i < num[len]));
  26.     }
  27.     if (flag) tdp = ans;
  28.     return ans;
  29. }
  31. ll CalcAns(ll n) {
  32.     if (n <= 0) return 0;
  33.     int len = 0;
  34.     while (n) {
  35.         num[++len] = n % 10;
  36.         n /= 10;
  37.     }
  38.     return DP(len, 0, 0, 0);
  39. }
  41. void solve() {
  42.     int cnt = 0;
  43.     idx[0] = cnt++;
  44.     for (int i = 1; i <= MOD; i++)
  45.         if (MOD % i == 0) idx[i] = cnt++;
  46.     // cout << cnt << endl;
  48.     c[0][0] = 0;
  49.     for (int i = 1; i <= 9; i++) c[0][i] = i;
  50.     for (int i = 1; i <= MOD; i++) {
  51.         c[i][0] = i;
  52.         for (int j = 1; j <= 9; j++) {
  53.             c[i][j] = i * j / __gcd(i, j);
  54.         }
  55.     }
  56.     int Q;
  57.     scanf("%d", &Q);
  58.     while (Q--) {
  59.         ll l, r;
  60.         scanf("%lld%lld", &l, &r);
  61.         printf("%lld\n", CalcAns(r) - CalcAns(l - 1));
  62.     }
  63. }
  65. int main() {
  66.     memset(dp, -1, sizeof(dp));
  68.     int T = 1;
  69.     // scanf("%d", &T);
  70.     while (T--) solve();
  71.     return 0;
  72. }

Line And Circle

  2. // https://leetcode.cn/contest/autox2023/problems/TcdlJS/
  4. class Solution {
  5. public:
  6.     typedef long long ll;
  7.     struct Line {
  8.         ll x1, y1, x2, y2;
  9.         Line(ll x1, ll y1, ll x2, ll y2) : x1(x1), y1(y1), x2(x2), y2(y2) {
  10.             // if (x1 > x2) swap(x1, x2), swap(y1, y2);
  11.             // else if (x1 == x2 && y1 > y2) swap(y1, y2);
  12.         }
  14.         array<ll, 3> Get() const {
  15.             // y-y1 = (y2-y1)/(x2-x1)*(x-x1)
  16.             // (y-y1)*(x2-x1)=(y2-y1)*(x-x1)
  17.             ll a = (y2-y1), b = (x1-x2), c = -x1*(y2-y1)+y1*(x2-x1);
  18.             ll g = __gcd(a, __gcd(b, c));
  19.             a /= g, b /= g, c /= g;
  20.             if (a < 0) a = -a, b = -b, c = -c;
  21.             else if (a == 0 && b < 0) b = -b, c = -c;
  22.             return {a, b, c};
  23.         }
  25.         bool Contain(ll x, ll y) const {
  26.             return x >= min(x1, x2) && x <= max(x1, x2) && y >= min(y1, y2) && y <= max(y1, y2);
  27.         }
  29.         bool Inter(const Line& rhs) const {
  30.             auto l = Get(), r = rhs.Get();
  31.             if (l[0]*r[1] == r[0]*l[1]) {
  32.                 if (l[0] == r[0] && l[1] == r[1] && l[2] == r[2]) {
  33.                     return Contain(rhs.x1, rhs.y1) || Contain(rhs.x2, rhs.y2) || rhs.Contain(x1, y1) || rhs.Contain(x2,y2);
  34.                 }
  35.                 return false;
  36.             }
  37.             if (r[0] == 0) swap(l, r);
  38.             assert(r[0]);
  39.             double y = 1.0 * (l[0]*r[2]-r[0]*l[2]) / (r[0]*l[1] - l[0]*r[1]);
  40.             double x = 1.0 * (-r[2]-r[1]*y)/r[0];
  41.             static const double eps = 1e-8;
  42.             if (y > min(y1, y2) - eps && y < max(y1, y2) + eps &&
  43.                 y > min(rhs.y1, rhs.y2) - eps && y < max(rhs.y1, rhs.y2) + eps &&
  44.                 x > min(x1, x2) - eps && x < max(x1, x2) + eps &&
  45.                 x > min(rhs.x1, rhs.x2) - eps && x < max(rhs.x1, rhs.x2) + eps)
  46.                 return true;
  47.             return false;
  48.         }
  49.     };
  51.     struct Circle {
  52.         ll x, y, r;
  53.         Circle(ll x, ll y, ll r) : x(x), y(y), r(r) {}
  55.         bool Contain(const Circle& rhs) const {
  56.             return (x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y) < (r-rhs.r)*(r-rhs.r);
  57.         }
  59.         bool Separated(const Circle& rhs) const {
  60.             return (x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y) > (r+rhs.r)*(r+rhs.r);
  61.         }
  63.         bool Inter(const Circle& rhs) const {
  64.             if (Contain(rhs) || rhs.Contain(*this) || Separated(rhs)) return false;
  65.             return true;
  66.         }
  68.         static int sig(ll x) { return x == 0 ? 0 : (x < 0 ? -1 : 1); }
  70.         bool Inter(const Line& rhs) const {
  71.             ll d1 = (x-rhs.x1)*(x-rhs.x1)+(y-rhs.y1)*(y-rhs.y1) - r*r;
  72.             ll d2 = (x-rhs.x2)*(x-rhs.x2)+(y-rhs.y2)*(y-rhs.y2) - r*r;
  74.             if (sig(d1)*sig(d2) <= 0) return true;
  75.             if (d1 < 0 && d2 < 0) return false;
  77.             ll a1 = rhs.x2-rhs.x1, b1 = rhs.y2-rhs.y1, c1 = x*(rhs.x1-rhs.x2)+y*(rhs.y1-rhs.y2);
  78.             ll a2 = rhs.y2-rhs.y1, b2 = rhs.x1-rhs.x2, c2 = rhs.x1*(rhs.y1-rhs.y2)+rhs.y1*(rhs.x2-rhs.x1);
  79.             if (a2 == 0) swap(a1, a2), swap(b1, b2), swap(c1, c2);
  80.             assert(a2);
  82.             double y0 = 1.0 * (a1*c2-a2*c1) / (a2*b1-a1*b2);
  83.             // printf("y0 %.5f, y1 %lld, y2 %lld\n", y0, rhs.y1, rhs.y2);
  84.             static const double eps = 1e-8;
  85.             if (y0 > min(rhs.y1, rhs.y2) - eps && y0 < max(rhs.y1, rhs.y2) + eps) {
  86.                 double x0 = 1.0*(-c2-b2*y0)/a2;
  87.                 // printf("%.10f %.10f\n", x0, y0);
  88.                 if ((x-x0)*(x-x0)+(y-y0)*(y-y0) < r*r+eps) return true;
  89.             }
  90.             return false;
  91.         }
  93.     };
  95.     void dfs(int u, const vector<vector<int>>& vis, vector<int>& id, int tmp) {
  96.         id[u] = tmp;
  97.         for (int i = 0; i < vis.size(); i++) {
  98.             if (vis[u][i] && id[i] < 0) {
  99.                 dfs(i, vis, id, tmp);
  100.             }
  101.         }
  102.     }
  104.     vector<bool> antPass(vector<vector<int>>& g, vector<vector<int>>& path) {
  105.         int n = g.size();
  106.         vector<pair<Line, int>> lines;
  107.         vector<pair<Circle, int>> cirs;
  108.         for (int i = 0; i < n; i++) {
  109.             const auto& v = g[i];
  110.             if (v.size() == 4) {
  111.                 Line line(v[0], v[1], v[2], v[3]);
  112.                 lines.emplace_back(line, i);
  113.             } else if (v.size() == 3) {
  114.                 Circle cir(v[0], v[1], v[2]);
  115.                 cirs.emplace_back(cir, i);
  116.             } else {
  117.                 assert(false);
  118.             }
  119.         }
  121.         vector<vector<int>> vis(n, vector<int>(n, 0));
  122.         for (const auto& [l1, i] : lines) {
  123.             for (const auto& [l2, j] : lines) {
  124.                 vis[i][j] = l1.Inter(l2);
  125.             }
  126.         }
  127.         for (const auto& [c1, i] : cirs) {
  128.             for (const auto& [c2, j] : cirs) {
  129.                 vis[i][j] = c1.Inter(c2);
  130.             }
  131.         }
  132.         for (const auto& [l, i] : lines) {
  133.             for (const auto& [c, j] : cirs) {
  134.                 vis[i][j] = vis[j][i] = c.Inter(l);
  135.             }
  136.         }
  137.         for (int i = 0; i < n; i++) {
  138.             for (int j = 0; j < n; j++) {
  139.                 assert(vis[i][j] == vis[j][i]);
  140.                 // printf("%d %d %d\n", i, j, vis[i][j]);
  141.             }
  142.         }
  144.         vector<int> id(n, -1);
  145.         int tmp = 0;
  146.         for (int i = 0; i < n; i++) {
  147.             if (id[i] < 0) {
  148.                 dfs(i, vis, id, tmp++);
  149.             }
  150.         }
  152.         vector<bool> ans;
  153.         for (auto& q : path) {
  154.             if (id[q[0]] == id[q[1]]) ans.push_back(true);
  155.             else ans.push_back(false);
  156.         }
  157.         return ans;
  158.     }
  159. };

整体二分

  2. // https://acm.hdu.edu.cn/showproblem.php?pid=5412
  4. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  10. const int N = 3e5+10;
  12. struct Bits {
  13.     int bits[N], n;
  15.     void Reset(int n) {
  16.         std::fill(bits, bits + n + 1, 0);
  17.         this->n = n;
  18.     }
  20.     void Add(int i, int d) {
  21.         while (i <= n) {
  22.             bits[i] += d;
  23.             i += i & -i;
  24.         }
  25.     }
  27.     int Sum(int i) {
  28.         int ans = 0;
  29.         while (i) {
  30.             ans += bits[i];
  31.             i -= i & -i;
  32.         }
  33.         return ans;
  34.     }
  35. } bt;
  37. struct Query {
  38.     int op;
  39.     int l, r, k, id;
  40.     int flag;
  41.     void scan(int id) {
  42.         scanf("%d", &op);
  43.         if (op == 1) scanf("%d%d", &l, &k);
  44.         else scanf("%d%d%d", &l, &r, &k);
  45.         this->id = id;
  46.         flag = 1;
  47.     }
  49. } Q[N], Q1[N], Q2[N];
  50. int ans[N], tmp[N];
  52. void solve(int l, int r, int a, int b) {
  53.     if (a > b) return ;
  54.     if (l == r) {
  55.         for (int i = a; i <= b; i++) {
  56.             if (Q[i].op == 2)
  57.                 ans[Q[i].id] = l;
  58.         }
  59.         return ;
  60.     }
  62.     int m = (l + r) >> 1;
  63.     for (int i = a; i <= b; i++) {
  64.         if (Q[i].op == 1 && Q[i].k <= m) {
  65.             bt.Add(Q[i].l, Q[i].flag);
  66.         } else if (Q[i].op == 2) {
  67.             tmp[i] = bt.Sum(Q[i].r) - bt.Sum(Q[i].l-1);
  68.         }
  69.     }
  71.     for (int i = a; i <= b; i++) {
  72.         if (Q[i].op == 1 && Q[i].k <= m) {
  73.             bt.Add(Q[i].l, -Q[i].flag);
  74.         }
  75.     }
  77.     int t1 = 0, t2 = 0;
  78.     for (int i = a; i <= b; i++) {
  79.         if (Q[i].op == 1) {
  80.             if (Q[i].k <= m) Q1[t1++] = Q[i];
  81.             else Q2[t2++] = Q[i];
  82.         } else {
  83.             if (tmp[i] >= Q[i].k) Q1[t1++] = Q[i];
  84.             else {
  85.                 Q2[t2++] = Q[i];
  86.                 Q2[t2-1].k -= tmp[i];
  87.             }
  88.         }
  89.     }
  90.     assert(a + t1 + t2 - 1 == b);
  92.     for (int i = a; i < a + t1; i++) Q[i] = Q1[i-a];
  93.     for (int i = a + t1; i < a + t1 + t2; i++) Q[i] = Q2[i-a-t1];
  95.     solve(l, m, a, a + t1 - 1);
  96.     solve(m+1, r, a + t1, a + t1 + t2 - 1);
  97. }
  99. int b[N], m;
  100. int pre[N], n;
  102. int GetRank(int x) {
  103.     return lower_bound(b+1, b+m+1, x) - b;
  104. }
  106. bool solve() {
  107.     if (scanf("%d", &n) != 1) return false;
  109.     m = 0;
  110.     int tn = 0;
  111.     for (int i = 1; i <= n; i++) {
  112.         int x;
  113.         scanf("%d", &x);
  114.         auto& query = Q[++tn];
  115.         query.op = 1, query.l = i, query.k = x, query.flag = 1;
  116.         b[++m] = x;
  117.         pre[query.l] = x;
  118.     }
  119.     int q;
  120.     scanf("%d", &q);
  121.     for (int i = 1; i <= q; i++) {
  122.         auto& query = Q[++tn];
  123.         query.scan(i);
  124.         if (query.op == 1) {
  125.             b[++m] = query.k;
  127.             auto& query2 = Q[++tn];
  128.             query2 = query;
  129.             query2.k = pre[query.l];
  130.             query2.flag = -1;
  132.             pre[query.l] = query.k;
  133.             swap(query, query2);
  134.         }
  135.     }
  137.     sort(b+1, b+m+1);
  138.     // m = unique(b+1, b+m+1)-b-1;
  140.     for (int i = 1; i <= tn; i++)
  141.         if (Q[i].op == 1)
  142.             Q[i].k = GetRank(Q[i].k);
  144.     bt.Reset(n);
  145.     std::fill(ans+1, ans+q+1, -1);
  146.     solve(1, m, 1, tn);
  148.     for (int i = 1; i <= q; i++) {
  149.         if (ans[i] > 0) printf("%d\n", b[ans[i]]);
  150.     }
  152.     return true;
  153. }
  155. int main() {
  156.     while (solve());
  157.     return 0;
  158. }

Fast IO

  2. #include <bits/stdc++.h>
  4. using namespace std;
  5. typedef long long ll;
  6. typedef pair<int, int> pii;
  8. struct FastIO {
  9.     static const int BUFFER_SIZE = (1 << 24);
  10.     char buffer[BUFFER_SIZE];
  11.     char *head = nullptr, *tail = nullptr;
  13.     void ReadBuffer() {
  14.         int len = fread(buffer, 1, BUFFER_SIZE, stdin);
  15.         head = buffer, tail = buffer + len;
  16.     }
  18.     char getch() {
  19.         if (head == tail) ReadBuffer();
  20.         if (head == tail) return 0;
  21.         return *head++;
  22.     }
  24.     template<class T>
  25.     void Read(T& n) {
  26.         n = 0;
  27.         bool flag = false;
  28.         char ch = getch();
  29.         while (!isdigit(ch) && ch != '-') ch = getch();
  30.         if (ch == '-') flag = true, ch = getch();
  31.         do {
  32.             n = 10 * n + ch - '0';
  33.             ch = getch();
  34.         } while (isdigit(ch));
  35.         if (flag) n = -n;
  36.     }
  38.     template<class T>
  39.     void Print(const T n) const {
  40.         if (n < 0) {
  41.             putchar('-');
  42.             Print(-n);
  43.             return ;
  44.         }
  45.         if (n > 9) Print(n / 10);
  46.         putchar(n % 10 + '0');
  47.     }
  49. } io;
  51. void solve() {
  52.     int n;
  53.     io.Read(n);
  54.     io.Print(n);
  55.     printf("\n");
  56.     while (n--) {
  57.         ll x;
  58.         io.Read(x);
  59.         io.Print(x);
  60.         printf("\n");
  61.     }
  62. }
  64. void solve2() {
  65.     int n;
  66.     scanf("%d", &n);
  67.     printf("%d\n", n);
  68.     while (n--) {
  69.         ll x;
  70.         scanf("%lld", &x);
  71.         printf("%lld\n", x);
  72.     }
  73. }
  75. int main(int argc, char** argv) {
  76.     int t = atoi(argv[1]);
  77.     if (t == 1) solve();
  78.     else solve2();
  79.     return 0;
  80. }

vimrc

  1. set nu
  2. syntax on
  3. set autoindent
  4. set cindent
  5. set cursorline
  6. set mouse=a
  7. set ts=4
  8. set expandtab
  9. set shiftwidth=4
  10. set hlsearch
  11. set ignorecase
  13. if has("autocmd")
  14. au BufReadPost * if line("'\"") > 1 && line("'\"") <= line("$") | exe "normal! g'\"" | endif
  15. endif
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注