[关闭]
@Plutorabbit 2017-02-19T03:05:55.000000Z 字数 7644 阅读 2045

HNOI 2016

未分类

BZOJ 4537 ~ BZOJ 4542

[Hnoi2016]最小公倍数

分块+并查集
就是零散的部分用并查集来维护
但是不能路径压缩
因为要暴力撤回去。。。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <queue>
  6. #include <cmath>
  7. #include <cstring>
  8. #define NN 50010
  9. #define MM 100010
  10. using namespace std;
  11. struct Edge
  12. {
  13.     int x,y,a,b,id;
  14. }e[MM],q[MM],tmp[MM];
  15. int fa[MM],n,m,sz[MM],Q,tot,ma[MM],mb[MM],block,k;
  16. bool vis[MM]={0};
  17. struct PRE
  18. {
  19.     int x,y,sz,fa,yma,ymb,f,xma,xmb;
  20. }pre[MM];
  21. void read(int &xx)
  22. {
  23.     bool f=0; char CH;
  24.     for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
  25.     for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
  26. }
  27. bool cmp1(Edge xx,Edge yy) { if (xx.a==yy.a) return xx.b<yy.b; else return xx.a<yy.a;}
  28. bool cmp2(Edge xx,Edge yy) { if (xx.b==yy.b) return xx.a<yy.a; else return xx.b<yy.b;}
  29. int Find(int xx) { return (xx==fa[xx]?xx:Find(fa[xx]));}
  30. void Doit(int x,int y,int a,int b)
  31. {
  32.     int xx=Find(x), yy=Find(y);
  33.     if (sz[xx]>sz[yy]) swap(xx,yy);
  34.     pre[++tot].x=xx, pre[tot].y=yy, pre[tot].f=fa[xx], pre[tot].sz=sz[yy];
  35.     pre[tot].yma=ma[yy], pre[tot].ymb=mb[yy], pre[tot].xma=ma[xx], pre[tot].xmb=mb[xx];
  36.     if (xx==yy) 
  37.     {
  38.         ma[yy]=max(ma[yy],a), mb[yy]=max(mb[yy],b); return;
  39.     }
  40.     fa[xx]=yy, sz[yy]+=sz[xx], ma[yy]=max(ma[yy],max(ma[xx],a)), mb[yy]=max(mb[yy],max(mb[xx],b));
  41. }
  42. void Back()
  43. {
  44.     for (;tot;tot--)
  45.     {
  46.         fa[pre[tot].x]=pre[tot].f, ma[pre[tot].x]=pre[tot].xma, mb[pre[tot].x]=pre[tot].xmb;
  47.         sz[pre[tot].y]=pre[tot].sz, ma[pre[tot].y]=pre[tot].yma, mb[pre[tot].y]=pre[tot].ymb;
  48.     }
  49. }
  50. int main()
  51. {
  52.     read(n), read(m);
  53.     for (int i=1;i<=m;++i) read(e[i].x), read(e[i].y), read(e[i].a), read(e[i].b), e[i].id=i;
  54.     read(Q);
  55.     for (int i=1;i<=Q;++i) read(q[i].x), read(q[i].y), read(q[i].a), read(q[i].b), q[i].id=i;
  56.     sort(e+1,e+1+m,cmp1); sort(q+1,q+1+Q,cmp2);
  57.     block=(int)sqrt(m);
  58.     for (int i=1;i<=m;i+=block)
  59.     {
  60.         k=0;
  61.         for (int j=1;j<=Q;++j) 
  62.             if (q[j].a>=e[i].a && (i+block>m || q[j].a<e[i+block].a)) tmp[++k]=q[j];
  63.         if (!k) continue;
  64.         sort(e+1,e+i,cmp2);
  65.         for (int j=1;j<=n;++j) fa[j]=j, sz[j]=1, ma[j]=mb[j]=-1;
  66.         for (int j=1,t=1;j<=k;++j)
  67.         {
  68.             for (;t<i && e[t].b<=tmp[j].b;t++) Doit(e[t].x,e[t].y,e[t].a,e[t].b);
  69.             tot=0;
  70.             for (int l=i;l<i+block&&l<=m;++l)
  71.             if (e[l].a<=tmp[j].a && e[l].b<=tmp[j].b) Doit(e[l].x,e[l].y,e[l].a,e[l].b);
  72.             int xx=Find(tmp[j].x), yy=Find(tmp[j].y);
  73.             if (xx==yy && ma[xx]==tmp[j].a && mb[xx]==tmp[j].b) vis[tmp[j].id]=1;
  74.             Back();
  75.         }
  76.     }
  77.     for (int i=1;i<=Q;++i) if (vis[i]) puts("Yes"); else puts("No");
  78.     return 0;
  79. }

