CF R870 div.2

P32sx-qq1309267816 / 2023-05-07 / 原文

C

输出"NO"的充要条件是要在最初就选择 \(k\) 个物品，使得 \(k \mid N\)。
发现朴素做法是 \(O(TM)\)，可以对 \(N\) 的约数进行枚举，优化为 \(O(T\sqrt(N))\)，再特判 \(N \leq M\) 和 \(N = 1\)的情况。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int T, n, m;
int main(){
	cin >> T;
	while(T --){
		scanf("%d%d", &n, &m);
		bool ans = false;
		if(m >= n) ans = true;
		for(int i = 2; i <= sqrt(n); i++)
			if(n % i == 0 && i <= m) ans = true;
		if(n == 1) ans = false;
		if(ans) puts("NO");
		else puts("YES");
	}
	return 0;
}

D

对公式进行变形:\(ans=a[l]+l+a[p]+a[r]-r\)。
发现可以枚举\(p\)，又由单调性预处理出两个数组，\(pre[i]=max(pre[i-1],a[i]+i)\)，另一个数组同理。
于是可以 \(O(N)\) 线性求解，记得多测清空数组边界值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int T, n, a[N], pre[N], ed[N];
int main(){
	cin >> T;
	while(T --){
		scanf("%d", &n);
		pre[0] = ed[n + 1] = -INF;
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		for(int i = 1; i <= n; i++)
			pre[i] = max(pre[i - 1], a[i] + i);
		for(int i = n; i; i--)
			ed[i] = max(ed[i + 1], a[i] - i);
		int ans = 0;
		for(int i = 1; i <= n; i++)
			ans = max(ans, a[i] + pre[i - 1] + ed[i + 1]);
		printf("%d\n", ans);
	}
	return 0;
}