Codeforces Round 792 (Div. 1 + Div. 2)
A. Digit Minimization
题目大意
给你一个十进制表示中不包含的数,Alice可以选择交换两个不同位置的数,Bob删除十进制末尾的数,直到剩下的数字只有一个。
问最后剩下的数字,最小是多少?
题目解析
这个题首先是分析数字的个数是 到 的情况,然后将更多数字的情况转化到之前已有的情况当中。
- 当数字的个数是 的时候,结果就是 。
- 当数字的个数是 的时候,因为必须进行一次交换 ,所以结果就是 。
- 当数字的个数是 的时候,可以取到 中的最小值。
- 假如最小值是 ,第一步可以交换 ,第二步再交换 。
- 假如最小值是 ,第一步可以交换 ,第二步再交换 。
- 假如最小值是 ,第一步可以交换 ,第二步再交换 。
- 当数字个数大于 的时候,如果最小的数字不在前 的位置,可以先将最小的数字转移到前 的位置,然后如果长度还是大于 的话,可以将 进行交换,那么转移到长度为 的时候,确保最小值在这 个位置当中,那么一定能够取得最小值。
参考代码
int main() {
int t;
cin >> t;
while(t--){
string s;
cin >> s;
if(s.length() == 1) cout << s[0] << endl;
else if(s.length() == 2) cout << s[1] << endl;
else cout << *min_element(itr(s)) << endl;
}
return 0;
}
B. Z mod X = C
题目大意
已知 ,且满足以下条件:
对于每组给定的 , 构造一组 满足上述条件。
题目解析
把三个式子用公式表示,如下所示:
由上式可知,如果 均大于 ,可得:
那么 ,此时 ,不符合题意。
由此 当中至少有一个数是 。
由此我们有 。
把第三个式子带入第二个,
然后在把这个式子带入到第一个式子当中
由此,
设 均等于 。(当然构造其他正整数也可以)
参考代码
int main() {
int t;
cin >> t;
while(t--){
ll a, b, c;
cin >> a >> b >> c;
ll x = a + b + c, y = b + c, z = c;
cout << x << " "<< y << " " << z << endl;
}
return 0;
}
C. Column Swapping
题目大意
给你一个 行 列的格子,你可以选择两列,交换这两列中每一行的两个数字,使其满足每行满足从左到右不递减。
题目解析
把原本的数据拷贝一份,然后排序拷贝数据中的每一行。
比较第行第列中和是否相同。如果不同,就代表第列经过了交换。
然后讨论一下经过交换的列的数目:
- 经过交换的列的数目是,那么直接输出两个相同的列就可以了。
- 经过交换的列的数目是,不存在这样的情况。
- 经过交换的列的数目是,尝试在原本的中交换这两列,然后比较是否是和一致。
- 经过交换的列的数目大于,这样的情况不能再交换两列的情况下完成。
参考代码
int main() {
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
vector arr(n, vector<int>(m, 0));
for(auto& row: arr) for(auto& it: row) cin >> it;
vector brr(arr);
for(auto& row: brr){
sort(itr(row));
}
map<int, int> mp;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
if(brr[i][j] != arr[i][j]){
mp[j]++;
}
}
}
if(mp.size() < 2){
cout << 1 << " " << 1 << endl;
}else if(mp.size() == 2){
int x = mp.begin()->first, y = mp.rbegin()->first;
for(auto& row: arr) swap(row[x], row[y]);
bool ok = true;
for(int i = 0; i < n and ok; ++i){
for(int j = 0; j < m and ok; ++j){
if(arr[i][j] != brr[i][j]){
ok = false;
}
}
}
if(ok) cout << x + 1 << " " << y + 1 << endl;
else cout << -1 << endl;
}else{
cout << -1 << endl;
}
}
return 0;
}
Codeforces Round 792 (Div. 1 + Div. 2)
https://www.dianhsu.com/2022/05/20/cf1684/