D
题目大意：粉色士兵们在平面上绘制了 $n$ 个圆心位于 $x$ 轴上的圆。此外，他们告知这些圆的半径之和恰好为 $m$ $^{\text{∗}}$。请计算至少位于一个圆内或边界上的整数点数量。形式化地说，问题定义如下： 给定一个整数序列 $x_1, x_2, \ldots, x_n$ 和一个正整数序列 $r_1, r_2, \ldots, r_n$，已知 $\sum_{i=1}^n r_i = m$。
数据范围：$1 \le t \le 10^4$，$1 \le n \le m \le 2 \cdot 10^5$，$-10^9 \le x_i \le 10^9$，$1 \le r_i$，$\sum m \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void solve() {
int n, m;
cin >> n >> m;
vector<pll> ma(n);
rep(i, 0, n - 1) cin >> ma[i].first;
rep(i, 0, n - 1) cin >> ma[i].second;
map<ll, ll> ma2;
for (auto& [x, r] : ma) {
rep(i, x - r, x + r) {
if (!ma2.count(i)) {
ma2[i] = 2 * (int)sqrt(r * r - (x - i) * (x - i)) + 1;
} else
ma2[i] = max(ma2[i], 2LL * (int)sqrt(r * r - (x - i) * (x - i)) + 1);
}
}
ll ans = 0;
for (auto& [x, y] : ma2) ans += y;
cout << ans << endl;
return;
}
|
E
题目大意：这是一道交互题。粉色士兵们向你隐藏了 $n$ 个（$3 \le n \le 1500$）固定点 $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$，其坐标未给定。已知任意两点坐标不同，且任意三点不共线。你可以向主持人（Frontman）询问三个不同的下标 $i$、$j$、$k$。
数据范围：$1 \le t \le 20$，$3 \le n \le 1500$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int ask(int l, int r, int v) {
int op;
cout << "? " << l << ' ' << r << ' ' << v << '\n';
cout.flush();
cin >> op;
return op;
}
void report(int l, int r, int v) {
cout << "! " << l << ' ' << r << ' ' << v << '\n';
cout.flush();
}
void solve() {
int n;
cin >> n;
int x = 1, y = 2, z = 3;
while (true) {
int tem = rng() % 3;
int op = ask(x, y, z);
if (op == 0) {
report(x, y, z);
return ;
}
if (tem == 0)
x = op;
else if (tem == 1)
y = op;
else
z = op;
}
return;
}
|
F
题目大意：四叉树中每个节点对应一个正方形区域，区域边长为 $2^k$，叶子对应 $1 \times 1$ 区域。给定若干点或区域相关信息，需要按四叉树结构处理覆盖/查询。
数据范围：$1 \le t \le 10^4$，$0 \le l_i < r_i \le 10^6$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| void solve() {
ll a, b, c, d;
cin >> a >> b >> c >> d;
auto check = [&](ll l, ll r) -> vl {
vl cnt(62);
while (l < r) {
ll tem;
if (l == 0) {
tem = 63 - __builtin_clzll(r);
tem = (1LL << tem);
} else {
tem = lowbit(l);
while (tem > r - l) tem >>= 1;
}
cnt[__builtin_ctzll(tem)]++;
l += tem;
}
return cnt;
};
vl cnt1 = check(a, b);
vl cnt2 = check(c, d);
ll ans = 0;
rep(i, 0, 61) {
rep(j, 0, 61) { ans += cnt1[i] * cnt2[j] * (1LL << (abs(j - i))); }
}
cout << ans << endl;
return;
}
|
G
题目大意：Frontman 欢迎你来到这场生存游戏的最终回合。给定一个具有 $n$ 条边的正则多边形（$n \ge 3$），其顶点按顺时针顺序编号为 $1,2,\ldots,n$。每个顶点 $i$ 上被粉色士兵写有一个正整数 $a_i$。需要基于这个正则多边形进行如下定义的游戏。初始时你的得分为 $0$。你可以通过以下操作任意次来增加得分： - 选择三个未被选择过的不同顶点 $i$、$j$、$k$，并绘制这三个顶点形成的三角形。- 此时你的得分增加 $a_i \cdot a_j \cdot a_k$。- 但若该三角形与之前绘制的任意三角形存在正面积的公共区域，则不能执行此操作。
数据范围：$1 \le t \le 10^4$，$3 \le n \le 400$，$1 \le a_i \le 1000$，$\sum n^3 \le 400^3$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) a.push_back(a[i]);
vvl dp(2 * n, vl(2 * n));
rep(i, 3, n) {
rep(j, 0, 2 * n - i) {
rep(k, j, j + i - 2) dp[j][j + i - 1] = max(dp[j][j + i - 1], dp[j][k] + dp[k + 1][j + i - 1]);
rep(k, j + 1, j + i - 2) dp[j][j + i - 1] =
max(dp[j][j + i - 1], dp[j + 1][k - 1] + dp[k + 1][j + i - 2] + a[j] * a[k] * a[j + i - 1]);
}
}
ll ans = LLONG_MIN;
rep(i, 0, n - 1) ans = max(ans, dp[i][i + n - 1]);
cout << ans << endl;
return;
}
|
