https://codeforces.com/gym/102253

L. Limited Permutation

 

题意：给定 nn，长为 nn 的数组 l,rl,r，问有几种 nn 的排列 pp 满足：对于每一个 ii 都有：对于任意 L,RL,R，p[L...R]p[L...R] 的最小值为 p[i]p[i] 当且仅当 l[i]≤L≤i≤R≤r[i]l[i]\le L\le i\le R\le r[i]。

题目简单来说就是：对于每一个 ii，pip_i 是 p[li...ri]p[l_i...r_i] 的最小值，且 p[li−1]>pip[l_i-1]>p_i 且 p[ri+1]>pip[r_i+1]>p_i，问满足条件的排列数。

树上dp

首先要发现如果题目有解，那么给出的 [li,ri][l_i,r_i] 一定不会交叉，只会包含。

对于每个区间，找到最小的包含它的区间，作为父亲。

由于不会交叉，所以建出的一定是树，且由于一定有一个 [li,ri]=[1,n][l_i,r_i]=[1,n]，所以一定是一棵树。

可以通过将所有区间按照左端点从小到大，右端点从大到小排序，遍历的同时维护一个栈，保持栈顶就是当前区间的父亲。

建出树后，由于父亲的 [l,r][l,r] 区间包含儿子的 [l,r][l,r] 区间，所以父亲的值一定小于儿子，要求合法的赋值方案数。

dp[u]dp[u] 表示 uu 的子树的方案数，则 dp[u]=Csize[u]−1size[v1]dp[v1]×Csize[u]−1−size[v1]size[v2]dp[v2]×Csize[u]−1−size[v1]−size[v2]size[v3]dp[v3]×⋯dp[u]=C_{size[u]-1}^{size[v_1]}dp[v_1]\times C_{size[u]-1-size[v_1]}^{size[v_2]}dp[v_2]\times C_{size[u]-1-size[v_1]-size[v_2]}^{size[v_3]}dp[v_3]\times\cdots.

判断无解的情况比较多，除了建不出树，存在区间交叉外，如果儿子的 [l,r][l,r] 区间包含父亲的下标，那么也是矛盾的。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
bool dbg = true;
#define debug(x) if (dbg) cout << #x << ":\t" << (x) << endl;
#define here if (dbg) printf("Passing [%s] in Line %d\n", __FUNCTION__, __LINE__);
using namespace std;
typedef long long LL, ll;
typedef long long LD;
typedef pair<int, int> Pair;
#define random(a, b) uniform_int_distribution<int> ((a), (b))(mt)
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e6 + 5;
const int N = maxn;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const LD pi = acos(-1.0);
const LD eps = 1e-8;
ll fac[N], inv[N];

ll power(ll a, int x) {
    ll ans = 1;
    while (x) {
        if (x & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        x >>= 1;
    }
    return ans;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = power(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}

ll C(int n, int k) {
    if (n < k)return 0;
    return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int n;
int tt;
int l[N], r[N], d[N], c[N];
vector<int> G[N];
ll dp[N];

void dfs1(int u, int _fa) {
    c[u] = 1;
    for (int v:G[u]) {
        if (v == _fa)continue;
        dfs1(v, u);
        c[u] += c[v];
    }
}

void dfs2(int u, int _fa) {
    dp[u] = 1;
    int m = c[u] - 1;
    for (int v:G[u]) {
        if (v == _fa)continue;
        dfs2(v, u);
        dp[u] = dp[u] * C(m, c[v]) % mod * dp[v] % mod;
        m -= c[v];
    }
}

typedef pair<int, int> pii;

struct X {
    int id, l, r;

    bool operator==(const X &b) const {
        return l == b.l && r == b.r;
    }
};

bool cmp(const X &a, const X &b) {
    return a.l == b.l ? a.r > b.r : a.l < b.l;
}

vector<X> vc;
stack<X> st;
int vis[N];
vector<int>g[N];
bool dfs(int u)
{
    vis[u] = 1;
    for(int v:g[u]){
        if (vis[v] == 1) return false;
        if (vis[v] == 0 && !dfs(v)) return false;
    }
    vis[u] = -1;
    return true;
}
ll solve1() {

    for (int i = 1; i <= n; i++)G[i].clear(), d[i] = 0,g[i].clear(),vis[i]=0;
    for(int i=1;i<=n;i++){
        if(l[i]-1>=1)g[i].push_back(l[i]-1);
        if(r[i]+1<=n)g[i].push_back(r[i]+1);
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            if(!dfs(i))return 0;
        }
    }
    vc.clear();
    for (int i = 1; i <= n; i++)vc.push_back({i, l[i], r[i]});
    sort(vc.begin(), vc.end(), cmp);
    if (vc[0].l != 1 || vc[0].r != n) {
        return 0;
    }
    while (!st.empty())st.pop();
    int flg = 1;
    for (int i = 0; i < (int) vc.size() && flg; i++) {
        X p = vc[i];
        if (i != 0 && p == vc[i - 1]) {
            return 0;
        }
        if (!st.empty() && p.l <= st.top().r && p.r > st.top().r) {
            return 0;
        }
        while (!st.empty() && st.top().r < p.r) {
            st.pop();
        }
        if (i != 0 && st.empty()) {
            return 0;
        }
        if (!st.empty()) {
            if (st.top().r < p.r) {
                flg = 0;

                break;
            }
            int u = st.top().id, v = p.id;
            if(p.l<=u && p.r >= u)return 0;
            d[v]++;
            G[u].push_back(v);
        }
        st.push(p);
    }
    int rt = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] == 0) {
            rt = i;
            break;
        }
    if (!rt)return 0;
    dfs1(rt, 0);
    dfs2(rt, 0);
    for (int i = 1; i <= n; i++)
        if (!dp[i]) {
            return 0;
        }
    return dp[rt];
}

