test20191007-eve

发表于

闲扯

这场考试全是 $dp$ ，都是看出来了，但是写不来转移。。。

题面

见 $ftp$

$T1$

Solution

我们有一个很暴力的想法，设 $dp_{i,j}$ 表示数组 $A$ 走到第 $i$ 个，数组 $B$ 走到第 $j$ 个，且以 $i,j$ 为结尾的合法子序列的数量。

然后我们枚举 $i,j$ ，每次找到一组 $A_i=B_j$ 时，我们枚举所有的 $s,l$ ，满足 $s<i,l<j,A_s=B_l,lt_{A_s,A_i}$ ，将它们的状态转移给 $dp_i,j$ 。

这样做的时间复杂度是 $O(n^4)$ 的，需要考虑优化。

我们设一个 $f2$ 数组，其中 $f2_i$ 表示所有以 $i$ 结尾的公共子序列的方案数之和。

再设一个变量 $sum$ 表示对于当前的 $i$ ，所有的满足 $lt_{B_j,A_i}$ 的 $j$ 的 $f2$ 的和，更新时直接用 $sum$ 来更新 $dp_{i,j}$ 即可。

对于 $f2,sum$ 我们都是可以 $O(1)$ 转移的，这样时间复杂度就优化成了 $O(n^2)$ 。

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
#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 INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template <class I>
	inline void read (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: print;
const int MAXN = 3e3+5,mod = 1e9+7;
int n,m,k,u,v,a[MAXN],b[MAXN],s[MAXN*2],sz,f1[MAXN][MAXN],f2[MAXN],ans;
char lt[MAXN<<1][MAXN<<1];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int main(){
	freopen("gu.in","r",stdin);
	freopen("gu.out","w",stdout);
	read(n),read(m),read(k);
	for(ri i=1;i<=n;++i) read(a[i]),s[++sz]=a[i];
	for(ri i=1;i<=m;++i) read(b[i]),s[++sz]=b[i];
	sort(s+1,s+1+sz),sz=unique(s+1,s+1+sz)-s-1;
	for(ri i=1;i<=n;++i) a[i]=lower_bound(s+1,s+1+sz,a[i])-s;
	for(ri i=1;i<=n;++i) b[i]=lower_bound(s+1,s+1+sz,b[i])-s;
	for(ri i=1;i<=k;++i){
		read(u),read(v);
		ri x=lower_bound(s+1,s+1+sz,u)-s;
		ri y=lower_bound(s+1,s+1+sz,v)-s;
		if(s[x]==u&&s[y]==v) lt[x][y]=1;
	}
	for(ri i=1;i<=n;++i){
		ri sum=0;
		for(ri j=1;j<=m;++j){
			if(a[i]==b[j]) f1[i][j]=add(sum,1),ans=add(ans,f1[i][j]);
			if(lt[b[j]][a[i]]) sum=add(sum,f2[j]);
			f2[j]=add(f2[j],f1[i][j]);
		}
	}
	print(ans);
	return 0;
}

$T2$

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
78
79
80
81
82
83
#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 INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template <class I>
	inline void read (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: print;
const int MAXN = 3e3+5,mod = 1e9+7;
int n,m,k,du[MAXN][MAXN],dp[MAXN][MAXN],a,b,c,d;
int ty[MAXN][MAXN];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int main(){
	freopen("gugu.in","r",stdin);
	freopen("gugu.out","w",stdout);
	read(n),read(m),read(k),dp[1][1]=1;
	for(ri i=1;i<=k;++i){
		read(a),read(b),read(c),read(d);
		if(a==n&&b==m) continue;
		if(!a||!b||!c||!d||a>n||c>n||b>m||d>m){
			ty[a][b]=3;
			continue;
		}
		if(a==c){
			if(b+1==d){
				if(!ty[a][b]) ty[a][b]=2;
				else if(ty[a][b]==1) ty[a][b]=3;
			}
			else ty[a][b]=3;
		}
		if(b==d){
			if(a+1==c){
				if(!ty[a][b]) ty[a][b]=1;
				else if(ty[a][b]==2) ty[a][b]=3;
			}
			else ty[a][b]=3;
		}
	}
	for(ri i=1;i<=n;++i)
		for(ri j=1;j<=m;++j){
			if(ty[i][j]==3) continue;
			dp[i][j+1]=add(dp[i][j+1],dp[i][j]);
			dp[i+1][j]=add(dp[i+1][j],dp[i][j]);
			if(ty[i][j]==1) dp[i][j+1]=add(dp[i][j+1],mod-dp[i][j]);
			if(ty[i][j]==2) dp[i+1][j]=add(dp[i+1][j],mod-dp[i][j]);
		}
	print(dp[n][m]);
	return 0;
}

$T3$

Solution

我们设 $dp_i$ 表示覆盖了 $1\sim i$ 的权值和。

我们先对所有的区间按照左区间从小到大排序，如果第 $1$ 个区间的左端点不是 $1$ ，那么一定是无解的，我们直接输出 $0$ 即可。

考虑怎么转移。

对于一个端点为 $l,r$ 的区间，一定能从 $j\in[l-1,n]$ 转移。

  1. 对于 $j\in[l-1,r]$ ，我们转移到 $dp_r$ 。对于 $dp_r$ ，我们需要加上一个权值 $sum_{l-1,r}\cdot val$ 。其中 $sum_{i,j}$ 表示右端点在 $\sum_{k=i}^j dp_k$ 。
  2. 对于 $j\in[r+1,n]$ ，我们转移到 $dp_j$ 。对于 $dp_j$ 我们直接乘上一个 $val+1$ ，表示在之前的所有情况上，我们再多选一个当前区间或者保持不变。

然后就可以直接上线段树优化了。

时间复杂度： $O(m\log n)$ 。

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
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
#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 INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	template <class I>
	inline void read (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: print;
const int MAXN = 2e5+5,mod = 1e9+7;
int n,m,dp[MAXN],a[MAXN];
struct Node{
	int l,r,val;
	bool operator <(const Node &t) const{
		return l==t.l?r<t.r:l<t.l;
	}
}node[MAXN];
inl bool cmp(Node x,Node y){
//	return x.l==y.l?x.r<y.r:x.l<y.l;
	return x.l<y.l;
}
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;}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
	int sum,tag_add,tag_mul;
}T[MAXN<<2];
il build(int cur,int l,int r){
	T[cur].tag_mul=1;
	if(l==r) return ;
	build(lc,l,mid),build(rc,mid+1,r);
}
il pushup(int cur){T[cur].sum=add(T[lc].sum,T[rc].sum);}
il pushdown(int cur,int l,int r){
	if(!T[cur].tag_add&&T[cur].tag_mul==1) return ;
	if(T[cur].tag_mul!=1){
		T[lc].sum=mul(T[lc].sum,T[cur].tag_mul);
		T[lc].tag_mul=mul(T[lc].tag_mul,T[cur].tag_mul);
		T[lc].tag_add=mul(T[lc].tag_add,T[cur].tag_mul);
		T[rc].sum=mul(T[rc].sum,T[cur].tag_mul);
		T[rc].tag_mul=mul(T[rc].tag_mul,T[cur].tag_mul);
		T[rc].tag_add=mul(T[rc].tag_add,T[cur].tag_mul);
		T[cur].tag_mul=1;
	}
	if(T[cur].tag_add){
		T[lc].sum=add(T[lc].sum,mul(T[cur].tag_add,mid-l+1));
		T[lc].tag_add=add(T[lc].tag_add,T[cur].tag_add);
		T[rc].sum=add(T[rc].sum,mul(T[cur].tag_add,r-mid));
		T[rc].tag_add=add(T[rc].tag_add,T[cur].tag_add);
		T[cur].tag_add=0;
	}
}
il updata_add(int cur,int l,int r,int pos,int k){
	if(l==r) return T[cur].tag_add=add(T[cur].tag_add,k),T[cur].sum=add(T[cur].sum,k),void();
	pushdown(cur,l,r);
	if(mid>=pos) updata_add(lc,l,mid,pos,k);
	else updata_add(rc,mid+1,r,pos,k);
	pushup(cur);
}
il updata_mul(int cur,int l,int r,int L,int R,int k){
	if(l>=L&&r<=R) return T[cur].sum=mul(T[cur].sum,k),T[cur].tag_add=mul(T[cur].tag_add,k),T[cur].tag_mul=mul(T[cur].tag_mul,k),void();
	pushdown(cur,l,r);
	if(mid>=L) updata_mul(lc,l,mid,L,R,k);
	if(R>mid) updata_mul(rc,mid+1,r,L,R,k);
	pushup(cur);
}
it query(int cur,int l,int r,int L,int R){
	if(l>=L&&r<=R) return T[cur].sum;
	pushdown(cur,l,r);ri res=0;
	if(mid>=L) res=add(res,query(lc,l,mid,L,R));
	if(R>mid) res=add(res,query(rc,mid+1,r,L,R));
	return res;
}
int main(){
	freopen("gugugu.in","r",stdin);
	freopen("gugugu.out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=m;++i) read(node[i].l),read(node[i].r),read(node[i].val);
	sort(node+1,node+1+m,cmp);
	if(node[1].l!=1) return puts("0"),0;
	build(1,0,n),updata_add(1,0,n,0,1);
	for(ri i=1;i<=m;++i){
		ri res=query(1,0,n,node[i].l-1,node[i].r);
		updata_add(1,0,n,node[i].r,mul(res,node[i].val));
		updata_mul(1,0,n,node[i].r+1,n,node[i].val+1);
	}
	print(query(1,0,n,n,n));
	return 0;
}

总结

$dp$ 已经忘了。。。