how D?
  • 板块学术版
  • 楼主wo_hen_la
  • 当前回复10
  • 已保存回复12
  • 发布时间2024/12/14 21:45
  • 上次更新2024/12/15 08:50:28
查看原帖
how D?
794701
wo_hen_la楼主2024/12/14 21:45

样例3没过,思路是先把 S mod sum[n],再二分从前往后数i个加从后往前数j个的和是否等于 S

还有 E 为什么WA*4

#include <bits/stdc++.h>
using namespace std;

#define sp putchar(' ')
#define en putchar('\n')
#define pb push_back
#define int long long
#define HP 1000000000000002097
#define umap unordered_map

int read(){ char ch=getchar();int x=0,f=1;while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f; }
void print(int x){ if(x<0) putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0'); }

const int N=2e5+5,P=998244353;

int n,m,q,k;
int a[N],sum[N],hou[N];
int s;

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=n;i>=1;i--){
		hou[i]=hou[i+1]+a[i];
	}
	for(int i=1;i<=n/2;i++) swap(hou[i],hou[n-i+1]);
	if(sum[n]>=s){
		for(int i=1;i<=n;i++){
			if(sum[i]<s) continue;
			int x=sum[i]-s;
			int id=lower_bound(sum,sum+1+n,x)-sum;
			if(sum[id]==x) return cout<<"Yes",0;
		}
		cout<<"No";
		return 0;
	}
	s=s%sum[n];
	for(int i=0;i<=n;i++){
		int x=s-sum[i];
		if(x<0) x=s;
		int id=lower_bound(hou,hou+1+n,x)-hou;
		if(hou[id]==x) return cout<<"Yes",0;
	}
	cout<<"No";
	return 0;
}






2024/12/14 21:45
加载中...