链接
https://codeforces.com/contest/1284/problem/B
题意
定义一个长度为 $l$ 的序列中 $a$ 存在 $a_i<a_j(1\le i\le j\le l)$ 为合法序列
对于序列 $p$ 和序列 $q$，若 $p+q$ 为合法序列，则为有效组合
问 $n$ 个序列中有多少种有效组合
思路
当 $p+q$ 为无效组合只有一种情况：$p$ 和 $q$ 本身都不是合法序列且 $p_{min}>q_{max}$
因此对于每个序列只要找出有多少本身不是合法序列的序列的最大值 $\le$ 该序列最小值的个数
最后答案为 $n^2-$ 无效组合数
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct node {
int minn,maxn;
node() {
minn=INT_MAX;
maxn=-1;
}
}state[N];
int n,vis[N],cnt_max[N*10];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++) {
int l;
cin>>l;
for(int j=0;j<l;j++) {
int t;
cin>>t;
if(vis[i]==0) {
if(t>state[i].minn) vis[i]=1;
state[i].maxn=max(state[i].maxn,t);
state[i].minn=min(state[i].minn,t);
}
}
if(vis[i]==0) cnt_max[state[i].maxn]++;
}
for(int i=1;i<=1000000;i++) cnt_max[i]+=cnt_max[i-1];
ll ans=(ll)n*n;
for(int i=0;i<n;i++) if(vis[i]==0) ans-=cnt_max[state[i].minn];
cout<<ans<<endl;
return 0;
}
|