A.Median

这题的数据生成方式并没有什么规律，所以可以认为是随机数据。

维护一个桶，表示当前K长区间里的值域情况。

并且用变量记录中位数值域上的左侧有多少个数，当区间调整时一并调整桶和这个变量即可。

由于是随机数据，所以每次的调整幅度并不会很大，近似于常数。

复杂度$O(n)$。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e7+2;

int n,K,bu[N<<1];

ll ans=0;

int mod,a[N],b[N];

int pr[12000000],tot;

bool vis[200000005];

void ini()

{

    for(int i=2;i<=190000000;i++)

    {

        if(!vis[i])pr[++tot]=i;

        for(int j=1;j<=tot&&i*pr[j]<=190000000;j++)

        {

            vis[i*pr[j]]=1;

            if(i%pr[j]==0)break;

        }

    }

}

int main()

{

    ini();//cout<<tot<<endl;

    scanf("%d%d%lld",&n,&K,&mod);

    for(int i=1;i<=n;i++)

        a[i]=pr[i]*1LL*i%mod,b[i]=a[i]+a[i/10+1];

    for(int i=1;i<=K;i++)

        bu[b[i]]++;

    int lpos=K-1>>1,rpos=K>>1,cnt=0;

    int p=0;

    while(cnt<=lpos)cnt+=bu[p++];

    p--;

    for(int i=1;i+K-1<=n;i++)

    {

        int _p=p,_cnt=cnt;

        while(_cnt<=rpos)_cnt+=bu[++_p];

        ans+=p+_p;

        bu[b[i]]--;bu[b[i+K]]++;

        if(b[i]<=p)cnt--;

        if(b[i+K]<=p)cnt++;

        while(cnt<=lpos)cnt+=bu[++p];

        while(cnt-bu[p]>lpos)cnt-=bu[p--];

        //cout<<p<<endl;

    }

    cout<<ans/2<<(ans&1?".5":".0")<<endl;

    return 0;

}

B.Game

显然，最优策略即每次都选自己能选的最大的。

同样维护桶，表示当前可选集合内的值域情况。维护一个变量，表示这个集合内可选最大值。

如果要保证复杂度，就应当使这个变量整个过程中在值域上的跳动幅度不超过n。

所以每当一个新数加入集合，判断它和最大值的关系，如果大于最大值就直接被选走。反之把新数加入桶，最大值被选走，暴力跳值域找到新的最大值。

很容易发现这样最大值指针是单调不增的。

时间复杂度$O(nk)$。

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

typedef long long ll;

int n,a[N],K,P,b[N],key[N],bu[N];

ll ans[2];

void work()

{

    P=read();

    ans[0]=ans[1]=0;

    int now=0;

    for(int i=1;i<=P;i++)

        bu[a[i]]++,now=max(now,a[i]);

    int p=P+1,who=0;

    bu[now]--;ans[who]+=key[now];

    while(!bu[now])now--;

    for(int t=2;t<=n;t++)

    {

        who^=1;

        if(a[p]>=now)ans[who]+=key[a[p]];

        else

        {

            bu[a[p]]++,bu[now]--,ans[who]+=key[now];

            while(!bu[now])now--;

        }

        p++;

    }

    printf("%lld\n",ans[0]-ans[1]);

}

int main()

{

//	freopen("g.in","r",stdin);

    n=read();K=read();

    for(int i=1;i<=n;i++)

        a[i]=read(),b[i]=a[i];

    sort(b+1,b+n+1);

    int len=unique(b+1,b+n+1)-b-1;

    for(int i=1;i<=n;i++)

    {

        int now=lower_bound(b+1,b+len+1,a[i])-b;

        key[now]=a[i];

        a[i]=now;

    }

    while(K--)work();

    return 0;

}

C.Park(CEOI2017 Chase)

思路很棒的dp。设$w[x]$为$x$的点权(铁球数)，$al[x]$为与$x$相连所有点的点权和。

不难发现，每选择一个点扔下磁铁，就会对答案产生$al[x]-w[fa]$的贡献。

我们要求的是一条有序路径，不妨把它分成从下往上和从上往下两部分。

设$dp[x][i][0]$为从下往上走到x，使用了i个磁铁的最大贡献，$dp[x][i][1]$为从x往下走，使用i个磁铁的最大贡献。

这样就可以区分上一步从哪里来。

之后考虑怎么dp。首先向下dfs，在回溯过程中将儿子y的贡献计入x。注意要先把$dp[x]...$初始化为单点的贡献，先用它与$dp[y]...$拼接起来更新一下答案再进行转移。

$dp[x][i][0]=\max (dp[y][i][0],dp[y][i-1][0]+al[x]-w[y])$

$dp[x][i][1]=\max (dp[y][i][1],dp[y][i-1][1]+al[x]-w[fa])$

因为路径是有序的，所以$S \rightarrow T$与$T \rightarrow S$是不同的。需要把儿子顺序反转后再更新一遍。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<stack>

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=1e5+5;

typedef long long ll;

int n,val,w[N];

int to[N<<1],head[N],nxt[N<<1],tot;

ll dp[N][102][2],al[N],ans;

//0 down to up

//1 up to down

void add(int x,int y)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

}

void up(int x,int y,int f)

{

    for(int i=1;i<val;i++)

        ans=max(ans,dp[x][i][0]+dp[y][val-i][1]);

    for(int i=1;i<=val;i++)

    {

        ll maxx=max(dp[y][i][0],dp[y][i-1][0]+al[x]-w[y]);

        dp[x][i][0]=max(dp[x][i][0],maxx);

        maxx=max(dp[y][i][1],dp[y][i-1][1]+al[x]-w[f]);

        dp[x][i][1]=max(dp[x][i][1],maxx);

    }

}

void dfs(int x,int f)

{

    stack<int> son;

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        son.push(y);

        dfs(y,x);

    }

    for(int i=1;i<=val;i++)

        dp[x][i][0]=al[x],dp[x][i][1]=al[x]-w[f];

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        up(x,y,f);

    }

    for(int i=1;i<=val;i++)

        dp[x][i][0]=al[x],dp[x][i][1]=al[x]-w[f];

    while(!son.empty())

        up(x,son.top(),f),son.pop();

    ans=max(ans,max(dp[x][val][0],dp[x][val][1]));

}

int main()

{

    n=read();val=read();

    for(int i=1;i<=n;i++)

        w[i]=read();

    for(int i=1;i<n;i++)

    {

        int x=read(),y=read();

        add(x,y);add(y,x);

    }

    for(int x=1;x<=n;x++)

        for(int i=head[x];i;i=nxt[i])

            al[x]+=w[to[i]];

    dfs(1,0);

    cout<<ans<<endl;

    return 0;

}

巴特西

[CSP-S模拟测试63]题解

A.Median

B.Game

C.Park(CEOI2017 Chase)

最新文章

热门文章