链接：https://ac.nowcoder.com/acm/contest/634/B

来源：牛客网

题目描述

给出\(n\)条线段，第\(i\)条线段的长度为\(a_i\)，每次可以从第\(i\)条线段的j位置跳到第\(i + 1\)条线段的\(j+1\)位置。如果第\(i+1\)条线段长度不到\(j+1\)，那么就会回到第\(i\)条线段的\(0\)位置，然后继续跳。

问从第\(i\)条线段的\(0\)位置跳到第\(n\)条线段需要跳多少次

为了减少输入量，a数组将由以下方式得到

unsigned int SA, SB, SC;

 int mod;

 unsigned int Rand(){

 SA ^= SA << 16;

 SA ^= SA >> 5;

 SA ^= SA << 1;

 unsigned int t = SA;

 SA = SB;

 SB = SC;

 SC ^= t ^ SA;

 return SC;

 }

 int main() {

 cin>>n>>mod>>SA>>SB>>SC;

 for(int i = 1;i <= n;++i) a[i] = Rand() % mod + 1;

 }

输入描述:

第一行两个正整数\(n,mod\)，表示一共有\(n\)条线段

第二行\(3\)个数字，分别为\(SA,SB,SC\)

输出描述:

一行一个数字，表示从每条线段跳到\(n\)的次数之和。

示例1

输入

5 5

5 6 4

输出

13

备注:

\(1\leq n \leq 2 \times 10^7\)

\(1 \leq mod \leq 6662333\)

思路

首先我们可以计算出如果没有回到第\(i\)条线段\(0\)位置这个操作的次数和：\(ans=n\times (n-1)/2\)

然后我们只需找出需要跳回\(0\)位置的点的位置\(i\)，在位置\(i\)之前的点都需要多一次跳的操作，所以需要加上\(i-1\)次

代码

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=3e7+10;

// const int mod=1e9+7;

const int maxm=1e3+10;

using namespace std;

unsigned int SA, SB, SC;

int mod,n;

int a[maxn];

unsigned int Rand()

{

    SA ^= SA << 16;

    SA ^= SA >> 5;

    SA ^= SA << 1;

    unsigned int t = SA;

    SA = SB;

    SB = SC;

    SC ^= t ^ SA;

    return SC;

}

int main(int argc, char const *argv[])

{

    #ifndef ONLINE_JUDGE

        freopen("/home/wzy/in.txt", "r", stdin);

        freopen("/home/wzy/out.txt", "w", stdout);

        srand((unsigned int)time(NULL));

    #endif

    ios::sync_with_stdio(false);

    cin.tie(0);

    cin>>n>>mod>>SA>>SB>>SC;

    for(int i = 1;i <= n;++i) a[i] = Rand() % mod + 1;

    // 如果不回到0，有多少

    ll ans=1LL*(n-1)*n/2;

    int res=a[n];

    // 从后往前查找，

    for(int i=n-1;i>=1;i--)

    {

        res--;

        res=min(res,a[i]);

        if(!res)

        {

            ans+=(i-1);

            res=a[i];

        }

    }

    cout<<ans<<endl;

    #ifndef ONLINE_JUDGE

        cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

    #endif

    return 0;

}

巴特西

牛客练习赛44 B：小y的线段

题目描述

输入描述:

输出描述:

备注:

思路

代码

最新文章

热门文章