[关闭]
@Plutorabbit 2017-02-19T02:22:41.000000Z 字数 8878 阅读 2448

SDOI 2016

SDOI 2016 BZOJ OI

BZOJ-4513 ~ BZOJ-4518

[Sdoi2016]储能表

数位DP
f[i][0/1][0/1][0/1]表示考虑到第i位前i位[是/否]卡n的上界，卡m的上界，卡k的下界的数对个数
g[i][0/1][0/1][0/1]表示考虑到第i位前i位[是/否]卡n的上界，卡m的上界，卡k的下界的数对的和

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. int T;  
  5. LL n,m,k,mod,f[110][2][2][2],g[110][2][2][2],bin[65],ans;
  6. int main()
  7. {
  8.     scanf("%d",&T);
  9.     while (T--)
  10.     {
  11.         scanf("%lld%lld%lld%lld",&n,&m,&k,&mod);
  12.         --n, --m;
  13.         ans = 0ll;
  14.         bin[0]=1; for (int i=1;i<=63;++i) bin[i] = (bin[i-1]*2ll) % mod;
  15.         memset(f,0,sizeof(f)), memset(g,0,sizeof(g));
  16.         f[0][3][1][4] = 1, g[0][5][1][6] = 0;
  17.         int p,q,t,A,B,C;
  18.         for (int i=0;i<=63;++i)
  19.             for (int a=0;a<2;++a)
  20.                 for (int b=0;b<2;++b)
  21.                     for (int c=0;c<2;++c)
  22.                     if (f[i][a][b][c])
  23.                     {
  24.                         p = ((n&(1ll<<(63-i)))==0)?0:1, q = ((m&(1ll<<(63-i)))==0)?0:1, t = ((k&(1ll<<(63-i)))==0)?0:1;
  25.                         for (int x=0;x<2;++x)
  26.                         {
  27.                             if (a && x>p) continue;
  28.                             for (int y=0;y<2;++y)
  29.                             {
  30.                                 if (b && y>q) continue;
  31.                                 int z = x^y;
  32.                                 if (c && z<t) continue;
  33.                                 A = (a && x==p)?1:0, B = (b && y==q)?1:0, C = (c && z==t)?1:0;
  34.                                 f[i+1][A][B][C] = (f[i+1][A][B][C] + f[i][a][b][c]) % mod;
  35.                                 g[i+1][A][B][C] = (g[i+1][A][B][C] + g[i][a][b][c] + ((z!=0)?bin[63-i]:0)*f[i][a][b][c] % mod) % mod;
  36.                             }
  37.                         }
  38.                     }
  39.         k %= mod;
  40.         for (int a=0;a<2;++a)
  41.             for (int b=0;b<2;++b)
  42.                 for (int c=0;c<2;++c) ans = (ans + g[64][a][b][c] - k*f[64][a][b][c]%mod + mod) % mod;
  43.         printf("%lld\n",ans);
  44.     }
  45.     return 0;
  46. }

[Sdoi2016]数字配对

