D

读错题了。

考虑相邻两个集合仅有一个数不同，不妨设这个数为 $x_i$，那么对于一个给定的 $x$ 序列，如果 $S_1$ 给定，那么这个序列就给定了。

设 $A_i,B_i$ 分别为 $S_i$ 是否含有 $i$，序列 $i$ 中包含 $i$ 的集合个数。显然我们有 $A_i+B_i=n$，所以对对于固定的 $x$，答案为 $n^m$，而 $x$ 序列的选取有 $m^{n-1}$ 种，所以答案应该为 $n^m\times m^{n-1}$

E

思维题。

考虑如何判 -1，只需要把 $A,B$ 排个序，然后看 $A,B$ 的每一位是否都满足 $A_i\ge B_i$，如果不满足，那么就是 -1。

我们要对上面的判定条件进行转化，设 $cnt_t$ 表示满足 $B_i\le t$ 的 $i$ 的个数减去 $A_i\le t$ 的 $i$ 的个数。那么只需要保证对于所有的 $t$，$cnt_t\ge 0$ 即可。

现在考虑答案是多少。如果 $A_i<B_i$ 的 $i$ 的个数为 $n$，那么答案就是 $n$。否则，我们要从里面选出一个集合，满足集合的大小最小，而且集合中要包含所有不合法的 $i$，那么我们的答案就认为是这个集合的大小。

只需要让这个集合内的数满足 $cnt_t\ge 0$ 即可。每次我们找到这个集合内最小的不满足条件的 $t$，然后找到一个 $A_i,B_i$ 满足 $B_i<t$，如果有多个，显然选一个 $A_i$ 最大的是最优的。

模拟贪心即可，思维难度主要在转化判定条件上。

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

int n,a[N],b[N],ans,sum;
map<int,int> Map;
priority_queue<int> q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q1;

int main(){
    read(n);rep(i,1,n) read(a[i]),read(b[i]);
    ans=n;
    rep(i,1,n){
        if(a[i]<b[i]){
            ans--;Map[a[i]]--;Map[b[i]]++;  
        }
        q1.push(mp(b[i],a[i]));
    }
    for(P x:Map){
        sum+=x.second;
        while(q1.size()&&q1.top().fi<=x.fi){
            q.push(q1.top().se);q1.pop();
        }
        while(sum<0){
            if(q.empty()||q.top()<=x.fi){
                puts("-1");return 0;
            }
            int now=q.top();q.pop();
            sum++;Map[now]--;ans--;
        }
    }
    printf("%d\n",ans);
    return 0;
}