Practice.

A. Lucky Numbers

题意

此处给出 \(A\) 题和 \(C\) 题的定义：

对于一个数字，将所有位上的数取出，组成一个序列 \(a\)。定义 \(l = a_{\max} - a_{\min}\)。

那么，给定一个区间 \([l ,r]\)，\(l\) 的最大值对应的数就是最幸运数，最小值对应的数就是最不幸运数。

给定一个区间 \([l, r]\)，输出任意一个最幸运数。

思路

首先，如果考虑幸运数，那么我们不难发现，我们只需关注十位和个位上的数即可，因为在这里就可以搞出最大值。

那么，暴力遍历 \([l, l + 100]\) 即可。

时间复杂度：\(O(100x)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int l, r;
    cin >> l >> r;
    pii ans = {0, l};
    for(int i=l;i<=min(l + 100, r);i++){
        int tmp = i, mn = inf, mx = 0;
        while(tmp > 0){
            int cur = tmp % 10;
            mn = min(mn, cur);
            mx = max(mx, cur);
            tmp /= 10;
        }
        if(ans.fs < mx - mn){
            ans = {mx - mn, i};
        }
    }
    cout << ans.sc << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

为什么我会想着去构造（（

B. Playing in a Casino

题意

给定 \(n\) 个人的 \(m\) 张手牌对应的数字，构成序列 \(a_{i,x}\)。

输出总和。

思路

显然，我们可以直接竖着看，看一下去掉绝对值的情况。

不难发现，我们固定第二维 \(x\)，那么对于竖向构造得到的每一个序列，我们进行排序，可以得到形如下面的序列：

\(a, b, c, d, e\)。

最后，这个序列的值为 \(-4a-2b+2d+4e\)。

或者说，我们只需排序后遍历，乘上权重加起来即可。权重首项为 \(n - 1\)，依次递减 \(2\)。

时间复杂度：\(O(mn)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(m, vector<int>(n));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> a[j][i];
    int ans = 0;
    for(int i=0;i<m;i++){
        sort(a[i].begin(), a[i].end());
        for(int j=0;j<n/2;j++) ans += (a[i][n - j - 1] - a[i][j]) * (n - 1 - 2 * j);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

简简单单（x

C. Unlucky Numbers

题意

给定一个区间 \([l, r]\)，输出任意一个最不幸运数。

思路

我们可以考虑用 \(DFS\) 来实现，用拼接的方式得到答案。

考虑下面的两个剪枝：

当前拼接得到的数可以预测是否一定超出边界，如对于 \(12\)，范围为 \([135, 189]\)，那么由 \(12 \times 10 + 10 = 130 < 135\) 可知一定不在边界内。另一个边界直接判大小即可。
因为深搜，所以能提前得到一些答案，那么如果当前 \(\max - \min\) 已经大于之前求得的答案了，就不用继续了。

时间复杂度：不会分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

string l, r, ans;
int val = inf, vl, vr;

void init(){}

void dfs(int x, int mn, int mx, const string& now){
    int vn = stoll(now);
    if(x == l.size()){
        if(vn >= vl && vn <= vr && mx - mn < val){
            val = mx - mn;
            ans = now;
        }
        return;
    }
    int exp = vn * pow(10, l.size() - x); //优化一下查找
    if(exp + pow(10, l.size() - x) < vl || exp > vr || mx - mn >= val) return;
    for(int i=0;i<=9;i++) dfs(x + 1, min(mn, i), max(mx, i), now + (char) (i + '0'));
}

void solve() {
    cin >> l >> r;
    vl = stoll(l), vr = stoll(r);
    if(l.size() < r.size()){
        for(int i=0;i<l.size();i++) cout << 9;
        cout << '\n';
    }else{
        ans = "";
        val = inf;
        for(int i=l[0]-'0';i<=r[0]-'0';i++){
            dfs(1, i, i, to_string(i));
        }
        cout << ans << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

就很无脑，不知道dp咋做（