质因数分解看有奇数/偶数个质因数
建图跑费用流

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <queue>
  8. #define INF 100000000000000010
  9. #define LL long long
  10. #define NN 1000010
  11. using namespace std;
  12. int tot=1,n,m,a[NN],f[NN],prime[32000],head[NN],S,T,fa[NN];
  13. LL ans=0ll,cost=0ll,b[NN],c[NN],dis[NN];
  14. bool fprime[32100],vis[NN];
  15. queue<int> que;
  16. struct E
  17. {
  18.     int ne,v,u;
  19.     LL w,c;
  20. }e[NN];
  21. int read()
  22. {
  23.     int xx; 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.     return xx;
  27. }
  28. LL Read()
  29. {
  30.     LL xx; bool f=0; char CH;
  31.     for (CH=getchar();CH<'0'||CH>'9';CH=getchar()) if (CH=='-') f=1;
  32.     for (xx=0;CH>='0';CH=getchar()) xx=xx*10+CH-'0'; if (f) xx=-xx;
  33.     return xx;
  34. }
  35. void Build(int xx,int yy,LL zz,LL cc)
  36. {
  37.     e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].u=xx, e[tot].w=zz, e[tot].c=cc;
  38.     e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].u=yy, e[tot].w=0, e[tot].c=-cc;
  39. }
  40. bool SPFA()
  41. {
  42.     while (!que.empty()) que.pop();
  43.     memset(dis,-128,sizeof(dis));
  44.     memset(vis,0,sizeof(vis));
  45.     dis[S]=0, que.push(S), vis[S]=1;
  46.     while (!que.empty())
  47.     {
  48.         int now=que.front(); que.pop();
  49.         vis[now]=0;
  50.         for (int i=head[now];i;i=e[i].ne)
  51.         if (e[i].w && dis[e[i].v]<dis[now]+e[i].c)
  52.         {
  53.             dis[e[i].v]=dis[now]+e[i].c, fa[e[i].v]=i;
  54.             if (!vis[e[i].v]) vis[e[i].v]=1, que.push(e[i].v);
  55.         }
  56.     }
  57.     return dis[T]>=-INF;
  58. }
  59. LL MCF()
  60. {
  61.     LL xx=INF;
  62.     for (int i=fa[T];i;i=fa[e[i].u]) xx=min(xx,e[i].w);
  63.     if (cost+xx*dis[T]<0) xx=-cost/dis[T];
  64.     cost+=xx*dis[T];
  65.     for (int i=fa[T];i;i=fa[e[i].u]) e[i].w-=xx, e[i^1].w+=xx;
  66.     return xx;
  67. }
  68. int Fenjie(int xx)
  69. {
  70.     int total=0,x=xx;
  71.     for (int i=1;i<=prime[0]&&prime[i]<=(int)sqrt(x);++i)
  72.         while (xx%prime[i]==0) xx/=prime[i], ++total;
  73.     if (xx!=1) ++total;
  74.     return total;
  75. }
  76. bool Pri(int xx)
  77. {
  78.     for (int i=1;i<=prime[0]&&prime[i]<=(int)sqrt(xx);++i)
  79.         if (xx%prime[i]==0) return 0;
  80.     return 1;
  81. }
  82. int main()
  83. {
  84.     n=read(), S=n+1, T=n+2;
  85.     memset(fprime,0,sizeof(fprime));
  86.     memset(prime,0,sizeof(prime));
  87.     fprime[1]=1;
  88.     for (int i=2;i<=32000;++i)
  89.     {
  90.         if (!f[i]) prime[++prime[0]]=i;
  91.         for (int j=1;prime[j]*i<=n&&j<=prime[0];++j)
  92.         { fprime[prime[j]*i]=1; if (i%prime[j]==0) break;}
  93.     }
  94.     for (int i=1;i<=n;++i) a[i]=read();
  95.     for (int i=1;i<=n;++i) b[i]=Read();
  96.     for (int i=1;i<=n;++i) c[i]=Read();
  97.     for (int i=1;i<=n;++i) f[i]=Fenjie(a[i])&1;
  98.     for (int i=1;i<=n;++i)
  99.         if (f[i]) Build(S,i,b[i],0); else Build(i,T,b[i],0);
  100.     for (int i=1;i<=n;++i)
  101.     {
  102.         for (int j=i+1;j<=n;++j)
  103.             if (f[i]^f[j])
  104.             {
  105.                 if (a[i]%a[j]==0 && Pri(a[i]/a[j]))
  106.                     if (f[i]&1) Build(i,j,INF,c[i]*c[j]);
  107.                     else Build(j,i,INF,c[i]*c[j]);
  108.                 else
  109.                 if (a[j]%a[i]==0 && Pri(a[j]/a[i]))
  110.                     if (f[i]&1) Build(i,j,INF,c[i]*c[j]);
  111.                     else Build(j,i,INF,c[i]*c[j]);
  112.             }
  113.     }
  114.     while (SPFA())
  115.     {
  116.         LL tmpp=MCF();
  117.         if (tmpp==0ll) break;
  118.         ans+=tmpp;
  119.     }
  120.     printf("%lld\n",ans);
  121.     return 0;
  122. }

