NOIP2022模拟赛 4

, ,

T1

每块连续的相同的字符压成形如 $(l,r,x)$ 的三元组，表示 $[l,r]$ 之中全是 $x$。

然后暴力修改就好，复杂度 $O(n+m)$

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
#include<bits/stdc++.h>
#define maxn 5000005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int n,m;
struct yyy{
	int w,len;
	yyy(int a=-1,int b=0) {
		w=a;len=b;
	}
}a[maxn];
int cnt;
signed main(void){
	int i,l,x,j;char ch;
	read(n);read(m);
	cin>>ch;
	for (i=1;i<=n;i++) {
		x=ch-'0';
		if (x==a[cnt].w) a[cnt].len++;
		else a[++cnt].w=x,a[cnt].len=1; 
		ch=getchar();
	}
	cin>>ch;
	for (i=1;i<=m;i++) {
		if (ch=='+') {
			if (a[cnt].w==1) {
				l=a[cnt].len;
				if (cnt>1) {
					if (a[cnt-1].len==1) {
						a[cnt-2].len+=1;
						a[cnt-1].w=0;a[cnt-1].len=l;cnt--;
					}
					else {
						a[cnt-1].len--;
						a[cnt].len=1;
						a[++cnt].w=0,a[cnt].len=l;
					}
				}
				else {
					a[cnt].w=1;a[cnt].len=1;
					a[++cnt].w=0;a[cnt].len=l;
				}
			}
			else {
				a[cnt].len--;
				if (!a[cnt].len) {
					cnt--;
					if (a[cnt].w==1) a[cnt].len++;
					else a[++cnt].w=1,a[cnt].len=1;
				}
				else a[++cnt].w=1,a[cnt].len=1;
			}
		}
		else if (ch=='-') {
			l=a[cnt].len;
			if (a[cnt].w==1) {
				a[cnt].len--;
				if (!a[cnt].len) {
					cnt--;
	                if (a[cnt].w==0) a[cnt].len++;
					else a[++cnt].w=0,a[cnt].len=1;  
				}
				else a[++cnt].w=0,a[cnt].len=1;
			}
			else {
				if (a[cnt-1].len==1) {
					if (cnt==2) cnt=1,a[cnt].w=1,a[cnt].len=l;
					else a[cnt-2].len++,a[cnt-1].w=1,a[cnt-1].len=l,cnt--;
				}
				else {
					a[cnt-1].len--;a[cnt].w=0;a[cnt].len=1;
				    a[++cnt].w=1;a[cnt].len=l;
				}
			}
		}
		else if (ch=='*') {
			if (a[cnt].w==0) a[cnt].len++;
			else a[++cnt].w=0,a[cnt].len=1;
		}
		else {
			a[cnt].len--;
			if (!a[cnt].len) cnt--;
		}
 	//	for (j=1;j<=cnt;j++) printf("%d %d\n",a[j].w,a[j].len);put();
	    ch=getchar();
	}
	for (i=1;i<=cnt;i++) for (j=1;j<=a[i].len;j++) printf("%d",a[i].w);
	return 0;
}

T2

从大到小构造。

似乎用线段树可以用 $O(Tn\log n)$

借鉴了fls的代码：

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
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int n,m,tot[maxn];
struct yyy{
	int l,r,x;
	yyy(int a=0,int b=0,int c=0){
		l=a;r=b;x=c;
	}
}a[maxn];
vector<yyy>h[maxn];
inline void solve(void) {
	int i,j,flag=0;
    read(n);read(m);
    for (i=1;i<=n;i++) h[i].clear(),tot[i]=0;
	for (i=1;i<=m;i++) {
		read(a[i].l);read(a[i].r),read(a[i].x);
		if (a[i].x<0||a[i].x>n) flag=1;
		for (j=a[i].l;j<=a[i].r;j++) tot[j]++;
		h[a[i].x].push_back(a[i]);
	}	
	if (flag) return puts("Impossible"),void();
	for (i=n;i>=1;i--) {
		int x=1,y=n;
		for (auto tmp:h[i]) {x=max(x,tmp.l),y=min(y,tmp.r);for (j=tmp.l;j<=tmp.r;j++) tot[j]--;}
		if (x>y) return puts("Impossible"),void();
		for (j=x;j<=y;j++) if (!tot[j]) {tot[j]=1e9;break;} 
		if (j==y+1) return puts("Impossible"),void();
	}
	puts("Possible");
}
signed main(void){
	freopen("1.in","r",stdin);
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

线段树：

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
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int n,m,tot[maxn];
struct yyy{
	int l,r,x;
	yyy(int a=0,int b=0,int c=0){
		l=a;r=b;x=c;
	}
}a[maxn];
vector<yyy>h[maxn];
struct node{
	int Min,lazy,id;
	node(int a=0,int b=0,int c=0) {
		Min=a;id=b;lazy=c;
	}
}f[maxn<<2];
inline void Pushup(int rt) {
	if (f[rt<<1].Min<f[rt<<1|1].Min) f[rt].Min=f[rt<<1].Min,f[rt].id=f[rt<<1].id;
	else f[rt].Min=f[rt<<1|1].Min,f[rt].id=f[rt<<1|1].id;
}
inline void Pushdown(int rt){
	if (f[rt].lazy) {
		f[rt<<1].Min+=f[rt].lazy;f[rt<<1].lazy+=f[rt].lazy;
		f[rt<<1|1].Min+=f[rt].lazy;f[rt<<1|1].lazy+=f[rt].lazy;
		f[rt].lazy=0;
	}
}
inline void Build(int l,int r,int rt) {
	f[rt].lazy=0;
	if (l==r) return f[rt].id=l,f[rt].Min=tot[l],void();
	int mid=l+r>>1;
	Build(l,mid,rt<<1);
	Build (mid+1,r,rt<<1|1);
	Pushup(rt);
}
inline void Update(int l,int r,int rt,int head,int tail,int k) {
	if (head<=l&&r<=tail) return f[rt].lazy+=k,f[rt].Min+=k,void();
	int mid=l+r>>1;
	Pushdown(rt);
	if (head<=mid) Update(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  Update(mid+1,r,rt<<1|1,head,tail,k);
	Pushup(rt);
}
inline node Query(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt];
	Pushdown(rt);
	int mid=l+r>>1;node tmp1=node(1e9,0,0),tmp2=node(1e9,0,0);
	if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
	if (tmp1.Min<tmp2.Min) return tmp1;
	else return tmp2;
}
inline void solve(void) {
	int i,j,flag=0;
    read(n);read(m);
    for (i=1;i<=n;i++) h[i].clear(),tot[i]=0;Build(1,n,1);
	for (i=1;i<=m;i++) {
		read(a[i].l);read(a[i].r),read(a[i].x);
		if (a[i].x<0||a[i].x>n) flag=1;
		Update(1,n,1,a[i].l,a[i].r,1);
		h[a[i].x].push_back(a[i]);
	}	
	if (flag) return puts("Impossible"),void();
	
	for (i=n;i>=1;i--) {
		int x=1,y=n;
		for (auto tmp:h[i]) {x=max(x,tmp.l),y=min(y,tmp.r);Update(1,n,1,tmp.l,tmp.r,-1);}
		if (x>y) return puts("Impossible"),void();
		node tmp=Query(1,n,1,x,y);
		if (tmp.Min>0) return puts("Impossible"),void();
		Update(1,n,1,tmp.id,tmp.id,1e9);
	}
	puts("Possible");
}
signed main(void){
	freopen("1.in","r",stdin);
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

T3

不会。