A. Direction Change

通过镜像翻折，将目标点翻折到主对角线上

#include<bits/stdc++.h>
void solve() {
	int n,m;
	std::cin >> n >> m;
	int ans;
	if(n == 1) {
		if(m <= 2) ans = m - 1;
		else ans = -1;
	}
	else if(m == 1) {
		if(n <= 2) ans = n - 1;
		else ans = -1;
	}
	else {
		while(n + 2 <= m) n += 2;
		while(m + 2 <= n) m += 2;
		ans = m + n - 2;
	}
	std::cout << ans << '\n';
}
int main() {
}

将相近的点放在相邻位置，尽可能的让不可选位置重叠

注意数据范围 long long

#include<bits/stdc++.h>
bool solve() {
	int n,m;
	std::cin >> n >> m;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++)
		std::cin >> a[i];
	sort(a.begin(), a.end());
	long long pos = 1;
	for(int i = 0; i + 1 < n; i++) {
		pos = pos + std::max(a[i],a[i + 1]) + 1;
		if(pos > m) return false;
	}
	if(pos > m || (m - pos) < std::max(a[0],a[n - 1])) return false;
	return true;
}
int main() {
}

C. Make it Increasing

最优情况下，一定能确定有一个点的值没有改变

枚举值没改变的点

注意数据范围 long long

#include<bits/stdc++.h>
#define LL long long
void solve() {
	int n;
	std::cin >> n;
	std::vector<LL> a(n);
	for(int i = 0; i < n; i++)
		std::cin >> a[i];
	LL ans = 1e17 + 7;
	for(int i = 0; i < n; i++) {
		LL sum = 0,now;
		now = 0;
		for(int j = i - 1; j >= 0; j--) {
			LL k = now / a[j];
			if(k * a[j] <= now) k++;
			now = a[j] * k;
			sum += k;
		}
		now = 0;
		for(int j = i + 1; j < n; j++) {
			LL k = now / a[j];
			if(k * a[j] <= now) k++;
			now = a[j] * k;
			sum += k;
		}
		ans = std::min(ans,sum);
	}
	std::cout << ans << '\n';
}
int main() {
}

D. Optimal Partition

不难想到复杂度的转移方程

考虑使用数据结构优化

对于第个点，对它有贡献的满足，，考虑将单独列出去，则原方程变为在某个区间里找最大的

发现这是二维逆序，维护下标递增，通过实现前缀区间最大值查询

#include<bits/stdc++.h>
#define LL long long
std::vector<int> a,f,hash,ans;
std::vector<long long> prefix;
std::vector<std::pair<long long,int>> g;
int lowbit(int x) {
	return x & -x;
}
void add(int pos,int val) {
	int n = f.size() - 1;
	for(int x = pos; x <= n; x += lowbit(x))
		f[x] = std::max(f[x],val);
}
int ask(int pos) {
	int val = -1e7;
	for(int x = pos; x > 0; x -= lowbit(x))
		val = std::max(val,f[x]);
	return val;
}
void init(int n) {
	a.clear();a.resize(n + 1);
	ans.clear();ans.resize(n + 1);
	f.clear();f.resize(n + 1,-1e7);
	hash.clear();hash.resize(n + 1);
	prefix.clear();prefix.resize(n + 1);
	g.clear();g.resize(n);
}
void solve() {
	int n;
	std::cin >> n;
	init(n);
	for(int i = 1; i <= n; i++) {
		std::cin >> a[i];
		prefix[i] = prefix[i - 1] + a[i];
		g[i - 1] = std::make_pair(prefix[i],-i);
	}		
	std::sort(g.begin(), g.end());
	for(int i = 0; i < n; i++)
		hash[-g[i].second] = i + 1;
	for(int i = 1; i <= n; i++) {
		ans[i] = ans[i - 1] + ((a[i] > 0) ? 1 : (a[i] < 0) ? -1 : 0);
		ans[i] = std::max(ans[i],ask(hash[i] - 1) + i);
		if(prefix[i] > 0) ans[i] = i;
		add(hash[i],ans[i] - i);
	}
	std::cout << ans[n] << '\n';
}
int main() {
}

E. Half Queen Cover

比赛时想了很多乱七八糟的方法，赛后又想了一个多小时

感觉应该是将按能否整除分开讨论

整除时，会有一个点在主对角线上，负责占领边界上的那两个点，然后转移到的状态

不整除时，考虑递推的方式，开始是，然后是（横纵坐标分别加），然后是，后边还没推出来。。。

有空去研究下题解

F. Edge Elimination

挖坑

总结 & 吐槽

Rating 变化：

表现分：

Rank:

题在一些奇怪的地方卡住了，花了接近十分钟

题题比较显然，但有点着急，交之前没注意数据范围，了三次

题没想出来，想了二三十分钟就去想了。式子里面将单列出去的手法以前有见过，但比赛时没想起来。。。得练练了

题构造没想出来

总的来说，这场表现不是很好，了三次导致得分少了，如果没有的话，这次说不定能上一两分？

还得加练QAQ

这两周课程有丶多，然后期中考一堆。。。

后面几场可能不会打了，等有空再去一下，希望不要是送分场，我会心态裂开的