[关闭]
@Plutorabbit 2017-02-19T01:56:46.000000Z 字数 7168 阅读 1972

POI 2016

POI 2016 OI BZOJ

BZOJ-4345 ~ BZOJ-4348

[POI2016]Korale

先用优先队列构造出第k小的权值，然后DFS求出方案。
用线段树找比t小的最前面的元素

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. int read()
  5. {
  6.     int x=0; 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*10+ch-'0'; if (f) x=-x;
  9.     return x;
  10. }
  11. const int NN = 1000005;
  12. int n,m,cnt,top,a[NN],num[NN],mn[NN<<2],st[NN];
  13. LL ans[NN];
  14. struct Q
  15. {
  16.     LL x; int y;
  17. }tmp;
  18. bool operator < (Q xx,Q yy) { return xx.x > yy.x; }
  19. priority_queue<Q> que;
  20. void Build(int k,int l,int r)
  21. {
  22.     if (l == r) { mn[k] = a[l]; return; }
  23.     int mid = (l+r) >> 1;
  24.     Build(k<<1,l,mid), Build(k<<1|1,mid+1,r);
  25.     mn[k] = min(mn[k<<1],mn[k<<1|1]);
  26. }
  27. int Query(int k,int l,int r,int x,LL y)
  28. {
  29.     if (x <= l)
  30.     {
  31.         if (mn[k] > y) return 0;
  32.         if (l == r) return l;
  33.     }
  34.     int mid = (l+r) >> 1,tmpp;
  35.     if (x <= mid) if ((tmpp=Query(k<<1,l,mid,x,y))) return tmpp;
  36.     return Query(k<<1|1,mid+1,r,x,y);
  37. }
  38. void DFS(int xx,LL res)
  39. {
  40.     if (!cnt) return;
  41.     if (!res)
  42.     {
  43.         --cnt;
  44.         if (!cnt) for (int i=1;i<=top;++i) printf("%d ",st[i]);
  45.         return;
  46.     }
  47.     for (int i=xx+1;i<=n;++i)
  48.     {
  49.         i = Query(1,1,n,i,res);
  50.         if (i) st[++top] = i, DFS(i,res-a[i]), --top; else break;
  51.     }
  52. }
  53. int main()
  54. {
  55.     n = read(), m = read()-1;
  56.     if (m == 0) { puts("0"); return 0; }
  57.     for (int i=1;i<=n;++i) a[i] = num[i] = read();
  58.     sort(num+1,num+1+n);
  59.     tmp.x = num[1], tmp.y = 1;
  60.     que.push(tmp);
  61.     for (int i=1;i<=m;++i)
  62.     {
  63.         tmp = que.top(); que.pop();
  64.         ans[i] = tmp.x;
  65.         if (i < m && tmp.y < n)
  66.         {
  67.             tmp.y ++, tmp.x += num[tmp.y], que.push(tmp);
  68.             tmp.x -= num[tmp.y-1], que.push(tmp);
  69.         }
  70.     }
  71.     for (int i=m;i&&ans[i]==ans[m];--i) ++cnt;
  72.     printf("%lld\n",ans[m]);
  73.     Build(1,1,n);
  74.     DFS(0,ans[m]);
  75.     return 0;
  76. }

[POI2016]Nadajniki

