Codeforces Round #798 (Div. 2)

• A Lex String
• B. Mystic Permutation
• C Infected Tree
• D. Lena and Matrix
• E. ANDfinity

题意：给出两个字符串，每次可以从一个串中选一个字符加到答案串末尾，每个字符串最多只能连续选k次，直到有一个字符串被选完，问能得到的最小字典序的答案串。
题解：因为规定了两个字符串没有任意一个字符相同，所以排序模拟即可，一个字符串连续选k次就强制选另一个

#pragma warning(disable:4996)
#include
using namespace std;
const int N = 110;
char a[N], b[N];
void slove() {
    int n, m, k;
    scanf("%d%d%d%s%s", &n, &m, &k, a + 1, b + 1);
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m);
    int i = 1, j = 1;
    int ka = 0, kb = 0;
    while (i <= n && j <= m) {
        if (ka == k) {
            ka = 0, kb++;
            printf("%c", b[j++]);
        }
        else if (kb == k) {
            kb = 0, ka++;
            printf("%c", a[i++]);
        }
        else if (a[i] < b[j]) {
            ka++,kb=0;
            printf("%c", a[i++]);
        }
        else {
            kb++,ka=0;
            printf("%c", b[j++]);
        }
    }
    puts("");
}
int main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    int _;cin>>_;while(_--)
    slove();
    return 0.0;
}

题意：给你一个排列，求出字典序最小的完全错排
题解：若不考虑错排则最优解一定是a[i]=i，我们构建b数组令b[i]=i，
若碰到a[i]=i的情况我们则需要交换,这时肯定交换b[i]与b[i+1]为最优
(有可能会碰到n=a[n]的情况，我们交换b[n],b[n-1]即可）

#pragma warning(disable:4996)
#include
using namespace std;
const int N = 1010;
int a[N], b[N];
void slove() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)scanf("%d", &a[i]),b[i]=i;
    if (n == 1)puts("-1");
    else {
        for (int i = 1; i <= n; i++) {
            if (a[i] == b[i]) {
                if (i == n)swap(b[i], b[i - 1]);
                else swap(b[i], b[i + 1]);
            }
        }
        for (int i = 1; i <= n; i++)printf("%d ", b[i]);
        puts("");
    }
}
int main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    int _;cin>>_;while(_--)
    slove();
    return 0.0;
}

题意：给你一个二叉树，根节点为1，且已经被感染，每秒钟感染会扩散到被感染点的儿子上，同时每一秒你可以切断一个点边以保护整棵子数，问最多可以保护多少点
题解：树形dp的思想，如果只有一个或零个儿子，直接计算，若有两个儿子，我们肯定要感染一个，保护一个，维护一个dp数组，表示该节点被感染后最多能保护多少个点，所以每一层的答案就是max(s1.size()+dp[s2],s2.size()+dp[s1]};

#pragma warning(disable:4996)
#include
using namespace std;
const int N = 3e5+10;
vector h[N];
int sz[N];
int f[N];
void dfs(int u, int fa) {
    sz[u] = 1;
    int idx1 = -1, idx2 = -1;
    for (auto i : h[u]) {
        if (i == fa)continue;
        dfs(i, u);
        sz[u] += sz[i];
        if (idx1 == -1)idx1 = i;
        else if (idx2 == -1)idx2 = i;
    }
    if (idx1 == -1)f[u] = 0;
    else if (idx2 == -1)f[u] = sz[idx1] - 1;
    else f[u] = max(f[idx1] + sz[idx2] - 1, f[idx2] + sz[idx1] - 1);
}
void slove() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)h[i].clear();
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        h[u].push_back(v);
        h[v].push_back(u);
    }
    dfs(1, -1);
    printf("%dn", f[1]);
}
int main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    int _;cin>>_;while(_--)
    slove();
    return 0.0;
}

题意：平面上有k个黑点，让你找出一个位置使得到距离最远的黑点最近
题解：曼哈顿距离 绝对值拆项

