pkuwc2018题解

题解：

思路挺好想的。。然而今天写代码写成傻逼了

d1t1:

首先比较暴力的就是$f[i][j]$表示i个这个点是j的概率

然后前缀和一下dp就是$n^2$的

部分分树形态随机就说明树深度是$log$的

只转移子树中有的点,复杂度$nlogn$的

正解也很好想

我们化简一下那个式子（早上的草稿纸找不到了。。）

反正形如$(ai*sum[i]+bi)*pi$

因为最多只有两个儿子，显然启发式合并或者线段树合并可以维护这个sum[i]然后复杂度是$nlogn$的

30min写完一下过了样例一交爆0

然后就debug了无限久

大概先是通过手造发现要先做左二子，然后发现了查询没down

然后手造就再也发现不了问题

就改对拍（早知道就早点写了）

然后那个数据要在不太能手摸的时候才出错。。

找了半天才发现是merge里面没有把y的sum加到x上

然后交了tle70

然后我把map改了hash快了一点点还是70

于是又离散化才过

于是我写了2个半小时这题简直是傻逼

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define me(x) memset(x,0,sizeof(x))

#define ll long long

#define mid ((h+t)>>1)

namespace IO

{

    char ss[<<],*A=ss,*B=ss;

    IL char gc()

    {

        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

    }

    template<class T>void read(T &x)

    {

        rint f=,c;while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);

        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;

    }

    char sr[<<],z[]; int C=-,Z;

    template<class T>void wer(T x)

    {

        if (x<) sr[++C]='-',x=-x;

        while (z[++Z]=x%+,x/=);

        while (sr[++C]=z[Z],--Z);

    }

    IL void wer1() {sr[++C]=' ';}

    IL void wer2() {sr[++C]='\n';}

    template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}

    template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}

    template<class T>IL T MAX(T x,T y){ return x>y?x:y;}

    template<class T>IL T MIN(T x,T y){ return x<y?x:y;}

}

using namespace IO;

const int N=4e5;

const int M2=N*;

const int mo=;

const int INF=4e5;

int ch[N][],cnt[N],v[N];

const int mo2=1e7+;

struct Hash{

    int a[mo2+],b[mo2+];

    IL void push(int x,int y)

    {

        int pos=x%mo2;

        while (a[pos]&&a[pos]!=x) pos++;

        a[pos]=x; b[pos]=y;

    }

    IL int find(int x)

    {

        int pos=x%mo2;

        while (a[pos]&&a[pos]!=x) pos++;

        return b[pos];

    }

}H;

IL int fsp(int x,int y)

{

    ll now=;

    while (y)

    {

        if (y&) now=now*x%mo;

        x=1ll*x*x%mo; y>>=;

    }

    return now;

}

int rt[N];

map<int,int> M;

struct re{

    int a,b;

}p[N];

int tf;

struct sgt{

    int sum[M2],lazy[M2],ls[M2],rs[M2],cnt2;

    sgt() { rep(i,,M2-) lazy[i]=;}

    IL void down(int x)

    {

        if (lazy[x]!=)

        {

            sum[ls[x]]=1ll*sum[ls[x]]*lazy[x]%mo;

            sum[rs[x]]=1ll*sum[rs[x]]*lazy[x]%mo;

            lazy[ls[x]]=1ll*lazy[ls[x]]*lazy[x]%mo;

            lazy[rs[x]]=1ll*lazy[rs[x]]*lazy[x]%mo;

            lazy[x]=;

        }

    }

    int merge(int x,int y,int p1,int p2,int p)

    {

        down(x); down(y);

        if (!x&&!y) return ;

        if (!x)

        {

            lazy[y]=(1ll*p1*(*p-)+(-p))%mo;

            sum[y]=1ll*lazy[y]*sum[y]%mo;

            return y;

        }

        if (!y)

        {

            lazy[x]=(1ll*p2*(*p-)+(-p))%mo;

            sum[x]=1ll*sum[x]*lazy[x]%mo;

            return x;

        }

        rs[x]=merge(rs[x],rs[y],(p1+sum[ls[x]])%mo,(p2+sum[ls[y]])%mo,p);

        ls[x]=merge(ls[x],ls[y],p1,p2,p);

        sum[x]=(sum[ls[x]]+sum[rs[x]])%mo;

        return x;

    }

    void change(int &x,int h,int t,int pos)

    {

        x=++cnt2; sum[x]=;

        if (h==t) return;

        if (pos<=mid) change(ls[x],h,mid,pos);

        else change(rs[x],mid+,t,pos);

    }

    int query(int x,int h,int t)

