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]即可。

#include<bits/stdc++.h>
#define PII pair<int, int>
#define x first
#define y second
#define ll long long 
using namespace std;

const int N = 200010;

int n,m,w[N],need[N],ans[N],idx;
bool st[N], used[N];
vector<int> person[N];
PII rec[N];

bool topsort(){
    queue<int> q;
    for(int i = 1; i <= n; ++ i)
        if(need[i] <= w[i])
            q.push(i);
    while(!q.empty()){
        int fr = q.front(); q.pop();
        if(st[fr])    continue ;
        st[fr] = true;
        for(auto u : person[fr]){
            if(used[u])    continue ;
            used[u] = true;
            ans[idx --] = u;
            int tmp = rec[u].x == fr ? rec[u].y : rec[u].x;
            need[tmp] --;
            if(need[tmp] <= w[tmp])    q.push(tmp);
        }
    }
    return idx == 0;
}

int main(){
    cin >> n >> m;
    idx = m;
    for(int i = 1; i <= n; ++ i)    scanf("%d", &w[i]);
    for(int i = 1; i <= m; ++ i){
        int a, b;
        scanf("%d%d",&a,&b);
        need[a] ++, need[b] ++;
        person[a].push_back(i);
        person[b].push_back(i);
        rec[i] = {a, b};
    }
    if(topsort()){
        puts("ALIVE");
        for(int i = 1; i <= m; ++ i)
            printf("%d ", ans[i]); 
    }    
    else    puts("DEAD");
    return 0;
}