A - Similar String (abc303 a)
題目大意
給定兩個字串，問這兩個字串是否相似，
兩個字串相似，需要每個字母，要么完全相同，要么一個是1一個是l，要么一個是0一個是o
解題思路
按照題意模擬即可，
可以將全部1換成l，全部0換成o，再判斷相等，
神奇的代碼
#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, t;
cin >> n >> s >> t;
replace(s.begin(), s.end(), '1', 'l');
replace(s.begin(), s.end(), '0', 'o');
replace(t.begin(), t.end(), '1', 'l');
replace(t.begin(), t.end(), '0', 'o');
if (s == t)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
B - Discord (abc303 b)
題目大意
給定m個n的排列，問有多少對\((i, j),i < j\)沒在這\(m\)個排列里作為相鄰元素出現，
解題思路
拿set記錄每個相鄰對（小的在左），然后總數減去相鄰對就是答案，
神奇的代碼
#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;
set<array<int, 2>> qwq;
auto add = [&](int x, int y){
int l = min(x, y), r = max(x, y);
qwq.insert({l, r});
};
for(int i = 0; i < m; ++ i){
int la = -1;
for(int j = 0; j < n; ++ j){
int x;
cin >> x;
if (j)
add(la, x);
la = x;
}
}
cout << n * (n - 1) / 2 - qwq.size() << '\n';
return 0;
}
C - Dash (abc303 c)
題目大意
二維迷宮，當前\((0,0)\)，生命值h，給定關于 \(LRUD\)的操作序列， 一次移動消耗一生命值，生命值為負則失敗，給定\(m\)個生命值恢復物品坐標，當生命值小于 \(k\)時可以消耗該物品，恢復生命值至\(k\)，
問能否執行完給定的操作序列，
解題思路
按照題意模擬即可，可以用set儲存物品下標，
注意物品只能用一次，所以使用的話記得erase，
神奇的代碼
#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, h, k;
string s;
cin >> n >> m >> h >> k >> s;
set<array<int, 2>> item;
for(int i = 0; i < m ; ++ i){
int x, y;
cin >> x >> y;
item.insert({x, y});
}
auto ok = [&](){
int x = 0, y = 0;
for(auto &i : s){
if (i == 'L')
x --;
else if (i == 'R')
x ++;
else if (i == 'U')
y ++;
else if (i == 'D')
y --;
else {
assert(0);
}
-- h;
auto good = item.find({x, y});
if (h < 0)
return false;
if (good != item.end() && h < k){
h = k;
item.erase(good);
}
}
return true;
};
if (ok())
cout << "Yes" << '\n';
else
cout << "No" << '\n';
return 0;
}
D - Shift vs. CapsLock (abc303 d)
題目大意
在鍵盤上輸入aA串，三個操作，一個是按鍵a，一個是按鍵Shift+a，一個是按鍵caplock，效果同正常輸入一樣，分別耗時\(x,y,z\)，
問輸入給定aA串所花費的最小時間，
解題思路
設\(dp[i][0/1]\)表示輸入完前 \(i\) 個字符，當前caplock燈不亮（亮）的最小花費時間，
然后列舉上一次燈是否亮轉移即可，注意一些特別情況，比如當前caplock燈亮的，輸入a，可以是shift+a，也可以是caplock+a+caplock，
神奇的代碼
#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);
LL x, y, z;
string s;
cin >> x >> y >> z >> s;
array<LL, 2> dp{0, z};
for(auto &i : s){
array<LL, 2> dp2{0, 0};
if (i == 'a'){
dp2[0] = min(dp[0] + min(z + y + z, x), dp[1] + min(x, y) + z);
dp2[1] = min(dp[0] + min(x, y) + z, dp[1] + min(z + x + z, y));
}else{
dp2[0] = min(dp[0] + min(z + x + z, y), dp[1] + min(x, y) + z);
dp2[1] = min(dp[0] + min(x, y) + z, dp[1] + min(z + y + z, x));
}
dp.swap(dp2);
}
cout << min(dp[0], dp[1]) << '\n';
return 0;
}
E - A Gift From the Stars (abc303 e)
題目大意
一開始有一些徑訓圖，然后隨便選了兩個度數為\(1\)的不相連通的點，連了一條邊，最終得到了一棵樹，
現給定這棵樹，還原出原來的徑訓圖，以升序告訴每個徑訓圖的邊數，
解題思路
考慮最邊緣（度數為一）的點，其相鄰點必定是徑訓圖的中心，
然后該中心旁邊的旁邊的點又是另外一個中心的旁邊點，即另一個中心與該中心的距離為3，
即我們先去掉所有度數為\(1\)的點， 然后度數變成\(1\)的點就是一個徑訓圖的中心，
再去除度數為 \(1\)的點，剩下的度數為 1的點就是上述中心的相鄰點，
再去除度數為 \(1\)的點，就相當于把最外圍的徑訓圖去掉了，局面變成了一開始的樣子，即此時再去除度數為\(1\)的點，然后度數變成 \(1\)的點就是另一個徑訓圖的中心，
因此對這棵樹作一遍拓撲排序，與最外圍（葉子）的距離 對 \(3\)取模為 \(1\)的點都是徑訓圖的中心，其邊數就是該中心原來的度數，
神奇的代碼
#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<vector<int>> edges(n);
vector<int> du(n, 0);
for(int i = 0; i < n - 1; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edges[u].push_back(v);
edges[v].push_back(u);
du[u] ++;
du[v] ++;
}
queue<int> team;
vector<int> dis(n, -1);
for(int i = 0; i < n; ++ i)
if (du[i] == 1){
dis[i] = 0;
team.push(i);
}
vector<int> ans;
while(!team.empty()){
auto u = team.front();
team.pop();
if (dis[u] % 3 == 1){
ans.push_back(edges[u].size());
}
for(auto &v : edges[u]){
if (dis[v] != -1)
continue;
du[v] --;
if (du[v] == 1){
dis[v] = dis[u] + 1;
team.push(v);
}
}
}
sort(ans.begin(), ans.end());
for(auto &i : ans)
cout << i << ' ';
cout << '\n';
return 0;
}
F - Damage over Time (abc303 f)
題目大意
一個怪物\(h\)血，你有 \(n\)個技能，每回合僅選擇一個釋放，第 \(i\)個技能可以對怪物造成持續\(t_i\)回合的傷害，每回合傷害 \(d_i\)，
問將怪物血量變為 \(0\)或以下，最少需要的回合數，
解題思路
初看此題，對于怎么選擇技能感覺比較棘手，原因在于技能是持續傷害而不是一次性的，比如一個技能持續傷害10回，但可能5回合后怪物就死了，這樣該技能實際傷害量只有一半，因此在考慮選擇技能的時候不能僅考慮\(t_i \times d_i\)的值，盡管如此，對于如何選取技能仍沒有頭緒，
細想上述的棘手點，因為持續回合不確定，導致選擇的技能實際造成的傷害是不確定的，如果我們確定了一個持續回合，比如我就打 \(x\)回合，然后看怪物的血量是否變為\(0\)或以下，那么，假設當前是第\(i\)輪的話， 我用什么技能，其實際造成的傷害是確定的，此時那我肯定是貪心地選擇造成傷害最大的一個技能，
因此可以列舉持續的回合數\(x\)，然后從第一回合考慮依次使用什么技能，但因為回合數最多高達\(10^{18}\)，因此不能列舉，但注意到回合數與怪物剩余血量之間存在單調性，因此我們可以二分這個回合數，然后計算一下怪物的血量能否變為 \(0\)或以下，
假設列舉的回合數為 \(x\)，當前處在第 \(i\)回合，也就是說接下來使用的技能傷害最多持續\(t = x - i + 1\)回合，我們考慮使用什么技能，
根據技能生效的回合數\(t_i\)與 \(d\)的關系，可以將技能分成兩類：
- 剩余回合能完整造成傷害的，即造成傷害數為\(t_i \times d_i\)（即 \(t_i \leq t\)）
- 剩余回合不能完整造成傷害的，即造成傷害數為\(t \times d_i\)（即 \(t_i > t\)）
將技能按照\(t_i\)升序排序，前一類是\(t_i \leq t\) ，我們預處理一個關于\(t_i \times d_i\)的前綴最大值，后一類因為 \(t\)是固定的，因此就要找一個滿足\(t_i > t\)最大的\(d_i\)，因此再處理一個關于\(d_i\)的后綴最大值，
對于當前回合使用的技能，就取這兩類技能中造成傷害值較大的那個，
由于回合數高達\(10^{18}\)，一回合一回合考慮會超時，因此考慮能否多回合地考慮，
如果此時傷害值較大的第一類技能，那么包括這回合之后的回合，我們肯定是一直使用這個技能（因為它始終是第一類技能（能完整造成傷害）中傷害最大的，而第二類技能的傷害會隨著\(t\)減少而更少，不會比第一類傷害值大），直到剩下的回合數不足以該技能完整造成傷害，再重新考慮，即持續使用\(cnt = t - t_i + 1\)次，造成\(cnt \times t_i \times d_i\)的傷害，之后該技能變成了第二類，
而如果傷害值較大的是第二類技能，那么包括這回合之后的回合，我們還是一直使用這個技能（因為它始終是第二類技能（不能完整造成傷害）中傷害最大的），但由于隨著不斷的使用，其造成的傷害會越來越少（剩余回合\(t\)不斷變小），因此直到其傷害值小于第一類技能的最大值，再重新考慮，即持續使用\(cnt = t - \lfloor \frac{max_1}{d_i} \rfloor\)次，造成\(d_{max} \times (t + t - 1 + t - 2 + \cdots + t - cnt + 1) = d_{max} \times \frac{(t + t - cnt + 1)cnt}{2}\)傷害，其中\(max_1\)是第一類技能造成傷害的最大值，
這樣每個技能最多考慮兩次（一次第一類，一次第二類），因此驗證的復雜度為\(O(n)\)，
總的時間復雜度就是 \(O(n\log n)\)
由于回合數有\(O(10^{18})\)，技能總傷害也有\(O(10^{18})\)，驗證時可能會超 long long范圍，因此得開__int128，
神奇的代碼
#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;
LL h;
cin >> n >> h;
vector<array<LL, 3>> spell(n); // t * d, t, d
for(auto &i : spell){
cin >> i[1] >> i[2];
i[0] = i[1] * i[2];
i[1] = -i[1];
}
sort(spell.begin(), spell.end(), [](const auto& a, const auto&b){
return a[1] > b[1]; // t, small first
});
vector<array<LL, 3>> premax(n);
premax[0] = spell[0];
for(int i = 1; i < n; ++ i){
premax[i] = max(premax[i - 1], spell[i]);
}
auto check = [&](LL x){
int pos = n - 1;
__int128 cur = h;
LL sufmax = 0;
while(cur > 0 && x > 0){
while(pos >= 0 && -premax[pos][1] > x){
sufmax = max(sufmax, spell[pos][2]);
-- pos;
}
if (pos < 0 || premax[pos][0] < __int128(1) * sufmax * x){
__int128 down = 0;
if (pos >= 0)
down = premax[pos][0] / sufmax;
__int128 cnt = x - down;
__int128 sum = cnt * (x - cnt + 1 + x) / 2 * sufmax;
cur -= sum;
x -= cnt;
}else{
__int128 cnt = x - -premax[pos][1] + 1;
cur -= cnt * premax[pos][0];
x -= cnt;
}
}
return cur <= 0;
};
LL l = 0, r = 1e18;
while(l + 1 < r){
LL mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
cout << r << '\n';
return 0;
}
G - Bags Game (abc303 g)
題目大意
<++>
解題思路
<++>
神奇的代碼
Ex - Constrained Tree Degree (abc303 h)
題目大意
給定一個集合，其元素范圍在\(1 \sim n - 1\)內，
問有多少棵\(n\)個節點的數，其每個節點的度數都屬于該集合里，
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553869.html
標籤：其他
上一篇：Kali滲透Windows服務器
下一篇：返回列表