树型动规看出来应该很简单吧QAQ
分两种情况。
1. 在这个点放wifi。那么可以用h[i][1],h[i][2]表示放1、2个wifi的最优解,用儿子的对应状态转移一下即可。
2. 不放wifi。此时i到儿子的路径有两种情况：被i的儿子覆盖；被i的儿子的儿子和i的父亲覆盖。令f[i][x][y]表示i不放的时候，父亲节点放x个，儿子节点放y个。转移起来比较复杂，把9种状态压缩一下做。

  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 INF = 0x3f3f3f3f,NN = 200005;
  11. int n,ans,tot=0,head[NN],f[NN][3][3],g[NN][3],h[NN][3],q[NN][3],t[3][3];
  12. struct E
  13. {
  14.     int ne,v;
  15. }e[NN<<1];
  16. void Build(int xx,int yy)
  17. {
  18.     e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
  19.     e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
  20. }
  21. void DFS(int xx,int fa)
  22. {
  23.     h[xx][1] = 1, h[xx][2] = 2;
  24.     memset(g[xx],0x3f,sizeof(g[xx])), memset(f[xx],0x3f,sizeof(f[xx]));
  25.     f[xx][0][0] = 0;
  26.     for (int i=head[xx];i;i=e[i].ne)
  27.     if (e[i].v != fa)
  28.     {
  29.         DFS(e[i].v,xx);
  30.         int v = e[i].v, tmp = min(min(h[v][1],h[v][2]),q[v][1]);
  31.         for (int i=0;i<3;++i) tmp = min(tmp,g[v][i]);
  32.         h[xx][1] += tmp, h[xx][2] += min(tmp,q[v][2]);
  33.         memset(t,0x3f,sizeof(t));
  34.         for (int i=0;i<3;++i)
  35.             for (int j=0;j<3;++j)
  36.                 if (f[xx][i][j] < INF)
  37.                 {
  38.                     tmp = f[xx][i][j];
  39.                     for (int k=1;k<3;++k) t[min(2,i+k)][j] = min(t[min(2,i+k)][j],tmp+h[v][k]);
  40.                     for (int k=0;k<3;++k) t[i][max(2-k,j)] = min(t[i][max(2-k,j)],tmp+g[v][k]);
  41.                 }
  42.         memcpy(f[xx],t,sizeof(t));
  43.     }
  44.     for (int i=0;i<3;++i)
  45.         for (int j=0;j<=i;++j) g[xx][i] = min(g[xx][i],f[xx][i][j]);
  46.         q[xx][1] = min(f[xx][0][1],f[xx][1][2]), q[xx][2] = f[xx][0][2];
  47. }
  48. int main()
  49. {
  50.     n = read();
  51.     int x,y;
  52.     for (int i=1;i<n;++i) x = read(), y = read(), Build(x,y);
  53.     DFS(1,0);
  54.     ans = min(h[1][1],h[1][2]);
  55.     for (int i=0;i<3;++i) ans = min(ans,g[1][i]);
  56.     printf("%d\n",ans);
  57.     return 0;
  58. }

[POI2016]Nim z utrudnieniem

nim游戏变种，其实就是要求有多少种d为个数约数，剩余异或和为0的方案。
因此我们可以排序，由于x异或之后一定转移到2x内的数，所以说复杂度

  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 mod = 1000000007, NN = (1<<20);
  11. int n,m,d,f[10][NN],c[NN],g[NN];
  12. int main()
  13. {
  14.     n = read(), d = read();
  15.     f[0][0] = 1;
  16.     int x,l,t;
  17.     for (int i=1;i<=n;++i) x = read(), ++c[x], m = max(m,x);
  18.     for (int k=1;k<=m;++k)
  19.         while (c[k]--)
  20.         {
  21.             for (l=1;l<=k;l<<=1);
  22.             for (int i=0;i<l;++i) g[i] = (f[d-1][i] + f[0][i^k]) % mod;
  23.             for (int i=d-1;i;--i)
  24.                 for (int j=0;j<l;++j)
  25.                 {
  26.                     if (j > (j^k)) continue;
  27.                     t = f[i][j];
  28.                     f[i][j] = (f[i-1][j] + f[i][j^k]) % mod;
  29.                     f[i][j^k] = (f[i-1][j^k] + t) % mod;
  30.                 }
  31.             for (int i=0;i<l;++i) f[0][i] = g[i];
  32.         }
  33.     if (n % d == 0) f[0][0] = (f[0][0] - 1 + mod) % mod;
  34.     printf("%d\n",f[0][0]);
  35.     return 0;
  36. }

[POI2016]Park wodny

