河北工業大學ACM集訓隊日常訓練day1030
- 2020 年 2 月 18 日
- 筆記
emmm.昨天剛到青島.今天熱身賽結束.非常想記錄的一點就是.這個酒店太豪了.早餐特別豪.還有浴池.orz.要加油努力賺錢買大房子呀.補了一下題.記錄一下.
題目大意:
easy~
題解:
easy~
#include <bits/stdc++.h> using namespace std; int n, k; int a[110]; int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); while(cin >> n >> k){ for(int i = 1; i <= n; ++i) cin >> a[i]; int ans = 0; int i; for(i = 1; i <= n; ++i){ if(a[i] <= k) ++ans; else break; } for(int j = n; j > i; --j){ if(a[j] <= k) ++ans; else break; } cout << ans << endl; } return 0; }
C.Alphabetic Removals
題目大意:
easy~
題解:
easy~
#include <bits/stdc++.h> using namespace std; const int MAX_N = 4*1e5+100; int n,k; char s[MAX_N]; int t[26]; int can[26]; int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); while(cin >> n >> k){ cin >> s; memset(t, 0, sizeof t); int len = strlen(s); for(int i = 0; i < len; ++i){ ++t[s[i] - 'a']; } for(int i = 0; i < 26; ++i) can[i] = t[i]; for(int i = 0; i < 26; ++i){ if(t[i] != 0) { if(k - t[i] >= 0) { can[i] = 0; k -= t[i]; } else { can[i] -= k; break; } } } for(int i = 0; i < len; ++i){ int cur = s[i] - 'a'; if(can[cur] < t[cur]) { ++can[cur]; } else { putchar(s[i]); } } putchar('n'); } return 0; }
E.Reachability from the Capital
題目大意:
有一個有向圖.求最少添加幾條邊使得從s可以到達其他所有點.
題解:
(1)dfs標記所有從s可達的點是good (2)對於每個bad的結點.統計其他同樣是bad的結點可以到達它的數量.v結點計算出的值是cnt(v) (3)一次遍歷非增序列cnt(v),從大到小遍歷.如果它還是bad.從它dfs.標記所有可達的 點是good.ans加1.相當於加了一條邊(s,v)
#include <bits/stdc++.h> using namespace std; const int MAX_N = 5*1e3+100; typedef pair<int, int> P; vector<int> G[MAX_N]; vector<P> bad; bool has[MAX_N]; bool color[MAX_N]; int cnt; int n,m,s; void dfs(int u){ has[u] = true; for(int i = 0; i < G[u].size(); ++i){ int v = G[u][i]; if(!has[v]) dfs(v); } } // 統計從bad的點u出發能到達的bad點 void dfs2(int u){ ++cnt; color[u] = true; for(int i = 0; i < G[u].size(); ++i){ int v = G[u][i]; if(!color[v] && !has[v]) dfs2(v); } } int main(){ // freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); int u,v; while(cin >> n >> m >> s){ memset(has, false, sizeof has); bad.clear(); for(int i = 0; i <= n; ++i) G[i].clear(); for(int i = 0; i < m; ++i){ cin >> u >> v; G[u].push_back(v); } dfs(s); for(int i = 1; i <= n; ++i){ if(!has[i]) { cnt = 0; memset(color, false, sizeof color); dfs2(i); bad.push_back(P(cnt, i)); } } sort(bad.begin(), bad.end(), greater<P>()); int ans = 0; for(auto &x: bad){ int u = x.second; if(!has[u]){ ++ans; dfs(u); } } cout << ans << endl; } return 0; }
F.Cards and Joy
題目大意:
有n個人.有k*n張牌.第i張牌的權值是c_i 第j個人喜歡的數字是f_j 有一個等級序列.h1,h2,…,hk 每個人發k張牌.如果對於第j個人. 他分到的牌的權值是他喜歡的數字f_j 的牌的數量是t.他的等級就是h[t]. 注意h[0] = 0. 求一種方案.使得n個人的等級和最大 輸出最大的等級和.
題解:
如果喜歡某個數字的人數是x.這個數字的卡牌有y個. 也就是這y張卡牌怎麼分給這x個人使得等級之和最大. 可以看出.和數字本身是幾沒有關係.只和x,y有關係. dp[x][y] ::= 喜歡某個數字的人數是x(0 <= x <= n), 是這個數字的卡牌有y(0 <= y <= k*n)張時候最優的方案 得到等級和最大.如果我們求出了dp[x][y]. $ans = sum_{i = 1}^{1e5} dp[f[i]][c[i]]$
容易知道dp[0][y] = dp[x][0] = 0. 狀態轉移方程: $dp[x][y] = max dp[x-1][y-i] + h[i], 0 <= i <= k$ 解釋一下: 就是有x個人y張牌的時候的最大值.是安排第x個人i張喜歡的牌. 加上剩下x-1個人安排y-i張牌.類似背包 時間複雜度$O(n^2*k^2)$
#include <bits/stdc++.h> using namespace std; // http://codeforces.com/problemset/problem/999/F typedef long long LL; const int MAX_N = 1e5+10; int f[MAX_N], c[MAX_N]; int dp[510][5100]; int h[15]; int n,k; int main(){ //freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); int x; cin >> n >> k; memset(c, 0, sizeof c); memset(f, 0, sizeof f); memset(dp, 0, sizeof dp); for(int i = 0; i < n*k; ++i) { cin >> x; ++c[x]; } for(int i = 0;i < n; ++i){ cin >> x; ++f[x]; } h[0] = 0; for(int i = 1; i <= k; ++i){ cin >> h[i]; } for(int i = 1; i <= n; ++i){ for(int j = 1; j <= n*k; ++j){ for(int l = 0; l <= min(j, k); ++l){ dp[i][j] = max(dp[i][j], dp[i-1][j-l] + h[l]); } } } LL ans = 0; for(int i = 0; i < MAX_N; ++i){ if(f[i] != 0) ans += dp[f[i]][c[i]]; } cout << ans << endl; return 0; }
