[关闭]
@y20070316 2017-02-17T00:59:36.000000Z 字数 7813 阅读 1043

GDKOI2017模拟赛三

OI 校内赛

【xsy1084】Evaluation - 莫比乌斯变换 or 快速沃尔什变换

题意

给定，。
求，其中

分析1：莫比乌斯变换

假如存在某个变换，使得。我们快速的进行变换和逆变换，则可以快速求解答案。

这里介绍莫比乌斯变换：


则有：

考虑如何进行变换和逆变换。

变换：给定，求
考虑dp，设表示对于集合，前位可以任意改动的所有子集的和。
奠基：


转移：


答案：

我们还可以考虑降维，写成一段很精简的代码。

  1. void Trans(int *f,int n) {
  2.     for (int i=1;i<(1<<n);i<<=1)
  3.         for (int j=0;j<(1<<n);j++)
  4.             if (j&i)
  5.                 f[j]+=f[j^i];
  6. }

逆变换：给定，求。
怎么变换过去的，就怎么变换回来。
直接和上面的代码相反就好了。

代码1：莫比乌斯变换

  1. #include <cstdio>
  2. #include <cctype>
  4. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  6. #define LL unsigned int
  8. LL rd(void);
  10. const int N=1048576;
  12. int n,nk;
  13. LL f[N];
  14. LL g[N];
  15. LL h[N];
  16. LL ans;
  18. int main(void) {
  19.     #ifndef ONLINE_JUDGE
  20.         freopen("a.in","r",stdin);
  21.         freopen("a.out","w",stdout);
  22.     #endif
  24.     n=rd();
  25.     nk=(1<<n);
  26.     F(i,0,nk-1)
  27.         f[i]=rd();
  28.     F(i,0,nk-1)
  29.         g[i]=rd();
  31.     for (int j=1;j<nk;j<<=1)
  32.         F(i,0,nk-1) if (i&j) {
  33.             f[i]+=f[i^j];
  34.             g[i]+=g[i^j];
  35.         }
  37.     F(i,0,nk-1)
  38.         h[i]=f[i]*g[i];
  39.     for (int j=1;j<nk;j<<=1)
  40.         F(i,0,nk-1) if (i&j)
  41.             h[i]-=h[i^j];
  42.     F(i,0,nk-1)
  43.         ans+=h[i]*(i+1);
  44.     printf("%u\n",ans);
  46.     return 0;
  47. }
  49. LL rd(void) {
  50.     LL x=0,f=1; char c=getchar();
  51.     while (!isdigit(c)) {
  52.         if (c=='-') f=-1;
  53.         c=getchar();
  54.     }
  55.     while (isdigit(c)) {
  56.         x=x*10+c-'0';
  57.         c=getchar();
  58.     }
  59.     return x*f;
  60. }

代码2：快速沃尔什变换

  1. #include <cstdio>
  2. #include <cctype>
  4. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  6. #define LL unsigned int
  8. LL rd(void);
  10. const int N=32;
  11. const int S=1048576;
  13. int n,nk;
  14. LL f[S];
  15. LL g[S];
  16. LL h[S];
  17. LL ans;
  19. void FWT(LL *a,int nk) {
  20.     for (int i=2;i<=nk;i<<=1)
  21.         for (int j=0;j<nk;j+=i)
  22.             F(k,0,i/2-1) {
  23.                 LL x=a[j+k];
  24.                 LL y=a[j+k+i/2];
  25.                 a[j+k]=x;
  26.                 a[j+k+i/2]=x+y;
  27.             }
  28. }
  30. void DWT(LL *a,int nk) {
  31.     for (int i=2;i<=nk;i<<=1)
  32.         for (int j=0;j<nk;j+=i)
  33.             F(k,0,i/2-1) {
  34.                 LL x=a[j+k];
  35.                 LL y=a[j+k+i/2];
  36.                 a[j+k]=x;
  37.                 a[j+k+i/2]=y-x;
  38.             }
  39. }
  41. int main(void) {
  42.     #ifndef ONLINE_JUDGE
  43.         freopen("A.in","r",stdin);
  44.         freopen("A.out","w",stdout);
  45.     #endif
  47.     n=rd();
  48.     nk=(1<<n);
  49.     F(i,0,nk-1)
  50.         f[i]=rd();
  51.     F(i,0,nk-1)
  52.         g[i]=rd();
  54.     FWT(f,nk);
  55.     FWT(g,nk);
  56.     F(i,0,nk-1)
  57.         h[i]=f[i]*g[i];
  58.     DWT(h,nk);
  59.     F(i,0,nk-1)
  60.         ans+=h[i]*(i+1);
  61.     printf("%u\n",ans);
  63.     return 0;
  64. }
  66. LL rd(void) {
  67.     LL x=0,f=1; char c=getchar();
  68.     while (!isdigit(c)) {
  69.         if (c=='-') f=-1;
  70.         c=getchar();
  71.     }
  72.     while (isdigit(c)) {
  73.         x=x*10+c-'0';
  74.         c=getchar();
  75.     }
  76.     return x*f;
  77. }