[Sdoi2016]游戏

好久没有写树剖了QAQ
其实就是在树上维护好几条直线
注意判断交点什么的大小关系就可以了

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. LL read()
  5. {
  6.     LL x=0ll; bool f=0; char ch;
  7.     for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
  8.     for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10ll+ch-'0'; if (f) x=-x;
  9.     return x;
  10. }
  11. const int NN = 100005;
  12. const LL INF = 123456789123456789ll;
  13. int n,m,tot,id;
  14. int head[NN],sz[NN],fa[NN],pos[NN],num[NN],belong[NN],son[NN];
  15. LL ans,deep[NN];
  16. struct E
  17. {
  18.     int ne,v;
  19.     LL w;
  20. }e[NN<<1];
  21. struct TR
  22. {
  23.     LL a,b,mn;
  24. }tr[NN<<2];
  25. inline void Build(int xx,int yy,LL zz)
  26. {
  27.     e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy, e[tot].w = zz;
  28.     e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx, e[tot].w = zz;
  29. }
  30. void DFS1(int xx)
  31. {
  32.     sz[xx] = 1;
  33.     for (int i=head[xx];i;i=e[i].ne)
  34.     if (e[i].v != fa[xx])
  35.     {
  36.         fa[e[i].v] = xx, deep[e[i].v] = deep[xx] + e[i].w;
  37.         DFS1(e[i].v);
  38.         sz[xx] += sz[e[i].v];
  39.         if (sz[e[i].v] > sz[son[xx]]) son[xx] = e[i].v;
  40.     }
  41. }
  42. void DFS2(int xx,int chain)
  43. {
  44.     belong[xx] = chain, pos[xx] = ++id, num[id] = xx;
  45.     if (son[xx]) DFS2(son[xx],chain);
  46.     for (int i=head[xx];i;i=e[i].ne)
  47.         if (e[i].v != fa[xx] && e[i].v != son[xx]) DFS2(e[i].v,e[i].v);
  48. }
  49. void Build_tr(int k,int l,int r)
  50. {
  51.     tr[k].a = 0, tr[k].b = tr[k].mn = INF;
  52.     if (l == r) return;
  53.     int mid = (l+r) >> 1;
  54.     Build_tr(k<<1,l,mid), Build_tr(k<<1|1,mid+1,r);
  55. } 
  56. LL Cal(LL a,LL b,LL x) { return a*deep[num[x]] + b; }
  57. void Update(int k,int l,int r,LL a,LL b)
  58. {
  59.     LL lx = Cal(tr[k].a,tr[k].b,l), rx = Cal(tr[k].a,tr[k].b,r), ly = Cal(a,b,l), ry = Cal(a,b,r);
  60.     if (lx <= ly && rx <= ry) return;
  61.     if (lx >= ly && rx >= ry) { tr[k].a = a, tr[k].b = b; return; }
  62.     int mid = (l+r) >> 1;
  63.     LL mx = Cal(tr[k].a,tr[k].b,mid), my = Cal(a,b,mid);
  64.     if (mx >= my) { swap(a,tr[k].a), swap(b,tr[k].b), swap(lx,ly), swap(rx,ry), swap(mx,my); }
  65.     if (lx >= ly) Update(k<<1,l,mid,a,b);
  66.     else Update(k<<1|1,mid+1,r,a,b);
  67. }
  68. void Add(int k,int l,int r,int L,int R,LL a,LL b)
  69. {
  70.     tr[k].mn = min(tr[k].mn,min(Cal(a,b,L), Cal(a,b,R)));
  71.     if (l == L && r == R) { Update(k,l,r,a,b); return; }
  72.     int mid = (l+r) >> 1;
  73.     if (R <= mid) Add(k<<1,l,mid,L,R,a,b);
  74.     else if (L > mid) Add(k<<1|1,mid+1,r,L,R,a,b);
  75.     else Add(k<<1,l,mid,L,mid,a,b), Add(k<<1|1,mid+1,r,mid+1,R,a,b);
  76. }
  78. void Query(int k,int l,int r,int L,int R)
  79. {
  80.     ans = min(ans,min(Cal(tr[k].a,tr[k].b,L), Cal(tr[k].a,tr[k].b,R)));
  81.     if (l == L && r == R) { ans = min(ans, tr[k].mn); return; }
  82.     int mid = (l+r) >> 1;
  83.     if (R <= mid) Query(k<<1,l,mid,L,R);
  84.     else if (L > mid) Query(k<<1|1,mid+1,r,L,R);
  85.     else Query(k<<1,l,mid,L,mid), Query(k<<1|1,mid+1,r,mid+1,R);
  86. }
  87. inline void Solve_add(int x,int f,LL a,LL b)
  88. {
  89.     for (;belong[x] != belong[f]; x = fa[belong[x]]) Add(1,1,n,pos[belong[x]],pos[x],a,b);
  90.     Add(1,1,n,pos[f],pos[x],a,b);
  91. }
  92. inline void Solve_query(int x,int f)
  93. {
  94.     for (;belong[x] != belong[f]; x = fa[belong[x]]) Query(1,1,n,pos[belong[x]],pos[x]);
  95.     Query(1,1,n,pos[f],pos[x]);
  96. }
  97. inline int LCA(int xx,int yy)
  98. {
  99.     for (;belong[xx] != belong[yy]; deep[belong[xx]] > deep[belong[yy]] ? xx = fa[belong[xx]]: yy = fa[belong[yy]]);
  100.     return deep[xx] < deep[yy] ? xx : yy;
  101. }
  102. int main()
  103. {
  104.     n = read(), m = read();
  105.     int x,y,z,lca,op;
  106.     LL a,b;
  107.     for (int i=1;i<n;++i) x = read(), y = read(), z = read(), Build(x,y,z);
  108.     DFS1(1);
  109.     DFS2(1,1);
  110.     Build_tr(1,1,n);
  111.     while (m--)
  112.     {
  113.         op = read(), x = read(), y = read();
  114.         if (op == 1)
  115.         {
  116.             a = read(), b = read();
  117.             lca = LCA(x,y);
  118.             Solve_add(x,lca,-a,a*deep[x]+b);
  119.             Solve_add(y,lca,a,a*(deep[x]-(deep[lca]*2))+b);
  120.         }
  121.         else
  122.         {
  123.             lca = LCA(x,y);
  124.             ans = INF;
  125.             Solve_query(x,lca), Solve_query(y,lca);
  126.             printf("%lld\n",ans);
  127.         }
  128.     }
  129.     return 0;
  130. }

