A - Treasure Chest (abc299 a)
題目大意
給定一個包含 |*.的字串，其中|兩個，*一個，問*是否在兩個|之間，
解題思路
找到兩個|的下標\(l, r\)以及 *的下標\(mid\)，看看是否滿足 \(l < mid < r\)即可，
神奇的代碼
#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;
int l = s.find('|'), r = s.find('|', l + 1), m = s.find('*');
if (m > l && m < r)
cout << "in" << '\n';
else
cout << "out" << '\n';
return 0;
}
B - Trick Taking (abc299 b)
題目大意
給定\(n\)個人的卡片，顏色為 \(c_i\)，數字為 \(r_i\)，
如果其中有顏色為 \(T\)的牌，則該顏色中數字最大的卡片對應的人贏，如果沒有，則顏色為第一個人的卡牌顏色（即\(c_0\)）中數字最大的卡片對應的人贏，
問誰贏，
解題思路
按照題意的兩種情況，分別判斷即可，
神奇的代碼
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, t;
cin >> n >> t;
int maxx = 0;
int win = 0;
bool ok = false;
vector<int> c(n);
for(int i = 0; i < n; ++ i){
cin >> c[i];
ok |= (c[i] == t);
}
if (!ok)
t = c[0];
for(int i = 0; i < n; ++ i){
int r;
cin >> r;
if (c[i] == t){
if (maxx < r){
maxx = r;
win = i;
}
}
}
cout << win + 1 << '\n';
return 0;
}
C - Dango (abc299 c)
題目大意
定義一種字串\(s\)的等級\(X\)（是一個正整數）， 滿足僅包含 -o，且頭或尾僅一處為-，其余都為o，其等級\(X\)為 o的數量，
給定一個字串\(T\)，問其子串的最大等級，
解題思路
依次遍歷字串\(T\)，遇到兩個 -時期間就有一個等級，
然后再考慮從頭到第一個-的子串，從最后一個-到尾的子串的等級，
注意單純的一個-并不是合法的（\(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;
string s;
cin >> n >> s;
int la = 0;
int ans = 0;
for(int i = 0; i < n; ++ i){
if (s[i] == '-'){
ans = max(ans, i - la);
la = i;
}
}
if (int pos = s.find('-'); pos != string::npos){
ans = max(ans, n - la);
ans = max(ans, pos + 1);
}
if (ans == 1)
ans = 0;
cout << ans - 1 << '\n';
return 0;
}
D - Find by Query (abc299 d)
題目大意
互動題，
這里有個長度為\(n\)的\(01\)字串 \(s\) ，其中\(s_1 = 0, s_n = 1\) ，
你可以詢問\(s_i\)的值，
輸出一個位置 \(p\)滿足 \(s_p \neq s_{p + 1}\)，
給定字串長度\(n\)，你最多問20次， \(n \leq 2 \times 10^5\)，
解題思路
感覺好像和某次 \(cf\)的互動題很像，
注意題意保證了\(s_1 = 0, s_n = 1\)，
首先詢問中間位置\(mid = \frac{n}{2}\)，如果\(s_{mid} = 1\)，由于\(s_n = 1\)，最壞情況很有可能這后半部份都是 \(1\)，顯然我們不該去問，但因為 \(s_1 = 0, s_{mid} = 1\)，所以前半部份必定有一處\(s_p = 0, s_{p + 1} = 1\)， 反之\(s_{mid} = 0\)的情況同理，
這樣，通過一次詢問，我們可以把答案保證存在的區間砍半了，那最多砍 \(\log n\)次就找到結果了，由于 \(n \leq 2 \times 10^5\)，所以不會超過\(20\)次，
神奇的代碼
#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;
int l = 1, r = n;
while(l + 1 < r){
int mid = (l + r) >> 1;
cout << "? " << mid << endl;
int ok;
cin >> ok;
if (ok)
r = mid;
else
l = mid;
}
cout << "! " << l << endl;
return 0;
}
E - Nearest Black Vertex (abc299 e)
題目大意
給定一張圖，要求給點涂黑白色，要求至少有一個黑點，且滿足\(k\)個要求，
每個 要求 \((p_i, d_i)\)表示點 \(p_i\)距離黑點的最近距離恰好為 \(d_i\)，
點數、邊數 \(\leq 2000\)
解題思路
注意邊數只有\(2000\)，
我們可以對每個要求的 \(p_i\)進行 \(BFS\)，把距離其小于 \(d\)的點都標記為白色，
然后再對每個要求的 \(p_i\)進行 \(BFS\)，把距離其為\(d\)的且未被標記為白色的點標記為黑色，
如果有個要求沒有找到可以被涂黑色的點，就無解了，
神奇的代碼
#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 = 0; i < m; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edge[u].push_back(v);
edge[v].push_back(u);
}
int k;
cin >> k;
vector<int> forbid(n);
vector<int> col(n);
vector<array<int, 2>> rule(k);
auto BFS = [&](int s, int d){
if (d == 0)
return;
vector<int> dis(n, -1);
queue<int> team;
dis[s] = 0;
team.push(s);
while(!team.empty()){
int u = team.front();
forbid[u] = 1;
team.pop();
for(auto &v : edge[u]){
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (dis[v] < d)
team.push(v);
}
}
};
for(auto &[p, d] : rule){
cin >> p >> d;
-- p;
BFS(p, d);
}
bool ok = true;
auto paint = [&](int s, int d){
vector<int> dis(n, -1);
queue<int> team;
dis[s] = 0;
team.push(s);
while(!team.empty()){
int u = team.front();
team.pop();
if (!forbid[u] && dis[u] == d){
col[u] = 1;
return true;
}
for(auto &v : edge[u]){
if (dis[v] != -1)
continue;
dis[v] = dis[u] + 1;
if (dis[v] <= d)
team.push(v);
}
}
return false;
};
for(auto &[p, d] : rule){
ok &= paint(p, d);
}
if (!ok)
cout << "No" << '\n';
else{
cout << "Yes" << '\n';
if (k == 0)
col[0] = 1;
for(auto &i : col)
cout << i;
cout << '\n';
}
return 0;
}
F - Square Subsequence (abc299 f)
題目大意
給定一個字串\(s\)，問有多少個串 \(t\)，滿足 \(tt\)是 \(s\)的一個子序列，
解題思路
首先不考慮拼接，即問字串\(s\)中本質不同的子序列數量，這個難點在于如何不算重，一個方法就是規定一種子序列映射到字串的方式，
容易想到的就是最近匹配，就是判斷字串\(t\)是不是字串 \(s\)的子序列時，對依次對每個 \(t_i\)進行最近的匹配，能匹配\(s_j\)就匹配上 ，我們就按照這個方式去計算，每個本質不同的子序列就只算到一次，
即設 \(dp[i]\)表示以 \(i\)結尾的本質不同的子序列數量，設 \(pos\)表示最大的 \(j\)滿足 \(j < i\)且 \(s_{pos} == s_i\)，那么 \(dp[i] = \sum_{j = pos}^{i} dp[j]\)
同樣，我們可以按照此方式解決算重問題，從上述問題轉到這個問題，一個自然的想法是設\(dp[i][j]\)表示串 \(tt\)中，前一個 \(t\)的末尾在 \(i\)，后一個 \(t\)的末尾在 \(j\)（顯然有 \(s_i == s_j\)）的子串數量，
為方便敘述，設 \(tt\)為 \(t_1 t_2\) ，即\(T_{10}T_{11}..T_{1n}T_{20}T_{21}...T_{2n}\)，\(nxt(i, j)\)表示 \(s_i\)后第一個 字符是 \(j\)的位置，
考慮初始狀態，如果我們列舉第一個字母是\(k\)的話，那么 \(i = nxt(0, k)\)，而 \(j\)的話感覺難以確定，它可以在任意的 \(a_j = k\)處，區別可能是串 \(t\)的長度不同，因此我們得列舉\(j\)的位置，
確定了初始狀態 \(dp[i][j] = 1\)后，然后就列舉下一個字母 \(k\)，由于采取的是最近匹配的原則，那么下一個匹配位置就分別是 \(nxt(i, k)\)和 \(nxt(j, k)\)，即 \(dp[nxt(i, k)][nxt(j,k)] += dp[i][j]\)，轉移式子即為此，
最后累計答案時，因為采取最近匹配的原則，我們只對滿足 \(nxt(x, s_{i}) = j\)的 \(dp[x][y]\)（ \(y \geq j\)即可）進行累加，
總的來說，就是設\(dp[i][j][k]\)表示 \(t_2\)開頭在 \(s_i\)， \(t_1\)末尾在\(s_j\)， \(t_2\) 末尾在\(s_k\)的方案數，
轉移式子 \(dp[i][nxt(j, c)][nxt(k, c)] += dp[i][j][k]\)，
答案\(ans = \sum_{i = 1}^{n} \sum_{nxt(j, s_i) == i} \sum_{k = i}^{n} dp[i][j][k]\)
總的時間復雜度是 \(O(n^3)\)
神奇的代碼
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
cin >> s;
int n = s.size();
vector<array<int, 26>> nxt(n);
array<int, 26> pos;
pos.fill(-1);
for(int i = n - 1; i >= 0; -- i){
nxt[i] = pos;
pos[s[i] - 'a'] = i;
}
int ans = 0;
for(int st = 1; st < n; ++ st){
vector<vector<int>> dp(n, vector<int>(n, 0));
int first = s[st] - 'a';
int l = pos[first], r = st;
dp[l][r] = 1;
for(int i = l; i < r; ++ i)
for(int j = r; j < n; ++ j){
for(int k = 0; k < 26; ++ k){
int nl = nxt[i][k], nr = nxt[j][k];
if (nl == -1 || nr == -1 || nl >= r)
continue;
dp[nl][nr] += dp[i][j];
if (dp[nl][nr] >= mo)
dp[nl][nr] -= mo;
}
}
for(int i = l; i < r; ++ i)
for(int j = r; j < n; ++ j){
if (nxt[i][first] == r){
ans += dp[i][j];
if (ans >= mo)
ans -= mo;
}
}
}
cout << ans << '\n';
return 0;
}
G - Minimum Permutation (abc299 g)
題目大意
給定一個長度為\(n\)，僅包含數字 \(1 \sim m\)的陣列\(a\)，問其字典序最小的一個子序列，是一個排序，
解題思路
從左到右依次考慮陣列\(a\)，對于當前的數字\(a_i\)，一個樸素的想法是，選不選它，如果不選它，剩下的序列還能不能組成一個排列，如果不能，則一定要選它，那問題就剩下如何判斷能不能組成，以及如果不一定選擇，該怎么辦，
能不能組成一個排列，就是看剩下序列的數字包不包含還沒選擇的數，設還沒選擇的數為\(left\)，
然后對于不是一定要選的數，我們可以先存起來，這樣就有一個由滿足要求的\(a_i\)組成的候選集合，
繼續往右遍歷，會遇到第一個不滿足要求的位置\(a_r\)，此時可以從候選集合里選數字最小的數，放到答案里，此時\(left\)就少了一個數，
因為\(left\)是判斷某個數是不是一定要選的條件，當\(left\)少一時，說明這個條件變得更容易滿足，因此\(a_r\)可能會滿足，因此可以繼續往右邊遍歷，往候選集合里添加新的數，而之前滿足要求的還是滿足，
由此就回圈就可以得到最終答案了，
神奇的代碼
#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<int> a(n);
vector<int> cnt(m + 1);
int ok = 0;
auto add = [&](int x, int val){
if (cnt[x] == 0)
ok ++;
cnt[x] += val;
};
auto sub = [&](int x, int val){
cnt[x] -= val;
if (cnt[x] == 0)
ok --;
};
for(auto &i : a){
cin >> i;
add(i, 1);
}
vector<int> ans;
vector<int> used(m + 1, 0);
priority_queue<array<int, 2>> candidate;
int target = m;
int l = -1;
for(int i = 0; i < n; ++ i){
if (used[a[i]])
continue;
if (ok != target){
while(-candidate.top()[1] < l || used[-candidate.top()[0]])
candidate.pop();
int val = -candidate.top()[0];
int pos = -candidate.top()[1];
ans.push_back(val);
used[val] = 1;
l = pos;
if (cnt[val])
sub(val, cnt[val]);
candidate.pop();
-- i;
-- target;
continue;
}
sub(a[i], 1);
candidate.push({-a[i], -i});
}
while(ans.size() < m){
int val = -candidate.top()[0];
int pos = -candidate.top()[1];
candidate.pop();
if (pos < l || used[val])
continue;
ans.push_back(val);
used[val] = 1;
l = pos;
}
for(int i = 0; i < m; ++ i){
cout << ans[i] << ' ';
}
cout << '\n';
return 0;
}
賽后發現是道原題，去年的時候做過，
當時的思路更樸素，首先把第一個數\(a_0\)放入答案末尾，然后依次考慮之后的每個數\(a_i\)和答案的末尾的數 \(ans_{back}\)比較，如果 \(a_i < ans_{back}\)，且之后還有一個 \(a_j(j > i) == ans_{back}\)的話，那么當前的 \(ans_{back}\)可以扔掉（仍能保證后續能構造出一個排列），一直扔掉直到\(a_i > ans_{back}\)或者不存在 \(a_j(j > i) == ans_{back}\)，此時把 \(a_i\)放到答案末尾，
然后依次考慮就可以了，時間復雜度是\(O(n)\)的，
簡短的代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 8;
int a[N], cnt[N];
bool used[N];
int ans[N], cur;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> m >> n;
for(int i = 1; i <= m; ++ i){
cin >> a[i];
cnt[a[i]] ++;
}
cur = 0;
for(int i = 1; i <= m; ++ i){
cnt[a[i]] --;
if (used[a[i]])
continue;
while (cur > 0 && cnt[ans[cur]] && ans[cur] >= a[i]){
used[ans[cur]] = false;
-- cur;
}
++ cur;
ans[cur] = a[i];
used[a[i]] = true;
}
for(int i = 1; i <= n; ++ i)
cout << ans[i] << " \n"[i == n];
return 0;
}
Ex - Dice Sum Infinity (abc299 h)
題目大意
<++>
解題思路
<++>
神奇的代碼
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550947.html
標籤：其他
下一篇：返回列表