Codeforces Round 792 (Div. 1 + Div. 2)

A. Digit Minimization

题目大意

给你一个十进制表示中不包含$0$的数$s$，Alice可以选择交换两个不同位置的数，Bob删除十进制末尾的数，直到剩下的数字只有一个。

问最后剩下的数字，最小是多少？

题目解析

这个题首先是分析数字的个数是 $1$ 到 $3$ 的情况，然后将更多数字的情况转化到之前已有的情况当中。

• 当数字的个数是 $1$ 的时候，结果就是 $s_0$ 。
• 当数字的个数是 $2$ 的时候，因为必须进行一次交换 $s_0 \leftrightarrow s_1$ ，所以结果就是 $s_1$。
• 当数字的个数是 $3$ 的时候，可以取到 $s_0, s_1, s_2$ 中的最小值。
  • 假如最小值是 $s_0$，第一步可以交换 $s_0, s_1$，第二步再交换 $s_0, s_1$。
  • 假如最小值是 $s_1$，第一步可以交换 $s_0, s_2$，第二步再交换 $s_0, s_1$。
  • 假如最小值是 $s_2$，第一步可以交换 $s_1, s_2$，第二步再交换 $s_0, s_1$。
• 当数字个数大于 $3$ 的时候，如果最小的数字不在前 $3$ 的位置，可以先将最小的数字转移到前 $3$ 的位置，然后如果长度还是大于 $3$ 的话，可以将 $s_0, s_1$ 进行交换，那么转移到长度为 $3$ 的时候，确保最小值在这 $3$ 个位置当中，那么一定能够取得最小值。

参考代码

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

题目大意

已知 $a, b, c (a < b < c)$ ，且$x, y, z$满足以下条件：

$$\left\{\begin{matrix} x \bmod y = a\\ y \bmod z = b\\ z \bmod x = c \end{matrix}\right.$$

对于每组给定的 $a, b, c$， 构造一组 $x, y, z$ 满足上述条件。

题目解析

把三个式子用公式表示，如下所示：

$$\left\{ \begin{matrix} x = k_1 * y + a\\ y = k_2 * z + b\\ z = k_3 * x + c \end{matrix} \right.$$

由上式可知，如果 $k_1, k_2, k_3$ 均大于 $0$，可得：

$$\left\{ \begin{matrix} x \geq y \\ y \geq z \\ z \geq x \end{matrix} \right.$$

那么 $x = y = z$，此时 $a = b = c = 0$，不符合题意。
由此 $k_1, k_2, k_3$ 当中至少有一个数是 $0$。
由此我们有 $k_1k_2k_3 = 0$。

把第三个式子带入第二个，$y = k_2k_3x + k_2c + b$
然后在把这个式子带入到第一个式子当中

$$x = k_1k_2k_3x + k_1k_2c + k_1b + a$$

由此，$x = k_1k_2c + k_1b + a$

设 $k_1, k_2$ 均等于 $1$。（当然构造其他正整数也可以）

$$\left\{ \begin{matrix} x = a + b + c \\ y = b + c \\ z = c \end{matrix} \right.$$

参考代码

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

题目大意

给你一个 $n$ 行 $m$ 列的格子，你可以选择两列，交换这两列中每一行的两个数字，使其满足每行满足从左到右不递减。

题目解析

把原本的数据$arr$拷贝一份$brr$，然后排序拷贝数据$brr$中的每一行。
比较第$i$行第$j$列中$arr_{ij}$和$brr_{ij}$是否相同。如果不同，就代表第$j$列经过了交换。

然后讨论一下经过交换的列的数目：

• 经过交换的列的数目是$0$，那么直接输出两个相同的列就可以了。
• 经过交换的列的数目是$1$，不存在这样的情况。
• 经过交换的列的数目是$2$，尝试在原本的$arr$中交换这两列，然后比较是否是和$brr$一致。
• 经过交换的列的数目大于$2$，这样的情况不能再交换两列的情况下完成。

参考代码

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;
}