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

题意

已知你在 Y 年 M 月 D 日向十年后的自己发送了一条消息；请你精确的计算出，哪一天的自己会收到这条消息。

大概思路

不难，直接字符串截取前四个，转int后加10，直接输出，并顺便输出后半部分。

参考代码

void solve() {
	std::string s;
    std::cin >> s;
    
    int y = std::stoi(s.substr(0, 4));
    std::cout << y + 10 << s.substr(4);
}

B. 简单图形问题 - 0123

题意

对于给定的未知多边形的面积，请你判断这是一个以整数为边长的正方形、或是以整数为边长的等边三角形、或是两者均是、或是两者均不是。

大概思路

简单数学题，易知等边三角形面积一定会挂个无理数 $\sqrt 3$，所以只需要判断输入是否为平方数即可。

参考代码

void solve() {
	int n;
    std::cin >> n;
    
    int n_ = std::sqrt(n);
    if (n_ * n_ == n) {
        std::cout << 0 << "\n";
    } else {
        std::cout << 3 << "\n";
    }
}

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

题意

在无限大的网格平面上，我们使用 $(x,y)$ 表示网格中第 $x$ 行第 $y$ 列的单元格。 小红有一只笨笨机器人初始位于 $(0,0)$ 单元格，她会向机器人下达 $n$ 个指令，机器人跟随指令上下左右移动。指令字符串由 $U,D,L,R$ 四个字符混合构成，以 $1$ 作为初始下标，形式化写作 $s1​s2​⋯sn$​ 。具体的，假设 $t$ 时刻机器人位于 $(i,j)$ 单元格，若指令字符串的第 $t+1$ 个字符存在：

• 若 $s_{t+1}​=U$ ，则第 $t+1$ 时刻机器人位于 $(i+1,j)$ ；
• 若 $s_{t+1}​=D$ ，则第 $t+1$ 时刻机器人位于 $(i−1,j)$ ；
• 若 $s_{t+1}​=L$ ，则第 $t+1$ 时刻机器人位于 $(i,j−1)$ ；
• 若 $s_{t+1}​=R$ ，则第 $t+1$ 时刻机器人位于 $(i,j+1)$ ；

给出指令字符串，询问，能否删除部分指令（保持其余指令的相对位置不变），使得机器人最终位于 $(x,y)$ 。如果可以，计算有多少种不同的删除方案（删除不同下标视为不同方案），并输出其中任意一种。

大概思路

什么OI制三合一？

对于task1，我们直接统计每种字符的数量，然后判断x，y方向对应的字符是否都分别大于等于 $|x|$ 和 $|y|$。

对于task2，我们可以在根据 $x$ 和 $y$ 的值，设定每种字符只能输出多少个，然后遍历字符串模拟即可。

对于task3，我们考虑基于最少输出字符的情况，一对一对的加上相反方向的字符，对最终位置不影响。然后枚举可以加多少对，用组合数算贡献即可。显然这个枚举是 $O(n)$ 的。

参考代码

constexpr int M = 1e9 + 7;
constexpr int N = 1e5 + 5;
i64 powp(i64 a, i64 n) {
    i64 ans = 1;
    while (n) {
        if (n & 1) (ans *= a) %= M;
        (a *= a) %= M;
        n >>= 1;
    }
    return ans;
}

i64 inv(i64 x) {
    return powp(x, M - 2);
}

i64 fac[N], invfac[N];
 
void pre() {
    fac[0] = invfac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i % M;
    invfac[N - 1] = inv(fac[N - 1]);
    for (int i = N - 2; i >= 1; i--) invfac[i] = invfac[i + 1] * (i + 1) % M;
}
 
i64 C(i64 n,i64 m) {
    if (m > n) return 0;
    return fac[n] * invfac[n - m] % M * invfac[m] % M;
}


