[关闭]
@Plutorabbit 2017-02-19T03:24:53.000000Z 字数 8096 阅读 1467

TJOI2016 & HEOI2016

未分类

[Tjoi2016&Heoi2016]树

并查集会是一种很好的思路
离线
用表示每个点被标记的次数。
倒过来做,对于 的点，它的father指向它的父亲，否则指向自己。
如果是标记操作，就给减1 

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NN = 100005;
  4. int tot,head[NN],fa[NN],father[NN],n,m,c[NN],ans[NN];
  5. struct Q
  6. {
  7.     int x,op;
  8. }q[NN];
  9. struct E
  10. {
  11.     int ne,v;
  12. }e[NN<<1];
  13. char ch[11];
  14. void Build(int xx,int yy)
  15. {
  16.     e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
  17.     e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
  18. }
  19. int Find(int xx) { return (father[xx] == xx) ? xx : (father[xx] = Find(father[xx])); }
  20. void DFS(int xx)
  21. {
  22.     if (c[xx]) father[xx] = xx; else father[xx] = fa[xx];
  23.     for (int i=head[xx];i;i=e[i].ne)
  24.         if (e[i].v != fa[xx]) fa[e[i].v] = xx, DFS(e[i].v);
  25. }
  26. int main()
  27. {
  28.     scanf("%d%d",&n,&m);
  29.     int x,y;
  30.     for (int i=1;i<n;++i) scanf("%d%d",&x,&y), Build(x,y);
  31.     c[1] = 1;
  32.     for (int i=1;i<=m;++i)
  33.     {
  34.         scanf("%s%d",ch,&q[i].x);
  35.         if (ch[0] == 'C') ++ c[q[i].x], q[i].op = 1;
  36.     }
  37.     DFS(1);
  38.     for (int i=m;i;--i)
  39.     {
  40.         x = q[i].x;
  41.         if (q[i].op)
  42.         {
  43.             -- c[x];
  44.             if (c[x] == 0) father[x] = fa[x];
  45.         }
  46.         else ans[i] = Find(x);
  47.     }
  48.     for (int i=1;i<=m;++i) if (!q[i].op) printf("%d\n",ans[i]);
  49.     return 0;
  50. }

[Tjoi2016&Heoi2016]排序

二分＋线段树
二分答案，需要知道进行m次排序后p位置上的数字是否大于mid。
对于一个mid，我们可以把序列里的数字分为两类，即大于mid的数和小于等于mid的数，分别用1和0表示。
对这些0和1进行排序时，对于一个区间[l,r]进行升序排序，等价于把所有的0放在前面，所有的1放在后面；降序排序反之。
线段树解决
调试成傻B

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NN = 100005;
  4. int n,m,now,a[NN],b[NN],tr[NN<<2],tag[NN<<2],ans;
  5. struct Q
  6. {
  7.     int op,l,r;
  8. }q[NN];
  9. void Build(int k,int l,int r)
  10. {
  11.     tag[k] = -1;
  12.     if (l == r) { tr[k] = b[l]; return; }
  13.     int mid = (l+r) >> 1;
  14.     Build(k<<1,l,mid), Build(k<<1|1,mid+1,r);
  15.     tr[k] = tr[k<<1] + tr[k<<1|1];
  16. }
  18. inline void down(int k,int l,int r,int v) { tr[k] = (r-l+1) * v, tag[k] = v; }
  19. inline void push_down(int k,int l,int r)
  20. {
  21.     int mid = (l+r) >> 1;
  22.     down(k<<1,l,mid,tag[k]);
  23.     down(k<<1|1,mid+1,r,tag[k]);
  24.     tag[k] = -1;
  25. }
  26. void Change(int k,int l,int r,int L,int R,int v)
  27. {
  28.     if (L > R) return;
  29.     if (L <= l && R >= r) { down(k,l,r,v); return; }
  30.     if (tag[k] != -1) push_down(k,l,r);
  31.     int mid = (l+r) >> 1;
  32.     if (L <= mid) Change(k<<1,l,mid,L,R,v);
  33.     if (R > mid) Change(k<<1|1,mid+1,r,L,R,v);
  34.     tr[k] = tr[k<<1] + tr[k<<1|1];
  35. }
  36. int Query(int k,int l,int r,int L,int R)
  37. {
  38.     if (L <= l && R >= r) return tr[k];
  39.     if (tag[k] != -1) push_down(k,l,r);
  40.     int sum = 0, mid = (l+r) >> 1;
  41.     if (L <= mid) sum += Query(k<<1,l,mid,L,R);
  42.     if (R > mid) sum += Query(k<<1|1,mid+1,r,L,R);
  43.     return sum;
  44. }
  45. bool Check(int xx)
  46. {
  47.     for (int i=1;i<=n;++i) b[i] = (a[i] < xx);
  48.     Build(1,1,n);
  49.     for (int i=1;i<=m;++i)
  50.     {
  51.         int sum = Query(1,1,n,q[i].l,q[i].r);
  52.         if (q[i].op)
  53.         {
  54.             Change(1,1,n,q[i].l,q[i].r-sum,0);
  55.             Change(1,1,n,q[i].r-sum+1,q[i].r,1);
  56.         }
  57.         else
  58.         {
  59.             Change(1,1,n,q[i].l,q[i].l+sum-1,1);
  60.             Change(1,1,n,q[i].l+sum,q[i].r,0);
  61.         }
  62.     }
  63.     return Query(1,1,n,now,now) == 0;
  64. }
  65. int main()
  66. {
  67.     scanf("%d%d",&n,&m);
  68.     for (int i=1;i<=n;++i) scanf("%d",&a[i]);
  69.     for (int i=1;i<=m;++i) scanf("%d%d%d",&q[i].op,&q[i].l,&q[i].r);
  70.     scanf("%d",&now);
  71.     int l,r,mid;
  72.     l = 1, r = n, ans = 0;
  73.     while (l < r)
  74.     {
  75.         mid = (l+r) >> 1;
  76.         if (Check(mid)) ans = mid, l = mid + 1;
  77.         else r = mid;
  78.     }
  79.     printf("%d\n",ans);
  80.     return 0;
  81. }