[Hnoi2016]网络

树剖上乱搞

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <queue>
  8. #define INF 0x3f3f3f3f
  9. #define NN 100010
  10. using namespace std;
  11. struct Edge
  12. {
  13.     int ne,u,v;
  14. }e[NN<<1];
  15. struct A 
  16. { 
  17.     int x,y;
  18. }a[110];
  19. bool operator <(A xx,A yy) { return xx.x<yy.x;}
  20. int n,m,num,numm=0,tot=0,ans=0,cnt,now,x,y,op;
  21. int pos[NN],son[NN],fa[NN],sz[NN],deep[NN],head[NN],anc[NN];
  22. bool flag[NN<<1];
  23. priority_queue<A> que[300010];
  24. int read()
  25. {
  26.     int xx; bool f=0; char CH;
  27.     for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
  28.     for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
  29.     return xx;
  30. }
  31. void Build(int xx,int yy)
  32. {
  33.     e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].u=xx;
  34.     e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].u=yy;
  35. }
  36. void DFS1(int xx)
  37. {
  38.     sz[xx]=1;
  39.     for (int i=head[xx];i;i=e[i].ne)
  40.     if (e[i].v!=fa[xx])
  41.     {
  42.         fa[e[i].v]=xx, deep[e[i].v]=deep[xx]+1;
  43.         DFS1(e[i].v);
  44.         sz[xx]+=sz[e[i].v];
  45.         if (sz[e[i].v]>sz[son[xx]]) son[xx]=e[i].v;
  46.     }
  47. }
  48. void DFS2(int xx,int chain)
  49. {
  50.     pos[xx]=++numm, anc[xx]=chain;
  51.     if (son[xx]) DFS2(son[xx],chain);
  52.     for (int i=head[xx];i;i=e[i].ne)
  53.     if (e[i].v!=son[xx] && e[i].v!=fa[xx]) DFS2(e[i].v,e[i].v);
  54. }
  55. void Query(int k,int l,int r,int x)
  56. {
  57.     while (!que[k].empty() && flag[que[k].top().y]) que[k].pop();
  58.     if (!que[k].empty()) ans=max(ans,que[k].top().x);
  59.     if (l<r)
  60.     {
  61.         int mid=(l+r)>>1;
  62.         if (x<=mid) Query(k<<1,l,mid,x); else Query(k<<1|1,mid+1,r,x);
  63.     }
  64. }
  65. void Insert(int k,int l,int r,int x,int y)
  66. {
  67.     if (l==x && r==y) { que[k].push(A{num,now}); return;    }
  68.     int mid=(l+r)>>1;
  69.     if (y<=mid) Insert(k<<1,l,mid,x,y);
  70.     else if (x>mid) Insert(k<<1|1,mid+1,r,x,y);
  71.     else Insert(k<<1,l,mid,x,mid), Insert(k<<1|1,mid+1,r,mid+1,y);
  72. }
  73. int main()
  74. {
  75.     n=read(), m=read();
  76.     for (int i=1;i<n;++i) x=read(), y=read(), Build(x,y);
  77.     DFS1(1), DFS2(1,1);
  78.     for (now=1;now<=m;++now) 
  79.     {
  80.         op=read();
  81.         if (op==0)
  82.         {
  83.             x=read(), y=read(), num=read(), cnt=0;
  84.             for (;anc[x]!=anc[y];x=fa[anc[x]])
  85.             {
  86.                 if (deep[anc[x]]<deep[anc[y]]) swap(x,y);
  87.                 a[++cnt].x=pos[anc[x]], a[cnt].y=pos[x];
  88.             }
  89.             if (deep[x]>deep[y]) swap(x,y);
  90.             a[++cnt].x=pos[x], a[cnt].y=pos[y];
  91.             sort(a+1,a+1+cnt);
  92.             for (int i=1;i<=cnt;++i)
  93.                 if (a[i-1].y+1<a[i].x) Insert(1,1,n,a[i-1].y+1,a[i].x-1);
  94.             if (a[cnt].y<n) Insert(1,1,n,a[cnt].y+1,n);
  95.         }
  96.         else if (op==1) flag[read()]=1;
  97.         else ans=-1, Query(1,1,n,pos[read()]), printf("%d\n",ans);
  98.     }
  99.     return 0;
  100. }