#pragma warning(disable:4996)
#include
using namespace std;
char mp[1010][1010];
void slove() {
    int m1 = -1e9, m2 = -1e9, m3 = -1e9, m4 = -1e9;
    //x+y         x-y         -x+y      -x-y
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", mp[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == 'B') {
                m1 = max(m1, i + j);
                m2 = max(m2, i - j);
                m3 = max(m3, -i + j);
                m4 = max(m4, -i - j);
            }
        }
    }
    int sum = 1e9;
    int vx = 0, vy = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int r = max({ m1 - (i + j),m2 - (i - j),m3 - (-i + j),m4 - (-i - j) });
            if (r < sum)sum = r, vx = i, vy = j;
        }
    printf("%d %dn", vx, vy);
}
int main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    int _;cin>>_;while(_--)
    slove();
    return 0.0;
}

题意：给定一个长度为 n 的数组 a ，如果 a[i]&a[j]>0 则给(i,j) 之前连边。你可以执行之下操作多次选择一个数，给他加一或者减一。问最少需要多少次操作，整个图是联通的。
题解：首先判断零，零无论如何也不会与别的数字连边，所以我们给所有零加一，然后我们可以证明只需至多操作两次便可以复原，首先判断可不可以一次复原，如果不可以就两次复原。

#pragma warning(disable:4996)
#include
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define pii pair
#define ll long long
#define INF 0x3f3f3f3f
#define all(x) x.begin(), x.end()
#define db double 
inline ll maxll(ll x, ll y) { return x > y ? x : y; }
inline ll minll(ll x, ll y) { return x < y ? x : y; }
inline ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
inline ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
inline bool fcmp(db x, db y) { return fabs(x - y) < 0.0000001; }
const int N = 500010;
const db pi = acos(-1.0);
const db phi = 0.5772156649;
int mod = 1e9 + 7;
inline int add(int x, int y) { return x + y < mod ? x + y : x + y - mod; }inline int sub(int x, int y) { return x < y ? mod + x - y : x - y; }inline int mul(ll x, int y) { return x * y % mod; }
inline ll fpow(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1)res = res * a % c; a = a * a % c; b >>= 1; } return res; }
int a[N];
int p[N];
int n;
int find(int x) {
    if (x != p[x])p[x] = find(p[x]);
    return p[x];
}
int lowbit(int x) { return (x & (-x)); }
void merger(int x, int y) {
    int a = find(x), b = find(y);
    if (a != b)p[a] = b;
}
bool check() {
    for (int i = 1; i <= n + 31; i++)p[i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 31; j++)if (a[i] >> j & 1)merger(n + j + 1, i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)if (find(i) == i)cnt++;
    return cnt == 1;
}
int res = 0;
void print() {
    printf("%dn", res);
    for (int i = 1; i <= n; i++)printf("%d ", a[i]);
    puts("");
}
void slove() {
	res=0;
    scanf("%d",&n);
    int maxbit = 0;
    for (int i = 1; i <= n; i++)scanf("%d",&a[i]);
    for (int i = 1; i <= n; i++){
    	if (a[i] == 0)res++, a[i]++;
    	maxbit=max(maxbit,lowbit(a[i]));
    }
    if (check()) { print(); return; }
    res++;
    for (int i = 1; i <= n; i++) {
        a[i]++;
        if (check()) { print(); return; }
        a[i]--;
        if(a[i]==1)continue;
        a[i]--;
        if (check()) { print(); return; }
        a[i]++;
    }
    res++;
    for(int i=1;i<=n;i++)if(lowbit(a[i])==maxbit){a[i]++;break;}
    for (int i = 1; i <= n; i++)if (lowbit(a[i]) == maxbit){a[i]--;break;}
    print();
}
int main() {
    //ios::sync_with_stdio(0), cin.tie(0);
    int _;cin>>_;while(_--)
    slove();
    return 0.0;
}