HGOI20190813 省常中互测6

Problem A 蛋糕

将$n \times m $大小的蛋糕切成每块为$1 \times 1$大小的$n\times m$块。

交换任意两块蛋糕的切割顺序的方案算作一种。

对于$100 \%$的数据满足$1 \leq n,m \leq 300$

Solution ：一个比较明显的DP

设$f[i][j]$表示蛋糕大小为$i \times j$时候的答案。

　　当前步可以在第$k(1\leq k \leq i-1)$行切一刀分成$[1,k]$和$[k+1,i]$两部分；

　　或者可以在第$k(q\leq k \leq j-1)$列切一刀分成$[1,k]$和$[k+1,j]$ 两部分。

　　问题就可以转化为两个子问题了（由乘法原理可以合并），然后把所有子问题相加就是最后的答案。

　枚举状态是$O(n^2)$，然后枚举转移是$O(n)$的复杂度，总复杂度是$O(n^3)$

# include<bits/stdc++.h>

# define int long long

using namespace std;

const int N=,mo=1e9+;

int f[N][N];

int dfs(int i,int j)

{

    if (i== && j==) return ;

    if (i< || j<) return ;

    if (f[i][j]!=-) return f[i][j];

    int ret=;

    for (int k=;k<=i-;k++)

     ret=(ret+dfs(k,j)*dfs(i-k,j)%mo)%mo;

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

     ret=(ret+dfs(i,k)*dfs(i,j-k)%mo)%mo;

    return f[i][j]=ret;

}

signed main()

{

    int n,m; scanf("%lld%lld",&n,&m);

    memset(f,-,sizeof(f));

    printf("%lld\n",dfs(n,m));

    return ;

}

A.cpp

Problem B 找钱　

有$n$种面值为$a_i$的纸币,小L手上有$b_i$张，而商店手上有$c_i$张。

小L到商店去购买价格为$X$的商品，问有多少种不同的付钱-找钱的方法。

一种不同的且合法的方案满足，小$L$付出的纸币必须是必要的且付钱方案或者找钱的方案有不同。

对于$100\%$的数据满足$n \leq 10^3 ,\leq a_i,b_i,c_i \leq 10^4$

Solution : 还是一个比较明显的(背包)DP

　　设$f[i][j]$表示小L在后$n$种纸币（纸币币值需要单调）中找出钱数位$j$的方案数。

　　设$g[i][j]$表示商店在前$i$种纸币中找出钱数为$j$的方案数。

　　可以有一个显然的多重背包的转移，

　　$g[i][j]=g[i][j]+g[i-1][j-k*a[i]] , f[i][j]=f[i][j]+f[i+1][j-k*a[i]]$

　　初始值为$f[n+1][0] = 1, g[0][0] = 1$ ，复杂度大概是$O(n X \sum c[i])$

　　上面的DP可以用前缀和优化，上一层的转移区间每一次会向右平移$a[i]$个单位，于是我们只需要计算上一个区间里转移区间内的和即可。

　　所以我们只需要枚举余数$j$和跳$a[i]$单位的步数$k$即可用$j+k\times a[i]$拼成一个物品了。

　　具体来说，若把上一层转移而来的元素记为$j$那么，当前元素就是$j + k\times a[i]$，当前元素的转移区间就是$[j,j+k\times a[i]]$

　　所以，每当$k$+1，转移区间就向右平移$a[i]$个单位，于是我们只需要维护一个变量$Sum$记录一下$i-1$层的转移区间的和即可。每一次滑动$O(1)$计算。

　　用上述方法，我们可以将复杂度优化到$O(n Max\{a_i , X\})$ 。

# include <bits/stdc++.h>

# define ll long long

using namespace std;

const int mo=1e9+;

int a[],b[],c[];

int f[][],n,m,g[][];

signed main()

{

//  freopen("deal12.in","r",stdin);

//  freopen("deal13.out","w",stdout);

    scanf("%d%d",&n,&m);

    int Lim=m;

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

    g[][]=;

//  for (int i=1;i<=n;i++) {

//      for (int j=0;j<=m;j++) {

//           for (int k=0;k<=min(j/a[i],c[i]);k++)

//           g[i][j]=(g[i][j]+g[i-1][j-k*a[i]])%mo;

//      }

//  }

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

     for (int j=;j<=a[i]-;j++) {

        int sum=;

        for (int k=;j+k*a[i]<=Lim;k++) {

            sum=(sum+g[i-][j+k*a[i]])%mo;

            if (k>c[i]) sum=((sum-g[i-][j+a[i]*(k-c[i]-)])%mo+mo)%mo;

            g[i][j+a[i]*k]=sum;

         }

     }

    f[n+][]=;

//  for (int i=n;i>=1;i--) {

//      for (int j=0;j<=2*m;j++) {

//          for (int k=0;k<=min(j/a[i],b[i]);k++)

//          f[i][j]=(f[i][j]+f[i+1][j-k*a[i]])%mo;

//      }

//  }

    for (int i=n;i>=;i--)

        for (int j=;j<=a[i]-;j++) {

            int sum=;

            for (int k=;j+k*a[i]<=*Lim;k++) {

                sum=(sum+f[i+][j+k*a[i]])%mo;

                if (k>b[i]) sum=((sum-f[i+][j+a[i]*(k-b[i]-)])%mo+mo)%mo;

                f[i][j+a[i]*k]=sum;

            }

        }

    ll ans=;

    for (int i=;i<=Lim;i++) {

        int w=;

        for (int j=;j<=n;j++) if (a[j]>i) { w=j; break;}

        if (w) ans=(ans+(ll)g[n][i]*f[w][m+i]%mo)%mo;

    }

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

    return ;

}

