河北工业大学ACM集训队日常训练day1030

emmm.昨天刚到青岛.今天热身赛结束.非常想记录的一点就是.这个酒店太豪了.早餐特别豪.还有浴池.orz.要加油努力赚钱买大房子呀.补了一下题.记录一下.

河北工业大学ACM集训队日常训练day1030
原:Codeforces Round #490 (Div. 3)

A.Mishka and Contest

题目大意:

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;
}