    {

        if (!x) return();

        if (h==t)

        {

          return 1ll*h*p[h].a%mo*sum[x]%mo*sum[x]%mo;

        }

        down(x);

        return (query(ls[x],h,mid)+query(rs[x],mid+,t))%mo;

    }

}S;

void dfs(int x)

{

    if (!x) return;

    if (cnt[x]==)

    {

      dfs(ch[x][]); dfs(ch[x][]);

      rt[x]=S.merge(rt[ch[x][]],rt[ch[x][]],,,v[x]);

    } else if (cnt[x]==)

    {

      dfs(ch[x][]);

      rt[x]=rt[ch[x][]];

    } else

    {

        S.change(rt[x],,INF,v[x]);

    }

}

int n;

bool cmp(re x,re y)

{

    return x.a<y.a;

}

int main()

{

    read(n);

    rep(i,,n)

    {

      int x;

      read(x);

      ch[x][cnt[x]++]=i;

    }

    int ni10000=fsp(,mo-),num=;

    rep(i,,n)

    {

      read(v[i]);

      if (cnt[i]) v[i]=1ll*v[i]*ni10000%mo;

      else p[++num]=(re){v[i],i};

    }

    sort(p+,p+num+,cmp);

    rep(i,,num) v[p[i].b]=i;

  //  rep(i,1,num) H.push(p[i],i);

    dfs();

    cout<<S.query(rt[],,INF)<<endl;

    return ;

}

d1t2:

（我的做法可能比较麻烦常数比别人大2-3倍）

这个贪心的性质非常明显，有强化卡肯定强化他然后选最大的（没有当然只能选攻击了）

看数据范围就知道这个东西很明显是$n^2$的并且不能带$log$

于是这时候很明显是dp了

对于强化卡我们$f[i][j]$表示前i张选j张不同方案的乘积和（注意如果>k-1只取k-1张）所以要先排序

那对于攻击卡我们怎么选择呢，似乎暴力$dp$需要$f[i][j][k]$，i张里面选j张，使用k张攻击卡

但我们排序后发现，对后面的我们可以直接乘组合数

于是处理出$f[i][j]$表示前i张选j张并且攻击了

最后枚举$i$和强化卡使用数量num，那么j就是$max(1,k-num)$，再乘个组合数就好了

刚开始第二个样例wa了

写了个拍查了一下就对了

然后提交上去30？？？？？

卧槽卡常这么恐怖的么

然后就是30-40-60-100了

（大概是把多次调用数组同一个值的地方改掉了上下界修改了一下 MAX只调用一次 C数组改变了一下两维的顺序）

连续两天用指针卡常发现没用

以后再也不改指针了，最花时间又最没用的卡常

当然这些都改了也只有60

通过删减代码发现时间在最后统计处

然后用常用的套路去减少取模次数

于是我循环展开了然后4次取模一次（8次测出来和4次效果差不多）

终于过了

我也不知道为啥这个常数这么大。。。跟正解好像没啥区别。。。

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define me(x) memset(x,0,sizeof(x))

#define ll long long

#define mid ((h+t)>>1)

namespace IO

{

    char ss[<<],*A=ss,*B=ss;

    IL char gc()

    {

        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

    }

    template<class T>void read(T &x)

    {

        rint f=,c;while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);

        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;

    }

    char sr[<<],z[]; int C1=-,Z;

    template<class T>void wer(T x)

    {

        if (x<) sr[++C1]='-',x=-x;

        while (z[++Z]=x%+,x/=);

        while (sr[++C1]=z[Z],--Z);

    }

    IL void wer1() {sr[++C1]=' ';}

    IL void wer2() {sr[++C1]='\n';}

    template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}

    template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}

    template<class T>IL T MAX(T x,T y){ return x>y?x:y;}

    template<class T>IL T MIN(T x,T y){ return x<y?x:y;}

}

using namespace IO;

const int N=4e3;

const int mo=;

int w1[N],w2[N];

int f1[N][N],f2[N][N],C[N][N],g[N][N],C2[N][N],f3[N][N];

bool cmp(int x,int y)

{

    return x>y;

}

int main()