[Hnoi2016]树

树上乱搞QAQ
感觉不想写就烂这了

[Hnoi2016]序列

莫队+rmq统计

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <queue>
  8. #define INF 0x3f3f3f3f
  9. #define NN 100010
  10. #define LL long long
  11. using namespace std;
  12. struct Query
  13. {
  14.     int l,r,id;
  15. }q[NN];
  16. int st[NN],a[NN],l[NN],r[NN],f[NN][20],n,m,top=0,block,Log[NN];
  17. LL ans[NN],now,ld[NN],rd[NN];
  18. bool cmp1(Query xx,Query yy)
  19. {
  20.     if (xx.l/block==yy.l/block) return xx.r<yy.r;
  21.     else return xx.l/block<yy.l/block;
  22. }
  23. int read()
  24. {
  25.     int xx; bool f=0; char CH;
  26.     for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
  27.     for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
  28.     return xx;
  29. }
  30. int Q(int x,int y)
  31. {
  32.     int tmpp=(int)log2(y-x+1);
  33.     if (a[f[x][tmpp]]<a[f[y-(1<<tmpp)+1][tmpp]]) return f[x][tmpp];
  34.     else return f[y-(1<<tmpp)+1][tmpp];
  35. }
  36. void L_(int x,int y,LL t)
  37. {
  38.     int tmp=Q(x,y);
  39.     now+=t*a[tmp]*(y-tmp+1)+t*(rd[x]-rd[tmp]);
  40. }
  41. void R_(int x,int y,LL t)
  42. {
  43.     int tmp=Q(x,y);
  44.     now+=t*a[tmp]*(tmp-x+1)+t*(ld[y]-ld[tmp]);
  45. }
  46. void pre()
  47. {
  48.     for (int i=1;i<=n;++i)
  49.     {
  50.         while (top && a[st[top]]>a[i]) r[st[top--]]=i;
  51.         if (a[st[top]]==a[i]) l[i]=l[st[top]]; else l[i]=st[top];
  52.         st[++top]=i;
  53.     }
  54.     while (top) r[st[top--]]=n+1;
  55.     for (int i=1;i<=n;++i) ld[i]=ld[l[i]]+1ll*(i-l[i])*a[i];
  56.     for (int i=n;i>=1;--i) rd[i]=rd[r[i]]+1ll*(r[i]-i)*a[i];
  57.     for (int i=1;i<=n;++i) f[i][0]=i;
  58.     for (int i=1;(1<<i)<=n;++i)
  59.         for (int j=1;j<=n-(1<<i)+1;j++)
  60.         {
  61.             if (a[f[j][i-1]]<a[f[j+(1<<(i-1))][i-1]]) f[j][i]=f[j][i-1];
  62.             else f[j][i]=f[j+(1<<(i-1))][i-1];
  63.         }
  64. }
  65. int main()
  66. {
  67.     n=read(), m=read();
  68.     block=(int)sqrt(n);
  69.     for (int i=1;i<=n;++i) a[i]=read();
  70.     pre();
  71.     for (int i=1;i<=m;++i) q[i].l=read(), q[i].r=read(), q[i].id=i;
  72.     sort(q+1,q+1+m,cmp1);
  73.     int x=1,y=1;
  74.     now=a[1];
  75.     for (int i=1;i<=m;++i)
  76.     {
  77.         if (q[i].r>y) while (y!=q[i].r) y++, R_(x,y,1);
  78.         if (q[i].l>x) while (x!=q[i].l) L_(x,y,-1), x++;
  79.         if (q[i].l<x) while (x!=q[i].l) x--, L_(x,y,1);
  80.         if (q[i].r<y) while (y!=q[i].r) R_(x,y,-1), y--;
  81.         ans[q[i].id]=now;
  82.     }
  83.     for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
  84.     return 0;
  85. }

