比赛链接

A题

判断四个数是否相同即可:

1
2
3
4
5
6
7
8
9
10
void solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
std::set<int> s{a, b, c, d};
if (s.size() == 1) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}

B题

对于边$x$,$y$,能构成三角形所能添加的最大边为$x+y-1$。累计加$n-1$次后,数列长度变为1,答案为$\sum_ia_i-n+1$。

1
2
3
4
5
6
7
8
9
void solve() {
int n;
cin >> n;
std::vector<int> a(n);
for (auto& it : a) {
cin >> it;
}
cout << std::accumulate(a.begin(), a.end(), 0) - n + 1 << "\n";
}

C题

为了确保$b<a$,我们选择初始$b=a$并且将$b$的最高位1换为0。

为了确保$(x\oplus y)+y>x$,我们选择对$x$中某位为0的位置,在$y$中对应位置,将其替换为1,这样$x\oplus y$该为也为1,相加发生进位,大于$x$。

为了确保$x+y>(x\oplus y)$,我们选择对$x$中某位(非最高位)为1的位置,在$y$中对应位置的1保留,这样$x+y$发生进位,大于$x\oplus y$。

并且可以得出,如果$x$为2的次幂或者二进制位均为1,无法得到对应的$y$。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
int x;
cin >> x;
int n = __lg(x);
if (x == (1 << n) || x == (1 << (n + 1)) - 1) {
cout << -1 << "\n";
} else {
int y = x;
y ^= 1 << n;
y ^= 1 << __builtin_ctz(~x);
cout << y << "\n";
}
}

D题

由于已知$\sum_ir_i \le 2e5$,所以枚举所有在圆内的$x$即可,对于每个圆心为$a$,半径为$r$的圆,在横坐标为$x$时,它所涵盖的$y$有$2\lfloor \sqrt{r^2-(a-x)^2}\rfloor+1$个。对于有多个圆包括的$x$值,只累加一次它能覆盖最多的$y$。

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
33
34
35
36
void solve() {
int n, m;
cin >> n >> m;
std::vector<int> x(n), r(n);
for (auto& i : x) {
cin >> i;
}
for (auto& i : r) {
cin >> i;
}

auto sqrt = [](i64 x) -> int {
int k = 0, p = 1;
while (p) {
if (1ll * (k + p) * (k + p) <= x) {
k += p;
p <<= 1;
} else {
p >>= 1;
}
}
return k;
};
std::map<int, int> mm;
for (int i = 0; i < n; i++) {
int a = x[i], ri = r[i];
for (int x = a - ri; x <= a + ri; x++) {
mm[x] = std::max(mm[x], 2 * sqrt(1ll * ri * ri - 1ll * (a - x) * (a - x)) + 1);
}
}
i64 ans = 0;
for (auto [x, y] : mm) {
ans += y;
}
cout << ans << "\n";
}

E题

随机算法,每次将得到的在三角形内部的点随机替换原来三个点的其中一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, 2);
int n;
cin >> n;
int a[3] = {1, 2, 3};
for (int i = 0, p = 0; i < 75; i++) {
cout << "? " << a[0] << " " << a[1] << " " << a[2] << std::endl;
int q;
cin >> q;
if (q == 0) {
cout << "! " << a[0] << " " << a[1] << " " << a[2] << std::endl;
return;
} else {
a[dis(gen)] = q;
}
}
cout << "! " << a[0] << " " << a[1] << " " << a[2] << std::endl;
}

F题