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

A. Digit Minimization

题目大意

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

问最后剩下的数字,最小是多少?

题目解析

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

  • 当数字的个数是 11 的时候,结果就是 s0s_0
  • 当数字的个数是 22 的时候,因为必须进行一次交换 s0s1s_0 \leftrightarrow s_1 ,所以结果就是 s1s_1
  • 当数字的个数是 33 的时候,可以取到 s0,s1,s2s_0, s_1, s_2 中的最小值。
    • 假如最小值是 s0s_0,第一步可以交换 s0,s1s_0, s_1,第二步再交换 s0,s1s_0, s_1
    • 假如最小值是 s1s_1,第一步可以交换 s0,s2s_0, s_2,第二步再交换 s0,s1s_0, s_1
    • 假如最小值是 s2s_2,第一步可以交换 s1,s2s_1, s_2,第二步再交换 s0,s1s_0, s_1
  • 当数字个数大于 33 的时候,如果最小的数字不在前 33 的位置,可以先将最小的数字转移到前 33 的位置,然后如果长度还是大于 33 的话,可以将 s0,s1s_0, s_1 进行交换,那么转移到长度为 33 的时候,确保最小值在这 33 个位置当中,那么一定能够取得最小值。

参考代码

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)a, b, c (a < b < c) ,且x,y,zx, y, z满足以下条件:

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

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

题目解析

把三个式子用公式表示,如下所示:

{x=k1y+ay=k2z+bz=k3x+c\left\{ \begin{matrix} x = k_1 * y + a\\ y = k_2 * z + b\\ z = k_3 * x + c \end{matrix} \right.

由上式可知,如果 k1,k2,k3k_1, k_2, k_3 均大于 00,可得:

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

那么 x=y=zx = y = z,此时 a=b=c=0a = b = c = 0,不符合题意。
由此 k1,k2,k3k_1, k_2, k_3 当中至少有一个数是 00
由此我们有 k1k2k3=0k_1k_2k_3 = 0

把第三个式子带入第二个,y=k2k3x+k2c+by = k_2k_3x + k_2c + b
然后在把这个式子带入到第一个式子当中

x=k1k2k3x+k1k2c+k1b+ax = k_1k_2k_3x + k_1k_2c + k_1b + a

由此,x=k1k2c+k1b+ax = k_1k_2c + k_1b + a

k1,k2k_1, k_2 均等于 11。(当然构造其他正整数也可以)

{x=a+b+cy=b+cz=c\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

题目大意

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

题目解析

把原本的数据arrarr拷贝一份brrbrr,然后排序拷贝数据brrbrr中的每一行。
比较第ii行第jj列中arrijarr_{ij}brrijbrr_{ij}是否相同。如果不同,就代表第jj列经过了交换。

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

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

参考代码

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://dianhsu.com/2022/05/20/cf1684/
作者
Dian Hsu
发布于
2022年5月20日
许可协议