河北工业大学ACM集训队日常训练day1030
河北工业大学ACM集训队日常训练day1030
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;
}