感覺F寫了個亂搞做法
A - Nine (abc309 A)
題目大意
給定一個\(3 \times 3\)的網格，以及兩個數字，
問這兩個數字是否水平相鄰，
解題思路
求出兩個數字的橫縱坐標，看是否橫坐標相同，縱坐標差一即可，
讀題不仔細，開題就WA了，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int a, b;
cin >> a >> b;
-- a, -- b;
if (abs(a % 3 - b % 3) == 1 && abs(a / 3 - b / 3) == 0)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Rotate (abc309 B)
題目大意
給定一個矩形，將最外圍的數字順時針旋轉一格，
解題思路
可以模擬一個指標跑，也可以分別考慮四個邊界的轉移公式，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<string> a(n);
for(auto &i : a)
cin >> i;
auto ans = a;
for(int i = 0; i < n; ++ i){
ans[0][i] = i ? a[0][i - 1]: a[1][0];
ans[i][0] = i == n - 1 ? a[n - 1][1] : a[i + 1][0];
ans[n - 1][i] = i == n - 1 ? a[n - 2][n - 1] : a[n - 1][i + 1];
ans[i][n - 1] = i ? a[i - 1][n - 1] : a[0][n - 2];
}
for(auto &i : ans){
cout << i;
cout << '\n';
}
return 0;
}
C - Medicine (abc309 C)
題目大意
給定\(n\)種藥，第 \(i\)種藥吃 \(a_i\)天，每天 \(b_i\)粒，
問最早到第幾天，吃的藥的粒數 \(\leq K\)，
解題思路
我們可以從小到大列舉天數，直到某天吃的藥的粒數\(\leq K\)，但天數高達\(O(10^9)\)，直接列舉會超時，
但是我們會發現，每天的吃的藥的粒數會越來越少，因此每天吃的藥的粒數和天數之間有單調性，
于是我們可以二分天數，判斷這一天吃的藥的粒數是否\(\leq K\)，進而排除一半的答案，搜索另一片，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k;
cin >> n >> k;
vector<array<int, 2>> a(n);
for(auto &i : a)
cin >> i[0] >> i[1];
int l = 0, r = 1e9 + 7;
auto check = [&](int x){
LL tot = 0;
for(auto &i : a){
tot += i[1] * (i[0] >= x);
}
return tot > k;
};
while(l + 1 < r){
int mid = (l + r) >> 1;
if (check(mid))
l = mid;
else
r = mid;
}
cout << r << '\n';
return 0;
}
D - Add One Edge (abc309 D)
題目大意
給定兩個連通塊，現在從這兩個連通塊中各選一個點，連一條邊，問\(1\)號點和 \(n_1+n_2\)號點的最小距離的最大值，
解題思路
很顯然，從\(1\)號點到 \(n_1+n_2\)號點，其路徑是 \(1 \to l \to r \to n_1 + n_2\)，其中\(l\)號點在第一個連通塊，\(r\)號點在第二個聯通塊，是我們選擇連邊的兩個點，其中 \(l \to r\)距離是 \(1\)，最大化總距離，那就是最大化 \(1 \to l\)和 \(r \to n_1 + n_2\)，
那就分別從\(1\)號點和 \(n_1 + n_2\)號點分別 \(BFS\)，找到最遠的距離的點，連邊即是答案，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int inf = 1e9 + 7;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n1, n2, m;
cin >> n1 >> n2 >> m;
vector<array<int, 2>> edges(m);
vector<vector<int>> e(n1 + n2);
for(int i = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edges[i] = {u, v};
e[u].push_back(i);
e[v].push_back(i);
}
vector<int> dis(n1 + n2, inf);
auto BFS = [&](int st){
dis[st] = 0;
queue<int> team;
team.push(st);
while(!team.empty()){
int u = team.front();
team.pop();
for(auto &i : e[u]){
int v = u ^ edges[i][0] ^ edges[i][1];
if (dis[v] > dis[u] + 1){
dis[v] = dis[u] + 1;
team.push(v);
}
}
}
};
BFS(0);
BFS(n1 + n2 - 1);
cout << *max_element(dis.begin(), dis.begin() + n1) + *max_element(dis.begin() + n1, dis.end()) + 1 << '\n';
return 0;
}
E - Family and Insurance (abc309 E)
題目大意
給定一棵（？或者若干棵）樹，以及\(m\)次操作，
每次操作將以\(x_i\)號點的子樹，到根距離不超過\(y_i\) 的點都加一，
問有多少個點至少加了一，
解題思路
如果將問題簡化成一條鏈，那很顯然就是個區間加問題，差分一下，每次操作就變成一個點加一，一個點減一，最后再求一遍前綴和還原陣列就解決了，
但本題是樹，與鏈的區別是，每次操作是一個點加一，很多個點減一（并且減一的點不能很快找到），
但考慮對這棵樹\(DFS\)，在某一刻，我們維護的資訊其實就是當前點到根的這條鏈，于是問題貌似就解決了？
在\(DFS\)時，實時維護上述的差分陣列和該差分陣列的和（即在搜索到該點時才考慮對該點操作的影響，影響都是對后續的影響），回溯的時候消除對該點操作影響到的差分陣列和和即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> edge(n);
for(int i = 1; i < n; ++ i){
int v;
cin >> v;
-- v;
edge[v].push_back(i);
}
int ans = 0;
vector<int> visit(n, false);
vector<int> diff(n + 1, 0);
int sum = 0;
vector<int> ins(n, 0);
for(int i = 0; i < m; ++ i){
int x, y;
cin >> x >> y;
-- x;
ins[x] = max(ins[x], y);
}
function<void(int, int)> dfs = [&](int u, int deep){
visit[u] = 1;
if (ins[u]){
++ sum;
diff[min(n, deep + ins[u] + 1)] -= 1;
}
sum += diff[deep];
if (sum)
++ ans;
for(auto &v : edge[u]){
dfs(v, deep + 1);
}
sum -= diff[deep];
if (ins[u]){
-- sum;
diff[min(n, deep + ins[u] + 1)] += 1;
}
};
for(int i = 0; i < n; ++ i){
if (!visit[i])
dfs(i, 0);
}
cout << ans << '\n';
return 0;
}
也可以用\(dp\)，設 \(dp[i]\)表示從該節點往下，保隙訓能有效多少代子孫，很顯然從父親轉移過來即可，因此從根直接 \(DFS\)求該 \(dp\)值即可，
F - Box in Box (abc309 F)
題目大意
給定\(n\)個三元組，可以交換三元組的元素的順序，
問是否存在兩個三元組，其一個三元組的三個元素都嚴格大于另一個三元組的三個元素，
解題思路
考慮二元組的做法，
如果不能交換，這就是一個典型的二維偏序問題，
如果能交換，列舉一下交換情況，可以發現在比較的時候，希望讓最大值之間比較，最小值之間比較，而不是讓一個二元組的最大值和一個二元組的最小值比較，
因此我們將二元組的元素排個序，小的在左，大的在右，然后再按第一位排序，此時可以發現用雙指標法就解決了，當然也可以用二維偏序的解法比如樹狀陣列解決，
從左到右列舉列舉一個二元組\(a_i\)，然后找到第一個 \(a_j[0] > a_i[0]\)，此時如果 \(\max_{k \geq j} a_k[1] > a_i[1]\)，那就存在兩個二元組滿足上述條件了，而\(\max_{k \geq j} a_k[1]\)就是一個后綴最大值，事先預處理一下就可以 \(O(1)\)查詢，
二維的解決了，考慮三維，
二維偏序轉到三維偏序的一個做法是\(CDQ\)分治（然后花了幾分鐘學了下\(CDQ\)分治），注意二維偏序的做法是保證一維有序的情況下處理另一維，而三維的話就是要保證兩維都有序的情況下處理第三維，
如何保證兩維都有序呢？首先我們對第一維排個序，這樣就保證了一維有序，還有一維如何保證？如果我們對整個區間的第二維排序，那么第一維有序就不一定了，
能否不對整個區間排序？而取部分的區間？
首先對于一個區間\([l, r]\)是否存在答案，根據分治，答案的分布有三種可能，要么兩個三元組都在 \([l, mid]\)，要么都在 \([mid + 1, r]\),要么一個在左區間，一個在右區間，
前兩種可能我們可以遞回解決，對于第三種可能，我們就要找到兩個區間的三元組的偏序關系，由于第一維事先排好序了，因此在總會有 \(a_i \leq a_j, i \in [l, mid], j \in [mid + 1, r]\) ，因此第一維可以忽略，此時就剩下第二維和第三維，問題就變成上述的二維問題，那么我們可以分別對\([l, mid],[mid + 1, r]\)的第二維排序，然后用上述提到的雙指標法和后綴最大值解決，
但還有個問題，注意我們的第一維的關系是\(\leq\)，而不是題目要求的嚴格小于，因此此時的第一維實際上不能忽略，萬一第一維相等就不能成為答案，但由于我們對第二維排了序，因此第一維的大小是亂序的，似乎就沒有什么規律，
細想一下，在之前的\(CDQ\)分治統計不嚴格偏序數量時，答案的正確性在于第一維關系是\(\leq\)，符合題目要求，就可以忽略這一維，而此處的 \(\leq\)并不符合題目要求，不能忽略第一維，如果強行忽略，答案可能會不正確（考慮答案的范圍就擴大成\(a_i[0] = a_j[0], a_i[1] < a_j[1], a_i[2] < a_j[2]\)），而如果能保證 \(<\)，那么答案的正確性就能保證，為了保證有\(<\)，考慮能否可以將\(mid\)設為 \(a_{mid + 1}[0] > a_{mid}[0]\)的地方？
但注意到， \(CDQ\)分治的時間復雜度是 \(O(n\log^2 n)\)，其每次分治時的\(mid = \frac{l + r}{2}\) 是一個保證復雜度的關鍵之處，這樣才保證每次分治處理的復雜度是\(f(n) + f(\frac{n}{2}) + f(\frac{n}{2}) + ...\)，而每次分治因為涉及到排序，因此 \(f(n) = n\log n\) ，
為了找一個\(mid\)使得 \(a_{mid + 1}[0] > a_{mid}[0]\)，同時又要保證復雜度，可以大膽猜想選擇\(a_{mid}[0]\)的數的最左邊或最右邊（因為對第一維排了序，相同數都在一起，因此分界點就從中間位置左右偏移一下，找到第一個\(\neq a_{mid}[0]\)之處作為分治的分界點，雖然每次分治的區間大小不一定減半，但從值域上感徑訓減半，并大膽猜想出題人不會卡，于是按此寫了寫發現過了，
如何找到從中間位置左右偏移的點，對第一維排序后預處理一下每個第一維值的最小下標和最大下標即可，
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<array<int, 3>> a(n);
for(auto &i : a){
for(auto &j : i)
cin >> j;
sort(i.begin(), i.end());
}
sort(a.begin(), a.end(), [&](const auto& x, const auto& y){
return x[0] < y[0];
});
map<int, int> posl, posr;
for(int i = n - 1; i >= 0; -- i){
posl[a[i][0]] = i;
}
for(int i = 0; i < n; ++ i){
posr[a[i][0]] = i;
}
bool ok = 0;
function<void(int, int)> solve = [&](int l, int r){
if (l >= r - 1)
return;
int mid = posl[a[(l + r) >> 1][0]];
if (mid <= l)
mid = posr[a[(l + r) >> 1][0]] + 1;
if (mid >= r)
return;
solve(l, mid);
solve(mid, r);
sort(a.begin() + l, a.begin() + mid, [&](const auto& x, const auto&y){
return x[1] < y[1];
});
sort(a.begin() + mid, a.begin() + r, [&](const auto& x, const auto&y){
return x[1] < y[1];
});
vector<int> suf(r - l);
for(int i = r - 1; i >= l; -- i){
suf[i - l] = a[i][2];
if (i < r - 1)
suf[i - l] = max(suf[i - l], suf[i - l + 1]);
}
int pos = mid;
for(int i = l; i < mid; ++ i){
while(pos < r && a[pos][1] <= a[i][1])
++ pos;
if (pos == r)
break;
if (suf[pos - l] > a[i][2])
ok = 1;
}
};
solve(0, n);
if (ok)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
G - Ban Permutation (abc309 G)
題目大意
問關于\(n\)的排列的數量，滿足 \(\forall i \in [1,n], |p_i - i| \geq x\)，
解題思路
<++>
神奇的代碼
Ex - Simple Path Counting Problem (abc309 Ex)
題目大意
<++>
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/556854.html
標籤：其他
下一篇：返回列表