【題解】Codeforces Round #798 (Div. 2)
本篇為 Codeforces Round #798 (Div. 2) 也就是 CF1689 的題解，因本人水平比較菜，所以只有前四題
A.Lex String
題目描述
原題面
給定兩個字元串 \(a,b\)，要求通過以下的兩種操作構造一個新的字元串 \(c\)，使得 \(c\) 的字典序最小，並且要求不能連續使用某一種操作超過 \(k\) 次
1.從 \(a\) 中任選一個字元插入到 \(c\) 的末尾
2.從 \(b\) 中任選一個字元插入到 \(c\) 的末尾
若某一個字元串為空則認為構造結束。
若字元串 \(x\) 比字元串 \(y\) 字典序小則必定滿足以下兩種情況之一：
1.\(x\) 為 \(y\) 的前綴，且 \(x \not= y\)
2.從左到右的順序，\(x\) 與 \(y\) 第一個不同的位置上 \(x\) 的字元的字典序比 \(y\) 的字元的字典序小
題目分析
我們首先可以發現一點：所謂的插入末尾與插入開頭並沒有任何的區別
所以為了字典序小我們肯定每一次選擇 \(a,b\) 中字典序最小的字元，如果超過了 \(k\) 次就選另一個字元串的，下一次再選它就好了
需要注意這裡的字典序小不包含：僅僅是字元串長度更小，所以不用考慮這樣的構造出的字元串長度上的問題
程式碼詳解
點擊查看程式碼
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
char a[MAXN],b[MAXN];
int main(){
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
for(int i=1; i<=n; i++){
cin>>a[i];
}
for(int i=1; i<=m; i++){
cin>>b[i];
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
int l = 1,r = 1,tmp = 0;
bool flag = false;
while(l <= n && r <= m){
if(a[l] < b[r]){
if(flag){
cout<<a[l++];
flag = false;
tmp = 1;
}
else{
if(tmp < k){
cout<<a[l++];
tmp++;
}
else{
cout<<b[r++];
tmp = 1;
flag = true;
}
}
}
else if(a[l] >= b[r]){
if(!flag){
cout<<b[r++];
flag = true;
tmp = 1;
}
else{
if(tmp < k){
cout<<b[r++];
tmp++;
}
else{
cout<<a[l++];
tmp=1;
flag = false;
}
}
}
}
cout<<endl;
}
return 0;
}
其實程式碼有一點複雜，但是其實思路很簡單
B. Mystic Permutation
題目描述
原題面
給定一個 \([1,n]\) 的排列，要求你構造一個 \([1,n]\) 的排列，使得這兩個排列之間的任意一個相同位置的元素都不相同，且滿足這個排列的字典序最小。
如果無法構造出這樣的序列則輸出 -1
題目分析
一個非常正常的想法：把元素從小到大插入，如果遇到了相同的或者用過的就跳過
但是這樣會出現一種情況那就是序列的最後一個元素是 \(n\)，那麼放到最後一個元素的時候就只剩下了 \(n\)，那麼就無論如何也無法放置了
這個問題也非常好解決：最後的這個元素 \(n\) 我們肯定不能放在很靠前的位置，因為這樣很明顯字典序不會最小了，那麼為了使得這個元素放得下我們就放在 \(n-1\) 的位置上，讓 \(n-1\) 的位置上原本應該放的元素放到 \(n\) 上，這樣能保證前 \(n-2\) 個一定是最小的，而不存在一種別的方法使得可以使得最後的兩個元素比我們現在放置的更小而且前 \(n-2\) 個依舊保持最小。
有一說一樣例是真強，不然的話我應該發現不了這一點。
程式碼詳解
點擊查看程式碼
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+5;
bool flag[MAXN];
int a[MAXN];
int main(){
int t;
cin>>t;
while(t--){
memset(flag,false,sizeof(flag));
int n;
cin>>n;
if(n == 1){
cin>>a[1];
printf("-1\n");
continue;
}
for(int i=1; i<=n; i++){
cin>>a[i];
}
for(int i=1; i<=n; i++){
if(i == n - 1 && !flag[a[n]]){
printf("%d ",a[n]);
flag[a[n]] = true;
}
for(int j=1; j<=n; j++){
if(!flag[j] && j != a[i]){
printf("%d ",j);
flag[j] = true;
break;
}
}
}
cout<<endl;
}
return 0;
}
因為數據範圍比較小，所以為了寫的來更加舒服就寫了這樣非常暴力的做法，但是我們應該理解起來更容易一些。
C. Infected Tree
題目描述
原題面
給定一棵以 \(1\) 號節點為根的二叉樹，現在 \(1\) 號節點感染了病毒，病毒每一回合都會去感染與該節點直接相連的節點，而你在這一回合里可以選擇刪除任意一個沒有被病毒感染的點，這樣就斷開了它與其直接相連的點得關係，詢問最多可以有多少不被病毒感染的點，被刪除的點不算做不被病毒感染的點
題目分析
我們考慮為了儘可能多的保留節點，我們每一次肯定是會刪除被病毒感染的節點的某個子節點，而刪除之後我們的問題就可以轉化為它的另一個兒子（注意為二叉樹）根被感染病毒能保留多少節點的子問題，那麼這很明顯就可以考慮一下 \(DP\)。\(DP\) 狀態也很簡單：\(dp[i]\) 表示以 \(i\) 為根的子樹若 \(i\) 被感染病毒，最多能保留多少節點
那麼下面就是考慮轉移了，轉移很明顯就是我們考慮刪除哪一個 \(i\) 的子節點就好了，因為是二叉樹所以不用考慮更多的情況。那麼我們就分別考慮究竟刪除哪一個子節點，假設刪除 \(son_1\)，那麼相當於在 \(son_1\) 的子樹里我們可以保留下 \(size[son_1] - 1\) 個節點，\(size[i]\) 代表以 \(i\) 為根的子樹的大小（包含節點 \(i\)），而在 \(son_2\) 的子樹里，我們依舊可以保留下 \(dp[son_2]\) 個節點，所以最終的狀態就是：
需要注意可能該子樹為空，那麼 \(size[son] - 1\) 就是一個負數，所以需要對 \(0\) 取 \(\max\)，避免這種情況
程式碼詳解
點擊查看程式碼
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+5;
struct edge{
int nxt,to;
edge(){}
edge(int _nxt,int _to){
nxt = _nxt,to = _to;
}
}e[2 * MAXN];
int ans = 0,cnt,head[MAXN],dp[MAXN],sz[MAXN];
//dp[now] 表示以 now 為根的子樹，假設 now 被感染，最多保留多少個
void add_edge(int from,int to){
e[++cnt] = edge(head[from],to);
head[from] = cnt;
}
void dfs(int now,int fa){
sz[now] = 1;
int son[3] = {0,0,0};
int tot = 0;
for(int i=head[now]; i;i = e[i].nxt){
int to = e[i].to;
if(to == fa) continue;
son[++tot] = to;
dfs(to,now);
sz[now] += sz[to];
}
//去 son[1] / 去 son[2]
dp[now] = max(dp[son[1]] + max(sz[son[2]] - 1,0),dp[son[2]] + max(sz[son[1]] - 1,0));
}
int main(){
int t;
cin>>t;
while(t--){
memset(head,0,sizeof(head));
memset(dp,0,sizeof(dp));
memset(sz,0,sizeof(sz));
ans = 0;
int n;
cin>>n;
for(int i=1; i<n; i++){
int from,to;
cin>>from>>to;
add_edge(from,to);
add_edge(to,from);
}
dfs(1,0);
printf("%d\n",dp[1]);
}
return 0;
}
先進行 \(dfs\) 再更新 \(sz\) 和 \(dp\)，以及多組數據所以每次需要將各種數組清零，清零 \(head\) 數組也相當於清零邊的數組了
D. Lena and Matrix
題目描述
原題面
給定一個 \(n\times m\) 的矩陣，每個位置都有一個顏色，分別為黑色或白色，要求你選擇一個位置（不計這個位置上是什麼顏色），使得整個位置到所有黑色格子的曼哈頓距離的最大值最小。
曼哈頓距離即：\(|x_1 - x_2| + |y_1 - y_2|\)
題目分析
要求的是最大值最小，其實發現這個最大值不是和任意一個黑色格子的距離都有可能成為最大值的，能成為最大距離的黑色格子一定是最左上、右下、左下、右上的黑格子，可以發現如果不是這四個格子，那麼把距離轉化到這四個黑色格子上都一定可以增加
下面就是如何尋找著四個黑色格子的問題了，我感覺這個思路還是很神奇的。
考慮如果一個格子離左上角越近，\(x\) 越小，\(y\) 越小，而且 \(x\) 與 \(y\) 的減小，對其離左上角的距離產生的貢獻是一樣的，那麼就直接令這個貢獻為 \(x+y\)，那麼最左上角的點也就一定是貢獻最小的點，最右下角的點也一定是貢獻最大的點，這就解決了兩個。
考慮如果一個格子里右上角越近，\(x\) 越大，\(y\) 越小，而且它們產生的貢獻也都是一樣的，所以就考慮直接令貢獻為 \(x-y\)，這樣最右上的點也就是 \(x-y\) 最大點，最左下的點也就是 \(x-y\) 最小的點，至此四個點全部解決了。
那麼就是要找一個位置使得這個位置到這四個位置的距離最大值最小，那麼就直接枚舉每一個位置尋找一下就好了
程式碼詳解
點擊查看程式碼
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+5;
struct node{
int x,y;
node(){}
node(int _x,int _y){
x = _x,y = _y;
}
};
int main(){
int t;
cin>>t;
while(t--){
node a[6];
bool flag[6];
memset(flag,0,sizeof(flag));
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
char h;
cin>>h;
if(h == 'B'){
if(i + j > a[1].x + a[1].y || !flag[1]) a[1] = node(i,j),flag[1] = true;
//越在右下角 i + j 越大
if(i + j < a[2].x + a[2].y || !flag[2]) a[2] = node(i,j),flag[2] = true;
//越在左上角 i + j 越小
if(i - j > a[3].x - a[3].y || !flag[3]) a[3] = node(i,j),flag[3] = true;
//越在右上角 i - j 越大
if(i - j < a[4].x - a[4].y || !flag[4]) a[4] = node(i,j),flag[4] = true;
//越在左下角 i - j 越小
}
}
}
int res = INF;
node ans;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
int h = 0;
for(int k=1; k<=4; k++){
h = max(h,abs(i - a[k].x) + abs(j - a[k].y));
}
if(h < res){
ans = node(i,j);
res = h;
}
}
}
printf("%d %d\n",ans.x,ans.y);
}
return 0;
}
先去找四個點找到了就每個位置枚舉一下，最後輸出就好了
