BestCoder Round #9

题目链接

A：暴力枚举一个数字，就能求出另一个数字，for一遍即可

B：博弈，判断前n - 1个开头连续1的奇偶性即可

C：先预处理出每个点对应哪几个点，每次查询计算一次即可

代码：

A：

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;

int t, a, b, c;

int main() {
	scanf("%d", &t);
	while (t--) {
		int ans = 0;
		scanf("%d%d%d", &a, &b, &c);
		for (int i = 1; a * i < c; i++) {
			int bs = c - a * i;
			if (bs % b) continue;
			int tmp = bs / b;
			if (tmp <= 0) continue;
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

#include <cstdio>
#include <cstring>

const int N = 1005;

int n, a[N], t;

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		int ans = 0;
		for (int i = 0; i < n - 1; i++) {
			if (a[i] > 1) break;
			ans++;
		}
		printf("%s\n", ans % 2 ? "No" : "Yes");
	}
	return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100005;

struct Point {
	double v;
	int x, l, r, id;
	void read(int id) {
		scanf("%d%lf", &x, &v);
		this->id = id;
	}
} p[N];

bool cmp(Point a, Point b) {
	return a.x < b.x;
}

int t;
int n, m, k, to[N];

void build(int u) {
	int l = u, r = u;
	while (r - l != k) {
		if (l == 1) {
			r = k + 1;
			break;
		}
		if (r == n) {
			l = r - k;
			break;
		}
		if (p[u].x - p[l - 1].x < p[r + 1].x - p[u].x) l--;
		else if (p[u].x - p[l - 1].x > p[r + 1].x - p[u].x) r++;
		else {
			if (p[l - 1].id < p[r + 1].id) l--;
			else r++;
		}
	}
	p[u].l = l;
	p[u].r = r;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++)
			p[i].read(i);
		sort(p + 1, p + 1 + n, cmp);
		for (int i = 1; i <= n; i++) {
			to[p[i].id] = i;
			build(i);
		}
		int q;
		double ans = 0;
		while (m--) {
			scanf("%d", &q);
			int u = to[q];
			int l = p[u].l;
			int r = p[u].r;
			double sum = 0;
			for (int i = l; i <= r; i++) {
				if (u == i) continue;
				sum += p[i].v;
			}
			double add = sum / k;
			p[u].v = add;
			ans += add;
		}
		printf("%.6lf\n", ans);
	}
	return 0;
}

BestCoder Round #9