[补题记录]AtCoder Beginner Contest 175 D

AtCoder Beginner Contest 175 D - Moving Piece

题意：

Takahashi will play a game using a piece on an array of squares numbered (1, 2, cdots, N). Square (i) has an integer (C_i) written on it. Also, he is given a permutation of (1, 2, cdots, N): (P_1, P_2, cdots, P_N).
Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between (1) and (K) (inclusive):

In one move, if the piece is now on Square (i) ((1 leq i leq N)), move it to Square (P_i). Here, his score increases by (C_{P_i}).

Help him by finding the maximum possible score at the end of the game. (The score is (0) at the beginning of the game.)

给你两组序列(N,P)，每次对于(1)到(n)的每一个(i)你要把Square (i)移到 Square (P_i)，然后(i)的score会增长(C_{p_i})，问在这场游戏中能达到的最大score

题解：

首先(kleq 10^9)我们肯定不能模拟，按照样例推导一遍是会发现它是有循环节的，也就是说问题简化为了对于每一个(i)，有(a_1,a_1+a_2,dots,a_1+a_2+a_3+dots+a_{temp}+a_1+a_2+a_3+dots)（一共k项）中出现过的数的最大值

那么我们对于每一个(i)，把一个循环结存到ve[i]中,ve[i].size()就是循环节的大小

然后记下来(d=k/len)最多跑多少个循环节 (m=k%len) 最后一个循环节多出来多少个数

如果一个循环节的总和>0，那我们一定是要把所有的循环节跑完的

    now=d*sum[i];
    for(int j=0;j<m;j++) now+=ve[i][j],ans=max(ans,now);

还有就是如果(m==0)，那(d--;m=len;)保留最后一次循环节

如果一个循环节的总和<=0，那我们选了这个循环节还不如不选，只对(0)到(d==0?m:ve[i].size())取个最优即可

唔 貌似别忘了还要开个long long

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 9;
// typedef pair<int,int>P;

int _;

//========================================================================
ll Pp[maxn],Cc[maxn],mp[5009];
ll a[maxn],sum[maxn];
vector<ll>ve[5009];
//========================================================================
int main()
{
    ll n,k;
    ll x;
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        Pp[i]=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&x);
        Cc[i]=x;
    }
    ll ans=-1e18;
    for(ll i=1;i<=n;i++)
    {
        ll now=i;
        clean(mp,0);
        while(1)
        { 
            now=Pp[now];
            if(mp[now]==1) break;
            mp[now]=1;
            sum[i]+=Cc[now];
            ve[i].push_back(Cc[now]);
        }
        int len=ve[i].size();
        ll d=k/len;
        ll m=k%len;
        now=0;
        if(sum[i]>0) 
        {
            if(m==0) 
            {
                now=(d-1)*sum[i];
                m=len;
            }
            else now=d*sum[i];
            for(int j=0;j<m;j++) now+=ve[i][j],ans=max(ans,now);
        }
        else 
        {
            if(d==0)
            {
                for(int j=0;j<m;j++) now+=ve[i][j],ans=max(ans,now);
            }
            else 
            {
                for(int j=0;j<len;j++) now+=ve[i][j],ans=max(ans,now);
            }
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     int len=ve[i].size();
    //     for(int j=0;j<len;j++) printf("%lld ",ve[i][j]);
    //     printf("
");
    // }
    printf("%lld
",ans);
    return 0;
}