Many Topological Problems

题目大意

给定两个数$n,k$。n表示一个有根树的结点个数。求好的全排列的数量取模1000000007的值。

定义好的全排列为，对于全排列每个存在par[i]的下标i，满足a[i] > a[par[i]] && a[i] <= a[par[i]] + k。

解题思路

可以发现，这个全排列的下标顺序的贡献与每个权值接在哪个子树下面所形成的贡献是独立的。

其实也就是树结点的编号和树的结构独立。

对于前者，顺序可以任意，有$n!$种情况，对于树的结构，权值为$i$的结点可以接在权值为$[max(1, i - k ), i - 1]$，每个权值有$\prod_2^n(max(i - 1), k)$

根据乘法原理，总情况数：$n!\prod_2^n(max(i - 1), k)$

Equalize the Array

题目大意

给定一个$n$个数，每次可以选择一个出现次数最多的所有$x$加一，问是否可以让所有值相等。

解题思路

记录每个数的出现次数，然后排序去重。

如果出现次数最多的数大于最小的数，则不可能让这个最小的数加1，输出NO

否则从小到大模拟，维护当前数的出现次数，如果它比下一个比它的数出现次数小，则输出NO

否则输出YES

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=1;
const int N=5e5+10;
int cnt[N];
int a[N];

void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cnt[i]=0;
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    int mx=0;
    for(int i=1;i<=n;i++){
        mx=max(mx,cnt[i]);
    }
    sort(a,a+n);
    if(mx>cnt[a[0]]){
        cout<<"NO\n";
        return;
    }
    n=unique(a,a+n)-a;
    int sum=0;
    for(int i=0;i<n-1;i++){
        sum+=cnt[a[i]];
        if(sum<cnt[a[i+1]]){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}