[Tjoi2016&Heoi2016]序列

一幅三维偏序的样子就用CDQ分治吧

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int read()
  4. {
  5.     int x=0; bool f=0; char ch;
  6.     for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
  7.     for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; if (f) x=-x;
  8.     return x;
  9. }
  10. const int NN = 100005;
  11. int n,m,ans,tr[NN],f[NN];
  12. struct REC
  13. {
  14.     int v,mn,mx,id;
  15. }a[NN],tmp[NN];
  16. inline bool cmp_mn(REC xx,REC yy) { return xx.mn < yy.mn; }
  17. inline bool cmp_id(REC xx,REC yy) { return xx.id < yy.id; }
  18. inline int lowbit(int xx) { return xx & -xx; }
  19. inline int Query(int xx)
  20. {
  21.     int mx = 0;
  22.     for (;xx;xx-=lowbit(xx)) mx = max(mx,tr[xx]);
  23.     return mx;
  24. }
  25. inline void Change(int xx,int yy) { for (;xx<=NN-5;xx+=lowbit(xx)) tr[xx] = max(tr[xx],yy); }
  26. inline void Clr(int xx) { for (;xx<=NN-5;xx+=lowbit(xx)) tr[xx] = 0; }
  27. void Solve(int l,int r)
  28. {
  29.     if (l >= r) return;
  30.     int mid = (l+r) >> 1, t, l1, l2;
  31.     Solve(l,mid);
  32.     sort(a+mid+1,a+r+1,cmp_mn);
  33.     t = l;
  34.     for (int i=mid+1;i<=r;++i)
  35.     {
  36.         for (;t <= mid && a[t].v <= a[i].mn;++t) Change(a[t].mx,f[a[t].id]);
  37.         f[a[i].id] = max(f[a[i].id], Query(a[i].v)+1);
  38.     }
  39.     for (int i=l;i<t;++i) Clr(a[i].mx);
  40.     sort(a+mid+1,a+r+1,cmp_id);
  41.     Solve(mid+1,r);
  42.     l1 = l, l2 = mid+1, t = l;
  43.     for (;l1<=mid && l2<=r;) tmp[t++] = a[l1].v < a[l2].v ? a[l1++] : a[l2++];
  44.     for (;l1<=mid;) tmp[t++] = a[l1++];
  45.     for (;l2<=r;) tmp[t++] = a[l2++];
  46.     for (int i=l;i<=r;++i) a[i] = tmp[i];
  47. }
  48. int main()
  49. {
  50.     n = read(), m = read();
  51.     int x,y;
  52.     for (int i=1;i<=n;++i) a[i].v = a[i].mn = a[i].mx = read(), a[i].id = i, f[i] = 1;
  53.     for (int i=1;i<=m;++i) x = read(), y = read(), a[x].mn = min(a[x].mn, y), a[x].mx = max(a[x].mx,y);
  54.     Solve(1,n);
  55.     ans = 0;
  56.     for (int i=1;i<=n;++i) ans = max(ans,f[i]);
  57.     printf("%d\n",ans);  
  58.     return 0;
  59. }

[Tjoi2016&Heoi2016]游戏

