[关闭]
@ljt12138 2017-06-19T21:33:30.000000Z 字数 9549 阅读 757

湖师大集训记录

lyoi303:「2017 山东一轮集训 Day1」Sum

吕老板讲的方法只有50....

TLE

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int p, n, m;
  5. const int mod = 998244353, g = 3;
  7. int power(int a, int n)
  8. {
  9.     int ans = 1, b = a;
  10.     for (register int i = 0; i <= 30; i++) {
  11.         if ((n>>i)&1) ans = (long long)ans*b%mod;
  12.         b = (long long)b*b%mod;
  13.     }
  14.     return ans;
  15. }
  17. inline int inv(int a)
  18. { return power(a, mod-2); }
  20. const int MAXN = 2049;
  21. int rev[MAXN];
  22. void NTT(int a[], int n, int flag)
  23. {
  24.     int m = 1, lgn = 0;
  25.     while (m < n) lgn++, m <<= 1;
  26.     rev[0] = 0;
  27.     for (register int i = 1; i < n; i++) rev[i] = (rev[i>>1]>>1)|((i&1)<<(lgn-1));
  28.     for (register int i = 0; i < n; i++)
  29.         if (rev[i] < i) swap(a[i], a[rev[i]]);
  30.     for (register int k = 1; k <= n; k <<= 1) {
  31.         int dw = power(g, (mod-1)/k);
  32.         if (flag == -1) dw = inv(dw);
  33.         for (register int i = 0; i < n; i += k) {
  34.             int w = 1;
  35.             for (register int j = 0; j < k>>1; j++) {
  36.                 int u = a[i+j], t = (long long)w*a[i+j+(k>>1)]%mod;
  37.                 a[i+j] = (u+t)%mod, a[i+j+(k>>1)] = ((u-t)%mod+mod)%mod;
  38.                 w = (long long)w*dw%mod;
  39.             }
  40.             }
  41.         }
  42.     if (flag == -1) {
  43.         int Inv = inv(n);
  44.         for (register int i = 0; i < n; i++)
  45.             a[i] = (long long)Inv*a[i]%mod;
  46.     }
  47. }
  49. int B[2049], C[2049];
  50. void mul(int a[2049], int M, int b[2049], int c[2049]) // $a = b\oplus c$
  51. {
  52.     memcpy(B, b, sizeof B), memcpy(C, c, sizeof C);
  53.     memset(a, 0, sizeof B);
  54.     int n = 1;
  55.     while (n < M) n <<= 1;
  56.     n <<= 1; // todo here
  57.     NTT(B, n, 1), NTT(C, n, 1);
  58.     for (register int i = 0; i < n; i++)
  59.         a[i] = (long long)B[i]*C[i]%mod;
  60.     NTT(a, n, -1);
  61.     for (register int i = M; i < 2048; i++)
  62.         a[i] = 0;
  63. }
  65. struct node {
  66.     int N, Pow;  // 10^N = Pow;
  67.     int A[55][2049];
  68.     void print()
  69.     {
  70.         puts("Matrix : ");
  71.         for (int i = 0; i < p; i++) {
  72.             for (int j = 0; j <= m; j++)
  73.                 cerr << A[i][j] << " ";
  74.             cerr << endl;
  75.         }
  76.         puts("End Matrix.");
  77.     }
  78.     node() {
  79.         memset(A, 0, sizeof A);
  80.     }
  81.     friend node operator * (node &a, node &b)
  82.     {
  83.         node ret;
  84.         static int A[MAXN];
  85.         memset(A, 0, sizeof A);
  86.         ret.N = a.N+b.N, ret.Pow = (long long)a.Pow*b.Pow%p;
  87.         for (register int i = 0; i < p; i++) {
  88.             for (register int j = 0; j < p; j++) {
  89.                 int M = ((long long)i*b.Pow%p+j)%p;
  90.                 mul(A, m+1, a.A[i], b.A[j]);
  91.                 for (register int k = 0; k <= m; k++) (ret.A[M][k] += A[k]) %= mod;
  92.             }
  93.         }
  94.         return ret;
  95.     }
  96. };
  98. node power(node a, int n)
  99. {
  100.     node ans;
  101.     int flag = -1;
  102.     for (int i = 0; i <= 30; i++) {
  103.         if ((n>>i) == 0) break;
  104.         if ((n>>i)&1) {
  105.             if (flag == -1) ans = a, flag = 1;
  106.             else ans = ans*a;
  107.         }
  108.         a = a*a;
  109.     }
  110.     return ans;
  111. }
  113. node A;
  115. int a[MAXN], b[MAXN], c[MAXN];
  116. int main()
  117. {
  118.     scanf("%d%d%d", &n, &p, &m);
  119.     A.N = 1, A.Pow = 10;
  120.     for (int j = 0; j <= min(m, 9); j++)
  121.     A.A[j%p][j]++;
  122.     A = power(A, n);
  123.     int ans = 0;
  124.     for (int i = 0; i <= m; i++) {
  125.         ans = (ans+A.A[0][i])%mod;
  126.         printf("%d ", ans);
  127.     }
  128.     puts("");
  129.     return 0;
  130. }

