[关闭]
@Plutorabbit 2017-02-19T10:48:39.000000Z 字数 5217 阅读 1860

CQOI 2016

BZOJ 2016 OI

BZOJ 4519~BZOJ 4524

[Cqoi2016]不同的最小割

[Cqoi2016]K远点对

KD-tree裸题
当时学校做练习的时候并不会这个东西QAQ

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. const int NN = 100005;
  5. int n,k,rt,q0,q1,cmp_d;
  6. struct TR
  7. {
  8.     int d[2],mn[2],mx[2],lc,rc;
  9. }tr[NN];
  10. priority_queue<LL,vector<LL>,greater<LL> >que;
  11. bool cmp(TR xx,TR yy) { return xx.d[cmp_d] < yy.d[cmp_d]; }
  12. LL sqr(LL xx) { return xx*xx; }
  13. void push_up(int k)
  14. {
  15.     int l = tr[k].lc, r = tr[k].rc;
  16.     for (int i=0;i<2;++i)
  17.     {
  18.         if (l) tr[k].mx[i] = max(tr[k].mx[i],tr[l].mx[i]), tr[k].mn[i] = min(tr[k].mn[i],tr[l].mn[i]);
  19.         if (r) tr[k].mx[i] = max(tr[k].mx[i],tr[r].mx[i]), tr[k].mn[i] = min(tr[k].mn[i],tr[r].mn[i]);
  20.     }
  21. }
  22. void Build(int &k,int l,int r,int D)
  23. {
  24.     int mid = (l+r)>>1; k=mid, cmp_d=D;
  25.     nth_element(tr+l,tr+mid,tr+r+1,cmp);
  26.     for (int i=0;i<2;++i) tr[k].mx[i] = tr[k].mn[i] = tr[k].d[i];
  27.     if (l<mid) Build(tr[k].lc,l,mid-1,D^1);
  28.     if (r>mid) Build(tr[k].rc,mid+1,r,D^1);
  29.     push_up(k);
  30. }
  31. LL Ask(int k)
  32. {
  33.     if (!k) return 0;
  34.     return max(sqr(tr[k].mn[0]-q0),sqr(tr[k].mx[0]-q0)) + max(sqr(tr[k].mn[1]-q1),sqr(tr[k].mx[1]-q1));
  35. }
  36. void Query(int k)
  37. {
  38.     LL dis = sqr(tr[k].d[0]-q0) + sqr(tr[k].d[1]-q1);
  39.     if (dis>que.top()) que.pop(), que.push(dis);
  40.     LL Dl = Ask(tr[k].lc), Dr = Ask(tr[k].rc);
  41.     if (Dl > Dr)
  42.     {
  43.         if (Dl > que.top()) Query(tr[k].lc);
  44.         if (Dr > que.top()) Query(tr[k].rc);
  45.     }
  46.     else
  47.     {
  48.         if (Dr > que.top()) Query(tr[k].rc);
  49.         if (Dl > que.top()) Query(tr[k].lc);
  50.     }
  51. }
  52. int main()
  53. {
  54.     scanf("%d%d",&n,&k);
  55.     for (int i=1;i<=n;++i) scanf("%d%d",&tr[i].d[0],&tr[i].d[1]);
  56.     Build(rt,1,n,0);
  57.     for (int i=1;i<=(k<<1);++i) que.push(0);
  58.     for (int i=1;i<=n;++i) q0 = tr[i].d[0], q1 = tr[i].d[1], Query(rt);
  59.     printf("%lld\n",que.top());
  60.     return 0;
  61. }

[Cqoi2016]手机号码

