题目1

题目链接
题目大意：
给出一个整数n，现在可以对整数执行一个操作：
选择整数上两个不同位数的数字交换位置，然后移除整数最右边一位的数字；
重复这个过程，直到整数只剩下1位；
现在想知道这个剩下的数字最小可能为多少。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例俩行，第一行 整数 𝑛 (10≤𝑛≤1e9)

输出：
每个样例一行，剩下最小的数字；

Examples
input
3
12
132
487456398
output
2
1
3

题目解析：
右边第二位是必胜位，每次都选择其他位数的数字进行交换，在只剩下2位数字的时候，将第一位和第二位交换，然后会去掉右边的数字，剩下原来右边第二位的数字；
也就是说，当时数字位数大于等于3的时候，可以选择整数上最小的数字，将这个数字放在右边第二位，再采用上面的策略必然可以留下来；
当数字位数只有2位时，留下来的数字必然是最右边的数字；

class Solution {
    static const int N = 201010;
    int a[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            if (n < 99) {
                cout << n % 10 << endl;
            }
            else {
                int ans = 9;
                while (n) {
                    ans = min(ans, n % 10);
                    n /= 10;
                }
                cout << ans << endl;
            }
        }
    }
}
ac;

题目2

题目链接
题目大意：
给出整数a，b，c，满足a<b<c；
构造三个整数x，y，z，满足：
x mod y = a;
y mod z = b;
z mod x = c;

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000)
每个样例一行，𝑎 , 𝑏, 𝑐 (1≤𝑎<𝑏<𝑐≤1e8).

输出：
每个样例一行，输出满足的𝑥 , 𝑦, 𝑧 (1≤𝑥,𝑦,𝑧≤1e18)

Examples
input
4
1 3 4
127 234 421
2 7 8
59 94 388
output
12 11 4
1063 234 1484
25 23 8
2221 94 2609

题目解析：
题目要求里面并没有包括x、y、z的大小关系，那么如果要满足x%y = a，最简单的做法就是x=a，并且满足x<y；
同理，可以得到y%z=b，会有y=b，并且满足y<z；
但是在z%x=c，假如我们令z=c，满足z<x则会出现异常，因为由前面两个已经可以递推得到x<y<z；并且由于a<c，x如果为a是无法得到c的；

由于a<c的约束，我们先考虑满足z%x=c的限制，即是令z=c，并且满足z<x；
接着是y%z=b，可以令y=b，由于b<c=z，所以这个也能够满足；
剩下的就是x%y=a，已知y=b，那么有x%b=a，即是x=b*k + a；

此时要满足x=bk + a，z<x，可以令k=c，那么有x=cb+a；

class Solution {
    static const int N = 201010;

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            lld a, b, c;
            cin >> a >> b >> c;
            cout << (c * b + a) << " " << b << " " << c << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
给出n x m的矩阵a，a[i][j]是一个整数；
现在需要选择任意两列进行交换，现在想知道是否存在一种交换方式，满足：
交换之后，每一行的元素，从左到右都是非递减的；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100)
每个样例第一行是整数𝑛 and 𝑚 (1≤𝑛,𝑚≤2⋅1e5)
接下来会有n行m列的整数 𝑎[𝑖,𝑗] (1≤𝑎[𝑖,𝑗]≤1e9)；

输出：
每个样例一行，输出满足的交换位置；（可以交换相同位置）
如果无解则输出-1；

Examples
input
5
2 3
1 2 3
1 1 1
2 2
4 1
2 3
2 2
2 1
1 1
2 3
6 2 1
5 4 3
2 1
1
2

output
1 1
-1
1 2
1 3
1 1

题目解析：
先考虑一维的情况，给出一个数组，交换任意两个数字，然后将数组变成非递减；
由于每次只能选择交换相同位置或者两个位置，也就是说要么影响2个数字，要么不影响，那么可以先计算一遍最长非递减的子序列得到长度k；
根据k和n的区别，如果n-k>2，那么就是必然无解；
但是由于k可以等于n、n-1、这几种情况是比较难以决策如何选择出来两个位置；
考虑到只有一次交换（2个位置），那么假如将数组直接排序，是不是也可以通过这个来对比得到这个位置？
假如排序之后，将有序数组和原数组对比，得到若干个不匹配的位置，如果不同数大于2则无解，如果不同数为2则就是交换的两个位置，如果不同数为0则不需要交换；（这里不存在不同数位1的情况）

基于上面一维的分析，我们可以推导到二维数组的情况。
当我们从上到下去遍历每一行元素时，当我们第一次找到存在2个位置不同的时候，我们就将这位置作为最终的交换位置；
将整个矩阵相应列进行交换，最后判断结果是否符合要求。

注意：如果某一行完全匹配（不同数为0），此时应该先忽略，去找不同位置为2的行；

