给出两个字符串，每次从其中一个串取一个字符加到 c c c中，同一个串不能连续取 k k k次，直到一个串为空，求字典序最小的 c c c串。
思路：对两个串排序，哪个串的小取拿个，设两个计数器判断是否连续取了 k k k个。
ACcodevoid 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 1-n 1−n的全排列 a a a，构造出一个新的字典序最小的全排列 p p p,，使得 p i ≠ a i p_i neq a_i pi=ai。
思路：用一个 s e t set 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 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
题意：
给定一个二叉树，从根节点开始感染病毒，每次可以选择删去一个未被感染的点，使得该点的子树不被感染，求最多的不被感染的节点的个数（删去节点的不算）。
思路：观察到一个节点最多只有两个儿子，如果有两个儿子，我们可以枚举删掉哪个收益更大。 d p [ u ] dp[u] dp[u]表示 u u u节点感染时最大的答案， f [ u ] f[u] f[u]表示以 u u u为根的子树的节点个数(包括其本身）。那么如果有两个儿子, d p [ u ] = m a x ( d p [ s o n 1 ] + f [ s o n 2 ] − 1 , d p [ s o n 2 ] + f [ s o n 1 ] − 1 ) dp[u] =max(dp[son1]+f[son2]-1,dp[son2]+f[son1]-1) dp[u]=max(dp[son1]+f[son2]−1,dp[son2]+f[son1]−1).做一遍树形dp即可。
ACcodeint 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 x_{i,j} xi,j,使得该点到所有黑色网格的曼哈顿距离的最大值最小。
思路：显然任意一个点到黑色网格的距离最大值只可能在矩阵最左上角，左下角，右上角，右下角的黑色网格的地方，预处理出这四个角的黑色网格的位置， O ( 1 ) O(1) O(1)的复杂度更新答案。
ACcodeint 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;
}