【xsy1085】Data - 凸包

分析

注意到，最终答案的情形必然是这样的：我们过两个点作一条直线，一个人巡查直线左边的所有点，一个人巡查右边的所有点，对应左边有面积，右边有面积，求凸包，通过分割成三角形的方法计算多边形面积。

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <algorithm>
  5. using namespace std;
  7. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  8. #define D(i,a,b) for (int i=(a);i>=(b);i--)
  10. #define LD long double
  12. int rd(void);
  14. const int N=64;
  15. const LD MAX=1e30;
  17. int n;
  18. struct point {
  19.     LD x,y;
  20.     point(LD _x=0,LD _y=0) {
  21.         x=_x,y=_y;
  22.     }
  23.     friend point operator - (point a,point b) {
  24.         return point(a.x-b.x,a.y-b.y);
  25.     }
  26.     friend LD operator * (point a,point b) {
  27.         return a.x*b.x+a.y*b.y;
  28.     }
  29.     friend LD operator ^ (point a,point b) {
  30.         return a.x*b.y-a.y*b.x;
  31.     }
  32.     friend int operator < (point a,point b) {
  33.         if (a.x!=b.x)
  34.             return a.x<b.x;
  35.         else return a.y<b.y;
  36.     }
  37.     void Read(void) {
  38.         x=(LD)rd();
  39.         y=(LD)rd();
  40.     }
  41. }p[N];
  43. point stk[N]; int top;
  44. point q1[N]; int len1;
  45. point q2[N]; int len2;
  47. point c[N]; int tc;
  49. LD ans;
  51. void Polygon(point *p,int n) {
  52.     //n>=1
  54.     sort(p+1,p+n+1);
  56.     while (len1>0)
  57.         q1[len1--]=point();
  58.     F(i,1,n) {
  59.         while (len1>=2) {
  60.             if (((q1[len1]-q1[len1-1])^(p[i]-q1[len1-1]))<=0)
  61.                 q1[len1--]=point();
  62.             else break;
  63.         }
  64.         q1[++len1]=p[i];
  65.     }
  67.     while (len2>0)
  68.         q2[len2--]=point();
  69.     D(i,n,1) {
  70.         while (len2>=2) {
  71.             if (((q2[len2]-q2[len2-1])^(p[i]-q2[len2-1]))<=0)
  72.                 q2[len2--]=point();
  73.             else break;
  74.         }
  75.         q2[++len2]=p[i];
  76.     }
  78.     while (top>0)
  79.         stk[top--]=point();
  80.     F(i,1,len1)
  81.         stk[++top]=q1[i];
  82.     F(i,2,len2-1)
  83.         stk[++top]=q2[i];
  84. }
  86. LD dis(point a,point b) {
  87.     return sqrt((a-b)*(a-b));
  88. }
  90. LD get(point a,point b,point c) {
  91.     LD x=dis(a,b);
  92.     LD y=dis(b,c);
  93.     LD z=dis(c,a);
  94.     LD p=(x+y+z)/2;
  95.     return sqrt(p*(p-x)*(p-y)*(p-z));
  96. }
  98. LD Calc(void) {
  99.     if (top<=2)
  100.         return 0;
  101.     LD sum=0;
  102.     F(i,2,top-1) {
  103.         LD t=get(stk[1],stk[i],stk[i+1]);
  104.         sum+=t;
  105.     }
  106.     return sum;
  107. }
  109. void Split(point s,point t,int kd) {
  110.     /*
  111.         kd=0：左边，包括两点及线上的点 
  112.         kd=1：右边 
  113.     */
  114.     while (tc>0)
  115.         c[tc--]=point();
  116.     F(i,1,n)
  117.         if (kd==(((t-s)^(p[i]-s))<0))
  118.             c[++tc]=p[i];
  119. }
  121. int main(void) {
  122.     #ifndef ONLINE_JUDGE
  123.         freopen("B.in","r",stdin);
  124.         freopen("B.out","w",stdout);
  125.     #endif
  127.     n=rd();
  128.     F(i,1,n)
  129.         p[i].Read();
  131.     ans=MAX;
  132.     F(i,1,n)
  133.         F(j,1,n) {
  134.             Split(p[i],p[j],0);
  135.             Polygon(c,tc);
  136.             LD t=Calc();
  138.             Split(p[i],p[j],1);
  139.             Polygon(c,tc);
  140.             t=max(t,Calc());
  142.             ans=min(ans,t);
  143.         }
  144.     printf("%0.6Lf\n",ans);
  146.     return 0;
  147. }
  149. int rd(void) {
  150.     int x=0,f=1; char c=getchar();
  151.     while (!isdigit(c)) {
  152.         if (c=='-') f=-1;
  153.         c=getchar();
  154.     }
  155.     while (isdigit(c)) {
  156.         x=x*10+c-'0';
  157.         c=getchar();
  158.     }
  159.     return x*f;
  160. }

