GET

• reverse()
• ve.pop_back()
• ve.back()

A. Mishka and Contest

題意

給定一個序列表示題目的難度和Mishka的能力，問Mishka能解決幾道問題，只能從兩端解決問題。

AC

#include <bits/stdc++.h> using namespace std;int main() {int n, k;cin >> n >> k;vector<int> v(n);for (int i = 0; i < n; i++) {cin >> v[i];}int ans = 0;while (!v.empty() && v.back() <= k) {ans++;v.pop_back();}reverse(v.begin(), v.end());while (!v.empty() && v.back() <= k) {ans++;v.pop_back();}cout << ans << endl;return 0; }

B. Reversing Encryption

題意

給定一個長度為N的字符串，每次在N的除數區間 ( [1 - d] ) 進行翻轉，求原來的字符串。

AC

#include <bits/stdc++.h> using namespace std;int main() {int n;string s;cin >> n >> s;for (int i = 1; i <= n; i++) {if (n % i == 0) {reverse(s.begin(), s.begin() + i);}}cout << s << endl;return 0; }

C. Alphabetic Removals

題意

給定一個長度為N字符串和操作次數K，一共刪除K個字母，按字典序刪除第一個出現的字母，輸出剩下的字母

AC

• 用數組統計每個字符一共刪除幾個，輸出的時候進行判讀

// 數組記錄刪除個數 #include <bits/stdc++.h> using namespace std;int main() {int n, k;string s;cin >> n >> k >> s;vector<int> sum(26), d(26);for (auto c : s) {sum[c - 'a']++;}for (int i = 0; i < 26; i++) {if (k >= sum[i]) {k -= sum[i];d[i] = sum[i];}else {d[i] = k;break;}}for (auto c : s) {if (d[c - 'a'] > 0) {d[c - 'a']--;}else {cout << c;}}cout << endl;return 0; }

• 用pair，先對字典序排序，刪除K個字母之后再按小標排序

// pair #include <bits/stdc++.h> using namespace std;int main() {int n, k;string s;cin >> n >> k >> s;vector<pair<char,int>> v(n);for (int i = 0; i < n; i++) {v[i] = make_pair(s[i], i);}sort(v.begin(), v.end());sort(v.begin() + k, v.end(), [&] (const pair<char, int> &a, const pair<char, int> &b){return a.second < b.second;});for (int i = k; i < n; i++) {cout << v[i].first;}cout << endl;return 0; }

D. Equalize the Remainders

題意

給一個長度為N的序列和M，求最小的改動數使得改變后的序列的每個數對M取模，每個模都有 K = N / M 個，輸出最小改動次數和改變后的序列

AC

把原序列的每個mod的數量統計下，將數量大于K的存一下，有小于K的就補上。至少需要兩個循環

#include <bits/stdc++.h> #define N 200005 using namespace std;int main() {// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);int n, m, k;cin >> n >> m;k = n / m;vector<int> a(n);vector<vector<int>> d(m);vector<pair<int,int>> f;for (int i = 0; i < n; i++) {cin >> a[i];d[a[i] % m].push_back(i);}long long ans = 0;for (int i = 0; i < 2 * m; i++) {int cur = i % m;while(int(d[cur].size()) > k) {int elem = d[cur].back();f.push_back(make_pair(elem, i));d[cur].pop_back();}while (int(d[cur].size()) < k && !f.empty()) {int elem = f.back().first;int dif = f.back().second;ans += i - dif;a[elem] += i - dif;d[cur].push_back(elem);f.pop_back();}}cout << ans << endl;for (auto it : a) {cout << it << " ";}cout << endl;return 0; }

E. Reachability from the Capital

題意

N個點、M條邊（單向邊）、起點S。問最少加幾條邊可以使得S到大所有點

AC

• 建圖，構建每個點能到達的點的關系，將不能直接從S到達的點列舉出來，根據點點關系兩兩枚舉，如果可以到達就刪去這個點（縮邊）