B.cpp

Problem C 城镇

初始离散的$n$个点，每次添加$1$条边，共添加$n-1$次构成一棵树。

每一次连边之后，输出在该边所在的连通块中的直径为多少。

对于$100 \%$的数据 $n \leq 3\times 10^5$

　Solution :

　　首先想到每一次合并直径，若一个连通块中直径为$s1,t1$，另外一个连通块中直径为$s2,t2$

　　那么合并后的连通块直径为$s1,t1,s2,t2$四个点中取2个点组成路径的最长路。

　　如果不是这样，那么必然存在一条更加长的直径，与直径的最长性矛盾，所以定理显然成立。

　　于是我们就可以用并查集维护连通块。

　　我们发现每次合并时将size较小的块合并到size较大的块上即可。

　　这样子做的复杂度是$O(n \ log_2 \ n)$

　　由于还有求$LCA$所以本题的时间复杂度是$O(n \ {log_2}^2 \ n)$

# include<bits/stdc++.h>

using namespace std;

const int N=3e5+;

struct rec{

    int pre,to;

}a[N<<];

struct A{

    int size,s,t;

}mem[N];

int head[N],tot,gi[N],rec[N],dep[N],g[N][];

int n;

void adde(int u,int v)

{

    a[++tot].pre=head[u];

    a[tot].to=v;

    head[u]=tot;

}

int father(int x)

{

    if (gi[x]==x) return x;

    return gi[x]=father(gi[x]);

}

void dfs(int u,int fa)

{

    rec[++rec[]]=u; g[u][]=fa; dep[u]=dep[fa]+;

    for (int i=head[u];i;i=a[i].pre) {

        int v=a[i].to; if (v==fa) continue;

        dfs(v,u);

    }

}

int lca(int u,int v) {

    if (dep[u]<dep[v]) swap(u,v);

    for (int i=;i>=;i--)

     if (dep[g[u][i]]>=dep[v]) u=g[u][i];

    if (u==v) return u;

    for (int i=;i>=;i--)

     if (g[u][i]!=g[v][i]) u=g[u][i],v=g[v][i];

    return g[u][];

}

int getdist(int u,int v) {

    int l=lca(u,v);

    return dep[u]+dep[v]-*dep[l];

}

int main()

{

    scanf("%d",&n);

    for (int i=;i<=n;i++) gi[i]=i,mem[i].size=,mem[i].s=mem[i].t=i;

    int m=n-;

    while (m--) {

        int u,v; scanf("%d%d",&u,&v);

        int fx=father(u),fy=father(v); 

        if (mem[fx].size>mem[fy].size) swap(fx,fy),swap(u,v);

        adde(u,v); adde(v,u);  rec[]=; dfs(u,v);

        gi[fx]=fy; mem[fy].size+=mem[fx].size;

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

            for (int j=;j<=rec[];j++) {

                int u=rec[j];

                g[u][i]=g[g[u][i-]][i-];

            }

        }

        int t1=mem[fx].s,t2=mem[fx].t,t3=mem[fy].s,t4=mem[fy].t;

        int d1=getdist(t1,t3),d2=getdist(t1,t4);

        int d3=getdist(t2,t3),d4=getdist(t2,t4);

        int d5=getdist(t1,t2),d6=getdist(t3,t4);

        int num=,d=;

        if (d1>d) num=,d=d1; if (d2>d) num=,d=d2;

        if (d3>d) num=,d=d3; if (d4>d) num=,d=d4;

        if (d5>d) num=,d=d5; if (d6>d) num=,d=d6;

        if (num==) mem[fy].s=t1,mem[fy].t=t3;

        else if (num==) mem[fy].s=t1,mem[fy].t=t4;

        else if (num==) mem[fy].s=t2,mem[fy].t=t3;

        else if (num==) mem[fy].s=t2,mem[fy].t=t4;

        else if (num==) mem[fy].s=t1,mem[fy].t=t2;

        else if (num==) mem[fy].s=t3,mem[fy].t=t4;

        printf("%d\n",d);

    }

    return ;

}

C.cpp

巴特西

HGOI20190813 省常中互测6

最新文章

热门文章