{

    int T;

    read(T);

    rep(i,,)

    {

      rep(j,,i)

        C[i][j]=(C[i-][j]+C[i-][j-])%mo;

      C[i][]=;

    }

    rep(i,,)

      rep(j,,)

        C2[i][j]=C[j][i];

    while (T--)

    {

        int n,m,k;

        read(n); read(m); read(k);

        rep(i,,n) read(w1[i]);

        rep(i,,n) read(w2[i]);

        sort(w1+,w1+n+,cmp); sort(w2+,w2+n+,cmp);

        f1[][]=; f2[][]=;

        rep(i,,n) f1[i][]=;

        rep(i,,n)

        {

          int t=MIN(i,m);

          rep(j,,t)

          {

            if (j<k) f1[i][j]=(f1[i-][j]+1ll*f1[i-][j-]*w1[i])%mo;

            else f1[i][j]=(f1[i-][j]+f1[i-][j-])%mo;

          }

        }

        rep(i,,n)

        {

          int t=MIN(i,m);

          rep(j,,t)

          {

              f2[i][j]=(g[i-][j-]+1ll*w2[i]*C[i-][j-])%mo;

              g[i][j]=(g[i-][j-]+g[i-][j]+1ll*w2[i]*C[i-][j-])%mo;

          }

        }

        unsigned ll ans=;

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

        {

          int tt=MAX(k-j,),tt1=f1[n][j];

          int *pp=C2[m-j-tt];

          register int i;

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

          {

            ans+=1ll*tt1*f2[i][tt]%mo*pp[n-i];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans+=1ll*tt1*f2[i+][tt]%mo*pp[n-i-];

            ans%=mo;

          }

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

           ans+=1ll*tt1*f2[i][tt]%mo*pp[n-i];

          ans%=mo;

        }

        wer(ans); wer2();

    }

    fwrite(sr,,C1+,stdout);

    return ;

}

d1t3:
果然是不可做题。。再见

d2t1:

因为记得我看过游记说这个是道傻逼题

于是看了题目10min写了个next_permutation然后拿了10分

我才意识到把排序当2^n了

然后就先去写了一道lct

写完重新开始想。。感觉已经晕了

然后我就很zz的想出了$nlog^3n$的做法

然后发现这个东西常数极小就写了

大概就是$f[i][j]$表示当前状态中有i这些点，然后与它相连的点有j个（包括自己）

然后转移就可以枚举现在放了几个点在后面

然后挺好写

不过拍了一下发现我把$A()$搞成了$x!$ 改了就拍上了

交了之后发现数组开小了

然后并不是很理解为啥这个数组要40

后来发现我把自己重复计数了（我也不懂为什么这都是对的）

果然跑的飞快

也就是$nlogn$慢了3倍

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define me(x) memset(x,0,sizeof(x))

#define ll long long

#define mid ((h+t)>>1)

namespace IO

{

    char ss[<<],*A=ss,*B=ss;

    IL char gc()

    {

        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

    }

    template<class T>void read(T &x)

    {

        rint f=,c;while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);

        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;

    }

    char sr[<<],z[]; int C=-,Z;

    template<class T>void wer(T x)

    {

        if (x<) sr[++C]='-',x=-x;

        while (z[++Z]=x%+,x/=);

        while (sr[++C]=z[Z],--Z);

    }

    IL void wer1() {sr[++C]=' ';}

    IL void wer2() {sr[++C]='\n';}

    template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}

    template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}

    template<class T>IL T MAX(T x,T y){ return x>y?x:y;}

    template<class T>IL T MIN(T x,T y){ return x<y?x:y;}

}

using namespace IO;

const int N=1.5e6;

const int M=;

#define lowbit(x) (x&(-x))

bool f[][N],o[N];

int g[N][];

int a[N],num,ans1[N],ans2[N],jc[],jc2[];

const int mo=;

IL int fsp(int x,int y)

{

    ll now=;

    while (y)

    {

        if (y&) now=now*x%mo;

        x=1ll*x*x%mo; y>>=;

    }

    return now;

}

int main()

{

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

    int n,m;

    read(n); read(m);

    rep(i,,m)

    {

        int x,y;

        read(x); read(y);

        f[y][<<(x-)]=;

        f[x][<<(y-)]=;

    }

    jc[]=; jc2[]=;

    rep(i,,) jc[i]=1ll*jc[i-]*i%mo,jc2[i]=fsp(jc[i],mo-);

    rep(i,,n)

      rep(j,,(<<n)-)

        f[i][j]=f[i][j-lowbit(j)]|f[i][lowbit(j)];

    rep(j,,(<<n)-)

      rep(i,,n)

      {

        if (f[i][j]||(j>>(i-))&) ans1[j]++;

        if ((j>>(i-))&) ans2[j]++;

      }

    g[][]=;

    rep(i,,(<<n)-)

      rep(j,ans2[i],ans1[i])

        if (g[i][j])

        {

            if (j>=) cout<<"sb"<<endl;

            rep(k,,n)

              if (!((i>>(k-))&)&&!f[k][i])

              {

                  o[i|(<<(k-))]=;

                  int pu=ans1[i|(<<(k-))];

                rep(i1,j+,pu)

                {

                  if (i1>=) cout<<(i|(<<(k-)))<<endl;

                  g[i|(<<(k-))][i1]=(g[i|(<<(k-))][i1]+1ll*g[i][j]*jc[pu-j-]%mo*jc2[pu-i1])%mo;

                }

              }

        }

    int cnt=;

    dep(i,(<<n)-,)

      if (o[i])

      {

          maxa(cnt,ans2[i]);

      }

    ll ans=;

    rep(i,,(<<n)-)

      if (ans2[i]==cnt) (ans+=g[i][n])%=mo;

    ll ans3=;

    rep(i,,n) ans3=ans3*i%mo;

    cout<<ans*fsp(ans3,mo-)%mo<<endl;

    return ;

}