数位DP
表示 len 当前数值 重复 4/8 ==a[len]
语文越来越差了却还要考学考

  1. #include <iostream> 
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #define LL long long
  8. using namespace std;
  9. LL l,r,ans,f[15][11][5][5][3];
  10. int a[20],tmp[20];
  11. int Xun(int xx,int yy)
  12. {
  13.     if (xx+yy>=3) return 3;
  14.     else if (xx) return yy+1;
  15.     else return 1;
  16. }
  17. int P(int xx,int yy)
  18. {
  19.     if (xx==4) return yy|1;
  20.     else if (xx==8) return yy|2;
  21.     else return yy;
  22. }
  23. LL solve(LL xx)
  24. {
  25.     int len=0;
  26.     memset(a,0,sizeof(a)); memset(tmp,0,sizeof(tmp));
  27.     memset(f,0,sizeof(f));
  28.     while (xx) { tmp[++len]=xx%10; xx=xx/10;}
  29.     for (int i=1;i<=len;++i) a[i]=tmp[len-i+1];
  30.     for (int i=1;i<=a[1];++i) f[1][i][1][P(i,0)][i==a[1]]++;
  31.     for (int i=2;i<=len;++i)
  32.     {
  33.         for (int j=0;j<=9;++j)
  34.             for (int k=1;k<=3;++k)
  35.                 for (int w=0;w<3;++w)
  36.                 {
  37.                     if (f[i-1][j][k][w][0])
  38.                         for (int t=0;t<=9;++t)
  39.                             f[i][t][Xun(t==j,k)][P(t,w)][0]+=f[i-1][j][k][w][0];
  40.                     if (f[i-1][j][k][w][1])
  41.                         for (int t=0;t<=a[i];++t)
  42.                             f[i][t][Xun(t==j,k)][P(t,w)][t==a[i]]+=f[i-1][j][k][w][1];
  43.                 }
  44.     }
  45.     ans=0;
  46.     for (int i=0;i<=9;++i)
  47.         for (int j=0;j<3;++j) ans+=f[len][i][3][j][0]+f[len][i][3][j][1];
  48.     return ans;
  49. }
  50. int main()
  51. {
  52.     scanf("%lld%lld",&l,&r);
  53.     if (l==10000000000ll) printf("%lld",solve(r));
  54.         else printf("%lld",solve(r)-solve(l-1));
  55.     return 0;
  56. }

[Cqoi2016]密钥破解

数论模板大综合
要是考场上考泼辣的肉肯定自爆

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. #define T 10007
  5. LL e,n,c,p,q,r,inv;
  6. LL Mul(LL xx,LL yy,LL mod)
  7. {
  8.     LL sum = 0ll;
  9.     for (xx%=mod;yy;xx = (xx+xx) % mod, yy >>= 1) if (yy & 1) sum = (sum + xx) % mod;
  10.     return sum;
  11. }
  12. LL KSM(LL xx,LL yy,LL mod)
  13. {
  14.     LL sum=1ll;
  15.     for (xx%=mod;yy;xx = Mul(xx,xx,mod)%mod,yy >>= 1) if (yy&1) sum = Mul(sum,xx,mod)%mod;
  16.     return sum;
  17. }
  18. void exGCD(LL a,LL b,LL &x,LL &y)
  19. {
  20.     if (b == 0) { x = 1, y = 0; return; }
  21.     exGCD(b,a%b,y,x), y -= a/b*x;
  22. }
  23. LL Get_inv(LL n,LL mod)
  24. {
  25.     LL x,y;
  26.     exGCD(n,mod,x,y);
  27.     return (x%mod + mod) % mod;
  28. }
  29. LL GCD(LL a,LL b)
  30. {
  31.     while (a) a ^= b ^= a ^= b %= a;
  32.     return b;
  33. }
  34. LL Pollard_Rho(LL n)
  35. {
  36.     LL x = rand() % (n-1) + 1,y = x,cnt = 1, k = 2;
  37.     while (1)
  38.     {
  39.         ++cnt;
  40.         x = (Mul(x,x,n) + T) % n;
  41.         LL gcd = GCD(abs(x-y),n);
  42.         if (gcd > 1 && gcd < n) return gcd;
  43.         if (x == y) return n;
  44.         if (cnt == k) y = x, k <<= 1;
  45.     }
  46. }
  47. int main()
  48. {
  49.     srand(T);
  50.     scanf("%lld%lld%lld",&e,&n,&c);
  51.     p = Pollard_Rho(n), q = n / p;
  52.     r = (p - 1) * (q - 1);
  53.     inv = Get_inv(e,r);
  54.     printf("%lld %lld\n",inv,KSM(c,inv,n));
  55.     return 0;
  56. }

