題干：

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

Summer vacation is coming and Mark has returned home from his university having successfully survived the exam week. Today, he is very bored. So his friend Alice challenges him to play a game with stones which is invented by her. Alice gives Mark?N\ N?N piles of stones numbered from?1\ 1?1 to?N\ N?N, and there are aia_iai? stones in the?i\ i?i-th pile. The rules of the game are simple: Mark will try to remove all stones. In each move, Mark chooses two different non-empty piles and removes one stone from each of those two piles. Mark can perform any number of moves. If all the piles are empty after some number of moves, Mark wins the game. If he can't make a valid move but not all piles are empty, he loses the game.?Obviously, if the total number of stones is odd, then Mark is not able to win the game. So there is an additional rule: if initially, the total number of stones is odd, then Mark removes a single stone from the pile with the fewest stones before starting the game. If there are multiple piles with the smallest number of stones, Mark chooses one among them to remove a stone.

?

Mark found the optimal strategy for Alice's game very quickly and gets bored again. Also, he noticed that for some configuration of stones there is no way to win. So he challenges you to solve this problem: count the number of integer pairs (l,r)?(1≤l<r≤N)(l,r) \ (1 \le l < r \le N)(l,r)?(1≤l<r≤N) such that it is possible for Mark to win the game if the game is played using only the piles numbered from?l\ l?l to?r\ r?r.

輸入描述:

The input contains multiple cases. The first line of the input contains a single positive integer?T\ T?T, the number of cases. The first line of each case contains a single integer N?(2≤N≤300000)N \ (2 \le N \le 300000)N?(2≤N≤300000), the number of piles. The following line contains?N\ N?N space-separated integers, where the?i\ i?i-th integer denotes ai?(1≤ai≤109)a_i \ (1 \le a_i \le 10^9)ai??(1≤ai?≤109), the number of stones in the?i\ i?i-th pile. It is guaranteed that the sum of?N\ N?N over all cases does not exceed?1000000\ 1000000?1000000.

輸出描述:

For each case, print a single integer on a single line, the number of pairs satisfying the required property.

示例1

輸入

復(fù)制

2 3 1 1 1 4 1 2 3 4

輸出

復(fù)制

3 3

題目大意：

給你N堆石子，每堆石子中有a[i]個石子，問多少個石子區(qū)間，可以滿足：

①石子總和若為偶數(shù)，那么可以兩兩取 來自不同堆的石子各一個，重復(fù)操作，直到取完。

②如果為奇數(shù)，那么在最多石子的一堆中去掉其中一個，使得石子總和變?yōu)榕紨?shù)，然后進(jìn)入操作①。

解題報(bào)告：

對于一個區(qū)間來說，如果最大值大于除它之外其他數(shù)的和，就肯定不能清空了，反之，通過歸納證明，一定可以清空。（這一個證明好像是前幾天codeforce的一個div2B原題？）

因?yàn)檫@題轉(zhuǎn)化后的題意是這樣：求有多少個長度不小于2的連續(xù)子序列，使得其中最大元素不大于序列和的1/2。

再轉(zhuǎn)化一下題意：求：區(qū)間最大值的兩倍 小于等于 區(qū)間和的區(qū)間個數(shù)。

子序列的統(tǒng)計(jì)的題，可以考慮分治解決。

首先找到最大值的位置pos，這樣的話[L,R]= [L,pos-1] + [pos+1,R] + 跨過pos這個位置的區(qū)間個數(shù)。不難發(fā)現(xiàn)這樣分治是正確的。（和第一場那個分治做法差不多啊）

但是注意下一步統(tǒng)計(jì)跨過pos這個位置的答案的時候，要枚舉那個小區(qū)間，好像可以證明均攤復(fù)雜度是nlogn的。（我也不會證）

