A - Echo (abc306 a)
題目大意
給定一個字串，將每個字符輸出兩次，
解題思路
模擬即可，
神奇的代碼
#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;
string s;
cin >> n >> s;
for(auto &i : s)
cout << i << i;
cout << '\n';
return 0;
}
B - Base 2 (abc306 b)
題目大意
給定一個從低位開始的二進制串，將其轉為十進制，
解題思路
注意有\(64\)位，得用 unsigned long long，
神奇的代碼
#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);
unsigned long long ans = 0;
unsigned long long ji = 1;
for(int i = 0; i < 64; ++ i){
int x;
cin >> x;
if (x)
ans += ji;
ji <<= 1;
}
cout << ans << '\n';
return 0;
}
C - Centers (abc306 c)
題目大意
給定一個\(1 \sim n\)都出現三次的陣列 \(a\)，
定義 \(f(x)\)表示 \(x\)第二次出現在 \(a\)的位置，
按照位置的升序輸出 \(x\)，
解題思路
按照題意求出位置后，排序即可，
神奇的代碼
#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<int> pos(n, -2);
for(int i = 0; i < 3 * n; ++ i){
int x;
cin >> x;
-- x;
if (pos[x] == -2){
pos[x] = -1;
}else if (pos[x] == -1)
pos[x] = i;
}
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
sort(ans.begin(), ans.end(), [&](int a, int b){
return pos[a] < pos[b];
});
for(auto &i : ans)
cout << i + 1 << ' ';
cout << '\n';
return 0;
}
D - Poisonous Full-Course (abc306 d)
題目大意
有\(n\)個療程，分為兩種：
- 解毒療程，增加美味值 \(y\)
- 中毒療程，增加美味值 \(y\)
高橋一開始很健康，他接受了解毒療程后還是很健康，接受中毒療程就會中毒，中毒狀態下接受解毒療程就恢復健康，如果又接受中毒療程則會掛，
高橋可以跳過一些療程，問最后在他沒掛的前提下，接受療程的美味值的和的最大值，
解題思路
注意\(y\)可能會有負數，比較簡單的\(dp\)，由于中毒下接受中毒療程會掛，為保證最后我們活著，我們只需保留最后的狀態這個資訊就好了，
設 \(dp[i][0/1]\)表示考慮前 \(i\)個療程后，當前是健康/中毒狀態下的最大美味值，
根據當前狀態轉移即可，
神奇的代碼
#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;
array<LL, 2> dp{0, 0};
for(int i = 0; i < n; ++ i){
array<LL, 2> dp2{0, 0};
LL x, y;
cin >> x >> y;
if (x == 0){
dp2[0] = max(dp[0] + max(y, 0ll), dp[1] + y);
dp2[1] = dp[1];
}else{
dp2[0] = dp[0];
dp2[1] = max(dp[0] + y, dp[1]);
}
dp.swap(dp2);
}
cout << *max_element(dp.begin(), dp.end()) << '\n';;
return 0;
}
E - Best Performances (abc306 e)
題目大意
給定一個陣列\(A\)，定義其價值為前\(k\)大的數的和，
有 \(q\)次操作，每次操作令\(A_x = y\) ，
每次操作后，回答其價值，
操作是持久化的，
解題思路
用兩個\(set\)，分別維護前 \(k\)大的和剩余的數，
每次操作則修改對應的 \(set\)的值，然后比較 左邊的最小值和右邊的最大值，如果小于則交換一下這兩個數，
每次操作最多就交換兩個數，因此復雜度是\(O(q\log n)\)
神奇的代碼
#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, q;
cin >> n >> k >> q;
array<set<pair<int, int>>, 2> num;
for(int i = 0; i < k; ++ i){
num[1].insert({0, i});
}
for(int i = k; i < n; ++ i){
num[0].insert({0, i});
}
LL ans = 0;
vector<int> a(n, 0);
while(q--){
int x, y;
cin >> x >> y;
-- x;
auto token = make_pair(a[x], x);
if (num[1].count(token)){
num[1].erase(token);
num[1].insert({y, x});
ans += y - a[x];
}else{
num[0].erase(token);
num[0].insert({y, x});
}
a[x] = y;
while(num[1].size() < k){
auto l = *num[0].rbegin();
ans += l.first;
num[1].insert(num[0].extract(l));
}
while(num[1].size() > k){
auto r = *num[1].begin();
ans -= r.first;
num[0].insert(num[1].extract(r));
}
while(!num[0].empty() && num[0].rbegin() -> first > num[1].begin() -> first){
auto l = *num[0].rbegin(), r = *num[1].begin();
ans += l.first - r.first;
num[1].insert(num[0].extract(l));
num[0].insert(num[1].extract(r));
}
cout << ans << '\n';
}
return 0;
}
F - Merge Sets (abc306 f)
題目大意
對于兩個交集為空的集合\(A,B\)，定義\(f(A, B)\)為， \(A\)中每個元素在 \(A \cup B\)的位置的和，\(A \cup B\)的位置即為將其所有數升序排序后的下標（從\(1\)開始），
現給定倆倆交集均為空的\(n\)個集合 \(s_i\) ，求\(\sum_{1 \leq i < j \leq n} f(s_i, s_j)\)，
解題思路
由于\(\sum_{1 \leq i < j \leq n} f(s_i, s_j) = \sum pos(s_{i,x}, s_j)\)，分析答案的貢獻，發現可以轉換成求每個數的貢獻，因此我們的視角從列舉集合轉移到列舉每個數，
對于第\(i\)個集合的升序排列的第 \(x\)個數 \(s_{i,x}\)（此處下標均從\(0\)開始，同代碼一致），我們考慮它會對答案貢獻多少，
注意 \(i < j\)，這意味著我們只有選擇 \(j > i\)的集合 \(s_j\)時，\(s_{i,x}\) 才有貢獻，
然后考慮選擇了\(s_j\)后， \(s_{i,x}\)的是排第幾位，假設 \(s_j\)中有 \(y_j\)個小于 \(s_{i,x}\)的，那么此時 \(s_{i,x}\)的貢獻是 \(x + y_j + 1\)，然后將所有\(j > i\)的 \(s_j\)的這些貢獻累加，就是 \(s_{i,x}\)對答案的貢獻，
直接累加的復雜度是 \(O(n^2)\)，很顯然不能這樣算，
我們分析這個貢獻式子，它可以拆成三部份 \(x, y_j, 1\)，第一項和最后一項會貢獻 \(n - i - 1\)次（注意從第\(0\)集合算起），
而第二項的\(y_j\)， 我們可以把\(n \times m\)個數全部丟到陣列\(Q\)里排個序，假設\(s_{i,x}\)排在第 \(a\)位，那么 \(\sum_{j > i} y_j\)的值就是在陣列\(Q\)中，所有位置\(pos < a\)，且位于集合下標 \(j > i\)的數的個數，
顯然這是一個二維偏序問題，同abc283f一樣，我們可以用樹狀陣列維護關于集合下標的數的個數，然后從小到大遍歷\(Q\)陣列，依次把每個數加進樹狀陣列中，這樣查詢一下后綴和，就是\(\sum_{j > i} y_j\)，進而 \(s_{i, x}\)的貢獻就是 \(\sum_{j > i}y_j + (x + 1) \times (n - i - 1)\)，對于每個數依次這么計算即可，
時間復雜度為\(O(nm \log n)\)
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<int, 2>> a(n * m);
int pos = 0;
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
cin >> a[pos][0];
a[pos][1] = i;
pos ++;
}
}
sort(a.begin(), a.end(), [](const auto &x, const auto &y){
return x[0] < y[0];
});
fenwick<int> cnt(n);
LL ans = 0;
int sum = 0;
for(int i = 0; i < n * m; ++ i){
int belong = a[i][1];
int pre = cnt.get(belong - 1);
int cur = cnt.get(belong);
ans += sum - cur + 1ll * (n - belong - 1) * (cur - pre + 1);
cnt.modify(belong, 1);
sum ++;
}
cout << ans << '\n';
return 0;
}
G - Return to 1 (abc306 g)
題目大意
給定一張有向圖，問能否從\(1\)號點出發，經過 \(10^{10^{100}}\)條邊后，回到 \(1\)號點，
解題思路
<++>
神奇的代碼
Ex - Balance Scale (abc306 h)
題目大意
給定一個陣列\(A\)，
進行 \(m\)次操作，每次操作從 \(A\)中取兩個數，然后將它們的大小結果 \(> = <\)之一加入字串 \(s\)的最后，
問字串\(s\)可能的情況數量，
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/555461.html
標籤：其他
上一篇：將HTML網頁轉換為Markdown格式的工具及方法
下一篇：返回列表