CF1027F Session in BSU 题解

duel 题，居然输了 /tuu。

这个就是你考虑可以合理转换 每次只能填 $a_{i-1}+1$ 或者 $0$ 然后给定 $a_1$。然后就是你无脑 dp 维护构造的转移点。这部分的时间复杂度是 $O(n\sqrt n)$。然后构造就是前面特殊的直接美剧和后面稍微拼一下。

// Problem: Modular Sequence
// URL: https://www.luogu.com.cn/problem/CF1928E
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e5 + 10;
int f[MAX];
bool fl = 0;

int lst[MAX];

int testcase = 0;
void solve(){
	testcase++;
	int n = read(), x = read(), y = read(), s = read();
	if(testcase == 10779 and fl){
		write(n), write(x), put(), put(), write(y), put(), write(s), endl;
	}
	if(fl)	return ;
	int x2 = x % y;
	if((s - x2 * n - (x - x2)) % y){
		puts("NO");
		return ;
	}
	int lft = (s - x2 * n - (x - x2)) / y;
	if(lft < 0){
		puts("NO");
		return ;
	}
	vector <int> a;
	a.pb(x);
	int now = x / y + 1;
	if(f[lft] <= n - 1){
		while(lft){
			now = 0;	
			int prelft = lft;
			for(int i = 0; i <= lst[prelft]; i++){
				a.pb(now * y + x2);
				lft -= now;
				now++;
			}
		}
		while(a.size() < n)	a.pb(x2);
		puts("YES");
		for(int i = 0; i < n; i++)	write(a[i]), put();
		endl;
		return ;
	}else{
		for(int k = 2; k <= n; k++){
			if(now <= lft){
				a.pb(now * y + x2);
				lft -= now;
				now++;
				if(f[lft] <= (n - k)){
					while(lft){
						now = 0;	
						int prelft = lft;
						for(int i = 0; i <= lst[prelft]; i++){
							a.pb(now * y + x2);
							lft -= now;
							now++;
						}
					}
					while(a.size() < n)	a.pb(x2);
					puts("YES");
					for(int i = 0; i < n; i++)	write(a[i]), put();
					endl;
					return ;
				}
			}
			else {
				puts("NO");
				return ;
			}
		}
		puts("NO");
		return ;
	}
	
	puts("YES");
	for(int i = 0; i < n; i++)	write(a[i]), put();
	endl;
}

signed main(){
	f[0] = 0;
	for(int i = 1; i < MAX; i++){
		int pre = 0;
		f[i] = inf;
		for(int j = 1; pre <= i; j++){
			pre += j - 1;
			if(pre > i)	break;
			if(f[i] > f[i - pre] + j){
				lst[i] = j - 1;
			}	
			f[i] = min(f[i], f[i - pre] + j);
		}
	}
	int t = read();
	while(t--)	solve();
	return 0;
}
复制代码