PKUSC订正

Day1 T2：最大前缀和

枚举答案集合（不直接枚举答案数，相当于状态的离散化），这个集合成为答案当且仅当存在方案使得答案集合的排列后缀和>=0（如果<0就可以去掉显然更优），答案补集的前缀和<0（不能再延伸）。预处理方案数。最后统计的时候注意要枚举答案子集的第一个元素，它不需要满足后缀和>=0。O(2^n*n)。

 #include<bits/stdc++.h>

 using namespace std;

 const int mod=;

 typedef long long ll;

 const int N=;

 int n,Max,a[N],sum[N],f[N],g[N],ans;

 void up(int &x,int y){x=((ll)x+y)%mod;}

 int main()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     Max=<<n;

     for (int i=;i<Max;i++)

       for (int j=;j<=n;j++)

         if (i&(<<(j-))) up(sum[i],a[j]);

     f[]=;

     for (int i=;i<Max;i++)//后缀和>=0

       if (sum[i]>=)

       {

         for (int j=;j<=n;j++)

           if (i&(<<(j-))) up(f[i],f[i^(<<(j-))]);

       }

     g[]=;

     for (int i=;i<Max;i++)//前缀和<0

       if (sum[i]<)

       {

           for (int j=;j<=n;j++)

             if (i&(<<(j-))) up(g[i],g[i^(<<(j-))]);

       }

     for (int i=;i<Max;i++)

       for (int j=;j<=n;j++)

           if (i&(<<(j-)))

             up(ans,(ll)f[i^(<<(j-))]*g[i^(Max-)]%mod*sum[i]%mod);

     printf("%d\n",((ll)ans+mod)%mod);//注意ans有可能是负数！

     return ;

 }

Day2

T1：星际穿越贪心+树上倍增

要想到肯定贪心走能走的较远点。单调肯定不会让你好好求最短路，建树是一个思路。

性质：当起点在终点右边时，起点要走到终点，必然只会往右走一步，接下来一直往左走。

每个点朝能够到达的点中覆盖区间左端点最左的点连边，如果它想要走最远，选择这一点一定最优。

往右走一步也是类似的道理，一定是往右走能够走到的点中覆盖区间左端点最左的点最优。（具体实现可以按照覆盖区间左端点排序）如果往右再往左两步没有直接往左两步优的话，一定不会往右走。

如果一步可以走到也一定不会往右。（询问的时候特判一下即可）

询问的时候对于[1..r]求走到x的距离和。倍增使得x在[1..r]外且l[x]在[1..r]内，分成[1..l[x])和[l[x]..r]两段通过走到当前x再走到终点。预处理一下[1..l[i])到i的距离的和。O((n+q)logn)。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=;

 int l[N],a[N][],par[N][],n,pre[N],q,fa[N],mx,b[N],rt[N];

 int getmin(int x,int y)

 {

   return l[x]<l[y]?x:y;

 }

 void init()

 {

   for (int i=;i<=n;i++) a[i][]=i;

   for (int j=;j<=;j++)

     for (int i=;i+(<<j)-<=n;i++)

       a[i][j]=getmin(a[i][j-],a[i+(<<(j-))][j-]);

 }

 int qry(int l,int r)

 {

   int len=;

   while ((<<(len+))<=r-l+) len++;

   return getmin(a[l][len],a[r-(<<len)+][len]);

 }

 bool cmp(int A,int B) {return l[A]<l[B];}

 int calc(int x,int y)//[1..x] to y

 {

     int ans=;

     if (rt[y])

     {

         if (l[y]<=x) ans+=x-l[y]+,x=l[y]-;

         y=rt[y];ans+=x;

     }

     if (!x) return ans;

     int sum=;

     for (int i=;i>=;i--)//倍增使得l[终点]跳进[1..x]

       if (l[par[y][i]]>x) y=par[y][i],sum+=(<<i);

     if (l[y]>x) y=par[y][],sum++;

     return ans+pre[y]+sum*(l[y]-)+(sum+)*(x-l[y]+);

 }

 int main()

 {

   scanf("%d",&n);

   for (int i=;i<=n;i++) scanf("%d",&l[i]);

   init();

   for (int i=;i<=n;i++) fa[i]=par[i][]=qry(l[i],i-);//找到可以跳到最左边的点作为父亲

   for (int j=;j<=;j++)//树上倍增

     for (int i=;i<=n;i++)

       par[i][j]=par[par[i][j-]][j-];

   for (int i=;i<=n;i++) b[i]=i;//处理会向右走一步的情况

   sort(b+,b+n+,cmp);

   for (int i=;i<=n;i++)

   {

         for (int j=mx+;j<b[i];j++) rt[j]=b[i];

         mx=max(mx,b[i]);

   }

   for (int i=;i<=n;i++)

     if (l[rt[i]]>=l[fa[i]]) rt[i]=;

   for (int i=;i<=n;i++)//处理前缀和[1..l[i]) to i

     if (fa[i]==) pre[i]=;else pre[i]=pre[fa[i]]+l[fa[i]]-+*(l[i]-l[fa[i]]);

   scanf("%d",&q);

   while (q--)

   {

        int l,r,x;

     scanf("%d%d%d",&l,&r,&x);

     int a=calc(r,x)-calc(l-,x),b=r-l+;

     int Gcd=__gcd(a,b);

     a/=Gcd;b/=Gcd;printf("%d/%d\n",a,b);

   }

   return ;

 }

