test20190925

发表于

闲扯

怎么感觉概率期望每次都不会做啊。。

还有 $T3$ 题意理解错了，没想到最后一个套娃的 $in$ 也要算进去，结果暴力都打挂了。。

题面

见$ftp$

$T1$

Solution

考虑计算所有的坏排列，然后用总方案数减去坏排列的个数即可得到好排列的个数。

因为坏排列的定义是有一个关键字单调不降，而我们有两个关键字，可以考虑容斥。

分别计算出每一个关键字单调不降时的方案数，再减去两个关键字都单调不降的方案数即可。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 3e5+5,mod = 998244353;
int n,val,ans,fac[MAXN];
struct Node{
	int a,b;
}node[MAXN];
inl bool cmp1(Node a,Node b){return a.a<b.a;}
inl bool cmp2(Node a,Node b){return a.b==b.b?a.a<b.a:a.b<b.b;}
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
int main(){
	freopen("per.in","r",stdin);
	freopen("per.out","w",stdout);
	read(n),fac[0]=1;
	for(ri i=1;i<=n;++i) read(node[i].a),read(node[i].b),fac[i]=mul(fac[i-1],i);
	ans=fac[n];
	sort(node+1,node+1+n,cmp1);
	ri res=1,fla=1;
	for(ri i=1;i<=n;++i){
		++val;
		if(node[i].a==node[i+1].a) continue;
		res=mul(res,fac[val]),val=0;
	}
	ans=add(ans,mod-res),res=1;
	sort(node+1,node+1+n,cmp2);
	for(ri i=1;i<=n;++i){
		++val;
		if(node[i].b==node[i+1].b) continue;
		res=mul(res,fac[val]),val=0;
	}
	ans=add(ans,mod-res),res=1;
	node[n+1].a=INF;
	for(ri i=1;i<=n;++i){
		++val,fla&=(node[i].a<=node[i+1].a);
		if(node[i].a==node[i+1].a&&node[i].b==node[i+1].b) continue;
		res=mul(res,fac[val]),val=0;
	}
	if(fla) ans=add(ans,res);
	print(ans);
	return 0;
}

$T2$

Solution

$30\ pts$ ：暴力即可。

$60\ pts$ ：我不会。

$100\ pts$ ：题解写的比我好。

Code

没有

$T3$

Solution

假如我们将套娃 $a$ 套进套娃 $b$ 中，那么我们得到的空气的体积（？？？）即为 $in_b-out_a$ 。

$a$ 能作为最外层的条件是 $\forall i\in [1,n],out_a>in_i$ 。

$a$ 能作为最内层的条件是 $\forall i\in [1,n],in_a<out_i$ 。（否则将满足条件的 $i$ 加入一定会使答案更优）

将每一个 $a$ 能包含 $b$ ，我们可以将其看做一条由 $a$ 连向 $b$ 的边权为 $in_a-out_b$ 的边。

又因为要空气的体积之和最小，那么我们就相当于是要求我们得到的图的最短路的数量。

但是我们直接连边的话，需要 $n^2$ 扫描一遍，时间上无法接受，所以我们需要优化。

方法一：线段树优化连边

我们先按照 $out$ 排序，那么每一个点都会向一段区间连边。这是我们可以像线段树一样，将这一个区间分为 $\log$ 段，然后再连边。这样我们就可以做到 $O(n\log n)$ 连边了。

方法二：DP

考虑我们最短路的松弛操作： $dis_u=min(dis_v+in_u-out_v)$ 。

将 $in_u$ 提出，那么我们需要维护的就是所有满足条件的点中， $dis_v-out_v$ 的最小值。

我们先将所有点按照 $out$ 从小到大排序，那么我们对每一个点，我们需要查询的都是一个前缀。

我们注意到一个事实，对于任意一个点 ，满足 $out>in$ 。

那么我们按照 $in$ 从小到大的顺序来处理，合法的，可以用来更新的区间，一定是不会变短的，这样我们就只需要维护一个最小值即可。

至于最短路计数问题，大家应该都会，就不再多说了。（不会的同学可以自行百度搜索）。

Code

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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class cnt>il read(cnt &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 2e5+5,mod = 1e9+7;
int n,mx,ans,a[MAXN],b[MAXN],cnt[MAXN],dis[MAXN],mn=INT_MAX;
struct Node{
	int x,y;
}node[MAXN];
it max(int x,int y){return x>y?x:y;}
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inl bool cmp1(int i,int j){return node[i].x<node[j].x;}
inl bool cmp2(int i,int j){return node[i].y<node[j].y;}
int main(){
//	freopen("easy.in","r",stdin);
//	freopen("easy.out","w",stdout);
	read(n);
	for(ri i=1;i<=n;++i) read(node[i].x),read(node[i].y),mx=max(mx,node[i].y),a[i]=b[i]=i;
	sort(a+1,a+1+n,cmp1); // 按照外层排序
	sort(b+1,b+1+n,cmp2); // 按照内层排序
	// DP方程：dis[x]=min(dis[y]-out[y])+in[x] 
	for(ri i=1,j=1,tt=1;i<=n;++i){
        // i 表示更新到了第几个， j 表示用来更新的区域已经拓展到了哪儿， tt 表示当前最小值对应的最短路数目
		ri id1=b[i];cnt[id1]=1;
		while(j<=n&&node[a[j]].x<=node[id1].y){ // 找到所有能更新 i 的 y
			ri id2=a[j++],x=node[id2].x;
			if(dis[id2]-x<mn) mn=dis[id2]-x,tt=cnt[id2];
			else if(dis[id2]-x==mn) tt=add(tt,cnt[id2]);
		}
		dis[id1]=node[id1].y+mn;
		cnt[id1]=tt;
	}
	// 最后统计答案
	mn=INT_MAX;
	for(ri i=n;i;--i){
		if(node[a[i]].x<=mx) break;
		if(dis[a[i]]<mn) mn=dis[a[i]],ans=cnt[a[i]];
		else if(dis[a[i]]==mn) ans=add(ans,cnt[a[i]]);
	}
	print(ans);
	return 0;
}

总结

还是太菜了特别是语文，甚至没想到最短路计数虽然最开始想到最那么一下，线段树连边这些操作也都还没学过，要更加努力才行。