class Solution {
    static const int N = 201010;
    vector<int> a[N];
    vector<int> b[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, m;
            cin >> n >> m;
            for (int i = 0; i < n; ++i) {
                a[i].clear();
                b[i].clear();
                for (int j = 0; j < m; ++j) {
                    int x;
                    scanf("%d", &x);
                    a[i].push_back(x);
                    b[i].push_back(x);
                }
            }
            vector<int> diff;
            bool ans = true;
            for (int i = 0; i < n; ++i) {
                sort(a[i].begin(), a[i].end());
                if (!diff.size()) {
                    for (int j = 0; j < m; ++j) {
                        if (a[i][j] != b[i][j]) {
                            diff.push_back(j);
                        }
                    }
                }
            }
            if (diff.size() > 2) {
                ans = false;
            }
            else if (!diff.size()){
                diff.push_back(0);
                diff.push_back(0);
            }
            else {
                for (int i = 0; i < n; ++i) {
                    int x = diff[0], y = diff[1];
                    int tmp = b[i][x];
                    b[i][x] = b[i][y];
                    b[i][y] = tmp;
                    for (int j = 0; j < m; ++j) {
                        if (a[i][j] != b[i][j]) {
                            ans = false;
                        }
                    }
                }
                
            }
            
            if (ans) {
                cout << diff[0] + 1 << " " << diff[1] + 1 << endl;
            }
            else {
                cout << (-1) << endl;
            }
            
        }
    }
}
ac;

题目4

题目链接
题目大意：
在一个n x m的方格矩阵中，小明要从左上角（1，1）到右下角（n，m），小红要从左下角（n，1）到右上角（1，m）；
每个相邻格子的行动代价是1；
小红先出发，沿路中每个经过格子都会放下一个传送器，这个不需要代价；
小明晚出发，小明如果站在某个有传送器的格子，那么可以花费1代价，传送到另外一个有传送器的格子；
问小红和小明到达目的，总的代价最小为多少；

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000)
每个样例第一行 整数 𝑛, 𝑚 ( (1≤𝑛,𝑚≤1e5)

输出：
每个样例一行，输出最小的总代价；

Examples
input
7
7 5
5 7
1 1
100000 100000
57 228
1 5
5 1
output
15
15
0
299998
340
5
5

题目解析：
在没有传送器的情况下，小红和小明的路径总代价都是n+m；
假设小红不考虑小明，按照最短路径到达，总代价是n+m；然后小明借助小红的路径，理论上能节省的最大路径是max(n, m)-1，总的代价就是n+m+max(n, m)-1；
此时路径应该就是小红先走到(1, 1)，再走到(1, m）；
有没有可能小红为了让小明能够尽可能传送，特意绕路？不会，因为小红要走过的路才能让小明传送；所以一旦远离小红的最优路径n+m，所有给小明节省的代价，其实都是不划算的.
注意：边界情况要考虑，n=1 和 m=1。

class Solution {
    static const int N = 201010;

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, m;
            cin >> n >> m;
            if (n == 1 || m == 1) {
                if (n == m) cout << 0 << endl;
                else cout << max(n, m) << endl;
            }
            else cout << (n + m - 2) * 2 - max(n, m) + 2 << endl;
        }
    }
}
ac;

题目5

题目链接
题目大意：
给出包括n个非负整数的数组a，我们可以计算这个数组的beauty值：
将数组每个元素除以k，向下取整得到这个元素的beauty值，数组的beauty值等于所有元素的beauty值总和；
现在给出n、k、数组beauty值b和数组元素累加和s，求是否能够构造数组a；

输入：
第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤1000)
每个样例第一行 整数 𝑛, 𝑘, 𝑏, 𝑠 (1≤𝑛≤1e5, 1≤𝑘≤1e9, 0≤𝑏≤1e9, 0≤𝑠≤1e18).

输出：
每个样例一行，如果无解输出-1；如果有解则输出n个整数；𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤1e18)

Examples
input
8
1 6 3 100
3 6 3 12
3 6 3 19
5 4 7 38
5 4 7 80
99978 1000000000 100000000 1000000000000000000
1 1 0 0
4 1000000000 1000000000 1000000000000000000
output
-1
-1
0 0 19
0 3 3 3 29
-1
-1
0
0 0 0 1000000000000000000

题目解析：
为了方便思考，我们先考虑数组只有3个元素的情况，那么有：
a1 + a2 + a3 = s ;
a1/k + a2/k + a3/k = b;

那么我们可以令a1=k * b，先保证条件b可以满足；
因为除以k的原因，接下来a1到a3，都可以增大k-1的大小而且不影响b的值；
那么s的上限就是k * b + n * (k - 1)，下限就是k * b；
满足这里的条件就有解。

思考：
如何证明正确性？假设a1/k + a2/k，a2需要大于k，那么将a2-k，并将a1+k是等价的；

注意：
超过int32，不过样例已经覆盖了这样的case。

class Solution {
    static const int N = 201010;
public:
    void solve() {
        lld t;
        cin >> t;
        while (t--) {
            lld n, k, b, s;
            cin >> n >> k >> b >> s;
            lld maxSum = k * b + n * (k - 1);
            if (maxSum < s || b * k > s) {
                cout << -1 << endl;
            }
            else {
                s -= b * k;
                for (lld i = 0; i < n; ++i) {
                    lld tmp = min(k - 1, s);
                    s -= tmp;
                    if (i == 0) tmp += b*k;
                    cout << tmp << " ";
                }
                cout << endl;
            }
        }
    }
}
ac;