又 了一次，久违了。QWQ

A. Letter Song ~ 致十年后的我们

思路

签到题，把年份加上十后输出即可。

复杂度

时间复杂度和空间复杂度均为

代码实现

// Problem: Letter Song ~ 致十年后的我们
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/91072/A
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    string s;
    cin >> s;
    int v = stoi(s.substr(0, 4)) + 10;
    string t;
    for (int i = 0; i < 4; i++) {
        t += '0' + v % 10;
        v /= 10;
    }
    for (int i = 3; i >= 0; i--) {
        cout << t[i];
    }
    for (int i = 4; i < s.size(); i++) {
        cout << s[i];
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

B. 简单图形问题 - 0123

思路

如果边长为 ，正方形的面积为 ，等边三角形三角形的面积为 。

注意到 为小数，不可能为整数，所以一定不可能为等边三角形的面积，只需要判断是否为正方形的面积即可。

复杂度

时间复杂度和空间复杂度均为

代码实现

// Problem: 简单图形问题 - 0123
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/91072/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n;
    cin >> n;
    int m = sqrt(n);
    cout << (m * m == n ? 0 : 3) << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

C. 小红的机器人构造 - Ⅰ+Ⅱ+Ⅲ

思路

因为 只对行号有影响， 只对列号有影响，所以可以先分别求出可以移动到 行的删除方案数 ，可以移动到 列的删除方案数 ， 即为可以移动到 的删除方案数。

若字符串中保留了 个 ，那么字符串中需要保留 个 ，才能移动到 行。

若字符串中有 个 ，有 个 ，那么保留 个 ， 个 的方案数为 。

因为符号数最多为字符串的长度，所以是可以枚举最后字符串保留 的数量 的，加起来即为走到 行的删除方案数 ，同理得到可以移动到 列的删除方案数 ，这样就计算出了删除方案数。

计算方案数涉及到组合数，可以利用 这条公式，先预处理阶乘，然后用快速幂求逆元，就可以在 的时间复杂度求出组合数。

注意，枚举的时候 可能为负数，表示当前 的数量不够，也可能大于 ，这都是不合法的方案，不能计数到 里面。

题目还要求判断是否存在删除方案，然后输出其中任意一种合法的删除方案，这又要怎么做呢？

因为上面计算方案数的时候，是枚举了保留多少个 或者 的，如果枚举到一个合法的方案，当前保留的数量是合法的，就记录一下当前 或者 保留了多少个，同时标记存在到达 行或者 列的删除方案。

如果到达 行的删除方案存在，到达 列的删除方案存在，那么就存在到达 的删除方案，则输出 ，否则输出 表示不存在。

记录下每种字符可以保留多少个，然后遍历原字符串 ，如果遍历到某个字符 ，之前遍历的数量小于其保留的数量，就把它输出，同时该字符记录的遍历数量加一，否则就不输出。

复杂度

时间复杂度 ，空间复杂度

代码实现

// Problem: 小红的机器人构造 - Ⅰ+Ⅱ+Ⅲ
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/91072/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 5, mod = 1e9 + 7;

int fact[N];

void init()
{
    fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
}

int qmi(int a, int b)
{
    a %= mod;
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int C(int a, int b)
{
    if (b > a)
        return 0;
    int up = fact[a];
    int down = qmi(fact[b] * fact[a - b] % mod, mod - 2);
    return up * down % mod;
    // c(a,b) = a!/b!(a-b)!
}

int n, x, y;
string s;

void solve()
{
    cin >> n >> x >> y >> s;

//     num 记录 s 中 字符 c的 总数
//     lim 记录 字符 c 可以保留的数量
//     cur 记录 字符 c 当前遍历的数量
    map<char, int> num, lim, cur;
    for (char c : s) {
        num[c]++;
    }
    int f1 = 0, s1 = 0, f2 = 0, s2 = 0;
    for (int i = 0; i <= num['R']; i++) {
        int j = i - y;
        // i - j = y
        if (num['L'] >= j && j >= 0) {
            f1 = 1;
            lim['L'] = j, lim['R'] = i;
            s1 = (s1 + C(num['L'], j) * C(num['R'], i) % mod) % mod;
        }
    }
    for (int i = 0; i <= num['D']; i++) {
        int j = i + x;
        if (num['U'] >= j && j >= 0) {
            f2 = 1;
            lim['U'] = j, lim['D'] = i;
            s2 = (s2 + C(num['U'], j) * C(num['D'], i) % mod) % mod;
        }
    }
    if (!f1 || !f2) {
        cout << "NO\n";
        return;
    }
    // cout << s1 << ' ' << s2 << '\n';
    int ans = s1 * s2 % mod;
    cout << "YES ";
    for (char c : s) {
        if (cur[c] < lim[c]) {
            cur[c]++;
            cout << c;
        }
    }
    cout << ' ' << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    init();

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. 小红的差值构造 - easy+hard+extreme

思路

可以看代码实现，证明之后补上。

代码实现

// Problem: 小红的差值构造 - easy+hard+extreme
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/91072/D
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

int cal(int n, int x, int y)
{

    int res = 0;
    // for (int i = 1; i <= n; i++) {
    // res += min(abs(x - i), abs(y - i));
    // }
    if (x > 1) {
        int v = min(n, x - 1);
        res += v * (1 + v) / 2;
    }
    if (y < n) {
        int v = min(n, n - y);
        res += v * (1 + v) / 2;
    }
    int mid = (x + y) / 2;
    int l = 1, r = n;
    int li = x, ri = mid;
    int lj = mid + 1, rj = y;
    int li1 = max(li, l), ri1 = min(r, ri);
    if (li1 < ri1) {
        int len = ri1 - li1 + 1;
        res += (li1 + ri1) * len / 2 - len * x;
    }
    int lj1 = max(lj, l), rj1 = min(r, rj);
    if (lj1 < rj1) {
        int len = rj1 - lj1 + 1;
        res += len * y - (lj1 + rj1) * len / 2;
    }
    return res;
}

void solve()
{
    int n, l;
    cin >> n >> l;
    int x = (n + 1) / 2 - l / 2;
    int y = x + l;
    if (l + 1 > n) {
        x = (n + 1) / 2 - l;
        y = x + l;
    }
    cout << x << ' ' << y << ' ' << cal(n, x, y) << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}