11.14 NOIP模拟赛 by FLY

, , , , ,

今天只挂了 20 分！竟然是这几天挂的最少的！

T1

image-20231114143725862

$1\le q\le 3\times 10^5,n\le 1000$

Solution

观察一阶差分的形式，对一阶差分再来一个列差分和斜的差分即可。

复杂度 $O(n^2+q)$。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 2008
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &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;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int ans,b[maxn];
int n,d[maxn][maxn],e[maxn][maxn],f[maxn],g[maxn],a[maxn];
signed main(void){
//	freopen("ex_xor2.in","r",stdin);
	int i,j,x,y,l,s,q;
	read(n);read(q);
	while (q--) {
		read(x),read(y);read(l);read(s);
		d[x][y]+=s;d[x+l][y]-=s;
		e[x][y+1]-=s;e[x+l][y+l+1]+=s;
	}
	for (i=1;i<=n;i++) {
		for (j=n;j>=1;j--) f[j]=f[j-1];
		for (j=1;j<=n;j++) f[j]+=e[i][j],g[j]+=d[i][j];
		for (j=1;j<=n;j++) a[j]=a[j-1]+f[j]+g[j],ans^=a[j];//,printf("%lld ",a[j]);put();
	}
	printf("%lld",ans);
	return 0;
}

T2

原来的 T2 被我原了，所以 fxt 换了一道。

https://qoj.ac/problem/1456

image-20231114143938794

$1\le n\le 5\times 10^5$。

Solution

考虑暴力 dp，我们钦定 $f_i$ 为以 $i$ 栈顶端且之后都不会被覆盖的点的最长长度。

考虑转移，如果一个点可以转移：

  • 当前后缀最大值，即 $j$ ，满足 ：$\forall k\in [j+1,i-1],a_i>a_j>a_k$。
  • 找一个东西 $l$ 挡一下然后换成 $i$，满足：$\forall k\in [l+1,i-1],a_l>a_k$，且 $\forall k\in [j+1,l-1],a_j>a_k$，还要满足 $a_l>a_i>a_j$。

这样显然有 $O(n^3)$ 的暴力。

前面那个是好转移的，观察到后面那个，放在笛卡尔树上就是当前的最右链上的点 $x$，$x$ 的左儿子的右链上的点 $y$，且满足 $a_y<a_i$。