[Hnoi2016]矿区

听说对偶图乱搞QAQ
不会。。。
输出-1得10分蛤蛤

[Hnoi2016]大数

又双是莫队
且 时：统计模下前缀和即可
且 时：暴力讨论即可

  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. typedef long long LL;
  4. const int NN = 100005;
  5. struct Q
  6. {
  7.     int l,r,id;
  8. }q[NN];
  9. LL mod,ans[NN],a[NN],bin[NN],b[NN],c[NN],pos[NN],cnt[NN],cnt2[NN],sum2[NN],now = 0;
  10. int tot,m,n,block;
  11. char ch[NN];
  12. inline bool cmp(Q xx,Q yy) { return (pos[xx.l] != pos[yy.l]) ? xx.l < yy.l : xx.r < yy.r; }
  13. inline void modify(int p,int op)
  14. {
  15.     now -= cnt[b[p]] * (cnt[b[p]]-1) / 2;
  16.     cnt[b[p]] += op;
  17.     now += cnt[b[p]] * (cnt[b[p]]-1) / 2;
  18. }
  19. void Solve1()
  20. {
  21.     block  = (int) sqrt(n);
  22.     bin[0] = 1; for (int i=1;i<=n+1;++i) bin[i] = bin[i-1] * 10ll % mod;
  23.     for (int i=1;i<=n;++i) pos[i] = (i-1)/block + 1;
  24.     for (int i=n;i;--i) b[i] = (b[i+1] + a[i] * bin[n-i]) % mod;
  25.     b[n+1] = 0;
  26.     memcpy(c,b,sizeof(c));
  27.     sort(c+1,c+n+2);
  28.     tot = unique(c+1,c+n+2) - c - 1;
  29.     for (int i=1;i<=n+1;++i) b[i] = lower_bound(c+1,c+n+2,b[i]) - c;
  30.     sort(q+1,q+m+1,cmp);
  31.     for (int i=1,l=1,r=0;i<=m;++i)
  32.     {
  33.         for (;r<q[i].r;++r) modify(r+1,1);
  34.         for (;r>q[i].r;--r) modify(r, -1);
  35.         for (;l<q[i].l;++l) modify(l, -1);
  36.         for (;l>q[i].l;--l) modify(l-1,1);
  37.         ans[q[i].id] = now;
  38.     }
  39.     for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
  40. }
  41. void Solve2()
  42. {
  43.     for (int i=1;i<=n;++i) cnt2[i] = cnt2[i-1] + (a[i] % mod == 0), sum2[i] = sum2[i-1] + (a[i]%mod == 0 ? i : 0);
  44.     int x,y;
  45.     for (int i=1;i<=m;++i)
  46.     {
  47.         x = q[i].l, y = q[i].r-1;
  48.         printf("%lld\n",sum2[y] - sum2[x-1] - (LL)(x-1) * (cnt2[y]-cnt2[x-1]));
  49.     }
  50. }
  51. int main()
  52. {
  53.     scanf("%lld%s%d",&mod,ch+1,&m);
  54.     n = strlen(ch+1);
  55.     for (int i=1;i<=n;++i) a[i] = ch[i] - '0';
  56.     for (int i=1;i<=m;++i) scanf("%d%d",&q[i].l,&q[i].r), ++q[i].r, q[i].id = i;
  57.     if (mod == 2 || mod == 5) Solve2(); else Solve1();
  58.     return 0;
  59. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注