NOIP2022模拟赛 6

, , ,

T1

设有的字母种类为 $n$ ，先降序排序。

若 $n=1$ ，则输出 $cnt_1(cnt_1-1)/2$

若 $n=2$ ，构造 122211111，1 为更少的那个字母，输出 $cnt_2-1$

若 $n>2$ ，构造 12223333242343221111，1 为最少的那个字母，输出 $cnt_n-1$

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
#include<bits/stdc++.h>
#define maxn
#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 T,cnt[105];
inline bool cmp(int x,int y) {return x>y;}
inline void solve(void) {
	int i,tot=0;
	for (i=1;i<=26;i++) read(cnt[i]),tot+=cnt[i]!=0;
	sort(cnt+1,cnt+27,cmp);
	if (tot==1) return printf("%d\n",cnt[1]*(cnt[1]-1)/2),void();
	else if (tot>2) return printf("%d\n",cnt[tot]-1),void();
	else {
		return printf("%d\n",cnt[tot]-1),void();//211111111122
	}
	
}
signed main(void){
	freopen("1.in","r",stdin);
	int i;
	read(T);
	while (T--) solve();
	return 0;
}

T2

考虑 $dp$ 。

因为 $r_i,p_i$ 的值域只有 $10^5$ ，向上整除后只有 $101$ 个值.

分段后暴力即可。类似于尺取（？

细节有点多。

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
#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;
int head=1,h[maxn],f[maxn][2],w[maxn][2];
struct yyy{
	int to,z;
	inline void add(int x,int y) {
		to=y;z=h[x];h[x]=head;
	}
}a[maxn*2];
struct fff{
	int w,id,flag;
	fff(int a=0,int b=0,int c=0) {id=a;w=b;flag=c;} 
}rt[maxn];
inline bool cmp(fff x,fff y) {
	return x.w<y.w;
}
int t[maxn][2],len[maxn],p[maxn];
const int inf=1e15;
inline void dfs(int x) {
	int i,j,k,size=0,cnt=0,sum=0,ans1=-inf,ans0=-inf;
	for (i=h[x];i;i=a[i].z) dfs(a[i].to);
	rt[++cnt]=fff(x,w[x][0],0);rt[++cnt]=fff(x,w[x][1],1);
	f[x][0]=w[x][0];f[x][1]=w[x][1];
	size=1;
	for (i=h[x];i;i=a[i].z) {
		rt[++cnt]=fff(a[i].to,w[a[i].to][0],0);
		rt[++cnt]=fff(a[i].to,w[a[i].to][1],1);
	    size++;
	}
	sort(rt+1,rt+1+cnt,cmp);
	int r=0,tot=0;
//	printf("case %lld\n",x);printf("cnt = %lld\n",cnt);for (i=1;i<=cnt;i++) printf("%lld %lld %lld\n",rt[i].id,rt[i].w ,rt[i].flag);put();
	for (k=0;k<=rt[cnt].w/1000+1;k++) {
		sum=0;tot=0;r=0;
		t[x][0]=t[x][1]=-inf;len[x]=0;
		for (j=1;j<=cnt;j++) len[rt[j].id]=0,t[rt[j].id][0]=t[rt[j].id][1]=-inf;
		for (i=1;i<=cnt;i++) {
			while (r<cnt&&(rt[r+1].w-rt[i].w+999)/1000<=k){
				++r;
				if (len[rt[r].id]++==0) tot++;
				t[rt[r].id][rt[r].flag]=f[rt[r].id][rt[r].flag];
				if (rt[r].id!=x) {
					if (len[rt[r].id]==1) sum+=f[rt[r].id][rt[r].flag];
					else sum-=f[rt[r].id][rt[r].flag^1],sum+=max(f[rt[r].id][rt[r].flag],f[rt[r].id][rt[r].flag^1]);
				}
			}
		    if (tot==size) {
		    	if (t[x][0]>-inf) ans0=max(ans0,sum-k*666*x+w[x][0]);
				if (t[x][1]>-inf) ans1=max(ans1,sum-k*666*x+w[x][1]);
			}
			if (--len[rt[i].id]==1) {
				if (rt[i].id^x) {
					sum-=max(f[rt[i].id][rt[i].flag],f[rt[i].id][rt[i].flag^1]);
					sum+=f[rt[i].id][rt[i].flag^1];
				}
			}
			else {
				if (rt[i].id^x) sum-=f[rt[i].id][rt[i].flag];
				tot--;
			}
			t[rt[i].id][rt[i].flag]=-inf;
		}
	}
	f[x][0]=ans0,f[x][1]=ans1;
//	printf("f0=%lld f1=%lld\n",f[x][0],f[x][1]);
}
signed main(void){
	int i,x,y;
	read(n);
	for (i=1;i<=n;i++) f[i][0]=f[i][1]=-inf;
	for (i=1;i<=n;i++) {
		read(w[i][0]),read(w[i][1]);
		if (w[i][0]<w[i][1]) swap(w[i][0],w[i][1]);  
	}
	for (i=1;i<n;i++) {
		read(x);read(y);a[++head].add(x,y);
	}
	dfs(1);
	printf("%lld",max(f[1][0],f[1][1]));
 	return 0;
}

