A. 麻将入门

By Hetmes Askalana *

题意分析

给定三个数字 $a, b, c$ 且 $a \leq b \leq c$ ，判断三个数字是否满足 $a = b = c \lor |b - a| = |c - a| = 1$

题解

直接按上文所述判断即可。

代码

C++:

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if((a == b and b == c) or ((b - a) == (c - b) and (c - b) == 1)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

Python:

a, b, c = map(int, input().split()) # Python 针对单行文本多个同类型数据的快速读取小技巧
print("Yes" if (a == b == c) or (b - a == c - b == 1) else "No") # 三目表达式

B. 数数入门

By Hetmes Askalana *

题意分析

给定一个第 $i$ 层有 $i$ 个麻将的麻将塔，判断在这个塔中，是否满足每个麻将的数值都大于它左下、右下的麻将。形式化的，满足 $\forall i \in [1, n - 1], j \in [1, i]$ ，有 $G_{ij} \leq G_{i+1,j} \land G_{ij} \leq G_{i+1,j+1}$

题解

我们遍历从 $1$ 到 $n - 1$ 的每一层，并遍历每层的每一个麻将，对于所有的麻将我们判断它是否满足如上的式子，如果不是，直接终止遍历并输出 $\rm No$ 。

代码

void solve(){
    int n; cin >> n;
    vector<vector<int>> G(n);
    for(int i = 0; i < n; ++i){
        G[i].resize(i + 1); // 鉴于每一行都不一样，直接resize了。当然你直接开n*n也不会爆。
        for(int j = 0; j <= i; ++j){
            cin >> G[i][j];
        }
    }
    bool R = 1;
    for(int i = 0; i < n - 1; ++i){
        for(int j = 0; j <= i; ++j){
            R &= (G[i + 1][j] >= G[i][j]); // 左儿子
            R &= (G[i + 1][j + 1] >= G[i][j]); // 右儿子
            // 用 &= 命题 可以处理这种情况，等价于if(!(...)) return false的写法。
            if(!R) break; // 然鹅这个if还是妹省掉
        }
        if(!R) break;
    }
    if(R){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return;
}

C. 加法入门

By Hetmes Askalana *

题意分析

本题开始的主体就已经偏离麻将本身了。

在一个长度为 $\frac {n(n + 1)} 2$ 的原始排列中选择 $1 \leq l < r \leq \frac {n(n + 1)} 2$ 并翻转，问得到的数组在构建成“麻将塔”后，编号是否满足上一题的平衡条件。

题解

首先可以明确的，由于原始数组是一个 $1, 2, 3...$ 这样的排列，那么生成的塔中第 $i$ 层的任意一个数字都是小于第 $i + 1$ 层的，所以一个没有操作过的麻将塔自然平衡，而且如果我们选择的左右端点在塔中位于同一层，则也不会对麻将塔的平衡性造成任何影响。

同样因为这个结论，如果我们将第 $i$ 层的数字替换到第 $i + 2$ 层，那么该数字必然小于第 $i + 1$ 层的任何一个数字，故左右端点必然位于相同的两层，否则将必定破坏平衡。

我们考虑左右端点在相邻两层的情况。我们可以以左右端点为界将其所在层分成两半，不难看出分界点左侧的数字全部小于右侧，所以我们把上层端点右侧的数字翻到下层左侧也一定符合其不小于上层左侧的限制，同时其数值一定无法超过再下一层的数值。另一侧同理。

但是 $a_l < a_r$ 一定成立，如果我们在翻转后 $l$ 和 $r$ 存在连接关系，那在这个位置必然会破坏麻将塔的平衡。我们可以将这个结论推广到：

在 $l, r$ 位于相邻两层时，两层的受影响范围中任意两块麻将存在支撑关系，则翻转会导致麻将塔失衡。

我们定义 $L_l, L_r$ 为 $l, r$ 所在的层数， $N_l, N_r$ 为 $l, r$ 在其所在层排第几个，则该结论可转化为 $N_l > N_r + 1$ 。但在数据范围高达 $1 \times 10^9$ 的情况下我们不可能真的建一个麻将塔并且这么判断，会爆内存。所以我们可以分析一下它的编号性质。

对于第 $i$ 层，其左、右端点的编号依次是 $\frac {n(n - 1)} 2 + 1, \frac {n(n + 1)} 2$ ，我们可以通过二分查找的方式快速定位 $l, r$ 所在的层。同时不难看出，在相邻两层且 $N$ 相同时，二者的编号正好相差下面那一层的层号，所以我们可以据此将整个麻将塔铺开，将判断简化为：

$l > r - L_r + 1$

即可解出本题。

记得开long long。

代码

typedef long long LL; // 不定义也没事，下面记得用long long，但int绝对会爆
// 还有尽量别 #define int long long。
pair<LL, LL> findEdge(LL n){ // 返回第 n 层的左右端点的编号
    return {
        (n * (n - 1) / 2) + 1, 
        ((n + 1) * n) / 2
    };
}

LL locate(LL qs){ // 二分定位 qs 在第几层
    LL l = 1, r = (1 << 30); // 1 << 30 大概就是1e9多一点
    while(l < r){
        LL mid = (l + r) / 2;
        auto [lt, rt] = findEdge(mid);
        if(qs > rt){
            l = mid;
        }else if(qs < lt){
            r = mid;
        }else{
            return mid;
        }
    }
    return l;
}

void solve(){
    LL n, l, r;
    cin >> n >> l >> r;
    LL lvl = locate(l), lvr = locate(r);
    if(abs(lvl - lvr) > 1){ // 间隔一层，跨层翻转，肯定不行
        no cout << "NO" << endl;
    }else if(lvl == lvr){ // 同层必小于下一层
        cout << "YES" << endl;
    }else{
        if(l > (r - lvr + 1)){ // 见题解结论
            cout << "YES" << endl;
        }else{
            no cout << "NO" << endl;
        }
    }
}

D. 中场撸猫

By Hetmes Askalana & bandiaozi(data)

题意分析

给定一个 $n \times n$ 的方阵，问从第 $1$ 行开始，第 $i$ 行不计顺序选择 $i$ 个数字最高能组成多少层的平衡的麻将塔。

题解

由于 $n$ 不大，我们可以直接贪。

参照 B 中的平衡塔定义，我们不难看出一个最优贪的选择策略是在每一层都选择符合要求的尽可能小的的数字，所以我们可以把模板山的每一行都先排个序。

首先，麻将塔的第一次层选择第一行最小的数字，之后每一层除了最后一个都选择这一层中不小于这一个点的右父亲的那个数字，最后一个选择不小于左父亲的即可。

如果在操作过程中发现找不到所需的数字了，那么该层的构造无法完成，麻将塔的最高层数即为 $i - 1$ 层。

如果可以完成构造程序，那么麻将塔的最高层数是 $n$ 层。

可以证明在本题中无法通过 $n$ 层模板山构造出大于 $n$ 层的麻将塔。

为了节约时间，我们可以采用二分查找的方式，每次查找上一个选择的数字的下一个数字到该行模板末尾，寻找不小于该点右父亲的第一个数字即为所求，即lower_bound()。

代码

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> G(n, vector<int>(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> G[i][j];
        }
        sort(G[i].begin(), G[i].end()); // 预排序，贪就完了
    }
    vector<int> R; // 需要记录上一层的数据来比对
    R = {G[0][0]}; // 第一层选择最小的一个就行
    for(int i = 1; i < n; ++i){
        vector<int> tmp;
        int now = -1;
        for(int j = 0; j < i; ++j){
            auto it = lower_bound(G[i].begin() + now + 1, G[i].end(), R[j]); // STL 就是香
            if(it == G[i].end()){ // 如果返回的迭代器是数组结尾，就说明根本找不到合适的数字，直接跳出。
                cout << i << endl;
                return;
            }
            tmp.push_back(*it); // *是解引用运算符，可以直接返回该指针或迭代器对应的数值
            now = it - G[i].begin(); // 刷新起点位置
        }
        if(now < n - 1){
            tmp.push_back(G[i][now + 1]); // 最后一个直接选择下一个即可，可以证明是最优的
        }else{ // 但如果下一个已经是 G[i].end() 了，那就没辙了
            cout << i << endl;
            return;
        }
        R = tmp; // 刷新上一层的数据，进入船新的一层
    }
    cout << n << endl;
    return;
}

E. 建筑入门

By Hetmes Askalana(std, data) & 神崎兰子(idea)

题意分析

构造一个长度为 $n$ 的数组 $a$ 满足 $\forall i, j \in [1, n] \land i < j$ 有 $a_i < a_j$ ，且数组 $a$ 满足 $\sum_{i=1}^n a_i \times i=k$ 。

题解

不难看出，按题目要求一可以构造出的 $k$ 最小的数组是一个 $n$ 阶排列，它的最小值是 $\frac {n(n+1)(2n+1)} 6$ 。所以如果 $k$ 比它小，那一定不行。

那我们不妨以此为基础增加各项。但受要求一限制，我们在令 $a_i+1$ 时必须选择 $[i, n]$ 这一个区间并将其值全部 $+1$ ，其对 $k$ 的贡献是 $n + (n - 1) + (n - 2) + ... + i$ ，即 $\frac {(n+i)(n-i+1)} 2$ ，也是一个 $n$ 阶排列的后缀和。

所以我们可以把问题转化为：能否选择 $n$ 个非负整数 $x_i$ 使 $\sum_{i=1}^n \frac {x_i(n+i)(n-i+1)} 2=k-\frac {n(n+1)(2n+1)} 6$ 。

我们可以使用动态规划的方式，令 $f[i][j]$ 为能否在利用 $i$ 到 $n$ 的贡献使其贡献总和为 $j$ ，如果不行则为 $-1$ ，如果行则该值表示选择 $[i, n]$ 区间将其全部增加 $f[i][j]$ 是达成 $k=j$ 的一种 $x_i$ 。若在进行完 $dp$ 后 $f[1][k-goal]$ 仍为 $-1$ 则表示无解。这样这个问题就被转化为了一个完全背包问题。

之后，我们从第一项开始逐层回溯并还原操作过程，累加作用在 $a_i$ 上的增量，得出最终所求的数组 $a$ 。

代码

void solve(){
    int n, k, alt = 0;
    cin >> n >> k;

    int g = k - (n * (n + 1) * (2 * n + 1) / 6); // 直接对上式求和再求前n项和公式就是这个，不会爆LL，放心
    if(g < 0){ // 比基础排列还小的话，那一定不满足题目要求
        cout << -1 << endl;
        return;
    }

    vector<int> chs(n), R(n, 0), cnts(n, 0);
    vector<vector<int>> f(n + 1, vector<int>(g + 1, -1));
    for(int i = 0; i < n; ++i) chs[i] = (n + i + 1) * (n - i) / 2; // 因为我习惯是0-index所以和上文所述的公式有所差异，换成1-index是一样的。

    f[n][0] = 0;
    for(int j = 1; j <= g; ++j) f[n][j] = -1;
    for(int i = n - 1; i >= 0; --i){
        for(int j = 0; j <= g; ++j) if(f[i + 1][j] != -1) f[i][j] = 0; // 如果从下一个数字开始选的方案可行，那至少存在一个 x[i] = 0，使x序列满足最终要求。 
        for(int j = chs[i]; j <= g; ++j) if(f[i][j - chs[i]] != -1) f[i][j] = f[i][j - chs[i]] + 1; // 进行一个背包 
    }

    if(f[0][g] == -1){
        cout << -1 << endl;
        return;
    }
    
    int now = g; // 从初始值，即k个基础排列权值的差值开始
    for(int i = 0; i < n; ++i){
        while(now >= chs[i] && f[i][now] > 0){ // 回溯操作过程
            ++cnts[i]; // 记录选了一个
            now -= chs[i]; // 撤销当前贡献
        }
        alt += cnts[i];
        R[i] = (i + 1) + alt;
    }

    for(int i = 0; i < n; ++i) cout << R[i] << " ";
    cout << endl;
    return;
}

F. 拆迁入门

By Hetmes Askalana(idea) & yeVegeTable(std, data)

题意分析

给定一个 $n$ 层麻将塔，问在移除 $k$ 个麻将后，总共有多少个满足被移除或因失去左右支点被移除的麻将。

题解（苯环）

$\begin{array}{c} \hspace{30pt} 1 \hspace{30pt} \\ \hspace{15pt} 2 \quad 3 \hspace{15pt} \\ 4 \quad 5 \quad 6 \\ 7 \quad 8 \quad 9 \quad 10 \\ \end{array}$

不难发现的是，如果我们移除了一行中一段连续的麻将，则实际上移除的是一个等边三角形形状的麻将。

例如上图中，如果我们移除 $7\ 8\ 9$ ，则实际上 $2,4,5,7,8,9$ 这个边长为 $3$ 的等边三角形都会消失。

因此就不难想到做法，我们可以按行倒着来维护这一过程，具体来说：

我们倒序枚举输入数据的点中出现过的行，每次统计一段等边三角形的贡献，但是这里需要注意的是，如果我们直接统计贡献，这实际上是不方便的，这是因为可能在这个三角形占据的行中，有别的麻将也被推倒了。（例如 $7,8,9$ 对应的等边三角形所占据的行中， $6$ 这个点也有可能被主动移除了，而我们也需要处理 $6$ 所产生的贡献）因此我们还需要处理这些麻将的贡献。

而这里，更方便的处理方式是，我们只统计这个等边三角形的下面一部分，即一个等腰梯形。而等腰梯形上面的部分，在我们下一次的处理中再去做统计。因此我们需要计算出这个本应被完全处理的等边三角形现在没有被处理的部分的长度和高度，扔到下一个需要处理的行的 $vector$ 中处理。

而对于每行的处理，我们只需要用 $vector<pair>$ 维护所有连续点组成的区间，然后做区间合并即可，详见代码：

void solve() {
    int n, k;
    cin >> n >> k;
    map<int, vector<P>> mp;
    int up = n * (n + 1) / 2;
    for(int i = 1, x; i <= k; i++) {
        cin >> x;
        int lo = 1, hi = n;
        while(lo < hi) {
            int mid = (lo + hi) / 2;
            if(mid * (mid + 1) / 2 >= x) hi = mid;
            else lo = mid + 1;
        }
        mp[lo].emplace_back(x, x);
    }
    vector<vector<P>> a;
    vector<int> step;
    for(auto & [x, v] : mp) {
        a.emplace_back(v);
        step.emplace_back(x);
    }
    reverse(a.begin(), a.end());
    reverse(step.begin(), step.end());
 
    int ans = 0;
    for(int i = 0; i < a.size(); i++) {
        auto v = a[i];
        int down = step[i], up = 0;
 
        sort(v.begin(), v.end());
        vector<P> merged;
        for(auto & [L, R] : v) {
            if(merged.size() && merged.back().y >= L - 1) {
                merged.back().y = max(merged.back().y, R);
            } else {
                merged.emplace_back(L, R);
            }
        }
 
        if(i + 1 < a.size()) {
            up = step[i + 1];
        }
 
        for(auto & [L, R] : merged) {
            int len = R - L + 1;
            if(up <= down - len) {
                ans += len * (len + 1) / 2;
            } else {
                int H = down - up;
                int nL = L - (H * down - (H + 1) * H / 2);
                int nR = R - (H * down - (H - 1) * H / 2);
                int U = nR - nL + 1 + 1, D = len;
                ans += (U + D) * H / 2;
                if(i + 1 < a.size()) {
                    a[i + 1].emplace_back(nL, nR);
                }
            }
        }
    }
    cout << ans << endl;
}

时间复杂度： $O(k\times log(k))$ （均摊）。

牛客周赛81 - 题解

A. 麻将入门

题意分析

题解

代码

B. 数数入门

题意分析

题解

代码

C. 加法入门

题意分析

题解

代码

D. 中场撸猫

题意分析

题解

代码

E. 建筑入门

题意分析

题解

代码

F. 拆迁入门

题意分析

题解（苯环）