Summer Training Check-in Challenge (1 / 50)#
Hi! Everyone in the community!
The summer vacation has begun, and I am an Acmer who wants to train well during the 50 days of summer. During these 50 days, I will upload my problem solutions every day, hoping that through a lot of daily practice, I can earn a medal in the upcoming competitions.
I am very weak and quite foolish, but I hope I can persist for these 50 days.
I hope everyone will supervise me closely!
Daily Routine#
1843D#
- Timofey will shake the whole tree until all the fruits fall down, and the fruits will fall from parent nodes to child nodes. After that, queries will be given to find the number of combinations of falling fruits between two nodes.
Analysis shows that the number of falling fruits at each node equals the number of its child nodes. The falling direction is always downward, and the fruits at the upper end always fall later than those at the lower end; the parent node will only fall after all its child nodes have fallen.
The number of combinations of falling fruits between two nodes should equal the product of the number of falling fruits at each node.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
vector<vector<int>> e;
vector<i64> cnt; // cnt[i] maintain i's num of subverticles
void dfs(int u, int p) {
if(e[u].size() == 1 && e[u][0] == p) cnt[u] = 1;
else {
for(auto v : e[u]) {
if(v != p) {
dfs(v, u);
cnt[u] += cnt[v];
}
}
}
}
void solve() {
int n; cin >> n;
e.assign(n, vector<int>());
cnt.assign(n, 0);
for(int i = 0; i < n - 1; i++) {
int u, v; cin >> u >> v;
u--, v--;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(0, -1); // from head: 0
int q; cin >> q;
while (q--) {
int u, v; cin >> u >> v;
u--, v--;
cout << cnt[u] * cnt[v] << '\n';
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
Approach2:
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
void solve() {
int n; cin >> n;
vector<vector<int>> adj(n);
for(int i = 0; i < n - 1; i++) {
int a, b; cin >> a >> b;
a--, b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> cnt(n);
auto dfs = [&](auto &self, int u, int p) -> void {
if(adj[u].size() == 1 && adj[u][0] == p) cnt[u] = 1;
else {
for(auto v : adj[u]) {
if(v != p) {
self(self, v, u);
cnt[u] += cnt[v];
}
}
}
};
dfs(dfs, 0, -1);
int q; cin >> q;
while (q--) {
int a, b; cin >> a >> b;
a--, b--;
cout << 1LL * cnt[a] * cnt[b] << '\n';
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
1842B#
- Three columns of numbers, each time taking a number from one column to perform a bitwise AND operation with the current number, asking whether it is possible to achieve the final result x, starting with the current number as 0.
We can think of a reverse method; the final result ANDed with the numbers that meet the conditions must equal the final result itself, which is a property of the AND operation.
So as long as the result of the current number ANDed with the final result is the same, we can AND the current result 7 with that number and finally check if the result equals the final result xx.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
void solve() {
int n, x; cin >> n >> x;
int res = 0;
for(int i = 0; i < 3; i++) {
vector<int> a(n);
for(int j = 0; j < n; j++) cin >> a[j];
for(int j = 0; j < n; j++) {
if((x | a[j]) != x) break;
res |= a[j];
}
}
if(res == x) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
1841B#
- Let's maintain a binary sequence of selected numbers, where 0 means not selecting the current number, and 1 means selecting it.
This sequence must be able to split into two parts from some position i, and moving the front half to the back will result in a monotonically increasing sequence that can repeat.
We need to keep track of the previous number and the first number (the first element at the concatenation point for comparison).
When traversing the sequence, when encountering a number that satisfies the sequence concatenation position, we mark it with down and carefully compare the subsequent elements.
It can be thought that special judgment can begin at the position of the number that satisfies the sequence concatenation, and there is no need to reset down during the traversal of the sequence, because we can use it as needed without worrying about the optimal problem.
Throughout the process, we ensure a monotonically non-decreasing sequence.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
void solve() {
int n; cin >> n;
int a0 = -1, prev = -1;
bool down = false;
for(int i = 0; i < n; i++) {
int cur; cin >> cur;
if(i == 0) {
a0 = prev = cur;
cout << 1;
}
else if(down) {
if(cur <= a0 && cur >= prev) {
prev = cur;
cout << 1;
} else cout << 0;
}
else if(cur >= prev) {
prev = cur;
cout << 1;
}
else if(cur <= a0) {
down = true;
prev = cur;
cout << 1;
}
else cout << 0;
}
cout << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
1840D#
- Given a series of numbers, three carpenters each choose a number.
The difference between the number chosen by each person and the series of numbers is recorded, and the sum of the differences is the waiting time, aiming to minimize the maximum waiting time.
Each carpenter can choose a different number.
Clearly, the optimal allocation method is to divide the entire series of numbers into three parts, with each carpenter getting one part.
The problem hints clearly: find the minimum value of the maximum waiting time for each person.
So we consider binary search. This minimum value has a clear range, which is the left half of the range of the entire answer.
During binary search, we can find that each mid value enumerated is monotonically decreasing until it stops at the moment it increases.
Thus, our check function should return true when the current mid is too large and false when it is too small to terminate the search.
mid is the answer, so we should verify it in check.
In this problem, we can first derive the numbers chosen by the first and third carpenters based on mid, and then determine the difference values within the range for the second carpenter, comparing that value with mid to check the correctness of mid.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
void solve() {
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
auto chk = [&](int mid) {
int vall = a[0] + mid;
int valr = a[n-1] - mid;
int l = 1e9, r = 0;
for(auto x : a) {
// out of second carp's interval, continue
if(abs(x - vall) <= mid || abs(x - valr) <= mid) continue;
l = min(l, x);
r = max(r, x);
}
return mid * 2 >= r - l;
};
// search in left interval: (l + r) >> 1
int l = 0, r = 1e9;
while (l < r) {
int mid = (l + r) >> 1;
if(chk(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
1840B#
A person has k cakes, so there should be $ 2^k $ combinations, a mathematical rule unrelated to the binary system mentioned in this problem.
So it can be said that when he has unlimited money, the combination is $ ans = 2 ^ k $.
Starting from 0, the value of each cake is:
The prefix sum is the cost starting from buying 1 cake. The cost of buying k cakes is $ 2^k - 1 $, and $ ans = (2^k - 1) + 1 $.
When there is no limit on the number of cakes, with n money, we can buy n + 1 schemes.
The reason is that for any money x, the most expensive cake we can buy is $ 2^y \leq x $, and the cheapest is not to buy.
Any amount in between can be represented using cake prices (binary numbers).
Including 0, there can bex + 1representation schemes.
Therefore, when there is no limit on the number of cakes, the money he has n plus one is the total number of representation schemes $ ans = x + 1 $.
Thus, we take the minimum result of the above two schemes as the required answer.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
void solve() {
int n, k; cin >> n >> k;
k = min(k, 30);
cout << min(n, (1 << k) - 1) + 1 << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int _; cin >> _;
while (_--) solve();
return 0;
}
Today's Knowledge Point: Monotonic Queue#
p1886#
- For a queue of length n, slide a window of length k over it to find the maximum and minimum values of the interval at each moment.
Certainly, we cannot traverse the entire queue every time, so we consider maintaining a storage structure that satisfies the monotonic property.
We can check and compare the previous elements every time we store a new element. Since we only need the extreme values, we don't need to consider additional properties; when encountering old elements that do not satisfy the new property, we can directly delete them.
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << __LINE__ << " " << #x << " " << x << endl
using i64 = long long;
const int N = 100010;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k; cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1; i <= n; i++) cin >> a[i];
deque<int> q;
for(int i = 1; i <= n; i++) {
while (!q.empty() && a[q.back()] > a[i]) q.pop_back();
q.push_back(i);
if(i >= k) {
while (!q.empty() && i - q.front() >= k) q.pop_front();
cout << a[q.front()] << " ";
}
}
cout << '\n';
q.clear();
for(int i = 1; i <= n; i++) {
while (!q.empty() && a[q.back()] < a[i]) q.pop_back();
q.push_back(i);
if(i >= k) {
while (!q.empty() && i - q.front() >= k) q.pop_front();
cout << a[q.front()] << " ";
}
}
return 0;
}