二分图匹配

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NN = 5005;
  4. char ch[55][55];
  5. int head[NN],lk[NN],a[55][55],b[55][55],vis[NN],tota,totb,tot,ans,n,m;
  6. struct E
  7. {
  8.     int ne,v;
  9. }e[NN];
  10. void Build(int xx,int yy)
  11. {
  12.     e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
  13. }
  14. int Find(int xx,int yy)
  15. {
  16.     for (int i=head[xx];i;i=e[i].ne)
  17.     if (vis[e[i].v] != yy)
  18.     {
  19.         vis[e[i].v] = yy;
  20.         if (!lk[e[i].v] || Find(lk[e[i].v],yy)) { lk[e[i].v] = xx; return 1; }
  21.     }
  22.     return 0;
  23. }
  24. int main()
  25. {
  26.     scanf("%d%d",&n,&m);
  27.     tota = totb = 1;
  28.     for (int i=1;i<=n;++i,++tota)
  29.     {
  30.         scanf("%s",ch[i]+1);
  31.         for (int j=1;j<=m;++j) a[i][j] = (ch[i][j] == '#') ? ++tota : tota;
  32.     }
  33.     for (int j=1;j<=m;++j,++totb)
  34.         for (int i=1;i<=n;++i)
  35.         {
  36.             b[i][j] = (ch[i][j] == '#') ? ++totb : totb;
  37.         }
  38.     for (int i=1;i<=n;++i)
  39.         for (int j=1;j<=m;++j)
  40.             if (ch[i][j] == '*') Build(a[i][j],b[i][j]);
  41.     ans = 0;
  42.     for (int i=1;i<=tota;++i) ans += Find(i,i);
  43.     printf("%d\n",ans);
  44.     return 0;
  45. }

[Tjoi2016&Heoi2016]求和

第一次写NTT
一幅感觉和FFT相似的样子

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int NN = 400005;
  5. const LL mod = 998244353;
  6. int n;
  7. LL ans,a[NN],b[NN],f[NN],fac[NN],inv[NN],rev[NN],N,L;
  8. LL KSM(LL xx,LL yy)
  9. {
  10.     LL sum=1ll;
  11.     for (xx%=mod;yy;xx = xx*xx%mod,yy >>= 1) if (yy&1) sum = sum*xx%mod;
  12.     return sum;
  13. }
  14. void NTT(LL *a,int N,int flag)
  15. {
  16.     for (int i=0;i<N;++i) if (i < rev[i]) swap(a[i],a[rev[i]]);
  17.     for (int k=2;k<=N;k<<=1)
  18.     {
  19.         int mid = k >> 1;
  20.         LL wn = KSM(3,((mod-1)/k*flag+mod-1) % (mod-1));
  21.         for (int i=0;i<N;i+=k)
  22.         {
  23.             LL w = 1;
  24.             for (int j=0;j<mid;w=w*wn%mod,++j)
  25.             {
  26.                 LL xx = a[i+j], yy = a[i+j+mid] * w % mod;
  27.                 a[i+j] = (xx+yy) % mod, a[i+j+mid] = (xx-yy+mod) % mod;
  28.             }
  29.         }
  30.     }
  31.     if (flag == -1)
  32.     {
  33.         LL INV = KSM(N,mod-2);
  34.         for (int i=0;i<N;++i) a[i] = a[i] * INV % mod;
  35.     }
  36. }
  37. void Solve(int l,int r)
  38. {
  39.     if (l == r) return;
  40.     int mid = (l+r) >> 1;
  41.     Solve(l,mid);
  42.     N = mid - l + r - l, L = 1;
  43.     while ((1<<L) < N) ++L;
  44.     N = 1 << L;
  45.     for (int i=0;i<N;++i) a[i] = b[i] = 0;
  46.     for (int i=l;i<=mid;++i) a[i-l] = f[i];
  47.     for (int i=1;i<=r-l;++i) b[i-1] = inv[i] * 2 % mod;
  48.     for (int i=1;i<N;++i) rev[i] = (rev[i>>1]>>1) | ((i&1)<<(L-1));
  49.     NTT(a,N,1), NTT(b,N,1);
  50.     for (int i=0;i<N;++i) a[i] = a[i] * b[i] % mod;
  51.     NTT(a,N,-1);
  52.     for (int i=mid+1;i<=r;++i) f[i] = (f[i] + a[i-l-1]) % mod;
  53.     Solve(mid+1,r);
  54. }
  55. int main()
  56. {
  57.     scanf("%d",&n);
  58.     fac[0] = inv[0] = 1;
  59.     for (int i=1;i<=n;++i) fac[i] = fac[i-1] * i % mod, inv[i] = KSM(fac[i],mod-2);
  60.     f[0] = 1;
  61.     Solve(0,n);
  62.     for (int i=0;i<=n;++i) ans = (ans + f[i] * fac[i] % mod) % mod;
  63.     printf("%lld\n",ans);
  64.     return 0;
  65. }

