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

T1-Little Pony and Expected Maximum

暮暮刚刚在和她的朋友——AJ(苹果杰克)、FS(小蝶)、RD(云宝黛西)玩Ludo游戏。但是她马品没攒够总是输。回到城堡过后,她对游戏用的骰子产生了兴趣。
这个骰子有M面:骰子的第一面有一个点,第二面有两个点,以此类推,第m面含有M点。暮暮确信的是,当掷骰子时,每一面都有1/m的可能性出现,并且每次投掷的概率都是都是独立的。请你帮助她计算掷N次骰子后每次得到的点数中最大值的期望。

解法

容易得到,n面的骰子扔m次,全在1-(i-1)的总次数是(i-1)^m,全在1-i的总次数是i^m
所以最大值为i的总次数是i^m-(i-1)^m,而贡献就是i,最后除以总次数n^m
因为n^m太大,所以把它放到每一次计算中,每一个i的贡献即为((i/n)^m-((i-1)/n)^m)×i

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
double ans;
double power(double a,int b)
{
    double sum=1.0;
    while(b)
    {
        if(b&1)sum*=a;
        b/=2,a*=a;
    }
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)ans+=(power((1.0*i)/(1.0*n),m)-power((1.0*(i-1))/(1.0*n),m))*(1.0*i);
    printf("%.8lf\n",ans);
    return 0;
}

T2-Little Pony and Harmony Chest

紫悦正在宇宙公主和月亮的城堡里研究和谐之元的宝箱。
对于一个正整数序列bi,当且仅当它的任意两个元素都互质时,这个序列bi才是和谐的。据古书记载,宝箱的钥匙是能让以下表达式的值最小的和谐序列bi:
现在紫悦已经得到了序列ai,你能帮助紫悦找到开启宝箱的钥匙吗?

解法

因为1可以无限放,ai最多是30,所以最多放到58(59和1等价),互质的序列中没有相同的质因数,1~58的质因数只有16个,所以可以状压dp
复杂度大概就是100×60×2^17,时限是4s,能过,我最慢的点也不到1s

ac代码

#include<bits/stdc++.h>
#define lim 131072
using namespace std;
int n,cnt,flg,ans,a[110],p[60],pr[20],dp[110][lim],f[110][lim];
void get_prime()
{
    for(int i=2;i<=55;i++)
    {
        flg=1;
        for(int j=2;j<i;j++)if(i%j==0){flg=0;break;}
        if(flg)pr[++cnt]=i;
    }
}
int calc(int k)
{
    flg=0;
    for(int i=1;i<=cnt;i++)
    {
        if(pr[i]>k)break;
        if(k%pr[i]==0)
        {
            flg+=1<<i;
            while(k%pr[i]==0)k/=pr[i];
        }
    }
    return flg;
}
void print(int nw,int sum)
{
    if(nw>1)print(nw-1,sum-p[f[nw][sum]]);
    printf("%d ",f[nw][sum]);
}
int main()
{
    memset(dp,0x3f,sizeof(dp)),dp[0][0]=0,get_prime(),scanf("%d",&n);
    for(int i=2;i<=58;i++)p[i]=calc(i);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)for(int j=1;j<=58;j++)for(int k=0;k<lim;k++)
    {
        if(k&p[j])continue;
        if(dp[i][k+p[j]]>dp[i-1][k]+abs(j-a[i]))
            dp[i][k+p[j]]=dp[i-1][k]+abs(j-a[i]),f[i][k+p[j]]=j;
    }
    for(int i=0;i<lim;i++)if(dp[n][i]<dp[n][ans])ans=i;
    print(n,ans);
    return 0;
}

T3-Little Pony and Summer Sun Celebration

给一个无向图,n个点m条边,给定一个01序列,如果a[i]=1,要求走到这个点奇数次,否则,要求走到这个点偶数次,请你任选起点,输出满足要求的经过点的序列和序列长度,序列长度不能超过4n

解法

首先判断无解,如果图不连通,且两个块中都有要求走过奇数次的点,就无解
如果图连通,一定有解,下面给出过程
我们可以将a序列作为初始状态,每经过一次i号点,相当于a[i]^=1,目标是使a序列全部变成0
可以从一个a[root]=1的点开始走,每个点只走一次,走的路径就是一棵树,叶子节点只经过一次,其它节点经过两次
对于一个点,在回溯时,如果a[i]还是1,就要进行震荡操作,震荡操作是指对于点i回溯到fa[i]时,从fa[i]走到i再走回fa[i]的过程,经过这一操作,效果是a[i]^=1,a[fa[i]]^=1
对于回溯到root时,如果root需要震荡怎么办呢,我们可以不回溯到root,这样就相当于a[root]^=1
有人可能会问,这一定不超过4n吗?一定的
对于每一个点只走一次的情况,算上回溯的,一个点最多进队2次
而每一个点最多只会对其父节点震荡一次,多进队2个点,将这个2的贡献都算在子节点上,可以发现一个节点产生4的贡献,而且一定有节点不到4,比如root,它一定不会震荡

ac代码

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;}e[200010];
int n,m,x,y,ans,cnt,s,a[400010],head[100010];
bool vis[100010],c[100010];
void add(){e[++cnt]={y,head[x]},head[x]=cnt,e[++cnt]={x,head[y]},head[y]=cnt;}
void dfs(int u,int fa)
{
    vis[u]=1,a[++ans]=u,c[u]^=1;
    for(int i=head[u];i;i=e[i].next)
        if(!vis[e[i].to])
            dfs(e[i].to,u),a[++ans]=u,c[u]^=1;
    if(c[u]){a[++ans]=fa,c[fa]^=1,a[++ans]=u,c[u]^=1;}
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)scanf("%d%d",&x,&y),add();
    for(int i=1;i<=n;i++){cin >> c[i];if(c[i])s=i;}
    if(s){dfs(s,-1);for(int i=1;i<=n;i++)if(!vis[i]&&c[i]){puts("-1");return 0;}}
    if(ans>1&&a[ans-1]==-1)ans-=3;
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++)printf("%d ",a[i]);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20190510
T1-Little Pony and Expected Maximum 暮暮刚刚在和她的朋友——AJ(苹果杰克)、FS(小蝶)、RD(云宝黛西)玩Ludo游戏。但是她马品没攒够总是输。回到城堡过后,她对游戏用的骰子产生了…
扫描二维码继续阅读
2019-05-10
功能