前缀和应用

区间值为定值trick

题目链接：https://codeforces.com/contest/1915/problem/E

题意

给定一个数组a，问是否存在区间[l,r],使得该区间中奇偶下标的和相等.

题解1

    设奇数下标的前缀和为odd[i],偶数下标的前缀和为even[i],对于区间[l,r]要使得奇偶下标的和相同，即奇偶下标的前缀和相等，odd[r] - odd[l-1] = even[r] - even[l-1];
    移项化简可得，odd[r] - even[r] = odd[l-1] - even[l-1],易知，对于$i \in [0,n]$，只要有至少两个odd[i]-even[i]相等，那么该区间的奇偶下标一定相等.


Code1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int t,n,a[200010],odd[200010],even[200010];
signed main(){
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
    	cin>>n;
    	vector< int>v;
    	v.push_back(0);
    	bool flag=0;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(a[i]==0)flag=1;
    		odd[i]=odd[i-1],even[i]=even[i-1];
    		if(i&1)odd[i] += a[i];
    		else even[i] += a[i];
    		v.push_back(even[i]-odd[i]);
		}
		sort(v.begin(), v.end());
    	for(int i=0;i< n;i++){
    		if(v[i] == v[i+1])flag=1;
		}
		if(flag)cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

题解2

    奇偶下标的和相等，可以转化为奇数下标减去偶数下标的值为零。所以很明显，对于奇数下标我们照常相加，偶数下标则置负，这样就实现了”奇-偶”的区间前缀和！
    而对于一段区间内的值为零（或某一固定值），就是经典的区间前缀和trick——用map记录每个前缀和的值是否出现过，如若当前前缀和出现过，说明了当前到上一个相同值的下标所构成的区间和为零.


Code2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int t, n, a[200010];
map<int,int>mp;
signed main(){
    std::ios::sync_with_stdio(false);
    cin >> t;
    while(t--){
    	cin >> n;
    	int tot = 0;
    	bool flag = 0;
    	mp[0] = 1;
    	for(int i = 1; i <= n; i++){
    		cin >> a[i];
    		if(i & 1)tot += a[i];
    		else tot -= a[i];
    		if(mp[tot])flag=1;
    		mp[tot]++;
		}
    	if(flag)cout << "YES" << endl;
		else cout <<"NO"<< endl;
		mp.clear();	
	}
	return 0;
}

排序+前缀和

题目链接：https://ac.nowcoder.com/acm/contest/90070/D

题意

    给定$n$个正整数($a_1,a_2,…,a_n$),请问能否每次挑选若干个构成$1$ - $n$的任何整数?若能，则输出”Cool!”，反之，则输出不能构成整数的 最小值.

数据范围

  • $2 \le n \le 10^5,\sum n \le 2 \times 10^5$
  • $1 \le a_i \le 10^6$
题解

    对所有数首先进行排序，保证从小到大递增。设$pre[i]$为前$i$个能完全覆盖每个整数的区间，不难想到，遍历数组时，当前整数$a_i$如果不超过$pre[i-1]+1$，那么能覆盖的区间将 衍生到$pre[i-1]+a[i]$，也就是前缀和的总和；反之，则整数$pre[i-1]+1$没法被覆盖，也就是没有方案能够构成$pre[i-1]+1$，说明此时$pre[i]+1$就是所求的最小值 .
    最后注意，题目求的范围仅是$1-n$，当$pre[i] \ge n$时即可结束~~

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define endl '\n' 
using i64 = long long;
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<i64> pre(n + 1);
    for (int i = 1; i <= n;i++)
        cin >> a[i];
    sort(a.begin() + 1, a.end());
    if(a[1]!=1){
        cout << "1" << endl;
        return;
    }
    pre[1] = 1;
    for (int i = 2; i <= n;i++){
        if (a[i] > pre[i - 1] + 1){
            cout << pre[i - 1] + 1 << endl;
            return;
        }
        pre[i] = pre[i - 1] + a[i];
        if(pre[i]>=n)
            break;
    }
    cout << "Cool!" << endl;
}
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}