upd: 原来是我走神了QwQ。
做循环卷积的时候要先全部DFT，卷完了全部IDFT，复杂度少一个...
AC...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int p, n, m;
  5. const int mod = 998244353, g = 3;
  7. int power(int a, int n)
  8. {
  9.     int ans = 1, b = a;
  10.     for (register int i = 0; i <= 30; i++) {
  11.         if ((n>>i)&1) ans = (long long)ans*b%mod;
  12.         b = (long long)b*b%mod;
  13.     }
  14.     return ans;
  15. }
  17. inline int inv(int a)
  18. { return power(a, mod-2); }
  20. const int MAXN = 2049;
  21. int rev[MAXN];
  22. void NTT(int a[], int n, int flag)
  23. {
  24.     int m = 1, lgn = 0;
  25.     while (m < n) lgn++, m <<= 1;
  26.     rev[0] = 0;
  27.     for (register int i = 1; i < n; i++) rev[i] = (rev[i>>1]>>1)|((i&1)<<(lgn-1));
  28.     for (register int i = 0; i < n; i++)
  29.         if (rev[i] < i) swap(a[i], a[rev[i]]);
  30.     for (register int k = 1; k <= n; k <<= 1) {
  31.         int dw = power(g, (mod-1)/k);
  32.         if (flag == -1) dw = inv(dw);
  33.         for (register int i = 0; i < n; i += k) {
  34.             int w = 1;
  35.             for (register int j = 0; j < k>>1; j++) {
  36.                 int u = a[i+j], t = (long long)w*a[i+j+(k>>1)]%mod;
  37.                 a[i+j] = (u+t)%mod, a[i+j+(k>>1)] = ((u-t)%mod+mod)%mod;
  38.                 w = (long long)w*dw%mod;
  39.             }
  40.             }
  41.         }
  42.     if (flag == -1) {
  43.         int Inv = inv(n);
  44.         for (register int i = 0; i < n; i++)
  45.             a[i] = (long long)Inv*a[i]%mod;
  46.     }
  47. }
  49. int B[2049], C[2049];
  50. void mul(int a[2049], int M, int b[2049], int c[2049]) // $a = b\oplus c$
  51. {
  52.     memcpy(B, b, sizeof B), memcpy(C, c, sizeof C);
  53.     memset(a, 0, sizeof B);
  54.     int n = 1;
  55.     while (n < M) n <<= 1;
  56.     n <<= 1; // todo here
  57.     cerr << n << endl;
  58.     NTT(B, n, 1), NTT(C, n, 1);
  59.     for (register int i = 0; i < n; i++)
  60.         a[i] = (long long)B[i]*C[i]%mod;
  61.     NTT(a, n, -1);
  62.     for (register int i = M; i < 2048; i++)
  63.         a[i] = 0;
  64. }
  66. struct node {
  67.     int N, Pow;  // 10^N = Pow;
  68.     int A[55][2049];
  69.     void display()
  70.     {
  71.         puts("Matrix : ");
  72.         for (int i = 0; i < p; i++) {
  73.             for (int j = 0; j <= m; j++)
  74.                 cerr << A[i][j] << " ";
  75.             cerr << endl;
  76.         }
  77.         puts("End Matrix.");
  78.     }
  79.     node() {
  80.         memset(A, 0, sizeof A);
  81.     }
  82.     friend node operator * (node a, node b)
  83.     {
  84.         node ret;
  85.         static int C[55][MAXN], d[MAXN];
  86.         memset(C, 0, sizeof C);
  87.         ret.N = a.N+b.N, ret.Pow = (long long)a.Pow*b.Pow%p;
  88.         int np = 1;
  89.         while (np < m+1) np <<= 1;
  90.         np <<= 1; // todo here
  91.             for (int i = 0; i < p; i++) NTT(a.A[i], np, 1), NTT(b.A[i], np, 1);
  92.         for (int i = 0; i < p; i++) {
  93.             for (int j = 0; j < p; j++) {
  94.                 int M = ((long long)i*b.Pow%p+j)%p;
  95.                 for (int k = 0; k < np; k++)
  96.                         C[M][k] = (C[M][k]+(long long)a.A[i][k]*b.A[j][k]%mod)%mod;
  97.             }
  98.         }
  99.         for (int i = 0; i < p; i++) {
  100.             NTT(a.A[i], np, -1), NTT(b.A[i], np, -1),
  101.             NTT(C[i], np, -1);
  102.             for (int k = 0; k <= m; k++) ret.A[i][k] = (ret.A[i][k]+C[i][k])%mod;
  103.         }
  104.         return ret;
  105.     }
  106. };
  108. node power(node a, int n)
  109. {
  110.     node ans;
  111.     int flag = -1;
  112.     for (int i = 0; i <= 30; i++) {
  113.         if ((n>>i) == 0) break;
  114.         if ((n>>i)&1) {
  115.             if (flag == -1) ans = a, flag = 1;
  116.             else ans = ans*a;
  117.         }
  118.         a = a*a;
  119.     }
  120.     return ans;
  121. }
  123. node A;
  125. int a[MAXN], b[MAXN], c[MAXN];
  126. int main()
  127. {
  128.         scanf("%d%d%d", &n, &p, &m);
  129.     A.N = 1, A.Pow = 10;
  130.         for (int j = 0; j <= min(m, 9); j++)
  131.         A.A[j%p][j]++;
  132.     A = power(A, n);
  133.     int ans = 0;
  134.     for (int i = 0; i <= m; i++) {
  135.         ans = (ans+A.A[0][i])%mod;
  136.         printf("%d ", ans);
  137.     }
  138.     puts("");
  139.     return 0;
  140. }

