• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

NOIP 模拟 七十四

开发技术 开发技术 4小时前 2次浏览

T1 自然数

首先预处理以一为左端点所有的 mex 值,然后插入线段树中。

考虑如何修改,左端点右移一位,相当于把那一位的数删掉了,记录下一个出现这个数的位置为 pos ,那么i 到 pos 之间所有大于 x 的 mex 都要修改为 x。

剩下的就是线段树基本操作了。

#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
int n,jie,a[N];
long long ans;
int tree[N<<2],sum[N<<2],minn[N<<2],tag[N<<2],tong[N],ji,c[N],nxt[N],maxn[N<<2];
struct jj 
{int ai,id;}p[N];
inline void pushup(int x)
{   sum[x]=sum[x<<1]+sum[x<<1|1];
    minn[x]=min(minn[x<<1],minn[x<<1|1]);
    maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
}#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
int n,jie,a[N];
long long ans;
int tree[N<<2],sum[N<<2],minn[N<<2],tag[N<<2],tong[N],ji,c[N],nxt[N],maxn[N<<2];
struct jj 
{int ai,id;}p[N];
inline void pushup(int x)
{   sum[x]=sum[x<<1]+sum[x<<1|1];
    minn[x]=min(minn[x<<1],minn[x<<1|1]);
    maxn[x]=max(maxn[x<<1],maxn[x<<1|1]);
}
inline void pushdown(int x,int l,int r)
{   minn[x<<1]=minn[x<<1|1]=maxn[x<<1]=maxn[x<<1|1]=tag[x<<1]=tag[x<<1|1]=tag[x];
    int mid=(l+r)>>1;sum[x<<1]=tag[x]*(mid-l+1);sum[x<<1|1]=tag[x]*(r-mid);tag[x]=-1;
}
inline void build(int x,int l,int r)
{   if(l==r){sum[x]=minn[x]=maxn[x]=c[l];return;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    pushup(x);
}
inline int query(int x,int l,int r,int L,int R)
{   if(l>=L and r<=R)return sum[x];
    int mid=(l+r)>>1,res=0;if(tag[x]!=-1)pushdown(x,l,r);
    if(mid<R)res+=query(x<<1|1,mid+1,r,L,R);
    if(mid>=L)res+=query(x<<1,l,mid,L,R);
    return res;
}
inline void update(int x,int l,int r,int L,int R,int val)
{   if(L>R)return;
    if(l>=L and r<=R and minn[x]>=val){maxn[x]=minn[x]=val;sum[x]=val*(r-l+1);tag[x]=val;return;}
    int mid=(l+r)>>1;if(tag[x]!=-1)pushdown(x,l,r);
    if(mid<R and maxn[x<<1|1]>val)update(x<<1|1,mid+1,r,L,R,val);
    if(mid>=L and maxn[x<<1]>val)update(x<<1,l,mid,L,R,val);
    pushup(x);
}
signed main()
{   freopen("mex.in","r",stdin);
    freopen("mex.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),p[i]=(jj){a[i],i};
    int zhi=0;
    for(int i=1;i<=n;++i)
    {   if(a[i]<=n)tong[a[i]]=1;
        while(tong[zhi])++zhi;
        c[i]=zhi;
    }
    memset(tong,0,sizeof(tong));memset(tag,-1,sizeof(tag));
    for(int i=n;i;--i)if(a[i]<=n){nxt[i]=tong[a[i]];tong[a[i]]=i;} 
    build(1,1,n);
    for(int i=1;i<=n;++i)
    {   ans+=query(1,1,n,i,n);
        if(a[i]<=n)
        {   int pos=nxt[i];
            if(!pos)pos=n+1;
            update(1,1,n,i,pos-1,a[i]);  
        }
    }
    printf("%lldn",ans);
}
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    pushup(x);
}
inline int query(int x,int l,int r,int L,int R)
{   if(l>=L and r<=R)return sum[x];
    int mid=(l+r)>>1,res=0;if(tag[x]!=-1)pushdown(x,l,r);
    if(mid<R)res+=query(x<<1|1,mid+1,r,L,R);
    if(mid>=L)res+=query(x<<1,l,mid,L,R);
    return res;
}
inline void update(int x,int l,int r,int L,int R,int val)
{   if(L>R)return;
    if(l>=L and r<=R and minn[x]>=val){maxn[x]=minn[x]=val;sum[x]=val*(r-l+1);tag[x]=val;return;}
    int mid=(l+r)>>1;if(tag[x]!=-1)pushdown(x,l,r);
    if(mid<R and maxn[x<<1|1]>val)update(x<<1|1,mid+1,r,L,R,val);
    if(mid>=L and maxn[x<<1]>val)update(x<<1,l,mid,L,R,val);
    pushup(x);
}
signed main()
{   freopen("mex.in","r",stdin);
    freopen("mex.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]),p[i]=(jj){a[i],i};
    int zhi=0;
    for(int i=1;i<=n;++i)
    {   if(a[i]<=n)tong[a[i]]=1;
        while(tong[zhi])++zhi;
        c[i]=zhi;
    }
    memset(tong,0,sizeof(tong));memset(tag,-1,sizeof(tag));
    for(int i=n;i;--i)if(a[i]<=n){nxt[i]=tong[a[i]];tong[a[i]]=i;} 
    build(1,1,n);
    for(int i=1;i<=n;++i)
    {   ans+=query(1,1,n,i,n);
        if(a[i]<=n)
        {   int pos=nxt[i];
            if(!pos)pos=n+1;
            update(1,1,n,i,pos-1,a[i]);  
        }
    }
    printf("%lldn",ans);
}

T2 钱仓

贪心,一定存在中转点,一定存在一个分界点满足只向一遍运输,这个分界点就是最大子段和的起点。

#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n,c[N],sum[N],nxt[N],maxn,id,tmp,t[N],ans,old[N];
signed main()
{   freopen("barn.in","r",stdin);
    freopen("barn.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&c[i]);
    for(int i=1;i<=n;++i)
    {   tmp+=c[i];
        if(tmp<i-id)id=i,tmp=0;
    }
    ++id;
    for(int i=id;i<=n;++i)t[i-id+1]=c[i];for(int i=1;i<id;++i)t[i+n-id+1]=c[i];
    int zhi1=n;
    for(int i=n;i;--i)
    {   if(zhi1>i)zhi1=i;
        while(!t[zhi1])--zhi1;
        if(!t[i])ans+=(i-zhi1)*(i-zhi1),--t[zhi1];
    }
    printf("%lldn",ans);
}

T3 游戏

const int JBB=0;
Alice Bod 都绝顶聪明。因为他们的概率是得到自己想要的一面,而并不是固定的一面。所以我们首先来分析一下他们的策略,也就是他们到底想要干神魔。

  1. 如果本回合 A 想要正面,那么在这一回合结束之前 A 一直想要正面。

  2. 这次结果意味着下一轮的先后顺序,那么先手一定选择对他最有利的局面,也就是获胜概率最大的一个局面。

  3. 后手会选择和先手相同的策略,因为他要阻止先手获胜。

如果只剩下一个子,那么显然先手要去拿并且先手胜率大,那么两个子时先手为了保证自己是先手所以不会拿,以此类推。。。。我们得到省偶数个子时都不想拿,省奇数个子时都想拿。

于是我们接下来考虑计算拿到石子的概率,这个东西分八种,分别是谁先手想不想拿谁拿到了。

因为道理相同这里只推一个示例,A 先手,两人都想拿,A 拿到的概率。

显然为 $sumlimits _{i=0}^{+infty}p times ((1-p) times (1-q))^i$

设后面的底数为 x。

于是变为 $ptimes sumlimits_{i=0}{+infty}xi = dfrac{p}{1-x}$。

接下来设计状态转移,设f/g,i,0/1 表示谁先手,还剩几个子,最后谁赢得概率。

示例 $f_{i,0}$为 A 先手,还剩 i 个子,先手胜利的概率。

则$f_{i,0}=frac{p}{1-(1-p)times (1-q)}times g_{i-1,1}+(1-frac{p}{1-(1-p)times (1-q)}) times f_{i-1,0}$

其他的转移同理。

接下来考虑优化,我用了倍增。因为奇数偶数转移系数不同,所以我将一轮奇数偶数看成一个整体,做一半,然后再看最后是否还需要转移一步。

倍增的话就是把上述方程含义变为还剩下 $2^i$ 个石子。最后二进制拆分合并。

不得不吐槽,这傻逼题太坑了,我在考场上用肾旰了两个小时大样例,结果傻逼样例是错的,这TMD算怎么回事,dp 推出来死活不对,最后也没敢交。。。。。。。。。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int p,q,n,t,dp1[66][2],dp2[66][2],dp3[66][2],dp4[66][2],xi1[2][2],xi2[2][2],dip1[66][2],dip2[66][2];
int f[2][2];
inline int qpow(int a,int b){int base=1;while(b){if(b&1)base=base*a%mod;a=a*a%mod;b>>=1;}return base;}
signed main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    scanf("%lld",&t);
    while(t--)
    {   scanf("%lld%lld%lld",&n,&p,&q);
        p=p*qpow(100000000,mod-2)%mod;
        q=q*qpow(100000000,mod-2)%mod;
        int base1=(1-p+mod)%mod,base2=(1-q+mod)%mod;
        int ans=p*qpow((1-base1*base2%mconst int JBB=0;od+mod)%mod,mod-2)%mod;
        dp1[0][0]=xi1[0][0]=ans,dp1[0][1]=xi1[0][1]=(1-ans+mod)%mod;
        ans=q*qpow((1-base1*base2%mod+mod)%mod,mod-2)%mod;
        dp2[0][0]=xi1[1][0]=ans,dp2[0][1]=xi1[1][1]=(1-ans+mod)%mod;
        p=(1-p+mod)%mod;q=(1-q+mod)%mod;
        base1=(1-p+mod)%mod,base2=(1-q+mod)%mod;
        ans=p*qpow((1-base1*base2%mod+mod)%mod,mod-2)%mod;
        dp3[0][0]=xi2[0][0]=ans;dp3[0][1]=xi2[0][1]=(1-ans+mod)%mod;
        ans=q*qpow((1-base1*base2%mod+mod)%mod,mod-2)%mod;
        dp4[0][0]=xi2[1][0]=ans;dp4[0][1]=xi2[1][1]=(1-ans+mod)%mod;
        dip1[0][0]=(dp1[0][0]*dp3[0][1]%mod+dp2[0][1]*dp3[0][0]%mod)%mod;
        dip1[0][1]=(dp3[0][0]*dp2[0][0]%mod+dp3[0][1]*dp1[0][1]%mod)%mod;
        dip2[0][0]=(dp2[0][0]*dp4[0][1]%mod+dp1[0][1]*dp4[0][0]%mod)%mod;
        dip2[0][1]=(dp4[0][0]*dp1[0][0]%mod+dp4[0][1]*dp2[0][1]%mod)%mod;
        for(int i=1;i<=60;++i)
        {   dip1[i][0]=(dip1[i-1][0]*dip1[i-1][1]%mod+dip2[i-1][1]*dip1[i-1][0]%mod)%mod;
            dip1[i][1]=(dip2[i-1][0]*dip1[i-1][0]%mod+dip1[i-1][1]*dip1[i-1][1]%mod)%mod;
            dip2[i][0]=(dip2[i-1][0]*dip2[i-1][1]%mod+dip1[i-1][1]*dip2[i-1][0]%mod)%mod;
            dip2[i][1]=(dip1[i-1][0]*dip2[i-1][0]%mod+dip2[i-1][1]*dip2[i-1][1]%mod)%mod;
        }
        f[0][0]=0;f[0][1]=1;f[1][0]=0;f[1][1]=1;int res=n/2;
        for(int i=30;i>=0;--i)if(res>=(1<<i))
        {   res-=1<<i;int base1=f[0][0],base2=f[0][1],base3=f[1][0],base4=f[1][1];
            f[0][0]=(base1*dip2[i][1]%mod+base2*dip1[i][0]%mod)%mod;
            f[0][1]=(base1*dip2[i][0]%mod+base2*dip1[i][1]%mod)%mod;
            f[1][0]=(base3*dip1[i][1]%mod+base4*dip2[i][0]%mod)%mod;
            f[1][1]=(base3*dip1[i][0]%mod+base4*dip2[i][1]%mod)%mod;
        }
        if(n&1)f[0][0]=(dp1[0][1]*f[0][0]%mod+dp1[0][0]*f[1][1]%mod)%mod;
        printf("%lldn",f[0][0]);
    }
}

程序员灯塔
转载请注明原文链接:NOIP 模拟 七十四
喜欢 (0)