暑期集训打卡挑战 (1 / 50)#
こんにちは！コミュニティの皆さん！
夏休みが始まりました。筆者は蒻蒟 Acmer で、夏休みの 50 日間を使ってしっかりとトレーニングしようと思っています。この 50 日間、毎日自分の問題解決をアップロードする予定です。毎日の大量の練習を通じて、今後の大会で賞を獲得できることを願っています。
とても弱くて、愚かですが、この 50 日間を続けられることを願っています。
皆さん、しっかりと監視してください！
Daily Routine#
1843D#
- Timofey は、すべての果物が落ちるまで木全体を揺らします。果物は親ノードから子ノードの順に落ちます。その後、問い合わせがあり、2 つのノード間の落下状況の組み合わせの数を求めます。
分析すると、各ノードで落ちる果物の数はその子ノードの数に等しいことがわかります。落下方向は常に下向きで、上部の果物は下部の果物よりも遅れて落ち、子ノードがすべて落ちるまで親ノードは落ちません。
2 つのノードの落果の組み合わせの数は、それぞれのノードの落果の数を掛け合わせたものに等しいはずです。
#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] は i のサブノードの数を保持
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); // ルートから: 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;
}
アプローチ 2:
#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#
- 3 列の数字があり、毎回 1 列から 1 つの数字を取り出して現在の数字と AND 演算を行います。最終結果 x に到達できるかどうかを尋ねます。現在の数字は 0 から始まります。
逆推法を考えることができます。最終結果と条件を満たす数字との AND 演算の結果は、必ず最終結果自身に等しいというのが AND 演算の特性です。
したがって、現在の数字と最終結果との AND 演算の結果が同じであれば、現在の結果 7 とその数字との AND 演算を行い、最終的に結果が最終結果 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#
- 数を選ぶ 01 列を維持します。0 は現在の数字を選ばないことを示し、1 は選ぶことを示します。
この列は、ある位置 i から前後を 2 つの部分に分け、前半を後半に移動させた後、列が繰り返し単調増加することを満たす必要があります。
前の数字を記録する必要があります。最初の数字（接続位置の最初の要素、比較に使用）です。
列を遍歴する際、列の接続位置を満たす数字に出会ったら、downをマークし、後続の要素を注意深く比較します。
したがって、列の接続位置を満たす数字に出会ったときに特別な判断を開始すればよいです。列を遍歴する過程でdownをリセットする必要はありません。なぜなら、随時使用できるからであり、最適な問題を心配する必要はありません。
全体の過程で単調増加を保証します。
#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#
- 数の列が与えられ、3 人の大工がそれぞれ 1 つの数字を選びます。
各人が選んだ数字とこの列の数字との間の差を記録し、その差の合計を待機時間とし、最大待機時間を最小にします。
大工が選ぶ数字は任意で、異なっても構いません。
明らかに、最適な配分方法は、全体の数字を 3 つに分けることです。それぞれの大工に 1 つずつ。
問題のヒントは明確です：各人の最大待機時間の最小値を求めることです。
したがって、二分探索を考えます。この最小値には明らかな範囲があり、全体の答えの範囲の左半分です。
二分探索を行うと、毎回列挙される mid が単調減少し、最後に増加する瞬間に停止します。
したがって、check関数は現在のmidが大きすぎるときにtrueを返し、小さいときにfalseを返して探索を終了すべきです。
midが答えであるため、check内でこのmidに対して検証を行う必要があります。
本題では、まずmidを通じて第一と第三の大工が選ぶ数字を導き出し、これにより第二の大工が担当する範囲内の差を決定し、その値をmidと比較することで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) {
// 第二の大工の範囲外の場合は続行
if(abs(x - vall) <= mid || abs(x - valr) <= mid) continue;
l = min(l, x);
r = max(r, x);
}
return mid * 2 >= r - l;
};
// 左の範囲で探索: (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#
ある人がk個のケーキを持っている場合、$ 2^k $ 通りの組み合わせがあることになります。数学的な法則であり、この問題で言及されている二進法とは無関係です。
したがって、無限のお金がある場合、組み合わせの数は $ ans = 2 ^ k $ です。
0 から位置を記録し、各ケーキの価値は次のようになります：
前置和は 1 つのケーキを買い始めるときの費用です。k 個のケーキを買う費用は $ 2^k - 1 $ であり、$ ans = (2^k - 1) + 1 $ です。
ケーキの数 k に制限がない場合、私たちはnドルでn + 1通りのプランを購入できます。
理由は、任意のお金 x に対して、最も高価なケーキは $ 2^y \leq x $ であり、最も安価なものは購入しないことができるからです。
中間の任意の金額はケーキの価格（2 進数）で表現できます。
0 を含めると、x + 1通りの表現方法があります。
したがって、上記の 2 つのプランの最小結果が必要な答えです。
#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;
}
今日の知識点：単調キュー#
p1886#
- 長さ n のキュー上で、長さ k の区間をスライドさせ、各時点で区間の最大値と最小値を求めます。
毎回全体のキューを遍歴することはできないので、単調性を満たすストレージ構造を維持することを考えます。
新しい要素を保存するたびに、以前のキュー内の要素をチェックして比較します。最小値と最大値だけが必要なので、余分な特性を考慮する必要はありません。古い要素が新しい特性を満たさない場合は、直接削除します。
#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;
}