然后比較正確的做法就是枚舉這個小區(qū)間的每一個位置，然后對前綴和二分（因?yàn)榍熬Y和是具有單調(diào)性的，而值沒有），二分右區(qū)間的位置。如果尺取的話復(fù)雜度是不一定能保證的，詳見下面的代碼。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 3e5 + 5; int lg[MAX],f[MAX][33]; int a[MAX],n,Log[MAX]; ll sum[MAX],ans; inline void ST() {for(int i = 1; i<=n; i++) f[i][0] = i;for(int x,y,j = 1; (1<<j)<=n; j++) {for(int i = 1; i+(1<<j)-1<=n; i++) {x = f[i][j-1],y = f[i+(1<<j-1)][j-1];if(a[x] > a[y]) f[i][j] = x;else f[i][j] = y;}} } inline int gMax(int l,int r) {int k = Log[r-l+1];int x = f[l][k],y = f[r-(1<<k)+1][k];if(a[x] < a[y]) return y;else return x; } void solve(int L,int R) {if(L >= R) return ;int pos = gMax(L,R);solve(L,pos-1);solve(pos+1,R);if(pos - L + 1< R - pos + 1) {//如果左邊的數(shù)字少的話 int r = pos;for(int l = L; l<=pos; l++) {while(r <= R && sum[r] - sum[l-1] < 2*a[pos]) r++;ans += R-r+1;}// for(int l = pos; l>=L; l--) { // while(r >= pos && sum[r] - sum[l-1] >= 2*a[pos]) r--; // ans += R-r; // }}else {int l = pos;for(int r = R; r>=pos; r--) {while(l>=L && sum[r] - sum[l-1] < 2*a[pos]) l--;ans += l-L+1;}// for(int r = pos; r<=R; r++) { // while(l <= pos && sum[r] - sum[l-1] >= 2*a[pos]) l++; // ans += l-L; // }} } int main() {for(int i = 2; i<MAX; i++) Log[i] = Log[i>>1]+1;int t;cin>>t;while(t--) {scanf("%d",&n);for(int i = 1; i<=n; i++) scanf("%d",a+i),sum[i] = sum[i-1] + a[i];ST();ans = 0;solve(1,n);printf("%lld\n",ans);}return 0 ; }

TLE的代碼：

分析一下原因，其實(shí)思路都是一樣的，只是實(shí)現(xiàn)的時候他相當(dāng)于是 先移動左指針，然后看右指針最多移動到那里。我是按照一般的尺取，先移動右指針。這樣就有個問題當(dāng)他是遞減區(qū)間的時候，我這樣相當(dāng)于還是n^2的復(fù)雜度，但是他那樣的話雖然看起來也是n^2的復(fù)雜度，但是至少對于單減的序列或者單增序列復(fù)雜度都沒問題。（不過保險(xiǎn)起見這題還是寫二分比較好吧..最差復(fù)雜度保證了O(nlog^2 n)）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 3e5 + 5; int lg[MAX],f[MAX][33]; int a[MAX],n,Log[MAX]; ll sum[MAX],ans; inline void ST() {for(int i = 1; i<=n; i++) f[i][0] = i;for(int x,y,j = 1; (1<<j)<=n; j++) {for(int i = 1; i+(1<<j)-1<=n; i++) {x = f[i][j-1],y = f[i+(1<<j-1)][j-1];if(a[x] > a[y]) f[i][j] = x;else f[i][j] = y;}} } inline int gMax(int l,int r) {int k = Log[r-l+1];int x = f[l][k],y = f[r-(1<<k)+1][k];if(a[x] < a[y]) return y;else return x; } void solve(int L,int R) {if(L >= R) return ;int pos = gMax(L,R);solve(L,pos-1);solve(pos+1,R);if(pos - L + 1< R - pos + 1) {//如果左邊的數(shù)字少的話 int r = R;for(int l = pos; l>=L; l--) {while(r >= pos && sum[r] - sum[l-1] >= 2*a[pos]) r--;ans += R-r;}}else {int l = L;for(int r = pos; r<=R; r++) {while(l <= pos && sum[r] - sum[l-1] >= 2*a[pos]) l++;ans += l-L;}} } int main() {for(int i = 2; i<MAX; i++) Log[i] = Log[i>>1]+1;int t;cin>>t;while(t--) {scanf("%d",&n);for(int i = 1; i<=n; i++) scanf("%d",a+i),sum[i] = sum[i-1] + a[i];ST();ans = 0;solve(1,n);printf("%lld\n",ans);}return 0 ; }

咖啡雞的On代碼：（但是并不能看懂 先放著吧）

對于每個數(shù)都看把這個數(shù)當(dāng)成最大值得左邊界和右邊界的和，然后求是否這個區(qū)間成立。
但是這里不好統(tǒng)計(jì)有多少成立的區(qū)間，于是便反向取，即求有多少不滿足的區(qū)間。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=300005; ll a[maxn],l[maxn],r[maxn]; int main() {int t;int n,m;cin>>t;while(t--){cin>>n;ll ans=1LL*n*(n+1)/2;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){int x=0,y=0;while(i-x-1>=1&&a[i-x-1]+l[x]<a[i]){l[x+1]=l[x]+a[i-x-1];x++;}while(i+y+1<=n&&a[i+y+1]+r[y]<a[i]){r[y+1]=r[y]+a[i+y+1];y++;}for(int j=0;j<=x;j++){while(l[j]+r[y]>=a[i]) y--;ans-=y+1;}}cout<<ans<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的*【2019牛客暑期多校训练营（第三场）- G】Removing Stones（分治）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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