hgoi#20191108

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

T2- 能量传输

有 $n$ 个人排成一圈,每恰好相隔 $k$ 个人可以花费 $1$ 的代价传输 $1$ 的能量。 给出每个人的初始能量,为了使得每个人最终的能量都相等,输出最小代价。

解法

如果不是相隔 $k$ 个人,而是相邻的人 这题就是个环形均分纸牌 至于这玩意的解法,这里不作解释 QWQ 那相隔 $k$ 个人怎么办呢 我们考虑每次跳 $k$ 个人并以此来重构这个序列 然后对于所有重构出的序列,做一遍环形均分纸牌即可

ac 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,ans,a[500010],b[500010],f[500010];
bool tg[500010];
int calc(int a[500010],int n)
{
    int ans=0;
    for(int i=1;i<=n;i++)
        a[i]-=a[0]/n,f[i]=f[i-1]+a[i];
    sort(f+1,f+n+1);
    for(int i=1;i<=n;i++)
        ans+=abs(f[i]-f[n+1>>1]);
    return ans;
}
signed main()
{
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);
    scanf("%lld%lld",&n,&k),k++;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int st=1;st<=n;st++)if(!tg[st])
    {
        int i,nw;
        for(i=1,nw=st,b[0]=0;;i++,nw=(nw+k-1)%n+1)
            if(tg[nw])break;
            else b[i]=a[nw],tg[nw]=1,b[0]+=b[i];
        ans+=calc(b,i-1);
    }
    printf("%lldn",ans);
    return 0;
} 

T3- 矿物运输

给出一棵有 $n$ 个点的树,每一个点上面有一个权值 $val_i$ 先手和后手轮流操作,使得一个节点上 $1$ 的权值移到它的父亲节点上、 无法移动的人判负,先手胜利输出 "win" 否则输出 "lose"

解法

一个很显然的最优策略,对于偶数层,它做什么,我们做什么即可 对于奇数层,考虑到做一次就会变成偶数层的,也就是上一种情况 所以就和取石子的那种 nim 游戏一样了 将奇数层的权值 $xor$ 起来,如果有值就是 win

ac 代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>e[200010];
int T,n,x,ans,a[200010],d[200010];
void dfs(int u)
{
    for(auto v:e[u])
        d[v]=d[u]+1,dfs(v);
}
int main()
{
    freopen("ore.in","r",stdin);
    freopen("ore.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            vector<int>().swap(e[i]);
        for(int i=1;i<n;i++)
            scanf("%d",&x),e[x].pb(i);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        dfs(0),ans=0;
        for(int i=0;i<n;i++)
            if(d[i]&1)ans^=a[i];
        puts(ans?"win":"lose");
    }
    return 0;
}