hgoi#20191104

muronglin
muronglin 2019年11月04日
  • 在其它设备中阅读本文章

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<kx;
}
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 $ 个小朋友, 编号为 $ 1 $ 到 $ N $ , 幼儿园的园长是计算鸭, 他准备给这些小朋友分配 $ 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_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} ... \sum_{x_N=A_N}^{B_N} f(x_1,x_2...x_N) $ 答案对 $ 10^9+7 $ 取模

解法

设 $ f_{i,j} $ 表示前 i 个人分 j 个糖的答案
当 $ A_i=B_i $ 时, $ f_{i,j}=\sum_{k=0}^jf_{i-1,j-k}*{A_i}^k $
归纳一下, $ f_{i,j}=\sum_{k=0}^j(f_{i-1,j-k}*\sum_{l=A_i}^{B_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=1llreta%mod;
        a=1llaa%mod,b/=2;
    }
    return ret;
}
int n,m,a[500],b[500],s500,f500;
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++)
                (si+=p(k,j))%=mod;
    f0=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++)
                (fi+=1llfi-1si%mod)%=mod;
    printf("%dn",fn);
    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("%lldn",res);
    return 0;
}