[关闭]
@Plutorabbit 2017-02-19T11:30:42.000000Z 字数 4838 阅读 1860

JLOI 2016

BZOJ OI 2016

BZOJ 4557 ~ BZOJ 4561

[JLoi2016]侦察守卫

树形DP
: 的子树中，最高覆盖到向下第层
: 的子树全部覆盖，还能向上覆盖层

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NN = 500005, INF = 0x3f3f3f3f;
  4. int n,m,D,tot=0;
  5. int w[NN],head[NN],f[NN][25],g[NN][25];
  6. bool mark[NN];
  7. struct E
  8. {
  9.     int ne,v;
  10. }e[NN<<1];
  11. void Build(int xx,int yy)
  12. {
  13.     e[++tot].ne = head[xx], head[xx] = tot, e[tot].v = yy;
  14.     e[++tot].ne = head[yy], head[yy] = tot, e[tot].v = xx;
  15. }
  16. void DP(int xx,int fa)
  17. {
  18.     if (mark[xx]) f[xx][0] = g[xx][0] = w[xx];
  19.     for (int i=1;i<=D;++i) g[xx][i] = w[xx];
  20.     g[xx][D+1] = INF;
  21.     for (int i=head[xx];i;i=e[i].ne)
  22.     if (e[i].v != fa)
  23.     {
  24.         DP(e[i].v,xx);
  25.         for (int j=D;j>=0;--j) g[xx][j] = min(g[xx][j] + f[e[i].v][j], g[e[i].v][j+1] + f[xx][j+1]);
  26.         for (int j=D;j>=0;--j) g[xx][j] = min(g[xx][j], g[xx][j+1]);
  27.         f[xx][0] = g[xx][0];
  28.         for (int j=1;j<=D+1;++j) f[xx][j] += f[e[i].v][j-1];
  29.         for (int j=1;j<=D+1;++j) f[xx][j] = min(f[xx][j-1], f[xx][j]);
  30.     }
  31. }
  32. int main()
  33. {
  34.     scanf("%d%d",&n,&D);
  35.     int x,y;
  36.     for (int i=1;i<=n;++i) scanf("%d",&w[i]);
  37.     scanf("%d",&m);
  38.     for (int i=1;i<=m;++i) scanf("%d",&x), mark[x] = 1;
  39.     for (int i=1;i<n;++i) scanf("%d%d",&x,&y), Build(x,y);
  40.     DP(1,0);
  41.     printf("%d\n",f[1][0]);
  42.     return 0;
  43. }

[JLoi2016]方

大力容斥
4个点，计算坏点分别有个，除掉重复的就可以了

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int NN = 2005;
  5. const LL mod  = 100000007;
  6. int n,m,K;
  7. LL cnt1=0,cnt2=0,cnt3=0,cnt4=0,ans;
  8. struct POI
  9. {
  10.     int x,y;
  11.     POI(int xx = 0, int yy = 0) : x(xx), y(yy) { }
  12.     bool operator < (const POI &xx) const { return x < xx.x || (x == xx.x && y < xx.y); }
  13.     bool operator == (const POI &xx) const { return x == xx.x && y == xx.y; }
  14. }p[NN];
  15. set <POI> mp;
  16. inline bool In(int xx,int yy) { return xx>=0 && xx<=n && yy>=0 && yy<=m; }
  17. inline void Cal(int xx,int yy,int zz)
  18. {
  19.     if (!xx || !yy || zz<2) return;
  20.     zz = min(zz,xx+yy);
  21.     xx = min(xx,zz-1); yy = min(yy,zz-1);
  22.     cnt1 = (cnt1 + (LL)(zz-yy)*yy) % mod;
  23.     cnt1 = (cnt1 + ((LL)(zz-xx+yy-1)*(yy-zz+xx)>>1ll)%mod) % mod;
  24. }
  25. inline void Count(int xa,int ya,int xb,int yb)
  26. {
  27.     if (In(xa,ya) && In(xb,yb))
  28.     {
  29.         int tmp = mp.count(POI(xa,ya)) + mp.count(POI(xb,yb));
  30.         ++ cnt2;
  31.         cnt3 += tmp;
  32.         if (tmp > 1) ++ cnt4;
  33.     }
  34. }
  35. inline void Solve(int xa,int ya,int xb,int yb)
  36. {
  37.     int dx = xb - xa, dy = yb - ya;
  38.     Count(xa+dy,ya-dx,xb+dy,yb-dx); Count(xa-dy,ya+dx,xb-dy,yb+dx);
  39.     if (abs(dx+dy) & 1) return;
  40.     dy = (dx+dy) >> 1, dx -= dy;
  41.     Count(xa+dx,ya+dy,xb-dx,yb-dy);
  42. }
  43. int main()
  44. {
  45.     scanf("%d%d%d",&n,&m,&K);
  46.     for (int i=1;i<=min(n,m);++i) ans = (ans + (LL) i*(n-i+1) % mod *(m-i+1)) % mod;
  47.     for (int i=1;i<=K;++i)
  48.     {
  49.         scanf("%d%d",&p[i].x,&p[i].y); mp.insert(p[i]);
  50.     }
  51.     for (int i=1;i<=K;++i)
  52.     {
  53.         Cal(p[i].x,n-p[i].x,p[i].y); Cal(p[i].x,n-p[i].x,m-p[i].y);
  54.         Cal(p[i].y,m-p[i].y,p[i].x); Cal(p[i].y,m-p[i].y,n-p[i].x);
  55.         cnt1 = (cnt1 + min(p[i].x,p[i].y) + min(p[i].x,m-p[i].y) + min(n-p[i].x,p[i].y) + min(n-p[i].x,m-p[i].y)) %mod;
  56.         for (int j=1;j<i;++j) Solve(p[i].x,p[i].y,p[j].x,p[j].y);
  57.     }
  58.     ans = (ans - cnt1 + cnt2 - cnt3/3 + cnt4/6 + mod) % mod;
  59.     printf("%lld\n",ans);
  60.     return 0;
  61. }