[Cqoi2016]路由表

感觉现在看到各种01的题目都想着暴力上trie什么的QAQ
反正这题就是暴力上trie
用一个单调栈，使得能够匹配的表项出现的时间随着长度的增加而增加

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NN = 10005,MM = 31000005;
  4. int X[5],rt,tot,ch[MM][2],v[MM],cnt,top,stk[NN],n,l,r;
  5. char op[11];
  6. void Insert(int l,int t)
  7. {
  8.     int now = rt;
  9.     for (int i=1;i<=4;++i)
  10.         for (int j=7;~j;--j)
  11.         {
  12.             if (!l)
  13.             {
  14.                 v[now] = t;
  15.                 return;
  16.             }
  17.             --l;
  18.             if (!ch[now][(X[i]>>j)&1]) ch[now][(X[i]>>j)&1] = ++tot;
  19.             now = ch[now][(X[i]>>j)&1];
  20.         }
  21.     v[now] = t;
  22. }
  23. int Query(int l,int r)
  24. {
  25.     int now = rt;
  26.     top = 0;
  27.     for (int i=1;i<=4;++i)
  28.         for (int j=7;~j;--j)
  29.         {
  30.             now = ch[now][(X[i]>>j)&1];
  31.             if (!now)
  32.             {
  33.                 int res = top;
  34.                 for (int k=1;k<=top;++k) if (stk[k] < l) res --;
  35.                 return res;
  36.             }
  37.             if (v[now] <= r && v[now])
  38.             {
  39.                 for (;top&&stk[top] > v[now];--top);
  40.                 stk[++top] = v[now];
  41.             }
  42.         }
  43.     int res = top;
  44.     for (int k=1;k<=top;++k) if (stk[k] < l) -- res;
  45.     return res;
  46. }
  47. int main()
  48. {
  49.     scanf("%d",&n);
  50.     rt = tot = 1;
  51.     while (n--)
  52.     {
  53.         scanf("%s",op);
  54.         if (op[0] == 'A')
  55.         {
  56.             scanf("%d.%d.%d.%d/%d",&X[1],&X[2],&X[3],&X[4],&l);
  57.             Insert(l,++cnt);
  58.         }
  59.         else
  60.         {
  61.             scanf("%d.%d.%d.%d%d%d",&X[1],&X[2],&X[3],&X[4],&l,&r);
  62.             printf("%d\n",Query(l,r));
  63.         }
  64.     }
  65.     return 0;
  66. }

[Cqoi2016]伪光滑数

泥怎么还用STL啊
按顺序乱搞用堆维护就可以了QAQ

  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. typedef long long LL;
  7. struct REC
  8. {
  9.     LL v;
  10.     int t,pre,p;
  11. }tmp;
  12. bool operator <(REC xx,REC yy) { return xx.v < yy.v; }
  13. priority_queue <REC> que;
  14. LL n;
  15. int k,pri[55],f[205],tot=0;
  16. int main()
  17. {
  18.     scanf("%lld%d",&n,&k);
  19.     for (int i=2;i<=128;++i)
  20.         if (!f[i])
  21.         {
  22.             pri[++tot] = i;
  23.             for (int j=i+i;j<=128;j+=i) f[j] = 1;
  24.         }
  25.     while (!que.empty()) que.pop();
  26.     for (int i=1;i<=tot;++i)
  27.         for (LL t=1,j=1;(LL)(t*pri[i]) <= n;++j)
  28.             t *= (LL)pri[i], tmp.v = t, tmp.t = (int)j, tmp.pre = i-1, tmp.p = i, que.push(tmp);
  29.     while (k--)
  30.     {
  31.         tmp = que.top(), que.pop();
  32.         if (tmp.t > 1)
  33.         {
  34.             for (int i=tmp.pre;i;--i)
  35.                 que.push((REC){(LL)tmp.v/pri[tmp.p]*pri[i],tmp.t-1,i,tmp.p});
  36.         }
  37.     }
  38.     printf("%lld\n",tmp.v);
  39.     return 0;
  40. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注