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

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. }
  77. void Query(int k,int l,int r,int L,int R)
  78. {
  79. ans = min(ans,min(Cal(tr[k].a,tr[k].b,L), Cal(tr[k].a,tr[k].b,R)));
  80. if (l == L && r == R) { ans = min(ans, tr[k].mn); return; }
  81. int mid = (l+r) >> 1;
  82. if (R <= mid) Query(k<<1,l,mid,L,R);
  83. else if (L > mid) Query(k<<1|1,mid+1,r,L,R);
  84. else Query(k<<1,l,mid,L,mid), Query(k<<1|1,mid+1,r,mid+1,R);
  85. }
  86. inline void Solve_add(int x,int f,LL a,LL b)
  87. {
  88. for (;belong[x] != belong[f]; x = fa[belong[x]]) Add(1,1,n,pos[belong[x]],pos[x],a,b);
  89. Add(1,1,n,pos[f],pos[x],a,b);
  90. }
  91. inline void Solve_query(int x,int f)
  92. {
  93. for (;belong[x] != belong[f]; x = fa[belong[x]]) Query(1,1,n,pos[belong[x]],pos[x]);
  94. Query(1,1,n,pos[f],pos[x]);
  95. }
  96. inline int LCA(int xx,int yy)
  97. {
  98. for (;belong[xx] != belong[yy]; deep[belong[xx]] > deep[belong[yy]] ? xx = fa[belong[xx]]: yy = fa[belong[yy]]);
  99. return deep[xx] < deep[yy] ? xx : yy;
  100. }
  101. int main()
  102. {
  103. n = read(), m = read();
  104. int x,y,z,lca,op;
  105. LL a,b;
  106. for (int i=1;i<n;++i) x = read(), y = read(), z = read(), Build(x,y,z);
  107. DFS1(1);
  108. DFS2(1,1);
  109. Build_tr(1,1,n);
  110. while (m--)
  111. {
  112. op = read(), x = read(), y = read();
  113. if (op == 1)
  114. {
  115. a = read(), b = read();
  116. lca = LCA(x,y);
  117. Solve_add(x,lca,-a,a*deep[x]+b);
  118. Solve_add(y,lca,a,a*(deep[x]-(deep[lca]*2))+b);
  119. }
  120. else
  121. {
  122. lca = LCA(x,y);
  123. ans = INF;
  124. Solve_query(x,lca), Solve_query(y,lca);
  125. printf("%lld\n",ans);
  126. }
  127. }
  128. return 0;
  129. }

[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;
  35. int main()
  36. {
  37. scanf("%d",&n);
  38. for (int i=1;i<=n;++i) scanf("%d",&x), SAM.extend(x);
  39. return 0;
  40. }

[Sdoi2016]排列计数

小学递推错排
逆元搞搞

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

[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. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注