然后每个数只会被加入一次和删除一次，用线段树维护。复杂度 $O(n\log n)$。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &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;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,a[maxn];
int s[maxn],ls[maxn],rs[maxn],fa[maxn],tot;
int f[maxn];
void dfs(int x,int pre) {
	if (!x) return ;
	fa[x]=pre;
	dfs(ls[x],x);
	dfs(rs[x],x);
}
const int inf=1e9;
namespace seg{
	int f[maxn<<2];
	void Update(int l,int r,int rt,int head,int k) {
		if (l==r) return f[rt]=k,void();
		int mid=l+r>>1;
		if (head<=mid) Update(l,mid,rt<<1,head,k);
		else Update(mid+1,r,rt<<1|1,head,k);
		f[rt]=max(f[rt<<1],f[rt<<1|1]);
	}
	int Query(int l,int r,int rt,int head,int tail) {
		if (head<=l&&r<=tail) return f[rt];
		int mid=l+r>>1,tmp1=-inf,tmp2=-inf;
		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 max(tmp1,tmp2);
	}
}
using seg::Update;
using seg::Query;
void add(int x) {
	if (!x) return ;
	Update(0,n,1,a[x],f[x]);
	add(rs[x]);
}
void del(int x) {
	if (!x) return ;
	Update(0,n,1,a[x],-inf);
	del(rs[x]);
}
signed main(void){
	int i,j,k,ans=0;;
	read(n);
	for (i=1;i<=n;i++) read(a[i]);
	memset(f,-0x3f,sizeof(f));
	f[0]=0;
	for (i=1;i<=n;i++) {
		while (tot&&a[s[tot]]<a[i]) ls[i]=s[tot],tot--;
		if (tot) rs[s[tot]]=i;
		s[++tot]=i;
	}
	ls[1]=n+1;f[n+1]=0;                                                                    
	int root=s[0];
	dfs(root,0);
	s[tot=1]=n+1;
	for (i=1;i<=n;i++) Update(0,n,1,i,-inf);
	for (i=1;i<=n;i++) {
		if (a[i]>a[i-1]) f[i]=f[i-1]+1;
		f[i]=Query(0,n,1,0,a[i])+1;
		while (tot&&a[s[tot]]<a[i]) {
			f[i]=max(f[i],f[s[tot]]+1);
			del(ls[s[tot]]);
			tot--;
		}
		add(ls[i]);
		s[++tot]=i;
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

T3

$1\le n\le 10^5,a_i\le 10^7$。

Solution

对每对质因数新建一个点，包含这个质因数的就连一条边。再跑个点双。

注意还有 $4,9\dots$ 等也要新建一个点。

复杂度 $O(Tnw^2(x))$。$w(x)$ 为 $x$ 的不同质因数个数，这题下不超过 $10$。

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
#include<bits/stdc++.h>
#define ll long long 
#define maxn 2000005
#define put() putchar('\n')
using namespace std;
#define Tp template<typename T>
#define Ts template<typename T,typename... S>
Tp void read(T &x) {
	char ch=getchar();x=0;int f=1;
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x*=f;
} 
namespace Debug {
	Tp void _debug(char *f,T x) {cerr<<f<<'='<<x<<endl;}
	Ts void _debug(char *f,T x,S... t) {while (*f!=',') cerr<<*f++;cerr<<'='<<x<<',';_debug(f+1,t...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}
using namespace Debug;
#define M 2000005
#define fi first
#define se second
#define mk make_pair
int prime[M],cnt;
void getprime(int n) {	
	bitset<10000005>vis;
	int i,j;
	vis[1]=1;
	for (i=2;i<=n;i++) {
		if (!vis[i]) prime[++cnt]=i;
		for (j=1;j<=cnt&&prime[j]*i<=n;j++) {
			vis[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
}
const int inf=1e9;
int siz[maxn];
int a[maxn],n,g[maxn],f[maxn],rt[maxn];
vector<int>O[maxn],b[maxn];
vector<int>to[M],T[M];
int dfn[maxn],low[maxn],stac[maxn],tot,vis[maxn],times,dccnum;
int mp[10000006];
void ins(int x,int y) {
	T[x].push_back(y);
	T[y].push_back(x);
	
}
void insto(int x,int y) {
	to[x].push_back(y);
	to[y].push_back(x);
} 
int sumsiz,Max[maxn];
int id[M],root;
void tarjan(int x,int pre) {
	dfn[x]=low[x]=++times;
	stac[++tot]=x;vis[x]=1;sumsiz+=siz[x];
	for (auto y:to[x]) if (y^pre) {
		if (!dfn[y]) {
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if (dfn[x]<=low[y]) {
				++dccnum;
				ins(dccnum,x);
				while (tot) {
					ins(dccnum,stac[tot]);
					vis[stac[tot]]=1;
					if (stac[tot--]==y) break;
				}
			} 
		}
		else if (vis[y]) low[x]=min(low[x],dfn[y]);
	}
}
void dfs(int x,int pre) {
	id[x]=root;Max[x]=0;
	for (auto y:T[x]) {
		if (y^pre) {
			dfs(y,x);
			siz[x]+=siz[y];	
			Max[x]=max(Max[x],siz[y]);	
		}	
	}
	Max[x]=max(Max[x],sumsiz-siz[x]);
}
void solve(void) {
	int i,j,k,now,l;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),O[i].clear(),b[i].clear();
	int total=n;
	for (i=1;i<=n;i++) {
		now=a[i];
		for (j=1;j<=cnt&&prime[j]*prime[j]<=a[i];j++) 
			if (now%prime[j]==0) {
				int nums=0;
				while (now%prime[j]==0) now/=prime[j],nums++;
				O[i].push_back(prime[j]);
				if (nums>1) b[i].push_back(prime[j]*prime[j]);
			}
		if (now>1) O[i].push_back(now);
		int len=O[i].size();
		for (j=0;j<len;j++)	
			for (k=j+1;k<len;k++)
				if (!mp[O[i][j]*O[i][k]]) mp[O[i][j]*O[i][k]]=++total,rt[total]=O[i][j]*O[i][k];//,gdb(i,total,O[i][j],O[i][k]);
		for (auto y:b[i]) if (!mp[y]) mp[y]=++total,rt[total]=y;//,gdb(total,y);
	}
	int enums=0;
	for (i=1;i<=n;i++) siz[i]=1;
	for (i=1;i<=n;i++) {
		int len=O[i].size();
		int m=b[i].size();
		for (j=0;j<m;j++) 
			f[j]=mp[b[i][j]],insto(i,f[j]);
		for (j=0;j<len;j++) {
			for (k=j+1;k<len;k++) 
				g[k]=mp[O[i][j]*O[i][k]],insto(i,g[k]);
		}
	}//合并
	dccnum=total;
	pair<int,int>mx1,mx2;
	mx1=mx2=mk(0,0);
	for (i=1;i<=total;i++) if (!dfn[i]) {
		sumsiz=0;root=i;
		tarjan(i,0);
		dfs(i,0);
		if (mx1.fi<=sumsiz) {
			if (mx2.se!=i&&mx1.se!=i) mx2=mx1;
			mx1=mk(sumsiz,i); 
		}
		else if (mx2.fi<=sumsiz) mx2=mk(sumsiz,i);
	}
	int ans=inf;
	for (i=1;i<=n;i++) {
		if (mx1.se!=id[i]) Max[i]=max(Max[i],mx1.fi);
		if (mx2.se!=id[i]) Max[i]=max(Max[i],mx2.fi);
		ans=min(ans,Max[i]);
	} 
	printf("%d\n",ans);
	for (i=1;i<=total;i++) to[i].clear();
	tot=times=0;
	for (i=1;i<=dccnum;i++) T[i].clear(),siz[i]=dfn[i]=low[i]=vis[i]=stac[i]=id[i]=Max[i]=0;
	for (i=1;i<=total;i++) mp[rt[i]]=0;
}
signed main(void) {
	int T;
	getprime(1e7);
	read(T);
	while (T--) solve();
	return 0;
}

T4

好像要虚树，再见。