int main() {
    init();
    while(~scanf("%d", &n)){
        tt++;
        for(int i=1;i<=n;i++)scanf("%d", &l[i]);
        for(int i=1;i<=n;i++)scanf("%d", &r[i]);
        printf("Case #%d: %d\n", tt, solve1());
    }
    return 0;
}

 

C. Colorful Tree

 

题意：给定一棵树，每个节点有一种颜色，一条路径的权值等于路径上的不同颜色个数，问所有路径的权值之和。

dfs

对于每种颜色，逆向考虑不经过它的路径的条数。

siz[u] 表示 u 的子树大小，sum[i] 表示当前所有颜色 i 的节点的子树大小之和。

假设现在位于节点 uu，dfs完儿子 vv，则 vv 的子树的最上部分可能会有一些节点的颜色与 uu 不同，这时就出现了不经过颜色 c[u]c[u] 的路径。通过在进入 dfs(v) 之前记录一下 sum[cu]sum[c_u]，dfs(v) 之后再记一下 sum[cu]sum[c_u]，两者之差就是 vv 的子树中所有颜色为 cuc_u 的节点的子树大小之和。siz[v]−son[cu]siz[v]-son[c_u] 就是 vv 的子树中顶部的那部分颜色不等于 cuc_u 的节点的个数。

由于每次都是在 uu 处理儿子节点 vv，所以并没有处理整棵树顶部的那部分。n−sum[i]n-sum[i] 就是整棵树顶部颜色不为 ii 的节点的个数。

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
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const double eps = 1e-8;
const double PI = acos(-1);
typedef pair<int, int> pii;
int T;
int n, m, c[N], vis[N];
vector<int> G[N];
int siz[N], sum[N];

ll C(int n) { return 1ll * n * (n - 1) / 2; }

ll ans;

void dfs(int u, int _fa) {
    siz[u] = 1;
    int x = sum[c[u]];
    for (int v:G[u]) {
        if (v == _fa)continue;
        int tmp = sum[c[u]];
        dfs(v, u);
        siz[u] += siz[v];
        ans += C(siz[v] - (sum[c[u]] - tmp));
    }
    sum[c[u]] = x + siz[u];
}

int main() {
    while (~scanf("%d", &n)) {
        T++;
        for (int i = 1; i <= n; i++)G[i].clear(), vis[i] = 0, sum[i] = 0;
        ans = 0;
        m = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &c[i]);
            if (!vis[c[i]]) {
                m++;
                vis[c[i]] = 1;
            }
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);
        for (int i = 1; i <= n; i++)if (vis[i])ans += C(n - sum[i]);
        ans = 1ll * (n - 1) * n / 2 * m - ans;
        printf("Case #%d: %lld\n", T, ans);
    }
    return 0;
}

 

H. Hints of sd0061

 

题意：给定一个长为 1≤n≤1071\le n\le 10^7 的数组，多次询问，每次询问数组中第 bib_i 大的数。

STL+思维

题目还给了一个限制：对于任意 i,j,ki,j,k，若 bi≠bj,bi<bk,bj<bkb_i\neq b_j,b_i<b_k,b_j<b_k，则 bi+bj≤bkb_i+b_j\le b_k。

这就说明把所有询问去重后，不会超过 O(log⁡n)O(\log n) 个。

STL函数nth_element()可以在期望O(N)时间内把小于第k大的数都放到左边，大于第k大的数都放到右边。

把询问从小到大排序，从后向前遍历，每次调用nth_element()。则每次排序的范围都以2递减，总的长度期望为2N。

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
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>

#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const double eps = 1e-8;
const double PI = acos(-1);
typedef pair<int, int> pii;
int T;
int n, m;
unsigned x, y, z;

unsigned rng61() {
    unsigned t;
    x = x ^ (x << 16);
    x = x ^ (x >> 5);
    x = x ^ (x << 1);
    t = x;
    x = y;
    y = z;
    z = (t ^ x) ^ y;
    return z;
}

unsigned a[N], ans[200];

struct X {
    int q, id;

    bool operator<(const X &b) const {
        return q < b.q;
    }
} b[200];

int main() {
    while (~scanf("%d%d%u%u%u", &n, &m, &x, &y, &z)) {
        T++;
        for (int i = 1; i <= n; i++)a[i] = rng61();
        for (int i = 1; i <= m; i++) {
            scanf("%d", &b[i].q);
            b[i].id = i;
        }
        sort(b + 1, b + m + 1);
        for (int i = m; i >= 1; i--) {
            int q = b[i].q;
            if (i != m && b[i].q == b[i + 1].q) {
                ans[b[i].id] = a[q + 1];
                continue;
            }
            nth_element(a + 1, a + q + 1, a + n + 1);
            ans[b[i].id] = a[q + 1];
            n = q + 1;
        }
        printf("Case #%d: ", T);
        for (int i = 1; i <= m; i++)printf("%u%c", ans[i], " \n"[i == m]);
    }
    return 0;
}