[Sdoi2016]生成魔咒

Sam裸题QAQ

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int MM = 200010;
  5. int n,x;
  6. LL ans;
  7. struct Sam
  8. {
  9.     int tot,la,mx[MM],fa[MM],val[MM];
  10.     map <int,int> a[MM];
  11.     Sam() { la = ++tot; }
  12.     void extend(int xx)
  13.     {
  14.         int p = la, np = la = ++tot;
  15.         mx[np] = mx[p] + 1, val[np] = 1;
  16.         while (!a[p][xx] && p) a[p][xx] = np, p = fa[p];
  17.         if (!p) fa[np] = 1;
  18.         else
  19.         {
  20.             int q = a[p][xx];
  21.             if (mx[p]+1 == mx[q]) fa[np] = q;
  22.             else
  23.             {
  24.                 int nq = ++tot;
  25.                 mx[nq] = mx[p]+1;
  26.                 a[nq] = a[q];
  27.                 fa[nq] = fa[q] , fa[np] = fa[q] = nq;
  28.                 while (a[p][xx] == q && p) a[p][xx] = nq, p = fa[p];
  29.             }
  30.         }
  31.         ans += mx[np] - mx[fa[np]];
  32.         printf("%lld\n",ans);
  33.     }
  34. }SAM;
  36. int main()
  37. {
  38.     scanf("%d",&n);
  39.     for (int i=1;i<=n;++i) scanf("%d",&x), SAM.extend(x);
  40.     return 0;
  41. }

