[C++知识库]icpc香港G. Game Design（构造）牛客挑战 C.Rolling Girl（思维）

明天再写一下这个。

vp的时候状态不佳，思路都有了但是没人想去敲。
G. Game Design

题意：现在有个树，每个节点都有自己的权值c，在这个点如果建立一个防御塔将会产生价值为c的花费，并且防御塔会击杀所有经过其的怪物，树的叶子节点刷怪并且往根节点上走，如果有怪走到根节点的时候还未能将其击杀视为玩家任务失败。
现在要求你构造这样一棵带权数，满足让玩家完成任务且花费最小的方案数为k。

思路：一眼看上去这题应该是往二进制上靠，但是想了很多思路都是两种偏向：思路对实现不了，能实现但是发现思路不对。

最后发现可以按照类似于分解因子的做法来构造。
设目前剩余需要构造的方案数为rem，当前所在节点为now
1.rem可以被2整除的情况下，以now为根，now赋值无穷大，左子树为长度为2的链并且每个节点的权值为1，此时res除以2，并且继续以右儿子为now节点去构造。

2.rem为奇数，now赋值为当前rem二进制位的个数，左子树为长度为2的链并且每个节点的权值为1，此时res除以2，并且继续以右儿子为now节点去构造。

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=1e5+5;
int cnt,ans[N],fa[N];
int cal(int n)
{
    int cnt=0;
    while(n)
    {
        cnt++;
        n>>=1;
    }
    return cnt;
}
void DFS(int now,int sum)
{
    if(sum==1)
    {
        cnt=now;
        ans[now]=1;
        return ;
    }
    fa[now+1]=now;
    fa[now+2]=now+1;
    ans[now+2]=ans[now+1]=1;
    if(sum%2==0)
    {
        ans[now]=1e9;
        fa[now+3]=now;
        DFS(now+3,sum>>1);
    }
    else
    {
        ans[now]=cal(sum);
        fa[now+3]=now;
        DFS(now+3,sum>>1);
    }
}
signed main()
{
    int n;
    cin>>n;
    if(n==1)
    {
        cout<<2<<endl;
        cout<<1<<endl;
        cout<<1<<" "<<100<<endl;
        return 0;
    }
    DFS(1,n);
    cout<<cnt<<endl;
    for(int i=2;i<=cnt;i++)
        cout<<fa[i]<<" ";
    cout<<endl;
    for(int i=1;i<=cnt;i++)
        cout<<ans[i]<<" ";
    return 0;
}

Rolling Girl（思维）

我们仔细思考一下这个题，当弹跳距离为i的时候，假设n%i==0，那么显然他只能在i的倍数之间跳动，否则还要看是否是i是之前某个次跳跃距离为x且x满足n%x == 0的情况下的跳跃的路径中的一个点。如果是的话，应当和x取同一个值。

//晚安 wowaka
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int mod=1004535809;
const int N = 1e7+100;
unsigned p,seed;
unsigned a[N];
unsigned read()
{
    seed ^= seed << 13;
    seed ^= seed >> 5;
    seed ^= seed << 7;
    return seed % p + 1;
}
int g[N],ans[N];
vector<int> v;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin>>n;
	cin>>seed>>p;
	for(int i=1;i<=n;i++)
    {
        a[i]=read();
        g[i]=1;
    }
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            v.push_back(i);
            if(n/i!=i)
                v.push_back(n/i);
        }
    }
    sort(v.begin(),v.end());
    for(auto x:v)
    {
        unsigned minn=-1;
        for(int i=x;i<=n;i+=x)
        {
            minn>a[i]?minn=a[i]:0;
            g[i]=x;
        }
        ans[x]=(1ll*minn*(n/x))%mod;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        sum=(sum+ans[g[i]])%mod;
    }
    cout<<sum;
	return 0;
}