正解是这样的：

大概就是跟我反着记录

$f[i][j]$表示当前有状态i内的点不能经过，独立集内有j个点的方案

然后现在枚举加入一个点会带来k个不合法的，就把他们插入到剩下的位置就可以了

这样是$2^n*n^2$的

然后这么dp的话显然是$i$相同时j越大越好且一定好于j小的

所以记录一下最大就行了

复杂度$nlogn$

我那个方法完全没法优化理论复杂度。。

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for (int i=h;i<=t;i++)

#define dep(i,t,h) for (int i=t;i>=h;i--)

#define me(x) memset(x,0,sizeof(x))

#define ll long long

#define mid ((h+t)>>1)

namespace IO

{

    char ss[<<],*A=ss,*B=ss;

    IL char gc()

    {

        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

    }

    template<class T>void read(T &x)

    {

        rint f=,c;while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);

        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;

    }

    char sr[<<],z[]; int C=-,Z;

    template<class T>void wer(T x)

    {

        if (x<) sr[++C]='-',x=-x;

        while (z[++Z]=x%+,x/=);

        while (sr[++C]=z[Z],--Z);

    }

    IL void wer1() {sr[++C]=' ';}

    IL void wer2() {sr[++C]='\n';}

    template<class T>IL void maxa(T &x,T y) { if (x<y) x=y;}

    template<class T>IL void mina(T &x,T y) { if (x>y) x=y;}

    template<class T>IL T MAX(T x,T y){ return x>y?x:y;}

    template<class T>IL T MIN(T x,T y){ return x<y?x:y;}

}

using namespace IO;

const int N=1.5e6;

const int M=;

#define lowbit(x) (x&(-x))

bool f[][N],o[N];

int g[N][];

int a[N],num,ans1[N],ans2[N],jc[],jc2[];

const int mo=;

IL int fsp(int x,int y)

{

    ll now=;

    while (y)

    {

        if (y&) now=now*x%mo;

        x=1ll*x*x%mo; y>>=;

    }

    return now;

}

int main()

{

    freopen("1.in","r",stdin);

    freopen("1.out","w",stdout);

    int n,m;

    read(n); read(m);

    rep(i,,m)

    {

        int x,y;

        read(x); read(y);

        f[y][<<(x-)]=;

        f[x][<<(y-)]=;

    }

    jc[]=; jc2[]=;

    rep(i,,) jc[i]=1ll*jc[i-]*i%mo,jc2[i]=fsp(jc[i],mo-);

    rep(i,,n)

      rep(j,,(<<n)-)

        f[i][j]=f[i][j-lowbit(j)]|f[i][lowbit(j)];

    rep(j,,(<<n)-)

      rep(i,,n)

      {

        if (f[i][j]||(j>>(i-))&) ans1[j]++;

        if ((j>>(i-))&) ans2[j]++;

      }

    g[][]=;

    rep(i,,(<<n)-)

      rep(j,ans2[i],ans1[i])

        if (g[i][j])

        {

            if (j>=) cout<<"sb"<<endl;

            rep(k,,n)

              if (!((i>>(k-))&)&&!f[k][i])

              {

                  o[i|(<<(k-))]=;

                  int pu=ans1[i|(<<(k-))];

                rep(i1,j+,pu)

                {

                  if (i1>=) cout<<(i|(<<(k-)))<<endl;

                  g[i|(<<(k-))][i1]=(g[i|(<<(k-))][i1]+1ll*g[i][j]*jc[pu-j-]%mo*jc2[pu-i1])%mo;

                }

              }

        }

    int cnt=;

    dep(i,(<<n)-,)

      if (o[i])

      {

          maxa(cnt,ans2[i]);

      }

    ll ans=;

    rep(i,,(<<n)-)

      if (ans2[i]==cnt) (ans+=g[i][n])%=mo;

    ll ans3=;

    rep(i,,n) ans3=ans3*i%mo;

    cout<<ans*fsp(ans3,mo-)%mo<<endl;

    return ;

}

d2t2:

d2t3:

巴特西

pkuwc2018题解

最新文章

热门文章