#include <bits/stdc++.h> #define N 5005 #define ll long long using namespace std; int n, m, s; vector<vector<int>> G(N); bool vis[N], link[N][N]; // 找u能到達的點 void find(int u) {for (int i = 0; i < G[u].size(); ++i) {int v = G[u][i];if (!vis[v]) {vis[v] = true;find(v);}} } int main() {// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin >> n >> m >> s;for (int i = 0; i < m ; ++i) {int u, v;cin >> u >> v;G[u].push_back(v);}for (int i = 1; i <= n; ++i) {memset(vis, false, sizeof(vis));find(i);vis[i] = true;// 建圖for (int j = 1; j <= n; ++j) {if (vis[j]) link[i][j] = true;}}vector<int> ve;set<int> se;// 將不能到達的點加到vector和set中for (int i = 1; i <= n; i++) {if (!link[s][i]) {ve.push_back(i);se.insert(i);}}// 兩兩枚舉 縮邊for (int i = 0; i < ve.size(); ++i) {for (int j = i + 1; j < ve.size(); ++j) {int u = ve[i];int v = ve[j];if (link[u][v]) se.erase(v);else if(link[v][u]) se.erase(u);}}cout << se.size() << endl; }

• 統計S不能到達的點，然后統計這些點可以到達那些點的數量（同樣是S不能到達的點），從數量多的點依次加邊，并更新S可到達的邊。

#include <bits/stdc++.h> #define N 5005 #define ll long long using namespace std; int n, m, s, cnt; vector<vector<int>> G(N); bool vis[N], ok[N]; // 更新S可到達的點 void dfs1(int u) {ok[u] = true;for (auto it : G[u]) {if (!ok[it]) {dfs1(it);}} } // 統計每個不能到達的點的連通分量 void dfs2(int u) {vis[u] = true;for (auto it : G[u]) {if (!ok[it] && !vis[it]) {cnt++;dfs2(it);}} } int main() {// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);cin >> n >> m >> s;for (int i = 0; i < m ; ++i) {int u, v;cin >> u >> v;G[u].push_back(v);}dfs1(s);vector<pair<int,int>> ve;for (int i = 1; i <= n; ++i) {if (!ok[i]) {memset(vis, false, sizeof(vis));cnt = 0;dfs2(i);ve.push_back(make_pair(cnt, i));}}// 降序sort(ve.begin(), ve.end(), [&](const pair<int,int> &x, const pair<int,int> &y){return x.first > y.first;});int ans = 0;for (auto it : ve) {if (!ok[it.second]) {// 加邊ans++;// 更新S可到達的點dfs1(it.second);}}cout << ans << endl; }

F. Cards and Joy

題意

一共有N個人，每個人有K個數，給出N個人喜歡的數和K個喜好值，每個人的喜好值為K個數里包含多少個自己喜歡的數字對應的好感值，問怎么分配使得好感值最大

AC

• 關鍵是當有多個人喜歡的數字相同時怎么分配
  用dp[ x ][ y ] 表示x個人喜歡的數相同，對應有y個數
  復雜度：N^2 * k ^ 2

// 狀態轉移 for (int i = 0; i <= k; ++i) dp[x + 1][y + i] = max(dp[x + 1][y + i], dp[x][y] + h[i]) #include<bits/stdc++.h> #define mem(a, b) memset(a, b, sizeof(a)) #define P pair<int, int> #define mp(a, b) make_pair(a, b) #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <map> #include <string.h>using namespace std; const int N = 502, K = 15; const int C = 100005;// sum_t 記錄不同糖果的數量， sum_f 記錄不同喜好糖果數量 int sum_t[C], sum_f[C], h[C];// dp[x][y] 表示有x個人的喜好相同，對應的糖果一共有y個 int dp[N][K * N]; int main () {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false);int n, k;while (cin >> n >> k) {mem(sum_t, 0);mem(sum_f, 0);mem(dp, 0);mem(h, 0);for (int i = 0; i < n * k; ++i) {int x;cin >> x;++sum_t[x];}for (int i = 0; i < n; ++i) {int x;cin >> x;++sum_f[x];}for (int i = 1; i <= k; ++i) {cin >> h[i];}for (int i = 0; i < n; ++i) {for (int j = 0; j <= n * k; ++j) {for (int cur = 0; cur <= k; ++cur) {if (j + cur > n * k) continue;dp[i + 1][j + cur] = max(dp[i + 1][j + cur], dp[i][j] + h[cur]);}}}long long ans = 0;for (int i = 0; i < C; ++i) {ans += dp[sum_f[i]][sum_t[i]];}cout << ans << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Codeforces Round #490 (Div. 3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。