欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #643 (Div. 2) D. Game With Array

程序员文章站 2022-06-26 16:14:12
...

D. Game With Array

题目链接-D. Game With Array
Codeforces Round #643 (Div. 2) D. Game With Array
Codeforces Round #643 (Div. 2) D. Game With Array
题目大意
构造一个长度为nn的序列,并且nn个数的和为SS,问能不能找到一个数k[1,S]k∈[1,S],使得数组里找不出一个子序列的和为kk或者nkn-k

解题思路
贪心

  • k=1k=1,数组中的前n1n-1个元素都设为22,第nn个元素为S(n1)×2S-(n-1)×2 ,只要第nn个元素不等于11 即可,前提是n<=s/2,否则就输出NO
  • 具体操作见代码

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e5+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
inline void read(int &x){
    char t=getchar();
    while(!isdigit(t)) t=getchar();
    for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int n,s;
	cin>>n>>s;
	if(n<=s/2){
		cout<<"YES"<<endl;
		for(int i=0;i<n-1;i++){
			cout<<2<<" ";
			s-=2;
		}
		cout<<s<<endl<<1<<endl;
	}
	else
		cout<<"NO"<<endl;
	return 0;
}
相关标签: codeforces 贪心