lyoi306「2017 山东一轮集训 Day2」Pair

考虑匹配条件，令也就是。显然，一个序列匹配当且仅当排序后匹配。考虑排序后个和个的情况，容易发现，匹配当且仅当(排序后)对于任何一个前缀，的数量不少于。如果把看成左括号，看成右括号，就是经典的括号序列匹配问题了。用线段树维护前缀和的区间最小值即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 150005;
  5. int gt[MAXN];
  6. int n, m, h;
  8. struct p {
  9.     int dt, pos;
  10.     friend bool operator < (const p &a, const p &b)
  11.     {
  12.         if (a.dt == b.dt) return a.pos < b.pos;
  13.         return a.dt < b.dt;
  14.     }
  15. }a[MAXN], b[MAXN], dx[MAXN+MAXN];
  17. int A[MAXN], B[MAXN], dx_top = 0;
  19. void dx_init()
  20. {
  21.     for (int i = 1; i <= m; i++) dx[++dx_top] = b[i];
  22.     for (int i = 1; i <= n; i++) dx[++dx_top] = a[i];
  23.     sort(dx+1, dx+dx_top+1);
  24. }
  26. inline int dx_num(const p &a)
  27. { return lower_bound(dx+1, dx+dx_top+1, a)-dx; }
  29. struct tree {
  30.     int dat[MAXN*4], l[MAXN*4], r[MAXN*4], lc[MAXN*4], rc[MAXN*4], tag[MAXN*4], top, root;
  31.     inline void clear()
  32.     { top = root = 0; }
  33.     tree()
  34.     { clear(); }
  35.     void build(int &nd, int opl, int opr)
  36.     {
  37.         nd = ++top, dat[nd] = tag[nd] = 0, l[nd] = opl, r[nd] = opr;
  38.         if (opl < opr)
  39.             build(lc[nd], opl, (opl+opr)/2), build(rc[nd], (opl+opr)/2+1, opr);
  40.     }
  41.     void pdw(int nd)
  42.     {
  43.         if (!nd) return;
  44.         if (lc[nd]) tag[lc[nd]] += tag[nd], tag[rc[nd]] += tag[nd];
  45.         dat[nd] += tag[nd], tag[nd] = 0;
  46.     }
  47.     inline void update(int nd)
  48.     { if (lc[nd]) dat[nd] = min(dat[lc[nd]], dat[rc[nd]]); }
  49.     void modify(int nd, int opl, int opr, int dt)
  50.     {
  51.         pdw(nd);
  52.         if (l[nd] == opl && r[nd] == opr) tag[nd] += dt;
  53.         else {
  54.             int mid = (l[nd]+r[nd])/2;
  55.             if (opr <= mid) modify(lc[nd], opl, opr, dt);
  56.             else if (opl > mid) modify(rc[nd], opl, opr, dt);
  57.             else modify(lc[nd], opl, mid, dt), modify(rc[nd], mid+1, opr, dt);
  58.             pdw(lc[nd]), pdw(rc[nd]), update(nd);
  59.         }
  60.     }
  61.     int query(int nd, int opl, int opr)
  62.     {
  63.         pdw(nd);
  64.         if (l[nd] == opl && r[nd] == opr) return dat[nd];
  65.         int mid = (l[nd]+r[nd])/2;
  66.         if (opr <= mid) return query(lc[nd], opl, opr);
  67.         else if (opl > mid) return query(rc[nd], opl, opr);
  68.         else return min(query(lc[nd], opl, mid), query(rc[nd], mid+1, opr));
  69.     }
  70.     void display()
  71.     {
  72.         for (int i = 1; i <= dx_top; i++) printf("%d ", query(root, i, i));
  73.         puts("");
  74.     }
  75. } seg;
  77. int main()
  78. {
  79.     scanf("%d%d%d", &n, &m, &h);
  80.         for (int i = 1; i <= m; i++)
  81.         scanf("%d", &b[i].dt), b[i].dt = h-b[i].dt, b[i].pos = -i;
  82.     for (int i = 1; i <= n; i++)
  83.         scanf("%d", &a[i].dt), a[i].pos = i;
  84.     dx_init();
  85.     for (int i = 1; i <= m; i++) B[i] = dx_num(b[i]);//, printf("%d ", B[i]);
  86.     for (int i = 1; i <= n; i++) A[i] = dx_num(a[i]);//, printf("%d ", A[i]);
  87.     seg.build(seg.root, 1, dx_top);
  88.     for (int i = 1; i <= m; i++) seg.modify(seg.root, B[i], dx_top, 1);
  89.     int cnt = 0;
  90.     for (int i = 1; i <= m; i++) seg.modify(seg.root, A[i], dx_top, -1);
  91.     for (int i = 1; i <= n; i++) {
  92.         if (seg.query(seg.root, 1, dx_top) >= 0) cnt++;
  93.         seg.modify(seg.root, A[i], dx_top, 1);
  94.         if (i+m > n) break;
  95.         seg.modify(seg.root, A[i+m], dx_top, -1);
  96.     }
  97.     printf("%d\n", cnt);
  98.     return 0;
  99. }