[Sdoi2016]排列计数

小学递推错排
逆元搞搞

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. using namespace std;
  9. #define mod 1000000007ll
  10. #define LL long long
  11. #define NN 1002000
  12. #define N 1000010
  13. int n,m,T;
  14. LL fac[NN],f[NN];
  15. LL pow(LL xx,LL yy) 
  16. {
  17.     LL sum=1ll;
  18.     for (xx%=mod;yy;xx=xx*xx%mod,yy>>=1) if (yy&1) sum=sum*xx%mod;
  19.     return sum;
  20. }
  22. void Pre()
  23. {
  24.     fac[0] = 1ll;
  25.     for (LL i=1;i<=N;++i) fac[i] = (fac[i-1] * i) % mod;
  26.     f[0] = 1ll, f[1] = 0ll, f[2] = 1ll;
  27.     for (LL i=3;i<=N;++i) f[i] = (f[i-1] + f[i-2]) % mod *(i-1ll) % mod;
  28. }
  30. int main()
  31. {
  32.     Pre();
  33.     scanf("%d",&T);
  34.     while (T--)
  35.     {   scanf("%d%d",&n,&m);
  36.     printf("%lld\n",(f[n-m]*fac[n]%mod*pow(fac[n-m],mod-2)%mod*pow(fac[m],mod-2)%mod)%mod);
  37.     }
  38.     return 0;
  39. }

[Sdoi2016]征途

斜率优化DP
DP方程：

表示到第个点，分成了段，表示1~j的前缀和
斜率优化搞一搞还是资磁的

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int NN = 31005;
  5. int n,m,h,t,p,que[NN],summ;
  6. LL sum[NN],f[2][NN];
  7. LL sqr(LL xx) { return xx*xx; }
  8. double Y(int xx) { return (double)(f[p^1][xx]+sqr(sum[xx])); }
  9. double Cal(int xx,int yy) { return (Y(yy)-Y(xx))/(double)(sum[yy]-sum[xx]); }
  10. int main()
  11. {
  12.     scanf("%d%d",&n,&m);
  13.     for (int i=1;i<=n;++i)
  14.     {
  15.         scanf("%lld",&sum[i]);
  16.         summ += sum[i], sum[i] = (LL)sum[i]*m + sum[i-1];
  17.     }
  18.     p = 1;
  19.     memset(f,0x3f,sizeof(f));
  20.     f[0][0] = 0;
  21.     for (int i=1;i<=n;++i) f[0][i] = sqr(sum[i]-summ);
  22.     for (int k=1;k<=m;++k)
  23.     {
  24.         h = t = 1, que[h] = 0;
  25.         memset(f[p],0x3f,sizeof(f[p]));
  26.         for (int i=1;i<=n;++i)
  27.         {
  28.             while (h<t && Cal(que[h],que[h+1]) < (sum[i]-summ)*2) ++h;
  29.             int j = que[h];
  30.             f[p][i] = f[p^1][j] + sqr(sum[i]-sum[j]-summ);
  31.             while (h<t && Cal(que[t-1],que[t]) > Cal(que[t],i)) --t;
  32.             que[++t] = i;
  33.         }
  34.         p ^= 1;
  35.     }
  36.     printf("%lld\n",f[p^1][n]/m);  
  37.     return 0;
  38. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注