BestCoder Round #9
题目链接
A：暴力枚举一个数字，就能求出另一个数字，for一遍即可
B：博弈，判断前n - 1个开头连续1的奇偶性即可
C：先预处理出每个点对应哪几个点，每次查询计算一次即可
代码：
A：
#include
#include
#include
#include
#include
#include
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; }
B：
#include
#include
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; }
C：
#include
#include
#include
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; }