NOIP2022模拟赛2 3

, ,

T2 CE了/dk

T1

如果最大的那根没有超过全部的一半，那么一定有方法使全部烧完。

否则输出总长度减去最大。

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
#include<bits/stdc++.h>
#define maxn 100005
#define int 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,a[maxn];
inline void solve(void) {
	int i,sum=0;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),sum+=a[i];
	sort(a+1,a+1+n);
	if (sum-a[n]<a[n]) printf("%lld.0\n",sum-a[n]);
	else printf("%.1lf\n",1.0*sum/2); 
}
signed main(void){
	freopen("dan.in","r",stdin);
	freopen("dan.out","w",stdout);
	int T;
	read(T);
	while (T--) solve();
	return 0;
}

T2

单调队列优化dp

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
#include<bits/stdc++.h>
#define maxn 10005
#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,f[2][maxn];//等下压缩
struct yyy{
	int x,y,w;
	yyy(int a=0,int b=0,int c=0) {x=a;y=b;w=c;}
};
inline bool cmp(yyy x,yyy y) {return x.y<y.y;}
vector<yyy>h[maxn];
int delta,num,ans;
int q[maxn],head,tail,g[maxn];
signed main(void){
//	freopen("1.in","r",stdin);
	freopen("kill.in","r",stdin);
	freopen("kill.out","w",stdout);
	int i,j,x,y,z;
	read(n);read(m);read(delta);read(num);//delta=min(delta,n);
	for (i=1;i<=num;i++) {
		read(x);read(y);read(z);
		x++;y++;
		h[y].push_back(yyy(x,y,z));
	}
	for (i=1;i<=m;i++) {
		int tmp=i&1;
		memset(f[tmp],-0x3f,sizeof(f[tmp]));
		memset(g,0,sizeof(g));
		for (auto tmp:h[i]) g[tmp.x]=tmp.w;
		head=1;tail=0;
		for (j=1;j<=delta;j++) {
			while (head<=tail&&f[tmp^1][q[tail]]<=f[tmp^1][j]) tail--;
			q[++tail]=j;
		} 
	//	printf("case %d \n",i);for (j=1;j<=m;j++) printf("%d ",g[j]);put();
		for (j=1;j<=n;j++) {
			while (head<=tail&&q[head]+delta<j) head++;
			if (j+delta<=n) {
				while (head<=tail&&f[tmp^1][q[tail]]<=f[tmp^1][j+delta]) tail--;
				q[++tail]=j+delta;
			}
			f[tmp][j]=f[tmp^1][q[head]]+g[j];
		}
	}
	for (j=1;j<=n;j++) ans=max(ans,f[m&1][j]);
	printf("%d",ans);
	return 0;
}

T3

dsu on tree

我用的是并查集，复杂度 $O(n\log^2n)$

但是可以用双向链表，复杂度 $O(n\log n)$

ZJ老师似乎有线性的做法

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
#include<bits/stdc++.h>
#define maxn 200005
#define int 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;
vector<int>to[maxn];
int size[maxn],w[maxn],num[maxn],son[maxn];
int l[maxn],r[maxn],p[maxn],_p[maxn],times,id[maxn];
inline void dfs(int x) {
	size[x]=1;l[x]=++times;
	for (auto y:to[x]) {
		dfs(y);
		size[x]+=size[y];
		if (size[son[x]]<size[y]) son[x]=y;
	}
	r[x]=times;
}
int fa[maxn],fasize[maxn],sum,ans,vis[maxn],TOT;
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void merge(int x,int y) {
	if (!vis[x]||!vis[y]) return ;
	int fx=getfa(x),fy=getfa(y);
	if (fx^fy) {
		fa[fx]=fy;
		sum+=-fasize[fx]*(fasize[fx]+1)/2-fasize[fy]*(fasize[fy]+1)/2;
		fasize[fy]+=fasize[fx];
		sum+=(fasize[fy]+1)*fasize[fy]/2;
	} 
}
inline void clear(int x) {
	int i,tmp;sum=0;
	for (i=l[x];i<=r[x];i++) tmp=p[id[i]],fa[tmp]=tmp,fasize[tmp]=1,vis[tmp]=0;
//	TOT+=r[x]-l[x]+1;
}
inline void calc(int x,int L,int R) {
	int tmp;
	for (int i=l[x];i<=r[x];i++) {
		tmp=p[id[i]];vis[tmp]=1;sum++;
		if (L<=l[p[id[i]-1]]&&l[p[id[i]-1]]<=R) merge(tmp,p[id[i]-1]);
		if (L<=l[p[id[i]+1]]&&l[p[id[i]+1]]<=R) merge(tmp,p[id[i]+1]);
	}
//	TOT+=r[x]-l[x]+1;
}
inline void solve(int x) {
	if (!son[x]) return sum=num[x]=vis[x]=1,void();
	for (auto y:to[x]) if (y!=son[x]) solve(y),clear(y);
	solve(son[x]);
	for (auto y:to[x]) if (y!=son[x]) calc(y,l[x],r[x]);
	vis[x]=1;sum++;
	if (l[x]<=l[p[_p[x]-1]]&&l[p[_p[x]-1]]<=r[x]) merge(x,p[_p[x]-1]);
	if (l[x]<=l[p[_p[x]+1]]&&l[p[_p[x]+1]]<=r[x]) merge(x,p[_p[x]+1]);
	num[x]=sum;
}
inline void getans(int x) {
	if (!son[x]) return ans+=w[x],void();
	int tot=num[x];
	for (auto y:to[x]) getans(y),tot-=num[y];ans+=w[x]*tot;
}
signed main(void){
	freopen("lca.in","r",stdin);
	freopen("lca.out","w",stdout);
	int i,x;
	read(n);
	for (i=2;i<=n;i++) read(x),to[x].push_back(i);
	for (i=1;i<=n;i++) read(p[i]),_p[p[i]]=i;
	for (i=1;i<=n;i++) read(w[i]);
	dfs(1);
	for (i=1;i<=n;i++) id[l[i]]=_p[i];
//	for (i=1;i<=n;i++) printf("%lld ",son[i]);put();
	for (i=1;i<=n;i++) fasize[i]=1,fa[i]=i;
	solve(1);
	getans(1);
//	printf("TOT=%lld\n",TOT);
	printf("%lld",ans);
	return 0;
}