首先特判全部都是A或者全部都是B或者的情况。
然后把矩阵四周都填充上A，枚举一个块，分情况讨论：
1.暴力枚举四周两个块；
2.一个方向上在四周扩展两步；
3.一个角落上斜着扩展一步，再扩展另一步。
复杂度
感觉自己写得要死要活的了TAT

  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 = 1005;
  11. int n,m,tot,w,a[NN][NN],f[NN][NN],q[10005][3],ans;
  12. char ch[NN];
  13. struct S
  14. {
  15.     int x,y,l,r,s;
  16. }s[NN*NN];
  17. void UP(int xx,int yy,int zz){ q[++tot][0]=xx; q[tot][1]=yy; q[tot][2]=zz; }
  18. int SZ(int xx) { return s[xx].s; }
  19. void M(int xx) { w = max(w,xx); }
  20. void Get(int xx,int yy,int zz)
  21. {
  22.     s[zz].s ++, f[xx][yy] = zz, s[zz].y = max(s[zz].y,xx), s[zz].r = max(s[zz].r,yy);
  23.     if (a[xx+1][yy] && !f[xx+1][yy]) Get(xx+1,yy,zz);
  24.     if (a[xx][yy+1] && !f[xx][yy+1]) Get(xx,yy+1,zz);
  25. }
  26. int main()
  27. {
  28.     n = read();
  29.     if (n == 1) { puts("1"); return 0; }
  30.     for (int i=1,j;i<=n;++i)
  31.         for (scanf("%s",ch+1),j=1;j<=n;++j) a[i][j] = (ch[j]=='B');
  32.     int x,y,l,r,tmp;
  33.     for (int i=1;i<=n;++i)
  34.         for (int j=1;j<=n;++j)
  35.         if (a[i][j] && !f[i][j]) s[++m].x = i, s[m].l = j, Get(i,j,m);
  36.     if (m == 0) { puts("2"); return 0; }
  37.     if (m == 1) { printf("%d\n",min(n*n,s[1].s+2)); return 0; }
  38.     for (int i=1;i<=m;++i)
  39.     {
  40.         w = tot = 0;
  41.         x = s[i].x, y = s[i].y, l = s[i].l, r = s[i].r;
  42.         for (int j=x;j<=y;++j)
  43.         {
  44.             if (l > 2)
  45.             {
  46.                 if (a[j][l-2]) UP(f[j][l-2],0,0);
  47.                     else M(SZ(f[j][l-3])+(SZ(f[j-1][l-2])|SZ(f[j-1][l-1]))+(SZ(f[j+1][l-2])|SZ(f[j+1][l-1])));
  48.             }
  49.             if (r < n-1)
  50.             {
  51.                 if (a[j][r+2]) UP(f[j][r+2],0,0);
  52.                     else M(SZ(f[j][r+3])+(SZ(f[j-1][r+2])|SZ(f[j-1][r+1]))+(SZ(f[j+1][r+2])|SZ(f[j+1][r+1])));
  53.             }
  54.         }
  55.         for (int j=l;j<=r;++j)
  56.         {
  57.             if (x > 2)
  58.             {
  59.                 if (a[x-2][j]) UP(f[x-2][j],0,0);
  60.                     else M(SZ(f[x-3][j])+(SZ(f[x-2][j-1])|SZ(f[x-1][j-1]))+(SZ(f[x-2][j+1])|SZ(f[x-1][j+1])));
  61.             }
  62.             if (y < n-1)
  63.             {
  64.                 if (a[y+2][j]) UP(f[y+2][j],0,0);
  65.                     else M(SZ(f[y+3][j])+(SZ(f[y+2][j-1])|SZ(f[y+1][j-1]))+(SZ(f[y+2][j+1])|SZ(f[y+1][j+1])));
  66.             }
  67.         }   
  68.         if (a[x-1][l-1])
  69.         {
  70.             if (x>1) UP(f[x-1][l-1],f[x-2][l],0);
  71.             if (l>1) UP(f[x-1][l-1],f[x][l-2],0);
  72.         }
  73.         if (a[y+1][l-1])
  74.         {
  75.             if (y<n) UP(f[y+1][l-1],f[y+2][l],0);
  76.             if (l>1) UP(f[y+1][l-1],f[y][l-2],0);
  77.         }
  78.         if (a[x-1][r+1])
  79.         {
  80.             if (x>1) UP(f[x-1][r+1],f[x-2][r],0);
  81.             if (r<n) UP(f[x-1][r+1],f[x][r+2],0);
  82.         }
  83.         if (a[y+1][r+1])
  84.         {
  85.             if (y<n) UP(f[y+1][r+1],f[y+2][r],0);
  86.             if (r<n) UP(f[y+1][r+1],f[y][r+2],0);
  87.         }
  88.         if (l == r)
  89.         {
  90.             if (x>1) UP(f[x-2][l],f[x-1][l-1],f[x-1][l+1]);
  91.             if (y<n) UP(f[y+2][l],f[y+1][l-1],f[y+1][l+1]);
  92.         }
  93.         if (x == y)
  94.         {
  95.             if (l>1) UP(f[x][l-2],f[x-1][l-1],f[x+1][l-1]);
  96.             if (r<n) UP(f[x][r+2],f[x-1][r+1],f[x+1][r+1]);
  97.         }
  98.         for (int j=1;j<=tot;++j)
  99.             for (int k=j+1;k<=tot;++k)
  100.             {
  101.                 tmp = SZ(q[j][0]) + SZ(q[j][1]) + SZ(q[j][2]);
  102.                 if (q[j][0] != q[k][0] && q[j][1] != q[k][0] && q[j][2] != q[k][0]) tmp += SZ(q[k][0]);
  103.                 if (q[j][0] != q[k][1] && q[j][1] != q[k][1] && q[j][2] != q[k][1]) tmp += SZ(q[k][1]);
  104.                 if (q[j][0] != q[k][2] && q[j][1] != q[k][2] && q[j][2] != q[k][2]) tmp += SZ(q[k][2]);
  105.                 M(tmp);
  106.             }
  107.         if (x>1 && l>1 && !a[x-1][l-1])
  108.         {
  109.             M(SZ(f[x-1][l-2])+(SZ(f[x-2][l])|SZ(f[x-2][l-1]))+(l==r?SZ(f[x-1][l+1]):0));
  110.             M(SZ(f[x-2][l-1])+(SZ(f[x][l-2])|SZ(f[x-1][l-2]))+(x==y?SZ(f[x+1][l-1]):0));
  111.         }
  112.         if (x>1 && r<n && !a[x-1][r+1])
  113.         {
  114.             M(SZ(f[x-1][r+2])+(SZ(f[x-2][r])|SZ(f[x-2][r+1]))+(l==r?SZ(f[x-1][r-1]):0));
  115.             M(SZ(f[x-2][r+1])+(SZ(f[x][r+2])|SZ(f[x-1][r+2]))+(x==y?SZ(f[x+1][r+1]):0));
  116.         }
  117.         if (y<n && l>1 && !a[y+1][l-1])
  118.         {
  119.             M(SZ(f[y+1][l-2])+(SZ(f[y+2][l])|SZ(f[y+2][l-1]))+(l==r?SZ(f[y+1][l+1]):0));
  120.             M(SZ(f[y+2][l-1])+(SZ(f[y][l-2])|SZ(f[y+1][l-2]))+(x==y?SZ(f[y-1][l-1]):0));
  121.         }
  122.         if (y<n && r<n && !a[y+1][r+1])
  123.         {
  124.             M(SZ(f[y+1][r+2])+(SZ(f[y+2][r])|SZ(f[y+2][r+1]))+(l==r?SZ(f[y+1][r-1]):0));
  125.             M(SZ(f[y+2][r+1])+(SZ(f[y][r+2])|SZ(f[y+1][r+2]))+(x==y?SZ(f[y-1][r+1]):0));
  126.         }
  127.         ans = max(ans,w+SZ(i)+2);
  128.     }
  129.     printf("%d\n",ans);
  130.     return 0;
  131. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注