河北工业大学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; }
