ABC D题求帮调
  • 板块灌水区
  • 楼主hhy8399
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/12/14 23:17
  • 上次更新2024/12/15 10:34:25
查看原帖
ABC D题求帮调
1179906
hhy8399楼主2024/12/14 23:17
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 1e6 + 10;

int n,s,sum,a[MAXN],k[MAXN],k1[MAXN],a2[MAXN];//k为正向前缀和,k1为逆向前缀和 

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	
	//读入 
	
	cin >> n >> s;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
		sum += a[i];
	}
	
	//前缀和预处理 
	 
	for(int i = 1;i <= n;i++) {
		k[i] = k[i - 1] + a[i];
	}
	for(int i = n,j = 1;i >= 1;i --,j++) {
		a2[j] = a[i];
	}
	for(int i = 1;i <= n;i++) {
		k1[i] = k1[i - 1] + a2[i];
	}
	
	if(s % sum == 0) {
		cout << "Yes\n";
		return 0;
	}
	
	//测试前缀和计算 
	
/*	for(int i = 1;i <= n;i++) {
		cout << k[i] << " "; 
	}
	cout << endl;
	for(int i = 1;i <= n;i++) {
		cout << k1[i] << " ";
	}
	cout << endl;
	*/
	
	//二分查找 
	
	int x = s % sum;
//	cout << x << endl;
	x = sum - x;
	for(int i = 1;i <= n;i++) {
		int y = x - k[i],l = 0,r = n + 1;
		if(y == 0) {
			cout << "Yes\n";
			return 0;
		}
		if(y < 0) {
			y  = x;
		}
//		cout << k[i] << " " << y << endl;
		while(l + 1 != r) {
			int mid = (l + r) >> 1;
			if(k1[mid] < y) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
		if(k1[r] == y) {
			cout << "Yes\n";
			return 0;
		}
	} 
	cout << "No\n";
	return 0;
}

/*
748 5590
*/

题目传送门

2024/12/14 23:17
加载中...