lyoi323. 「2017 山东一轮集训 Day7」养猫

神奇的费用流...最大流限制/费用计算的好模型。

from visit_world
把 1 到 n 串成一条链
考虑上限：
想象你带了 mx 个小弟在链上走，到一个位置 p，你可以派出一个小弟去获得对应收益，但是他在 p + k 的时候才能归队
考虑下限：
在 p 这里派出一个小弟，会使得 [p, p+k) 上走“主干道”的小弟减少一名。
因此，我们限制“主干道”的流量为 mx - mi 即可满足下限

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1005;
  5. int n, k, ms, me;
  6. int mx, mn;
  8. int s[MAXN], e[MAXN];
  10. struct node {
  11.     int to, next, flow;
  12.     long long cost;
  13.     int neg;
  14. } edge[MAXN*200];
  15. int head[MAXN], top = 0;
  16. inline int push(int i, int j, int f, long long c)
  17. {
  18.     ++top, edge[top] = (node) {j, head[i], f, c, top+1}, head[i] = top;
  19.     ++top, edge[top] = (node) {i, head[j], 0, -c, top-1}, head[j] = top;
  20.     return top-1;
  21. }
  23. long long dis[MAXN];
  24. int vis[MAXN];
  25. queue<int> que;
  26. int pre[MAXN], pre_edge[MAXN];
  27. int S = MAXN-1, T = MAXN-2;
  28. const long long inf = 1e14;
  29. bool spfa(int &flow, long long &cost)
  30. {
  31.     memset(vis, 0, sizeof vis), memset(dis, 127/3, sizeof dis);
  32.     vis[S] = 1, dis[S] = 0, que.push(S);
  33.     while (!que.empty()) {
  34.         int nd = que.front(); que.pop(), vis[nd] = 0;
  35.         for (int i = head[nd]; i; i = edge[i].next) {
  36.             int to = edge[i].to;
  37.             if (!edge[i].flow || dis[to] <= dis[nd]+edge[i].cost) continue;
  38.             dis[to] = dis[nd]+edge[i].cost, pre[to] = nd, pre_edge[to] = i;
  39.             if (!vis[to])
  40.                 vis[to] = 1, que.push(to);
  41.         }
  42.     }
  43.     if (dis[T] > inf) return 0;;
  44.     int mf = INT_MAX;
  45.     for (int i = T; i != S; i = pre[i]) mf = min(mf, edge[pre_edge[i]].flow);
  46.     for (int i = T; i != S; i = pre[i]) 
  47.         edge[pre_edge[i]].flow -= mf, edge[edge[pre_edge[i]].neg].flow += mf;
  48.     cost += dis[T]*mf;
  49.     flow += mf;
  50.     return 1;
  51. }
  53. void mcf(int &flow, long long &cost)
  54. {
  55.     cost = flow = 0;
  56.     while (spfa(flow, cost));
  57. }
  59. int eg[MAXN];
  61. int main()
  62. {
  63.     scanf("%d%d%d%d", &n, &k, &ms, &me); // change t, t \le me, k-t \le ms \rightarrow t \ge k-ms
  64.     mx = k-ms, mn = me; // [mn, mx]
  65.     long long cnt = 0;
  66.     for (int i = 1; i <= n; i++) scanf("%d", &s[i]), cnt += s[i]; // sleep
  67.     for (int i = 1; i <= n; i++) scanf("%d", &e[i]);
  68.     push(S, 1, mx, 0), push(n, T, mx, 0);
  69.     for (int i = 1; i < n; i++) {
  70.         if (i >= k) push(i, i+1, mx-mn, 0);
  71.         else push(i, i+1, mx, 0);
  72.     }
  73.     for (int i = 1; i <= n; i++) {
  74.         int t = i+k <= n?i+k:T;
  75.         eg[i] = push(i, t, 1, -e[i]+s[i]);
  76.     }
  77.     int flow;
  78.     long long cost;
  79.     mcf(flow, cost);
  80.     printf("%lld\n", cnt-cost);
  81.     for (int i = 1; i <= n; i++) {
  82.         if (edge[eg[i]].flow)
  83.             putchar('S');
  84.         else putchar('E');
  85.     }
  86.     puts("");
  87.     return 0;
  88. }

