这里写自定义目录标题
- A. X Axis
- 题意：
- 题解：
- 代码：
- B. Matrix Stabilization
- 题意：
- 题解：
- 代码：
- C. Update Queries
- 题意：
- 题解：
- 代码：
- D. Mathematical Problem
- 题意：
- 题解：
- 代码：
A. X Axis
题意：
你得到了三个点 x 1 x_{1} x1， x 2 x_{2} x2， x 3 x_{3} x3和 你需要求出一个点使得 x 1 x_{1} x1， x 2 x_{2} x2， x 3 x_{3} x3与这个点的距离和最小。
题解：
暴力枚举各个点。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using 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 × m n \times m n×m 的矩阵，其中行的编号从上到下为 1 1 1 至 n n n ，列的编号从左到右为 1 1 1 至 m m m 。位于 i i i -th 行和 j j j -th 列交点上的元素用 a i j a_{ij} aij 表示。
考虑稳定矩阵 a a a 的算法：
- 找到单元格 ( i , j ) (i, j) (i,j) ，使其值严格大于所有相邻单元格的值。如果没有这样的单元格，则终止算法。如果有多个这样的单元格，则选择 i i i 值最小的单元格；如果仍有多个单元格，则选择 j j j 值最小的单元格。
- 设置 a i j = a i j − 1 a_{ij} = a_{ij} - 1 aij=aij−1 。
- 转到步骤 1 1 1 。
在这个问题中，如果单元格 ( a , b ) (a, b) (a,b) 和 ( c , d ) (c, d) (c,d) 有一个共同的边，即 ∣ a − c ∣ + ∣ b − d ∣ = 1 |a - c| + |b - d| = 1 ∣a−c∣+∣b−d∣=1 ，那么这两个单元格就是邻居。
您的任务是在执行稳定算法后输出矩阵 a a a 。可以证明这种算法不可能运行无限次迭代。
给你一个大小为 n ∗ m n * m n∗m 的矩阵，其中行的编号从上到下为 1 1 1 至 n n n ，列的编号从左到右为 1 1 1 至 m m m 。位于 i i i -行和 j j j -列交叉处的元素用 a _ i j a\_{ij} a_ij 表示。考虑稳定矩阵 a a a 的算法：1.找到单元格 ( i , j ) (i, j) (i,j) 使其值严格大于所有相邻单元格的值。如果没有这样的单元格，则终止算法。如果有多个这样的单元格，则选择 i i i 值最小的单元格；如果仍有多个单元格，则选择 j j j 值最小的单元格。2.设置 a i , j = a i , j − 1 a_{i,j} = a_{i,j} - 1 ai,j=ai,j−1 。3.转到步骤 1 1 1 .在此问题中，如果单元格 ( a , b ) (a, b) (a,b) 和 ( c , d ) (c, d) (c,d) 有一个公共边，即 ∣ a − c ∣ + ∣ b − d ∣ = 1 |a - c| + |b - d| = 1 ∣a−c∣+∣b−d∣=1 ，则这两个单元格被视为相邻单元格。您的任务是在执行稳定算法后输出矩阵 a a a 。可以证明这种算法不可能运行无限次迭代。
题解：
从左上角枚举各个点，判断当前点是否需要修改，若需要则将其修改为相邻点的最大值即可。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using 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 s s和长度为 m m m的 i n d ind ind数组，以及字符串 c c c，你可以任意安排 i n d ind ind数组和 c c c字符串的顺序，然后有m次操作，第i次操作，可以将 s i n d i s_{ind_i} sindi的值更改为 c i c_{i} ci，问m次操作后，要求经过 m m m 次操作后的字符串 s s s 的字典序最小，输出这个 s s s。
题解：
将 c c c 和 i n d ind ind排序，遍历 i n d ind ind数组， c c c的首元素代替 s s s中的元素，经过m次替换就是最小的字典序。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using 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个运算符（ × × ×或者 ＋ ＋ ＋），使得字符串变为一个合法表达式，求出该表达式最小的结果。
题解：
长度为 2 2 2 时，输出取出前导零的原数组即可，当长度大于 2 2 2 时，原字符串可以分为 n − 1 n-1 n−1 个数字，然后需要 n − 2 n-2 n−2 个运算符将其连接，因此有一个数字是两位数，其他的均为 1 1 1 位数，要使得最后的结果最小，因此当其中一个数字为 1 1 1 的时候运算符为乘法，其他的均为加法。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using 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;
}