【xsy1086】Version - 树链剖分+可持久化线段树维护等差数列

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  7. #define F(i,a,b) for (int i=(a);i<=(b);i++)
  8. #define fore(v,x) for (vector<int>::iterator v=g[x].begin();v!=g[x].end();v++)
  10. #define LL long long
  12. int rd(void);
  13. char rdc(void);
  15. int trans(int u,LL ans,int n);
  16. int trans_w(int u,LL ans,int tot);
  18. const int N=131072;
  19. const int M=20000000;
  21. int n,m;
  22. vector<int> g[N];
  24. int pre[N],siz[N],son[N],dep[N];
  25. int dfn[N],ind,top[N];
  27. int tot;
  28. int rt[N],tms,now_rt;
  29. struct Tree {
  30.     int lc,rc;
  31.     int cnt;
  32.     LL add,del;
  33.     //cnt表示区间公差，第一项为0 
  34.     LL sum;
  35. }tr[M];
  37. void Find(int x) {
  38.     siz[x]=1;
  39.     fore(v,x)
  40.         if (pre[x]!=*v) {
  41.             pre[*v]=x;
  42.             dep[*v]=dep[x]+1;
  43.             Find(*v);
  44.             siz[x]+=siz[*v];
  45.             if (siz[son[x]]<siz[*v])
  46.                 son[x]=*v;
  47.         }
  48. }
  50. void Split(int x,int anc) {
  51.     dfn[x]=++ind;
  52.     top[x]=anc;
  53.     if (son[x]>0)
  54.         Split(son[x],anc);
  55.     fore(v,x)
  56.         if (*v!=pre[x]&&*v!=son[x])
  57.             Split(*v,*v);
  58. }
  60. int LCA(int x,int y) {
  61.     while (top[x]!=top[y]) {
  62.         if (dep[top[x]]<dep[top[y]])
  63.             swap(x,y);
  64.         x=pre[top[x]];
  65.     }
  66.     return dep[x]<dep[y]?x:y;
  67. }
  69. void Update(int x) {
  70.     int lc=tr[x].lc,rc=tr[x].rc;
  72.     tr[x].cnt=tr[lc].cnt+tr[rc].cnt;
  74.     tr[x].sum=tr[lc].sum+tr[rc].sum;
  75.     tr[x].sum+=tr[x].add*tr[x].cnt;
  76.     tr[x].sum+=tr[x].del*(tr[x].cnt-1)*tr[x].cnt>>1;
  77. }
  79. int Build(int l,int r) {
  80.     int x=++tot;
  81.     tr[x].cnt=r-l+1;
  82.     if (l!=r) {
  83.         int mid=(l+r)>>1;
  84.         tr[x].lc=Build(l,mid);
  85.         tr[x].rc=Build(mid+1,r);
  86.     }
  87.     return x;
  88. }
  90. int Copynode(int frm) {
  91.     int x=++tot;
  92.     tr[x]=tr[frm];
  93.     return x;
  94. }
  96. int Change(int frm,int l,int r,int ql,int qr,LL a,LL b) {
  97.     if (ql>r||qr<l)
  98.         return frm;
  99.     int x=Copynode(frm);
  100.     if (ql<=l&&r<=qr) {
  101.         tr[x].add+=a+b*(l-ql);
  102.         tr[x].del+=b;
  103.         tr[x].sum+=(a+b*(l-ql))*tr[x].cnt;
  104.         tr[x].sum+=b*(tr[x].cnt-1)*tr[x].cnt>>1;
  105.         return x;
  106.     }
  107.     int mid=(l+r)>>1;
  108.     tr[x].lc=Change(tr[frm].lc,l,mid,ql,qr,a,b);
  109.     tr[x].rc=Change(tr[frm].rc,mid+1,r,ql,qr,a,b);
  110.     Update(x);
  111.     return x;
  112. }
  114. LL Query(int x,int l,int r,int ql,int qr) {
  115.     if (ql>r||qr<l)
  116.         return 0;
  117.     if (ql<=l&&r<=qr)
  118.         return tr[x].sum;
  119.     int mid=(l+r)>>1;
  120.     int aL=max(l,ql);
  121.     int aR=min(r,qr);
  122.     int cnt=aR-aL+1;
  123.     LL ans=tr[x].add*cnt+(tr[x].del*(aL-l+aR-l)*cnt>>1);
  124.     ans+=Query(tr[x].lc,l,mid,ql,qr);
  125.     ans+=Query(tr[x].rc,mid+1,r,ql,qr);
  126.     return ans;
  127. }
  129. void Change_Path(int u,int v,int a,int b) {
  130.     int anc=LCA(u,v);
  131.     int tu=u,tv=v;
  132.     while (top[u]!=top[anc]) {
  133.         int dis=dep[tu]-dep[top[u]];
  134.         now_rt=Change(now_rt,1,n,dfn[top[u]],dfn[u],a+b*dis,-b);
  135.         u=pre[top[u]];
  136.     }
  137.     while (top[v]!=top[anc]) {
  138.         int dis=dep[tu]+dep[top[v]]-dep[anc]-dep[anc];
  139.         now_rt=Change(now_rt,1,n,dfn[top[v]],dfn[v],a+b*dis,b);
  140.         v=pre[top[v]];
  141.     }
  142.     if (u==anc) {
  143.         int dis=dep[tu]-dep[anc];
  144.         now_rt=Change(now_rt,1,n,dfn[u],dfn[v],a+b*dis,b);
  145.     }
  146.     else {
  147.         int dis=dep[tu]-dep[anc];
  148.         now_rt=Change(now_rt,1,n,dfn[v],dfn[u],a+b*dis,-b);
  149.     }
  150.     rt[++tms]=now_rt;
  151. }
  153. LL Query_Path(int u,int v) {
  154.     int anc=LCA(u,v);
  155.     LL sum=0;
  156.     while (top[u]!=top[anc]) {
  157.         sum+=Query(now_rt,1,n,dfn[top[u]],dfn[u]);
  158.         u=pre[top[u]];
  159.     }
  160.     while (top[v]!=top[anc]) {
  161.         sum+=Query(now_rt,1,n,dfn[top[v]],dfn[v]);
  162.         v=pre[top[v]];
  163.     }
  164.     if (u==anc)
  165.         sum+=Query(now_rt,1,n,dfn[u],dfn[v]);
  166.     else sum+=Query(now_rt,1,n,dfn[v],dfn[u]);
  167.     return sum;
  168. }
  170. void Roll(int w) {
  171.     now_rt=rt[w];
  172. }
  174. int main(void) {
  175.     #ifndef ONLINE_JUDGE
  176.         freopen("a.in","r",stdin);
  177.         freopen("a.out","w",stdout);
  178.     #endif
  180.     n=rd(),m=rd();
  181.     F(i,1,n-1) {
  182.         int u=rd(),v=rd();
  183.         g[u].push_back(v);
  184.         g[v].push_back(u);
  185.     }
  187.     Find(1);
  188.     Split(1,1);
  190.     now_rt=rt[0]=Build(1,n);
  191.     LL ans=0;
  192.     F(i,1,m) {
  193.         char c=rdc();
  194.         if (c=='c') {
  195.             int u=rd(),v=rd(),a=rd(),b=rd();
  196.             u=trans(u,ans,n);
  197.             v=trans(v,ans,n);
  198.             Change_Path(u,v,a,b);
  199.         }
  200.         else if (c=='q') {
  201.             int u=rd(),v=rd();
  202.             u=trans(u,ans,n);
  203.             v=trans(v,ans,n);
  204.             ans=Query_Path(u,v);
  205.             printf("%lld\n",ans);
  206.         }
  207.         else if (c=='r') {
  208.             int w=rd();
  209.             w=trans_w(w,ans,tms);
  210.             Roll(w);
  211.         }
  212.     }
  214.     return 0;
  215. }
  217. int rd(void) {
  218.     int x=0,f=1; char c=getchar();
  219.     while (!isdigit(c)) {
  220.         if (c=='-') f=-1;
  221.         c=getchar();
  222.     }
  223.     while (isdigit(c)) {
  224.         x=x*10+c-'0';
  225.         c=getchar();
  226.     }
  227.     return x*f;
  228. }
  230. char rdc(void) {
  231.     char c=getchar();
  232.     while (!isalpha(c))
  233.         c=getchar();
  234.     return c;
  235. }
  237. int trans(int u,LL ans,int n) {
  238.     return (u+ans)%n+1;
  239. }
  241. int trans_w(int w,LL ans,int tot) {
  242.     return (w+ans)%(tot+1);
  243. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注