Codeforces Round #652 (Div. 2) （补题ing）

cf补题 652
B - AccurateLee

题意：如果一个字符串有连续10，可以去掉1或者去掉0,问最短的字典序最小的串。
思路：前面的0和后面的1一定去不掉。中间的10无论怎么排列，都可以消成一个0，所以前后找一遍即可。
注意特判00001111这种一个都消不掉的。

void solve(){
    cin >> n >> s + 1;
    int idx1 = 1, idx2 = 0;
    for(idx1 = 1; idx1 <= n; ++ idx1)
        if(s[idx1] == '1')
            break;

    for(idx2 = n; idx2 >= idx1; -- idx2)
        if(s[idx2] == '0')
            break;
    //printf("1 = %d 2 = %d\n", idx1, idx2);
    if(idx1 < idx2){
        for(int i = 1; i < idx1; ++ i)    printf("%c", s[i]);
        printf("0");
        for(int i = idx2 + 1; i <= n; ++ i)    printf("%c", s[i]);
    }else{
        for(int i = 1; i < idx1; ++ i)    printf("%c", s[i]);
        for(int i = idx2 + 1; i <= n; ++ i)    printf("%c", s[i]);
    }
    cout << endl;
}

C - RationalLee
题意：n个礼物送给m个人，每个人给mi个（mi的和等于n)，每个礼物有一个价值。每个人的开心值为礼物中的价值最大+价值最小，问最大的总开心值。
思路：如果有人只得到一个礼物，那肯定给价值最大的，这样maxx == minn == 最大价值。
剩下的人，让要得到礼物最多的人先选，选当前最大，然后剩下的从小往大选，这样一定可以剩下更多价值大的供后面人选择。【除了maxx minn, 剩下礼物没有用，所以肯定尽快处理小的】。

void solve(){
    ll ans = 0, idx;
    cin >> n >> k;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &a[i]);
    for(int i = 1; i <= k; ++ i)    scanf("%d", &b[i]);
    sort(a + 1, a + 1 + n, greater<int>() );
    sort(b + 1, b + 1 + k);
    for(int i = 1; i <= k; ++ i)    ans += a[i];
    for(int i = 1, idx = n; i <= k; ++ i){
        if(b[i] == 1)    ans += a[i];
        else{
            for(; idx > k; -- idx){
                ans += a[idx];
                idx -= (b[i] - 1);
            }
        }
    }
    cout << ans << endl;
}

D. TediousLee 【找规律，好玩好玩hao】
画图找规律emmmm.
称一个没有孩子的点为A，只有一个孩子的点为B，有三个孩子的点为C。
那么这一轮的A会变成下一轮的B（同时生成一个A），这一轮的B会变成下一轮的C，而这一轮的B又会给下一轮多生成两个A。
所以dp[i, A] = dp[i - 1, A] + dp[i - 1][B] * 2
dp[i, B] = dp[i - 1, A]
可以发现：至少有dp[i - 1, B]这么多的爪形结构新生成，但是还会有之前早就生成的爪形结构，观察发现（我也不知道为什么，就是看出来的emm) 还要加上i - 3轮之前的答案。
用rec数组记录A, B的递推情况， dp数组记录答案。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2000010, mod = 1e9 + 7;

int n,k;
ll dp[N] = {0,0,0,1,1,3,5,12};
ll rec[N][2];

void solve(){
    rec[1][0] = rec[1][1] = 0;
    rec[2][0] = rec[2][1] = 1;
    for(int i = 3; i <= 2000000; ++ i){
        rec[i][0] = rec[i - 1][1];
        rec[i][1] = (rec[i - 1][1] + rec[i - 1][0] * 2) % mod;
        dp[i] = (rec[i - 1][0] + dp[i - 3]) % mod;
    }
}

int main(){
    int t;
    solve();
    cin >> t;
    while(t --){
        cin >> n;
        cout << dp[n] * 4 % mod << endl;
    }
    return 0;
}

E DeadLee(贪心+拓扑)
题意： Lee的厨房中有 n 道菜，每道菜的数量为 w[ i ] ，现在 Lee 会邀请 m 个朋友，每个朋友都有最爱吃的两道菜 x[ i ] 和 y[ i ] ，当朋友 i 来到 Lee 家后，会选择吃掉 x[ i ] 和 y[ i ] 各一份，如果 x[ i ] 没有了的话，那么他只会选择吃掉一份 y[ i ] ，如果 y[ i ] 没有了的话同理，但是如果 x[ i ] 和 y[ i ] 同时没有的话，这个朋友就会吃掉 Lee，问 Lee 能否安排一个合适的顺序以保证存活，输出这个顺序。
思路：设 sum[ i ] 为每道菜的需求量，那么如果 sum[ i ] <= w[ i ] 的话，那么这 sum[ i ] 个人是一定可以吃到菜的，我们只需要将其安排在最后来吃就好了，同理，如果所有的 sum[ i ] > w[ i ] 成立的话，那么将会是无解的
可以使用topsort实现，把in[u] == 0 变成 need[u] <= w[u]即可。

Codeforces Round #652 (Div. 2) （补题ing）

全站热榜