void solve() {
	int n, x, y;
    std::cin >> n >> y >> x;
    std::string s;
    std::cin >> s;
    std::map<char, int> cnt;
    for (auto &c : s) cnt[c]++;
    
    //task1
    bool ck = ((x > 0 ? (cnt['R'] >= x) : (cnt['L'] >= -x)) & (y > 0 ? (cnt['U'] >= y) : (cnt['D'] >= -y)));
    
    if (ck) {
        std::cout << "YES ";
        //task2
        auto cnt_ = cnt;
        if (x > 0) {
            cnt_['L'] = 0;
            cnt_['R'] = x;
        } else {
            cnt_['R'] = 0;
            cnt_['L'] = -x;
        }
        if (y > 0) {
            cnt_['D'] = 0;
            cnt_['U'] = y;
        } else {
            cnt_['U'] = 0;
            cnt_['D'] = -y;
        }
        auto cnt__ = cnt_;
        for (auto &c : s) {
            if (cnt_[c]) {
                std::cout << c;
                cnt_[c]--;
            }
        }
        std::cout << " ";
        //task3
        i64 ans = 1;
        if (x >= 0) {
            i64 tmp = 0;
            for (int i = 0; i <= std::min(cnt['L'], cnt['R'] - cnt__['R']); i++) {
                (tmp += C(cnt['R'], cnt__['R'] + i) * C(cnt['L'], i) % M) %= M;
            }
            (ans *= tmp) %= M;
        } else {
            i64 tmp = 0;
            for (int i = 0; i <= std::min(cnt['R'], cnt['L'] - cnt__['L']); i++) {
                (tmp += C(cnt['L'], cnt__['L'] + i) * C(cnt['R'], i) % M) %= M;
            }
            (ans *= tmp) %= M;
        }       
        if (y >= 0) {
            i64 tmp = 0;
            for (int i = 0; i <= std::min(cnt['D'], cnt['U'] - cnt__['U']); i++) {
                (tmp += C(cnt['U'], cnt__['U'] + i) * C(cnt['D'], i) % M) %= M;
            }
            (ans *= tmp) %= M;
        } else {
            i64 tmp = 0;
            for (int i = 0; i <= std::min(cnt['U'], cnt['D'] - cnt__['D']); i++) {
                (tmp += C(cnt['D'], cnt__['D'] + i) * C(cnt['U'], i) % M) %= M;
            }
            (ans *= tmp) %= M;
        }
        std::cout << ans;
        
        std::cout << "\n";
    } else {
        std::cout << "NO\n";
    }
}

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

题意

小红有一个长度为 $n$ 的数组 $\{1,2,…,n\}$ 和一个整数 $l$ ，她想找到这样两个整数 $x$ 和 $y$ ，满足 $y−x=l$，记 $f_i=\min⁡{∣a_i−x∣,∣a_i−y∣}$，使得 $f_1​+f_2​+⋯+f_n$​ 最小。

你需要输出满足条件的 $x$ 和 $y$ ，以及这个最小值。

大概思路

分类讨论，当 $l > n$ 时，显然我们无法将 $x$ 和 $y$ 同时置于数组的值域中，因此我们可以选择将其中一个端点居中放置到数组中，容易证明，这样的贡献算出来一定是最小的。设该贡献为 $calc(n)$，表示对长为 $n$ 的区间，当 $l > n$ 时的最优答案，我们可以直接用两个等差数列求和搞定该值的计算。

当 $l <= n$ 时，我们也要尽可能“居中”地放 $x$ 和 $y$。手画样例可知，答案可以划分成两个 “$l > n$” 的情况，分别长为 $l$ 和 $n - l$。此时答案即为 $calc(l) + calc(n - l)$

参考代码

void solve() {
	i64 n, l;
    std::cin >> n >> l;
    
    auto calc = [](i64 n) {
    	i64 n_ = n / 2;
    	return 1ll * (1ll + n_) * n_ - (n % 2 == 0 ? n_ : 0);
    };
    
    if (l <= n) {
        i64 l_ = (l + 1) / 2;
        i64 r = n / 2 + l_ + (l % 2 == 0);
        std::cout << r - l << " " << r << " ";
        
        std::cout << calc(n - l) + calc(l);
    } else {
    	i64 l_ = (n + 1) / 2;
    	std::cout << l_ - l << " " << l_ << " ";
    	
    	std::cout << calc(n);
    }
    std::cout << "\n";
}

吐槽

这个D题，我真的是无语si了，怎么交都是错的，然后快结束的时候，你跟我说数据有问题，会重测？ 重测后赛时跟我说赛时第一发就是AC（忽略那个TLE，我忘删vectora(n)了）？那我整整一个1小时在对空气debug是吗？