T3

暴力 $O(mn^2)$

考虑优化这个暴力，马拉车跑出每个点为中心点向外扩展最远的距离 $d_i$。

  • 对于回文长度是奇数的

    对于位置 $i$ ，最长回文串的为 $[i-d_i,i+d_i]$，令 $x=\min(d_i,i-l,r-l)$。

    答案是 $\sum\limits_{j=0}^{x} sum_{i+j}-sum_{i-j-1}$

    令 $ss$ 为 $sum$ 的前缀和，则答案等价于 $ss_{i+j}-2ss_{i-1}+ss_{i-j-2}$

    根据回文的对称性，答案又等价于 $a_i(j+1)+2(ss_{i+j}-ss_i-j*sum_i)$

    则等价于在区间 $[i,i+j]$ 中每个点加上 $a_i$，在区间 $[i,i+j]$ 中的点 $k$ 加上 $2sum_k-2sum_i$。

    而 $x$ 的条件可以将询问离线，按右端点排序升序。将右半部分的点进行操作。

    左半部分同理。

  • 偶数同理。

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#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,m,a[maxn],sum[maxn],b[maxn],d[maxn],ss[maxn];
inline void Manacher(void) {
	int i;
	b[0]=0;b[2*n]=0;b[2*n+1]=1e9;
	for (i=1;i<=n;i++) b[i*2-1]=a[i];
	int N=n*2-1,mid,mx;
	for (i=1,mid=0,mx=0;i<=N;i++){
		if (i<=mx) d[i]=min(d[(mid<<1)-i],mx-i+1);
		while (b[i-d[i]]==b[i+d[i]]) d[i]++;
		if (mx<i+d[i]) mx=i+d[i]-1,mid=i;  
    }
    for (i=1;i<=N;i++) d[i]--;
    return;
}
struct yyy{
    int lazy1,lazy2,sum;
}f[maxn<<2];
inline void Pushup(int rt){
	f[rt].sum=f[rt<<1].sum+f[rt<<1|1].sum;
}
inline void Pushdown(int l,int r,int rt) {
	int mid=l+r>>1;
	if (f[rt].lazy1) {
		f[rt<<1].sum+=f[rt].lazy1*(ss[mid]-ss[l-1]);
		f[rt<<1|1].sum+=f[rt].lazy1*(ss[r]-ss[mid]);
		f[rt<<1].lazy1+=f[rt].lazy1;
		f[rt<<1|1].lazy1+=f[rt].lazy1;
		f[rt].lazy1=0;
	}
	if (f[rt].lazy2) {
		f[rt<<1].sum+=f[rt].lazy2*(mid-l+1);
		f[rt<<1|1].sum+=f[rt].lazy2*(r-mid);
		f[rt<<1].lazy2+=f[rt].lazy2;
		f[rt<<1|1].lazy2+=f[rt].lazy2;
		f[rt].lazy2=0;
	}
}
inline void Update1(int l,int r,int rt,int head,int tail,int k) {
	if (head<=l&&r<=tail) return f[rt].lazy1+=k,f[rt].sum+=k*(ss[r]-ss[l-1]),void();
//	if (rt==1) printf("111 %lld %lld %lld %lld %lld %lld\n",l,r,rt,head,tail,k);
	int mid=l+r>>1;
	Pushdown(l,r,rt);
	if (head<=mid) Update1(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  Update1(mid+1,r,rt<<1|1,head,tail,k);
	Pushup(rt);
}
inline void Update2(int l,int r,int rt,int head,int tail,int k) {
	if (head<=l&&r<=tail) return f[rt].lazy2+=k,f[rt].sum+=k*(r-l+1),void();
//	if (rt==1) printf("222 %lld %lld %lld %lld %lld %lld\n",l,r,rt,head,tail,k);
	int mid=l+r>>1;
	Pushdown(l,r,rt);
	if (head<=mid) Update2(l,mid,rt<<1,head,tail,k);
	if (tail>mid)  Update2(mid+1,r,rt<<1|1,head,tail,k);
	Pushup(rt);
}
inline int Query(int l,int r,int rt,int head,int tail) {
	if (head<=l&&r<=tail) return f[rt].sum;
	int mid=l+r>>1,tmp1=0,tmp2=0;
	Pushdown(l,r,rt);
	if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
	return tmp1+tmp2;
}/*
namespace BL2{
	inline int calc(int i,int j) {
	//	printf("1 %lld %lld\n",i,j);
		return a[i]*(j+1)+2*(ss[i+j]-ss[i]-j*sum[i]);//ss[i+j]-ss[i-1]-ss[i-1]+ss[max(0ll,i-j-2)];
	}
	inline int calc2(int i,int j) { 
	//	printf("2 %lld %lld\n",i,j);
	//	if (j<0) return 0;
	//	return ss[i+j+1]-ss[i]-(ss[i-1]-ss[max(0ll,i-j-2)]);
		return 2*(ss[i+j+1]-ss[i]-sum[i]*(j+1));
	}
	inline void main(void) {
		int i,l,r,j,k;
		while (m--) {
			int ans=0;
			read(l);read(r);
			for (i=l;i<=r;i++) ans+=calc(i,min(i-l,min(r-i,d[2*i-1]/2)));
			for (i=l;i<r;i++) ans+=calc2(i,min(i-l,min(r-i-1,d[2*i]/2-1)));
			printf("%lld\n",ans);
		}
	}
}*/
int Ans[maxn];
struct qqq{
	int l,r,id,flag;
	qqq(int a=0,int b=0,int c=0,int d=0) {
		id=a;l=b;r=c;flag=d;
	} 
}qw[maxn];
vector<qqq>q[maxn];
inline void solve(void) {
	int i,j,l,r;
	for (i=1;i<=m;i++) {
		read(l),read(r);qw[i].l=l;qw[i].r=r;qw[i].id=i;
		q[r].push_back(qqq(i,l,r,1)),q[(l+r)/2].push_back(qqq(i,l,r,-1));
	}
//	for (i=1;i<=2*n-1;i++) printf("%lld ",d[i]);put();
	for (i=1;i<=n;i++) {
		j=d[2*i-1]/2;
		if (i+j>=i+1&&i<n) Update1(1,n,1,i+1,i+j,2);
		if (i+j>=i+1&&i<n) Update2(1,n,1,i+1,i+j,-2*sum[i]);
		Update2(1,n,1,i,i+j,a[i]);
		j=d[2*i]/2-1;
		if (i<n&&j>=0) Update1(1,n,1,i+1,i+j+1,2);
		if (i<n&&j>=0) Update2(1,n,1,i+1,i+j+1,-2*sum[i]);
	//	printf("%lld\n",f[1].sum);
		for (auto tmp:q[i]) Ans[tmp.id]+=Query(1,n,1,tmp.l,tmp.r)*tmp.flag;//,printf("%lld %lld %lld %lld\n",tmp.id,tmp.l,tmp.r,tmp.flag);
	}//for (i=1;i<=m;i++) printf("%lld\n",Ans[i]);
	for (i=1;i<=n;i++) q[i].clear();
	for (i=1;i<=n*4;i++) f[i].sum=f[i].lazy1=f[i].lazy2=0; 
	for (i=1;i<=m;i++) {
		l=qw[i].l;r=qw[i].r;
		q[(l+r)/2].push_back(qqq(i,l,r,1)),q[l-1].push_back(qqq(i,l,r,-1));
	}
	for (i=n;i>=1;i--) ss[i]=ss[i-1];
	for (i=1;i<=n;i++) {
		j=d[2*i-1]/2;
		if (i-j<=i-1&&i>1) Update1(1,n,1,i-j,i-1,-2);
		if (i-j<=i-1&&i>1) Update2(1,n,1,i-j,i-1,2*sum[i-1]);
		Update2(1,n,1,i-j,i,a[i]);
		j=d[2*i]/2-1;
		if (i>0&&i-j<=i) Update1(1,n,1,i-j,i,-2);
		if (i>0&&i-j<=i) Update2(1,n,1,i-j,i,2*sum[i]);
		for (auto tmp:q[i]) Ans[tmp.id]+=Query(1,n,1,tmp.l,tmp.r)*tmp.flag;
	//	printf("%lld\n",f[1].sum);
	}
	for (i=1;i<=m;i++) printf("%lld\n",Ans[i]);
}
signed main(void){
	freopen("1.in","r",stdin);
	read(n);read(m);
	for (int i=1;i<=n;i++) read(a[i]),sum[i]=sum[i-1]+a[i],ss[i]=ss[i-1]+sum[i];
    Manacher();
//	if (n<=300&&m<=300) 
//	BL::main();
//	BL2::main();
    solve();
	return 0;
}