鏈接：https://ac.nowcoder.com/acm/contest/634/B
來源：牛客網(wǎng)

題目描述
給出n條線段，第i條線段的長度為a_ia
i
?
，每次可以從第i條線段的j位置跳到第i + 1條線段的j+1位置。如果第i+1條線段長度不到j(luò)+1，那么就會回到第i條線段的0位置，然后繼續(xù)跳。
問從第i條線段的0位置跳到第n條線段需要跳多少次
為了減少輸入量，a數(shù)組將由以下方式得到
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;
}
輸入描述:
第一行兩個正整數(shù)n,mod，表示一共有n條線段

第二行3個數(shù)字，分別為SA,SB,SC
輸出描述:
一行一個數(shù)字，表示從每條線段跳到n的次數(shù)之和。
示例1
輸入
復(fù)制
5 5
5 6 4
輸出
復(fù)制
13

思路：

假設(shè)每一個a[i] 都無限長的話， 那么ans = n * ( n-1 ) / 2

然后我們思考多出的跳躍是從哪里來的呢？

是當(dāng)如果第i+1條線段長度不到j(luò)+1，那么就會回到第i條線段的0位置，這里就會多跳一次。

那么我們可以知道，如果一個位置i，走到第j個線段會跳到0位置的話，那么i以上的所有線段都會因為i到j(luò) 之間線段長度的限制多跳躍一次， （可以畫圖理解一下。）

然后我們就可以 從后向前倒推，看那些i符合上面的情況，對答案做累加即可。

細(xì)節(jié)見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2) { ans = ans * a % MOD; } a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int *p); const int maxn = 20000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ unsigned int SA, SB, SC; int mod; int n; unsigned 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() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);cin >> n >> mod >> SA >> SB >> SC;for (int i = 1; i <= n; ++i) { a[i] = Rand() % mod + 1; }ll ans=(n*(n-1))/2;ll x=a[n];for(int i=n-1;i>=1;--i){x--;if(x>a[i]){x=a[i];// 取較小的作為限制條件}if(!x){ans+=(i-1);// 這個位置前面的每一個線段都會多跳一次。x=a[i];}}cout<<ans<<endl;return 0; }inline void getInt(int *p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}} else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11348352.html

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛44 B小y的线段 （思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。