竞赛地址

链接知乎版本

A. 等差数列

算下区间奇偶性，再算下开头元素第l项的奇偶性。

ll n, m;
ll k, x, y;
void solve() {
	scanf("%lld%lld%lld", &x, &k, &m);
	x = x % 2;
	k = k % 2;
	ll l, r;
	while (m--) {
		scanf("%lld%lld", &l, &r);
		
		if (!k) {
			printf("%d\n", x ? 1 : -1);
			continue;
		} else {
			r = r - l + 1;
			l = (l % 2) ? x : (1 - x);
			printf("%d\n", (r % 2) ? (l ? 1 : -1) : 0);
		}
	}
}

B. 挖坑

找规律。

首先，最少步数为l=n+3-2

其次，每次最多能增加的次数一定是偶数次：先上去一格，再下来一格。

行数固定是3，列数是n，我们可以发现， 在原来最少步数的基础上，每隔4个列，我们可以构造+2、+4个步数。

具体构造方法如下。

要+2，我们需要3个障碍物；

alt

要+4，我们需要4个障碍物。

alt

知道这个规律就可以计算了，详见代码注释。

#define debugging 0
int n, m;
int k, x, y;
void solve() {
	scanf("%d%d", &n, &k);
	// 最大能取的左右边界
	int l = n + 1, r = n + 1 + ((n - 1) / 4) * 4;
	// 除了不能超出边界，k的取值要和 l边界保持一样的奇偶性
	if (k < l || k > r || ((k & 1) ^ (l & 1))) {
		printf("-1\n");
		return;
	}
	if (debugging) {
		printf("l:%d r:%d\n", l, r);
	}
	// 需要走多少4格
	int res = (k - l) / 4 * 4;
	// 需要额外走2格的情况
	if ((k - l) % 4) {
		res += 3;
	}
	printf("%d\n", res);
}

D. 数组

二分，优先队列。

用前缀和预处理下。

先算出原始的mx,mn，

接着，把所有的右边界r都丢到最小堆里边，走m步，

每次优先取最小的r。

算出每一执行后的mn,mx，更新ans即可。

#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stack>
#include<deque> 
#include<queue>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define ll long long
#define inf 2000000009
#define pi 3.14159265358979323846
#define debugging 0
#define pii pair<int, int>
const int maxn = 200010;
const int mod = 1e9+7;

int n, m;
int k, x, y;
int c[maxn], b[maxn];
int a[maxn];
ll pre[maxn];
int l[maxn], r[maxn];
char s[maxn];
bool vis[maxn];
int dis[maxn], dis2[maxn];
vector<int> ve[maxn];

int cal(int i, int L) {
	int l = L, r = n, mid, pos = i - 1;
	ll val = 1LL * b[i] * c[i];
	while (l <= r) {
		mid = (l + r) / 2;
		if (pre[mid] - pre[i-1] <= val) {
			pos = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return pos;
}

void solve() {
	scanf("%d%d", &n, &m);
	pre[0] = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pre[i] = pre[i-1] + a[i];
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &b[i]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &c[i]);
	}
	priority_queue<pii, vector<pii>, greater<pii> > q;
	
	int mx = 0, mn = n;
	for (int i = 1; i <= n; ++i) {
		int pos = cal(i, i);
		int len = pos - i + 1;
		mx = max(mx, len);
		mn = min(mn, len);
		if (debugging) {
			printf("[%d]: %d r(%d)\n", i, len, pos);
		}
		q.push({len, i});
	}
	
	int ans = mx - mn;
	while (m--) {
		pii p = q.top();
		if (debugging) {
			printf("{%d, %d}\n", p.first, p.second);
		}
		q.pop();
		++c[p.second];
		int pos = cal(p.second, p.second + p.first - 1);
		
		int len = pos - p.second + 1;
		
		if (debugging) {
			printf("[%d]: %d r(%d)\n", p.second, len, pos);
		}
		mx = max(mx, len);
		p.first = len;
		q.push(p);
		mn = q.top().first;
		
		ans = min(ans, mx - mn);
	}
	printf("%d\n", ans);
} 
void debug() {
	
}
int main() {
	
	int t = 1, cas = 1;
//	scanf("%d", &t);
//	cin >> t;
	while (t--) {
//		debug();
//		if(debugging) printf("case :%d\n", cas++); // debug
		if (debugging) cout << "case: " << cas++ << endl;
		solve();
	}
}
/*
8 5 3
8 3
5 1
2 6
6 8
1 2
4 8
5 7
6 7

*/