Reincarnation

正因为梦易碎，才格外美好。

NOIP2023未来共同体 模拟十三

发表于 更新于 分类于
本文字数： 8.3k 阅读时长 ≈ 8 分钟

最好摆的一集，原神，启动！

A. 多树（trees）

题目简介

原题链接：https://codeforces.com/gym/102443/problem/L

给定 棵有 个结点的树，设 表示第 棵树上路径 中经过的点的集合。求：

数据范围：

可以考虑 std::bitset 优化，然后树上差分维护，可以做到 ，可以拿不少的分，但是过不了。

然后考虑点 在路径 上的充要条件，那就是 ，否则一定有 ，那么这是一个单向的差分约束，可以直接作为判断条件。

记 ，那么按照上面的方法同样可以判断点 是否全部都在 路径上。

时间复杂度 。

AC 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 re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e2+10;
const int Inf=0x3f3f3f3f;
int N,K;
struct G
{ int next,to; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dist[MAXN][MAXN];
inline void bfs(int st)
{
	std::queue<int>Q;
	for(int i=1;i<=N;++i) Dist[st][i]=Inf;
	Q.push(st),Dist[st][st]=0;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(checkMin(Dist[st][v],Dist[st][u]+1)) Q.push(v);
		}
	}
}
inline void build()
{
	for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
	for(int st=1;st<=N;++st) bfs(st);
}
ll ans[MAXN][MAXN];
int main()
{
	freopen("trees.in","r",stdin);
	freopen("trees.out","w",stdout);
	read(N,K);
	for(int i=1;i<=K;++i)
	{
		std::memset(Head,0,sizeof(Head)),Total=0;
		for(int i=2,u,v;i<=N;++i) read(u,v),addEdge(u,v);
		for(int x=1;x<=N;++x) bfs(x);
		for(int x=1;x<=N;++x) for(int y=1;y<=N;++y)	ans[x][y]+=Dist[x][y];
	}
	for(int x=1;x<=N;++x,puts(""))
		for(int y=1;y<=N;++y)
		{
			int cnt=0;
			for(int z=1;z<=N;++z) cnt+=(ans[x][z]+ans[z][y]==ans[x][y]);
			write(cnt,' ');
		}
	return 0;
}
/*

*/

B. 远古题（icecream）

题目简介

给定 次对称群 ，求 中阶最大的置换的阶。

原题面中的解释

对于一个置换，一定会在一定时间内循环，循环节的长度被称为置换的阶。

一个置换为一个与原序列同长的序列 ，若原序列为 ，那么一次置换之后，序列会变成 。

由于答案很大，求出答案的 。

数据范围：

考虑置换环，如果从图论的方式考虑，那么有 个结点的图会形成若干个简单换，设其长度为 ，那么， 这个置换的阶就是其 。

所以，题目转化为构造一组 ，满足 ，最大化 。

容易发现，最终 的值只与每个质数取的个数有关，所以我们设计 状态，记录 表示当前考虑前 个质数，总和为 时的最大 值。

那么有转移：

注意到最后求的是 ，根据 ，所以我们将转移改写为：

注意到质数一共 ， 总转移不超过 。

还有一种考虑平衡规划：

  • 若 ，那么暴力转移，不超过 ；
  • 否则 ，每个质数至多转移 ，时间复杂度 。
AC 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
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=8e4+10;
int N;
// std::vector<int>Pri,Mxpri(MAXN,0);
int pri[MAXN],Tot;
bool is[MAXN];
inline void sieve(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
double Dp[2][MAXN];
int main()
{
	freopen("icecream.in","r",stdin);
	freopen("icecream.out","w",stdout);
	read(N);
	sieve(MAXN-10);
	int M=Tot;
	for(int i=1;i<=Tot;++i)
	{
		if(pri[i]>N){ M=i-1;break; }
		int op=i&1;
		for(int j=pri[i];j<=N;++j)
		{
			int mul=pri[i];Dp[op][j]=Dp[op^1][j];
			double val=std::log(mul),tmp=val;
			while(mul<=j)
			{
				checkMax(Dp[op][j],Dp[op^1][j-mul]+val);
				mul*=pri[i],val+=tmp;
			}
		}
	}
	printf("%.7lf",Dp[M&1][N]);
	return 0;
}
/*

*/

C. 可爱（kawaii）

原题：https://www.luogu.com.cn/problem/P8408

D. 火大题（firebig）

题目简介

给定一个长度为 的序列 ，定义一次操作 ，表示从区间 内选出前 大的数中，距离 最远的数，然后跳到这个数所在的位置。

定义 ，表示从 开始，需要多少次操作 能够到达 （因为右端点是 ，所以一定到得到）。

给定 次询问，每次询问 。

数据范围：

首先离线。

然后分治，每次求出跨过 的答案。考虑将一个跨过分治中心的区间转化。容易发现对于越大的右端点就有越多的左端点可以直接跳到右侧，所以你直接预处理出来，然后求出每个最后在左端点的位置，然后直接用可持久化线段树维护即可。

AC 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
#include<bits/stdc++.h>
#define inl inline
using namespace std;
const int N=2e5+5;
struct TR {int c,a; }tr[N*4];
int n,m,d,ma[N],a[N],b[N],po[N],f[N],fa[N][18];
inl int Read()
{
	int s=0; char c; while(!isdigit(c=getchar()));
	for(;isdigit(c);c=getchar()) s=s*10+c-'0'; return s;
}
#define L (p<<1)
#define R (L|1)
#define md ((l+r)>>1)
inl void BD(int p,int l,int r) {if(l==r) return po[l]=p, void(); BD(L,l,md); BD(R,md+1,r); }
inl void AD(int t) {for(int p=po[t];p;p>>=1) ++tr[p].c, !tr[p].a&&(tr[p].a=t); }
inl int QR(int p,int l,int r,int ra,int &k)
{
	if(l>ra) return 0; if(r<=ra&&tr[p].c<k) return k-=tr[p].c, 0;
	if(l==r) return l; int t=QR(R,md+1,r,ra,k); return t?t:QR(L,l,md,ra,k);
}
inl int QA(int p,int l,int r,int la,int ra)
{
	if(l>ra||r<la) return 0; if(l>=la&&r<=ra) return tr[p].a;
	int x=QA(L,l,md,la,ra),y=QA(R,md+1,r,la,ra); return a[x]>a[y]?x:y;
}
#undef L
#undef R
#undef md
int main()
{
	freopen("firebig.in","r",stdin);
	freopen("firebig.out","w",stdout);
	n=Read(); m=Read(); d=Read();
	for(int i=1;i<=n;++i) ++b[a[i]=Read()]; for(int i=1;i<N;++i) b[i]+=b[i-1];
	for(int i=n;i>=1;--i) a[i]=b[a[i]]--; for(int i=1;i<=n;++i) b[i]=i;
	sort(b+1,b+n+1,[](int x,int y){return a[x]>a[y]; });
	BD(1,1,n); for(int i=1,p,k;i<=n;++i)
	{
		p=b[i]; k=d; f[p]=QR(1,1,n,p,k); fa[p][0]=QA(1,1,n,f[p],p); AD(p);
		for(int j=1;j<18;++j) fa[p][j]=fa[fa[p][j-1]][j-1];
	}
	while(m--)
	{
		int l=Read(),r=Read(),an=1; if(l==r) {puts("0"); continue; }
		for(int i=17;~i;--i) f[fa[r][i]]>l&&(an+=1<<i,r=fa[r][i]);
		printf("%d\n",an+(f[r]>l));
	}
	return 0;
}
相关文章