loj#6060. 「2017 山东一轮集训 Day1」Set

首先有为定值，设为。考虑的每一位，如果为1，由于必然一边为1一边为0，对和的贡献不变；如果为0，则应该尽可能让更高位两边全为1。

做法1：首先取出为0的位做一遍最大异或找到中必须为1的位置，然后作出线性基。贪心的从高到低放置每一位，用异或方程组判断下面是否有解「太麻烦了根本写不出来...」
// 但这个思路扩展性更好，可以出道题233

做法2：考虑统一处理，在贪心求最大异或的时候改变贪心顺序，首先是为0的位，然后是为1的。直接做就好了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. struct linear_base {
  5.     long long A[70];
  6.     void push(long long x, long long lim)
  7.     {
  8.         for (int i = 60; i >= 0; i--) {
  9.             if (lim&(1ll<<i)) continue;
  10.             if (!(x&(1ll<<i))) continue;
  11.             if (!A[i]) { A[i] = x; return;}
  12.             else x ^= A[i];
  13.         }
  14.             for (int i = 60; i >= 0; i--) {
  15.             if (!(lim&(1ll<<i))) continue;
  16.             if (!(x&(1ll<<i))) continue;
  17.             if (!A[i]) { A[i] = x; return; }
  18.             else x ^= A[i];
  19.         }
  20.     }
  21.     long long max_xor(long long lim)
  22.     {
  23.         long long val = 0;
  24.         for (int i = 60; i >= 0; i--)
  25.             if (!(lim&(1ll<<i)) && !(val&(1ll<<i)))
  26.                 val ^= A[i];
  27.         for (int i = 60; i >= 0; i--)
  28.             if ((lim&(1ll<<i)) && !(val&(1ll<<i)))
  29.                 val ^= A[i];
  30.             return val;
  31.     }
  32. } lb;
  33. int n;
  34. long long val[100005], xr = 0;
  36. int main()
  37. {
  38.     scanf("%d", &n);
  39.     for (int i = 1; i <= n; i++) scanf("%lld", &val[i]),  xr ^= val[i];
  40.     for (int i = 1; i <= n; i++)
  41.         lb.push(val[i], xr);
  42.     printf("%lld\n", xr^lb.max_xor(xr));
  43.     return 0;
  44. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注