T4

GSS5

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
#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;
}
const int inf=1e10;
int n,a[maxn],sum[maxn];
struct yyy{
	int lazy,Max,Min,ans;
	yyy(int a=-inf,int b=inf,int c=0) {Max=a,Min=b;ans=c;}
}f[maxn<<2];
inline void Pushup(int rt) {
	f[rt].Max=max(f[rt<<1].Max,f[rt<<1|1].Max);
	f[rt].Min=min(f[rt<<1].Min,f[rt<<1|1].Min);
	f[rt].ans=max(f[rt<<1].ans,max(f[rt<<1|1].ans,f[rt<<1|1].Max-f[rt<<1].Min));
}
inline void Pushdown(int rt) {
	if (f[rt].lazy) {
		int k=f[rt].lazy;
		f[rt<<1].Max+=k;f[rt<<1].Min+=k;f[rt<<1].lazy+=k;
		f[rt<<1|1].Max+=k,f[rt<<1|1].Min+=k,f[rt<<1|1].lazy+=k;
		f[rt].lazy=0;
	}
}
inline void Build(int l,int r,int rt) {
	if (l==r) {f[rt].ans=0;f[rt].Max=f[rt].Min=sum[l];return ;}
	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,f[rt].Max+=k,void();
	Pushdown(rt);
	int mid=l+r>>1;
	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 int Query1(int l,int r,int rt,int head,int tail){//max
	if (head<=l&&r<=tail) return f[rt].Max;
	Pushdown(rt);
	int tmp1=-inf,tmp2=-inf,mid=l+r>>1;
	if (head<=mid) tmp1=Query1(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query1(mid+1,r,rt<<1|1,head,tail);
	return max(tmp1,tmp2);
} 
inline int Query2(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt].Min;
	Pushdown(rt);
	int tmp1=inf,tmp2=inf,mid=l+r>>1;
	if (head<=mid) tmp1=Query2(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query2(mid+1,r,rt<<1|1,head,tail);
	return min(tmp1,tmp2);
}
inline yyy Query3(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;
	if (head<=mid&&tail>mid) {
		yyy tmp1=Query3(l,mid,rt<<1,head,tail),tmp2=Query3(mid+1,r,rt<<1|1,head,tail);
		return yyy(max(tmp1.Max,tmp2.Max),min(tmp1.Min,tmp2.Min),max(tmp1.ans,max(tmp2.ans,tmp2.Max-tmp1.Min)));
	}
	else if (head<=mid) return Query3(l,mid,rt<<1,head,tail);
	else if (tail>mid) return Query3(mid+1,r,rt<<1|1,head,tail);
}
signed main(void){
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	int n,T,i,x,y,l1,l2,r1,r2;char ch;
	read(n);read(T);
	for (i=1;i<=n;i++) read(a[i]),sum[i]+=sum[i-1]+a[i];
	Build(0,n,1);
	while (T--) {
		ch=getchar();while (ch!='C'&&ch!='Q') ch=getchar();
		if (ch=='C') read(x),read(y),Update(0,n,1,x,n,y-a[x]),a[x]=y;
		else {
			read(l1);read(r1);read(l2);read(r2);
			if (l1>r1) swap(l1,r1);
			if (l2>r2) swap(l2,r2);
			if (l1>l2) swap(l1,l2),swap(r1,r2);
	//		r1=min(r1,r2);
			if (r1<=l2) printf("%d\n",Query1(0,n,1,l2,r2)-Query2(0,n,1,l1-1,r1-1));
			else {
				int ans=0;
				if (r2<r1) {
					ans=max(Query1(0,n,1,l2,r2)-Query2(0,n,1,l1-1,l2-1),ans);
					ans=max(Query3(0,n,1,l2-1,r2).ans,ans);
				}
				else {
					ans=max(Query1(0,n,1,l2,r2)-Query2(0,n,1,l1-1,l2-1),ans);
					ans=max(Query1(0,n,1,r1,r2)-Query2(0,n,1,l1-1,r1-1),ans);
					ans=max(Query3(0,n,1,l2-1,r1).ans,ans);
				}
				printf("%d\n",ans);
			}
		}
	}
	return 0;
}