T2
20Pts
- (n^2)，暴力即可，注意卡常，max可以define一下
#include <bits/stdc++.h>
using namespace std;
#define max(a, b) (a) > (b) ? (a) : (b)
inline int read() {
int k = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
return k * f;
}
const int maxn = 5e5 + 100;
struct node { int a, b; } a[maxn];
int main() {
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
register int n = read(), q = read();
for (register int i = 1; i <= n; i++) a[i].a = read(), a[i].b = read();
while (q--) {
register int x = read(); register long long ans = -0x3f3f3f3f3f3f3f;
for (register int i = 1; i <= n; i++) { long long tmp = 1ll * (1ll * x * x * a[i].a + 1ll * x * a[i].b); ans = max(ans, tmp); }
printf("%lld
", ans);
}
}
40pts
- 按照数据范围(x)的(|32323|)显然比(q)的(5e5)小好多，开一个O2，题库能过，估计不开的话评测机也是可以的。
#include <bits/stdc++.h>
using namespace std;
#define max(a, b) (a) > (b) ? (a) : (b)
inline int read() {
int k = 0, f = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
return k * f;
}
const int maxn = 5e5 + 100;
struct node { int a, b; } a[maxn];
long long ans[32324];
long long absans[32324];
int main() {
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
register int n = read(), q = read();
register int x;
for (register int i = 1; i <= n; i++) a[i].a = read(), a[i].b = read();
register long long cur1, cur2, tmp1, tmp2;
for (register int j = 0; j <= 32323; j++) {
cur1 = cur2 = -0x7f7f7f7f;
for (register int i = 1; i <= n; i++) {
tmp1 = 1ll * j * j * a[i].a + 1ll * j * a[i].b;
tmp2 = 1ll * j * j * a[i].a - 1ll * j * a[i].b;
cur1 = max(cur1, tmp1), cur2 = max(cur2, tmp2);
}
ans[j] = cur1;
absans[j] = cur2;
}
while (q--) {
x = read();
if (x > 0) printf("%lld
", ans[x]);
else printf ("%lld
", absans[-x]);
}
}
T3:
- 首先第一个数据点, (n <= 5)，记忆化搜索。
- 第二个数据点，找规律：
int jc = 1, jc2 = 1;
int tmp = 0;
for (int i = n; i >= 1; i--) {
jc = 1ll * jc * i % mod;
if (i != n) jc2 = 1ll * jc2 * i % mod;
tmp = (tmp + 1ll * qpow(jc, mod - 2) * jc2 % mod * 1ll * (n - i + 1) % mod) % mod;
}
cout << tmp % mod << endl;
return 0;
- (n == 2)的时候，可以分为两种情况，第一种是不选完，这样的时候每次只可能
int x = read(), y = read();
jc[0] = ny[0] = ny[1] = jcny[0] = jcny[1] = 1;
for (int i = 1; i <= x + y; i++) jc[i] = jc[i - 1] * i % mod;
for (int i = 2; i <= x + y; i++) ny[i] = (mod - mod / i) * ny[mod % i] % mod;
for (int i = 2; i <= x + y; i++) jcny[i] = jcny[i - 1] * ny[i] % mod;
for (int i = x; i < x + y; i++) {
int a = qpow(2, i);
int b = qpow(a, mod - 2);
ans += C(i - 1, x - 1) * b % mod * i % mod;
//cout << C(i - 1, x - 1) << " " << a << endl;
}
for (int i = 0; i < x; i++) {
int a = qpow(2, i + y);
int b = qpow(a, mod - 2);
ans += C(i + y - 1, i) * b % mod * (x + y) % mod;
//cout << C(i + y - 1, i) << " " << a << endl;
}
cout << ans % mod << endl;
T4
for (int i = 1; i <= q; i++) {
int u = Q[i].u, v = Q[i].v;
int LCA = lca(u, v), d = 0;
long long ans = 0;
int dis = depth[u] + depth[v] - 2 * depth[LCA];
for (; u != fa[LCA]; u = fa[u], d++) ans += (d | a[u]);
d = 0;
for (; v != LCA; v = fa[v], d++) ans += ((dis - d) | a[v]);
printf("%lld
", ans);
}
- 当 (a_i < 2)， 的时候，因为只有偶数和 0 或的时候才会产生不一样的答案，所以使用倍增维护从每一个点 u 出发，与 u 距离为偶数并且点权为 1 的点的个数。