题解：AT_judge_update_202004_c Numbering Blocks

bjzjh · 2025-11-13 14:07:30 · 题解

:::warning

这篇文章是 C++ 的福利，P 党请跳过。

:::

看到题目，嗯……这题怎么做呢？应该是 \mathcal{O}(n^3) 的 dp 吧，让我们看看数据范围：What！N \le 9！STL 启动！

next_permutation 大法好！

直接枚举每个填数字的方法然后再判断是否合法就可以了。

时间复杂度：\mathcal{O}(N\times N!)，轻松通过。

:::info[Code]

#include <bits/stdc++.h>

using namespace std;

long long a1, a2, a3, Ans, a[100];

bool pd(){
    for(int i = 1; i <= a1; ++ i){
        if(a[i] <= a[i - 1]) return false;
    }

    for(int i = a1 + 1; i <= a1 + a2; ++ i){
        if(a[i] <= a[i - 1]) return false;
        if(a[i] <= a[i - a1]) return false;
    }

    for(int i = a1 + a2 + 1; i <= a1 + a2 + a3; ++ i){
        if(a[i] <= a[i - 1]) return false;
        if(a[i] <= a[i - a1 - a2]) return false;
    }

    return true;
}

int main(){
    cin >> a1 >> a2 >> a3;

    for(int i = 1; i <= a1 + a2 + a3; ++ i){
        a[i] = i;
    }

    do{
        if(pd()){
            Ans ++;
        }
    }while(next_permutation(a + 1, a + a1 + a2 + a3 + 1));

    cout << Ans;
}

:::