[Tjoi2016&Heoi2016]字符串

二分+Sam建SA+主席树

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NN = 200005,MM = 8000005;
  4. char ch[NN];
  5. int a[NN][26],fail[NN],c[NN],q[NN],fa[NN][20],mx[NN],rt[NN],pos[NN],lc[MM],rc[MM];
  6. int cnt,tot=1,la=1,n,m,ans;
  7. void Ins(int &rt,int l,int r,int x)
  8. {
  9.     rt = ++cnt;
  10.     if (l == r) return;
  11.     int mid = (l+r) >> 1;
  12.     if (x <= mid) Ins(lc[rt],l,mid,x); else Ins(rc[rt],mid+1,r,x);
  13. }
  14. int Merge(int x,int y)
  15. {
  16.     if (!x) return y;
  17.     if (!y) return x;
  18.     int z = ++cnt;
  19.     lc[z] = Merge(lc[x],lc[y]);
  20.     rc[z] = Merge(rc[x],rc[y]);
  21.     return z;
  22. }
  23. bool Query(int x,int l,int r,int L,int R)
  24. {
  25.     if (!x) return 0;
  26.     if (L <= l && R >= r) return 1;
  27.     int mid = (l+r) >> 1;
  28.     if (L <= mid && Query(lc[x],l,mid,L,R)) return 1;
  29.     if (mid < R && Query(rc[x],mid+1,r,L,R)) return 1;
  30.     return 0;
  31. }
  32. bool Check(int mid,int x,int l,int r)
  33. {
  34.     l = l+mid-1;
  35.     if (l > r) return 0;
  36.     for (int j=18;~j;--j)
  37.         if (mx[fa[x][j]] >= mid) x = fa[x][j];
  38.     return Query(rt[x],1,n,l,r);
  39. }
  40. int extend(int xx,int id)
  41. {
  42.     int p = la, np = la = ++tot; mx[np] = mx[p] + 1;
  43.     Ins(rt[np],1,n,id);
  44.     while (p && !a[p][xx]) a[p][xx] = np, p = fail[p];
  45.     if (!p) fail[np] = 1;
  46.     else
  47.     {
  48.         int q = a[p][xx];
  49.         if (mx[q] == mx[p] + 1) fail[np] = q;
  50.         else
  51.         {
  52.             int nq = ++tot; mx[nq] = mx[p] + 1;
  53.             memcpy(a[nq],a[q],sizeof(a[q]));
  54.             fail[nq] = fail[q], fail[np] = fail[q] = nq;
  55.             while (p && a[p][xx] == q) a[p][xx] = nq, p = fail[p];
  56.         }
  57.     }
  58.     return np;
  59. }
  60. void Get_fail()
  61. {
  62.     int x,f;
  63.     for (int i=1;i<=tot;++i) ++ c[mx[i]];
  64.     for (int i=1;i<=tot;++i) c[i] += c[i-1];
  65.     for (int i=tot;i;--i) q[c[mx[i]]--] = i;
  66.     for (int i=tot;i;--i) x = q[i], f = fail[x], rt[f] = Merge(rt[f],rt[x]);
  67.     for (int i=1;i<=tot;++i) fa[i][0] = fail[i];
  68.     for (int j=1;j<=18;++j)
  69.         for (int i=1;i<=tot;++i) fa[i][j] = fa[fa[i][j-1]][j-1];
  70. }
  71. int main()
  72. {
  73.     scanf("%d%d",&n,&m);
  74.     scanf("%s",ch+1);
  75.     int xa,ya,xb,yb,l,r;
  76.     reverse(ch+1,ch+1+n);
  77.     for (int i=1;i<=n;++i) pos[i] = extend(ch[i]-'a',i);
  78.     Get_fail();
  79.     for (int i=1;i<=m;++i)
  80.     {
  81.         scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
  82.         xa = n-xa+1, ya = n-ya+1, xb = n-xb+1, yb = n-yb+1;
  83.         swap(xa,ya), swap(xb,yb);
  84.         l = 0, r = yb-xb+1;
  85.         while (l < r)
  86.         {
  87.             //printf("%d %d\n",l,r);
  88.             int mid = (l+r+1) >> 1;
  89.             if (Check(mid,pos[yb],xa,ya)) l = mid; else r = mid-1;
  90.         }
  91.         printf("%d\n",l);
  92.     }
  93.     return 0;
  94. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注