比赛地址：https://codeforces.com/contest/1845

这次很幸运的做出来了四个题，感觉这次D题还挺简单的吧。
这次赛题难度不大，基本上就是贪心，贪心，再贪心！

A：大意就是从1-k之间，凑出来一个和为n的数，无限供应，x不能用。

解法：当x不是1的时候，直接润1。否则，如果n为奇数可以用23凑，n为偶数可以用2凑。根据这个判断一下k的范围即可。

code：

void solve()
{
	int n,k,x;
	cin>>n>>k>>x;
	if(x!=1){
		cyes;
		cout<<n<<endl;
		for(int i=1;i<=n;i++)
			cout<<1<<' ';
		cout<<endl;
		return;
	}
	if(n==1&&x==1){
		cno;
		return;
	}
	if(n&1){
		if(k>=3){
			cyes;
			cout<<n/2<<endl;
			for(int i=1;i<=(n-3)/2;i++)
				cout<<2<<' ';
			cout<<3<<endl;
		}else cno;
		return;
	}else{
		if(k>=2){
			cyes;
			cout<<n/2<<endl;
			for(int i=1;i<=n/2;i++)
				cout<<2<<' ';
			cout<<endl;
		}else cno;
		return;
	}
	cno;
}

B：大意就是给出A,B,C的坐标，求B-A，C-A的最短路中，重合的区域最大是多少。

解法：分类讨论。判断BC坐标都在A的左上左下右上右下，其他为1.

code：

void solve()
{
	ll ax,ay,bx,by,cx,cy;
	cin>>ax>>ay>>bx>>by>>cx>>cy;
	if(bx>=ax&&cx<=ax||bx<=ax&&cx>=ax){
		if(by<=ay&&cy<=ay||by>=ay&&cy>=ay){
			cout<<min(abs(by-ay),abs(cy-ay))+1<<endl;
		}else{
			cout<<1<<endl;
		}
	}else{
		if(by>=ay&&cy>=ay||by<=ay&&cy<=ay){
			cout<<min(abs(by-ay),abs(cy-ay))+min(abs(bx-ax),abs(cx-ax))+1<<endl;
		}else{
			cout<<min(abs(bx-ax),abs(cx-ax))+1<<endl;
		}
	}
}

C：大意就是给出一个字符串s仅0-9，给出一个长度为m的两个字符串代表上下边界。求是否能够构造一个字符串不是s的子序列，且在两个字符串范围内。

解法：直接贪心。从左到右的每一位，我们都取到一个在字符串s中的最右的一个位置，找不到时为yes。

code：

void solve()
{
	string s,l,r;
	int m;
	cin>>s>>m>>l>>r;
	
	char mint = '9'+1,maxt = '0'-1;
	for(int i=s.size()-1;i>=0;i--){
		mint = min(s[i],mint),maxt = max(s[i],maxt);
		mi[i] = mint;
		mx[i] = maxt;
	}
	int p = 0;
	for(int i=0;i<m;i++){
		int mp = p;
		for(char j=l[i];j<=r[i];j++){
			int tp = p;
			while(tp<s.size()&&s[tp]!=j) tp++;
			if(tp>=s.size()){
				cyes;
				return;
			}
			mp = max(mp,tp+1);
		}
		p = mp;
	}
	cno;
}

D：大意就是给出n长度的数组。你需要累加这些数。同时当你超过k时，你可以固定一个k以内的数，使得自身下降不会低于这个数。求获得最大的所确定的k，符合条件即可。

解法：很容易让人感觉是dp。刚开始我用dp求出来了最大值，然后想通过这个值来确定反推k，但是失败了。直觉告诉我，如果一个区间段累加最小，那么在这个区间段之前就需要将它固定。所以直接倒着推一下，当sum>=0时重置sum=0，然后每次计算最小区间，记录这个区间的前缀下标。最后将这个下标之前的数全部累加就是答案。

code：

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll sum = 0;
	ll mint = LNF;
	ll l=0;
	for(int i=n;i>=1;i--){
		sum+=a[i];
		if(sum<=mint){
			l = i;
			mint = sum;
		}
		if(sum>=0) sum = 0;
		// cout<<sum<<endl;
	}
	// cout<<l<<endl;
	ll ok = l-1;
	ll ans = 0;
	for(int i=1;i<=ok;i++){
		ans+=a[i];
	}
	cout<<max(ans,0LL)<<endl;
	// ll maxt = 0;有点诈骗DP的感觉......
	// for(int i=1;i<=n;i++){
		// f[i][0] = f[i-1][0]+a[i];
		// maxt = max(f[i][0],maxt);
		// f[i][1] = max(f[i-1][1]+a[i],max(maxt,f[i][0]));
	// }
	// s[n+1] = 0;
	// ll mint = LNF;
	// ll pos = n+1;
	// for(int i=n;i>=1;i--){
		// s[i] = s[i+1]+a[i];
		// if(s[i]<mint) mint = s[i],pos = i;
	// }
	// ll ans= 0;
	// for(int i=1;i<pos;i++){
		// ans+=a[i];
	// }
	// cout<<max(0LL,ans)<<endl;
}