hgoi#20190510

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

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.0i)/(1.0n),m)-power((1.0(i-1))/(1.0n),m))(1.0i);
    printf("%.8lfn",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],dp110,f110;
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-pf[nw]);
    printf("%d ",fnw);
}
int main()
{
    memset(dp,0x3f,sizeof(dp)),dp0=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(dpi]>dpi-1+abs(j-a[i]))
            dpi]=dpi-1+abs(j-a[i]),fi]=j;
    }
    for(int i=0;i<lim;i++)if(dpn<dpn)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("%dn",ans);
    for(int i=1;i<=ans;i++)printf("%d ",a[i]);
    return 0;
}