T2：神仙的游戏

border相交有循环节的性质。问题是快速检查循环节的合法性。（我都想到bitset了T_T）

如果循环节长度为len时，对应位置的i，j一个为0一个为1，那么循环节长度为len的因数的都不可行。（有一个部分分给的就是暴力枚举01的位置）

fft处理对应位置的01是否有冲突，需要多项式平移。枚举当前循环节长度的倍数判断可行。时间复杂度O(nlogn)。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod=;

 const int root=;

 const int N=;

 char s[N];

 int _n,l,w[N],pos[N],A[N],B[N],sl;

 int ksm(int x,int y)

 {

     int res=;

     while (y) {if (y&) res=(ll)res*x%mod; x=(ll)x*x%mod; y>>=;}

     return res;

 }

 void init(int n)

 {

     l=;

     while ((<<l)<=n) l++;

     _n=(<<l);int ww=ksm(root,<<-l);

     w[]=;

     for (int i=;i<_n;i++)

       w[i]=(ll)w[i-]*ww%mod,

       pos[i]=(i&)?pos[i-]|(<<(l-)):pos[i>>]>>;

 }

 void fft(int *a)

 {

     for (int i=;i<_n;i++) if (i<pos[i]) swap(a[i],a[pos[i]]);

     int len=,id=_n;

     for (int i=;i<l;i++)

     {

       int wn=w[id>>=];

       for (int j=;j<_n;j+=len*)

         for (int k=j,ww=;k<j+len;k++)

         {

             int l=a[k],r=(ll)a[k+len]*ww%mod;

             a[k]=((ll)l+r)%mod;a[k+len]=((ll)l-r+mod)%mod;

             ww=(ll)ww*wn%mod;

         }

       len<<=;

     }

 }

 int main()

 {

     scanf("%s",s+);sl=strlen(s+);

     for (int i=;i<=sl;i++)

       if (s[i]=='') A[i]=;

       else if (s[i]=='') B[sl-i+]=;

     init(sl*+);fft(A);fft(B);

     for (int i=;i<_n;i++) A[i]=(ll)A[i]*B[i]%mod;

     fft(A);reverse(A+,A+_n);

     int inv_n=ksm(_n,mod-);

     for (int i=;i<_n;i++) A[i]=(ll)A[i]*inv_n%mod;

     ll ans=(ll)sl*sl;

     for (int i=;i<sl;i++)

     {

         int fl=;

         for (int j=i;j<=sl&&fl;j+=i)

           fl&=(!A[sl-j+]&&!A[sl+j+]);

         if (fl) ans^=(ll)(sl-i)*(sl-i);

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

PKUSC订正

最新文章

热门文章