Codeforces Round ＃798 (Div. 2)（A~D)

A. Lex String

题意：

给出两个字符串，每次从其中一个串取一个字符加到$c$中，同一个串不能连续取$k$次，直到一个串为空，求字典序最小的$c$串。

思路：

对两个串排序，哪个串的小取拿个，设两个计数器判断是否连续取了$k$个。

ACcode

void solve(){
    int n, m, k;
    string a, b;
    cin >> n >> m >> k >> a >> b;
    int i = 0, j = 0;
    sort(all(a)), sort(all(b));
    string ans;
    int ca = 0, cb = 0;
    while(i < n && j < m){
         if(a[i] < b[j]){
             if(ca < k){
                 ca++;
                 ans = ans + a[i];
                 i++;
                 cb = 0;
             }else{
                 ans = ans + b[j];
                 cb++;
                 ca = 0;
                 j++;
             }
         }else{
             if(cb < k){
                 ans = ans + b[j];
                 j++;
                 cb++;
                 ca = 0;
 
             }else{
                 ans = ans + a[i];
                 i++;
                 ca++;
                 cb = 0;
                 
             }
         }
 
    }
    cout << ans << endl;
}   

B - Mystic Permutation

题意：

给定一个$1-n$的全排列$a$，构造出一个新的字典序最小的全排列$p$,，使得$p_i\ne a_i$。

思路：

用一个$set$记录当前还有哪些数没有填，每次填最小即可。

ACcode:

void solve(){
    int n;
    cin >> n;
    vi a(n + 1),  b(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n == 1){
        cout << -1 << endl;
        return;
    }
    set<int> st;
    for(int i = 1; i <= n; i++) st.insert(i);
    for(int i = 1; i <= n; i++){
        auto it = st.begin();
        if(*it == a[i] && st.size() == 1){
            b[i] = a[i];
            swap(b[i], b[i - 1]);
            break;
        }
        if(*it == a[i]) it++;
        b[i] = *it;
        st.erase(*it);
    }
    for(int i = 1; i <= n; i++) cout << b[i] << ' ';
    cout << endl;
}   

C - Infected Tree

题意：

给定一个二叉树，从根节点开始感染病毒，每次可以选择删去一个未被感染的点，使得该点的子树不被感染，求最多的不被感染的节点的个数（删去节点的不算）。

思路：

观察到一个节点最多只有两个儿子，如果有两个儿子，我们可以枚举删掉哪个收益更大。$dp[u]$表示$u$节点感染时最大的答案，$f[u]$表示以$u$为根的子树的节点个数(包括其本身）。那么如果有两个儿子,$dp[u]=max(dp[son1]+f[son2]-1,dp[son2]+f[son1]-1)$.做一遍树形dp即可。

ACcode

int h[N], ne[N * 2], e[N * 2], idx, n;
int dp[N], f[N];//dp[u]表示节点u被感染时有多少个节点没被砍掉也没有感染
void add(int a, int b){
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
int ans;
int dfs(int u, int fa){
    int sum = 1;
    int t = 0;
    vi now;
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(j == fa) continue;
        sum += dfs(j, u);
        now.pb(j);
    }
    f[u] = sum;
    if(now.size() == 1){
        dp[u] = f[now[0]] - 1;
    }
    if(now.size() == 2){
        dp[u] = max(f[now[0]] - 1 + dp[now[1]], f[now[1]] - 1 + dp[now[0]]);
    }
    return sum;
}
void solve(){
    cin >> n;
    idx = 0;
    
    for(int i = 0; i <= n; i++) h[i] = -1, dp[i] = f[i] = 0;
    for(int i = 1; i <= n - 1; i ++){
        int a, b; cin >> a >> b;
        add(a, b); add(b, a);
    }
    dfs(1, -1);
    cout << dp[1] << endl;
}   

D - Lena and Matrix

题意：

给一个只有黑色和白色的网格，找到一个点$x_{i,j}$,使得该点到所有黑色网格的曼哈顿距离的最大值最小。

思路：

显然任意一个点到黑色网格的距离最大值只可能在矩阵最左上角，左下角，右上角，右下角的黑色网格的地方，预处理出这四个角的黑色网格的位置，$O(1)$的复杂度更新答案。

ACcode

int n, m;
char s[N][N];
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    
    pii ans, a[5];
    a[1] = {0, 0}; a[2] = {inf, inf}; a[3] = {0, 1010}; a[4] = {1010, 0};
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s[i][j] == 'B'){
                if(i + j > a[1].fi + a[1].se) a[1] = {i, j}; //右下角
                if(i + j < a[2].fi + a[2].se) a[2] = {i, j}; //左上角
                if(i - j > a[3].fi - a[3].se) a[3] = {i, j}; //左下角
                if(i - j < a[4].fi - a[4].se) a[4] = {i, j};
            }
        }
    }
    int res = inf;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
           
                int now = 0;
                for(int q = 1; q <= 4; q++){
                    now = max(now, abs(a[q].fi - i) + abs(a[q].se - j));
                }
                // D(now);
                if(now < res){
                    res = now;
                    ans = {i, j};
                }
            
        }
    }
    cout << ans.fi << ' ' << ans.se << endl;
}