Codeforces Round 954 (Div. 3)

A. X Axis

题意：

你得到了三个点 $x_1$，$x_2$，$x_3$和 你需要求出一个点使得$x_1$，$x_2$，$x_3$与这个点的距离和最小。

题解：

暴力枚举各个点。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
#define int long longusing namespace std;void solve(){int x,y,z;cin>>x>>y>>z;int ans=0x3f3f3f3f;int l=min(min(x,y),z);int r=max(max(x,y),z);for(int i=l;i<=r;i++) ans=min(ans,abs(x-i)+abs(y-i)+abs(z-i));cout<<ans<<endl;
}
signed main(){int t;cin>>t;while(t--) solve();return 0;
}

B. Matrix Stabilization

题意：

给你一个大小为 $n\times m$ 的矩阵，其中行的编号从上到下为 $1$ 至 $n$ ，列的编号从左到右为 $1$ 至 $m$ 。位于 $i$ -th 行和 $j$ -th 列交点上的元素用 $a_{ij}$ 表示。

考虑稳定矩阵 $a$ 的算法：

1. 找到单元格 $(i,j)$ ，使其值严格大于所有相邻单元格的值。如果没有这样的单元格，则终止算法。如果有多个这样的单元格，则选择 $i$ 值最小的单元格；如果仍有多个单元格，则选择 $j$ 值最小的单元格。
2. 设置 $a_{ij}=a_{ij}-1$ 。
3. 转到步骤 $1$ 。

在这个问题中，如果单元格 $(a,b)$ 和 $(c,d)$ 有一个共同的边，即 $|a-c|+|b-d|=1$ ，那么这两个单元格就是邻居。

您的任务是在执行稳定算法后输出矩阵 $a$ 。可以证明这种算法不可能运行无限次迭代。

给你一个大小为 $n\ast m$ 的矩阵，其中行的编号从上到下为 $1$ 至 $n$ ，列的编号从左到右为 $1$ 至 $m$ 。位于 $i$ -行和 $j$ -列交叉处的元素用 $a\_ij$ 表示。考虑稳定矩阵 $a$ 的算法：1.找到单元格 $(i,j)$ 使其值严格大于所有相邻单元格的值。如果没有这样的单元格，则终止算法。如果有多个这样的单元格，则选择 $i$ 值最小的单元格；如果仍有多个单元格，则选择 $j$ 值最小的单元格。2.设置 $a_{i,j}=a_{i,j}-1$ 。3.转到步骤 $1$ .在此问题中，如果单元格 $(a,b)$ 和 $(c,d)$ 有一个公共边，即 $|a-c|+|b-d|=1$ ，则这两个单元格被视为相邻单元格。您的任务是在执行稳定算法后输出矩阵 $a$ 。可以证明这种算法不可能运行无限次迭代。

题解：

从左上角枚举各个点，判断当前点是否需要修改，若需要则将其修改为相邻点的最大值即可。

代码：

#include<iostream>
#include<algorithm>
#include<vector>
#define int long longusing namespace std;const int N=110;
int a[N][N];void solve(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){int temp=-0x3f3f3f3f;int cnt0=0;int cnt1=0;if(i-1>=1){cnt0++;temp=max(temp,a[i-1][j]);if(a[i-1][j]<a[i][j]) cnt1++;}if(i+1<=n){cnt0++;temp=max(temp,a[i+1][j]);if(a[i+1][j]<a[i][j]) cnt1++;}if(j-1>=1){cnt0++;temp=max(temp,a[i][j-1]);if(a[i][j-1]<a[i][j]) cnt1++;}if(j+1<=m){cnt0++;temp=max(temp,a[i][j+1]);if(a[i][j+1]<a[i][j]) cnt1++;}if(cnt0==cnt1) a[i][j]=temp;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) cout<<a[i][j]<<" ";cout<<endl;}
}
signed main(){int t;cin>>t;while(t--) solve();return 0;
}

C. Update Queries

题意：

给定一个长度为n的字符串$s$和长度为$m$的$ind$数组，以及字符串$c$，你可以任意安排$ind$数组和$c$字符串的顺序，然后有m次操作，第i次操作，可以将$s_{in{d}_i}$的值更改为$c_i$，问m次操作后，要求经过 $m$ 次操作后的字符串 $s$ 的字典序最小，输出这个 $s$。

题解：

将 $c$ 和$ind$排序，遍历$ind$数组，$c$的首元素代替$s$中的元素，经过m次替换就是最小的字典序。

代码：

#include<iostream>
#include<algorithm>
#include<vector>#define int long longusing namespace std;void solve() 
{int n;cin >> n;string s;cin >> s;int mask[n];for(int i = 0 ; i < n ; i ++){mask[i] = s[i] - '0';}	int ans = 101010;for(int i = 1 ; i < n ; i ++){vector<int>tmp;int tot = 0;for(int j = 0 ; j < n ; j ++){if(j == i - 1){int x = mask[j] * 10 + mask[j + 1];tmp.push_back(x);j++;}else{tmp.push_back(mask[j]);}}for(auto it : tmp){cout<<it<<" ";if(it == 0){cout << 0 << endl;return;}if(it == 1){continue;}else{tot += it;}}cout<<endl;if(tot == 0) tot++;ans = min(ans , tot);}cout << ans << endl;
}
signed main(){int t;cin>>t;while(t--) solve();return 0;
}

D. Mathematical Problem

题意：

给定一个长度为n的全为数字的字符串，你可以在字符串中添加n-2个运算符（$\times$或者$＋$），使得字符串变为一个合法表达式，求出该表达式最小的结果。

题解：

长度为 $2$ 时，输出取出前导零的原数组即可，当长度大于 $2$ 时，原字符串可以分为 $n-1$ 个数字，然后需要 $n-2$ 个运算符将其连接，因此有一个数字是两位数，其他的均为 $1$ 位数，要使得最后的结果最小，因此当其中一个数字为 $1$ 的时候运算符为乘法，其他的均为加法。

代码：

#include<iostream>
#include<algorithm>
#include<vector>#define int long longusing namespace std;void solve() 
{int n;cin >> n;string s;cin >> s;int mask[n];for(int i = 0 ; i < n ; i ++){mask[i] = s[i] - '0';}	int ans = 101010;for(int i = 1 ; i < n ; i ++){vector<int>tmp;int tot = 0;for(int j = 0 ; j < n ; j ++){if(j == i - 1){int x = mask[j] * 10 + mask[j + 1];tmp.push_back(x);j++;}else{tmp.push_back(mask[j]);}}for(auto it : tmp){cout<<it<<" ";if(it == 0){cout << 0 << endl;return;}if(it == 1){continue;}else{tot += it;}}cout<<endl;if(tot == 0) tot++;ans = min(ans , tot);}cout << ans << endl;
}
signed main(){int t;cin>>t;while(t--) solve();return 0;
}