慕容琳的后花园
慕容琳的后花园
hgoi#20191104

T1-卡牌游戏

计算鸭有 N 张卡牌, 第 i 张卡牌上写着数字 A_i , 计算鸭会选择一个整数 K , 然后重复下列操作
选择恰好 K 张数字不同的卡牌, 然后扔掉
对于每一个 K=1,2,3…N ,计算鸭想要知道最多可以执行多少次操作

解法

显然, K 越大答案越小,我们可以用双指针法来做
设取了 x 次,只要写一个检验 (k,x) 是否可行的函数即可
将数分为出现超过 x 次和不超过 x 次两种
设超过 x 次的数的种数为 tot ,不超过 x 次的数的总数为 sum
只要 sum+tot×x>=k×x 就可以取

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,x,ans,a[300010],s[300010],p[300010];
int check(int k,int x)
{
    return s[x]+(p[n]-p[x])*x<k*x;
}
int main()
{
    scanf("%d",&n),ans=n;
    for(int i=1;i<=n;i++)
        scanf("%d",&x),a[x]++;
    for(int i=1;i<=n;i++)
        if(a[i])s[a[i]]++;
    for(int i=1;i<=n;i++)
        p[i]=p[i-1]+s[i],
        s[i]=s[i-1]+s[i]*i;
    for(int i=1;i<=n;i++)
    {
        while(check(i,ans))ans--;
        printf("%d ",ans);
    }
    return 0;
}

T2-分糖果

517编程幼儿园有 N 个小朋友,编号为 1N ,幼儿园的园长是计算鸭,他准备给这些小朋友分配 C 个相同的糖果,如果第 i 个小朋友拿到了 a 个糖果,那么这个小朋友的快乐值为 {x_i}^a , x_i 是第i个小朋友的激动值, 整个幼儿园的活跃程度定义为所有小孩快乐值的乘积.
假设小朋友们的激动值分别为 x_1, x_2,…,x_N ,令 f(x_1,x_2…x_N) 为所有分配方案的活跃程度之和, 现在给你 N 对整数 A_i,B_i ,你的任务是求 \sum\limits_{x_1=A_1}^{B_1} \sum\limits_{x_2=A_2}^{B_2} … \sum\limits^{B_N}_{x_N=A_N} f(x_1,x_2…x_N)
答案对 10^9+7 取模

解法

f_{i,j} 表示前i个人分j个糖的答案
A_i=B_i 时, f_{i,j}=\sum\limits^j_{k=0}f_{i-1,j-k}×{A_i}^k
归纳一下, f_{i,j}=\sum\limits^j_{k=0}(f_{i-1,j-k}×\sum\limits^{B_i}_{l=A_i}l^k)

ac代码

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int p(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=1ll*ret*a%mod;
        a=1ll*a*a%mod,b/=2;
    }
    return ret;
}
int n,m,a[500],b[500],s[500][500],f[500][500];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=a[i];k<=b[i];k++)
                (s[i][j]+=p(k,j))%=mod;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++)
                (f[i][j]+=1ll*f[i-1][j-k]*s[i][k]%mod)%=mod;
    printf("%d\n",f[n][m]);
    return 0;
} 

T3-旅行规划

有一天, 小Y要在一棵树上旅行, 在旅行之前,他想知道这棵树有多少的 (x,y) 满足存在长度为 x 的路径 (a,b) , 以及长度为 y 的路径 (c,d) 使得 (a,b)(c,d) 两条路径不相交

解法

易得,对于一个合法的 (x,y) 一定有一种方案可以使得选取的两条路径,经过直径的两个端点
分两种情况:

第一种情况,一条路径为直径,还有一条路径随意
将直径上的点全部标记,计算剩下树的直径即可

第二种情况,两条路径分别以直径一段为起点,从直径上某一点下去,往边上走
只要算出直径上每个点的最长路即可

ac代码

#include<bits/stdc++.h>
#define pb push_back
#define pi pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define N 100010
#define ll long long
using namespace std;
vector<int>e[N];
pi po1,po2;
int n,x,y,po,maxx,cnt,ans[N],d[N],pr[N],vis[N],dep[N],p[N],D[N];
ll res;
void upd(int l1,int l2){ans[l1]=max(ans[l1],l2),ans[l2]=max(ans[l2],l1);}
void dfs1(int u,int fa,int dep)
{
    if(po1.sec<dep)po1=mp(u,dep);
    for(auto v:e[u])if(v!=fa)dfs1(v,u,dep+1);
}
void dfs2(int u,int fa)
{
    p[u]=fa;
    for(auto v:e[u])if(v!=fa)
        dep[v]=dep[u]+1,dfs2(v,u);
}
pi dfs3(int u,int fa)
{
    int len=0,max1=0,max2=0;
    for(auto v:e[u])if(v!=fa)
    {
        pi tmp=dfs3(v,u);
        len=max(len,tmp.fir);
        if(tmp.sec+1>max2)max2=tmp.sec+1;
        if(max1<max2)swap(max1,max2);
    }
    return mp(max(max1+max2,len),max1);
}
int dfs4(int u,int fa)
{
    int ret=0;
    for(auto v:e[u])
        if(v!=fa&&!vis[v])
            ret=max(ret,dfs4(v,u)+1);
    return ret;
}
int main()
{
    scanf("%d",&n),maxx=-1;
    for(int i=1;i<n;i++)
        scanf("%d%d",&x,&y),
        e[x].pb(y),e[y].pb(x);
    dfs1(1,0,0),dfs2(po1.fir,0);
    for(int i=1;i<=n;i++)
        if(po2.sec<dep[i])po2=mp(i,dep[i]);
    po=po2.fir;
    while(po)D[++cnt]=po,po=p[po];
    //get D 
    for(int i=1;i<=cnt;i++)vis[D[i]]=1;
    for(int i=1;i<=cnt;i++)
        for(auto v:e[D[i]])if(!vis[v])
            maxx=max(maxx,dfs3(v,D[i]).fir);
    if(maxx!=-1)upd(maxx+1,cnt);
    for(int i=1;i<=cnt;i++)
        d[i]=dfs4(D[i],0),pr[i]=max(pr[i-1],d[i]+i);
    for(int i=2;i<=cnt;i++)
        upd(pr[i-1],d[i]+cnt-i+1);
    for(int i=n;i;i--)
        ans[i]=max(ans[i],ans[i+1]),res+=ans[i];
    printf("%lld\n",res);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191104
T1-卡牌游戏 计算鸭有 $ N $ 张卡牌, 第 $ i $ 张卡牌上写着数字 $ A_i $ , 计算鸭会选择一个整数 $ K $ , 然后重复下列操作 选择恰好 $ K $ 张数字不同的卡牌, 然后扔掉 对于每一个 $ K…
扫描二维码继续阅读
2019-11-04
功能