[JLoi2016]成绩比较

为什么连着两道数学相关啊QAQ
公式说不清楚怎么破啊QAQ
看代码？

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int NN = 105;
  5. const LL mod = 1000000007;
  6. int n,m,k;
  7. LL ans,s[NN],rk[NN],fac[NN],inv[NN],f[NN],g[NN];
  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. inline LL C(int x,int y) { return fac[x] * inv[y] %mod * inv[x-y] %mod; }
  15. int main()
  16. {
  17.     scanf("%d%d%d",&n,&m,&k);
  18.     for (int i=1;i<=m;++i) scanf("%lld",&s[i]);
  19.     for (int i=1;i<=m;++i) scanf("%lld",&rk[i]);
  20.     fac[0] = inv[0] = 1;
  21.     for (int i=1;i<=100;++i) fac[i] = fac[i-1] * i % mod, inv[i] = KSM(fac[i],mod-2);
  22.     for (int i=n-1;i>=k;--i)
  23.     {
  24.         f[i] = C(n-1,i);
  25.         for (int j=1;j<=m;++j) f[i] = f[i] * C(n-1-i,rk[j]-1) % mod;
  26.         for (int j=i+1;j<n;++j) f[i] = (f[i] - f[j] * C(j,i) % mod + mod) % mod;
  27.     }
  28.     ans = 1;
  29.     for (int i=1;i<=m;++i)
  30.     {
  31.         g[0] = s[i];
  32.         for (int j=1;j<=n;++j)
  33.         {
  34.             g[j] = (KSM(s[i]+1,j+1)-1+mod) % mod;
  35.             for (int l=0;l<j;++l) g[j] = (g[j]-C(j+1,l)*g[l] %mod + mod) %mod;
  36.             g[j] = g[j] * KSM(j+1,mod-2) % mod;
  37.         }
  38.         LL tmp = 0, p = 1;
  39.         for (int j=0;j<=rk[i]-1;++j)
  40.             tmp = (tmp + C(rk[i]-1,j) * KSM(s[i], rk[i]-1-j) %mod *g[n-rk[i]+j] %mod *p +mod) % mod, p = -p;
  41.         ans = ans * tmp % mod;
  42.     }
  43.     printf("%lld\n",ans*f[k]%mod);
  44.     return 0;
  45. }

[JLoi2016]字符串覆盖

感觉做法很迷QAQ
并没有做QAQ

[JLoi2016]圆的异或并

两圆的关系只存在相离和包含
所以就可以像扫描线那样排序后从左到右扫QAQ

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int NN = 200005;
  5. int n,tot;
  6. LL ans,pos,f[NN];
  7. struct Cir
  8. {
  9.     LL x,y,r;
  10. }c[NN];
  11. struct POI
  12. {
  13.     int num,x,op;
  14. }b[NN<<1];
  15. set <POI> se;
  16. inline bool cmp(POI xx,POI yy) { return xx.x < yy.x; }
  17. inline LL sqr(LL xx) { return xx*xx; }
  18. inline bool operator < (POI xx,POI yy)
  19. {
  20.     double dx = c[xx.num].y + xx.op * sqrt(sqr(c[xx.num].r)-sqr(pos-c[xx.num].x));
  21.     double dy = c[yy.num].y + yy.op * sqrt(sqr(c[yy.num].r)-sqr(pos-c[yy.num].x));
  22.     return (dx != dy) ? dx<dy : xx.op < yy.op;
  23. }
  24. int main()
  25. {
  26.     scanf("%d",&n);
  27.     for (int i=1;i<=n;++i)
  28.     {
  29.         scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].r);
  30.         b[2*i-1] = (POI){i,(int)(c[i].x-c[i].r),1};
  31.         b[2*i] = (POI){i,(int)(c[i].x+c[i].r),-1};
  32.     }
  33.     sort(b+1,b+1+2*n,cmp);
  34.     set <POI> :: iterator it;
  35.     for (int i=1;i<=(n<<1);++i)
  36.     {
  37.         pos = b[i].x;
  38.         if (b[i].op == 1)
  39.         {
  40.             it = se.upper_bound((POI){b[i].num,0,-1});
  41.             if (it == se.end()) f[b[i].num] = 1;
  42.             else
  43.             {
  44.                 if ((*it).op == 1) f[b[i].num] = -f[(*it).num];
  45.                 else f[b[i].num] = f[(*it).num];
  46.             }
  47.             se.insert((POI){b[i].num,0,-1});
  48.             se.insert((POI){b[i].num,0,1});
  49.         }
  50.         else
  51.         {
  52.             se.erase((POI){b[i].num,0,-1});
  53.             se.erase((POI){b[i].num,0,1});
  54.         }
  55.     }
  56.     ans = 0ll;
  57.     for (int i=1;i<=n;++i) ans += sqr(c[i].r) * f[i];
  58.     printf("%lld\n",ans);
  59.     return 0;
  60. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注