Reincarnation

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

2022牛客OI赛前集训营-提高组（第六场）

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

不会出题可以不出。

我是A题

形式化题意

存在一个三维点阵，一共 次操作，每次操作会删除点 满足 ，其中 每次给定。求操作结束后被删除的点的个数。数据强随机。保证

随机数据满足，要么 且 ，否则 。

数据范围：

好神秘啊，第一次遇到敢写「请选手仔细观察给出的数据生成器，数据生成方式与解题强相关」的出题人，这要是放在正规场上绝对要被喷惨，不过这也说明正规场上没有可能是连审核都过不了。（

考虑首先处理 的点组，得到 ，作为我们的框架答案，然后考虑处理剩余的 的点组，我们记 表示当 时最大的 ，然后枚举 对每一层的 进行扫描线，然后直接计算即可。

理论时间复杂度 ，但是能过。最离谱的是我本地连 getData() 都跑不过。

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
#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){ putchar(x?'1':'0'); }
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 N=3e7+10;
typedef unsigned long long ull;
using int128=__int128_t;
int n,A,B,C,u[N],v[N],w[N];
inline ull rnd(ull &k1,ull &k2)
{
	ull k3=k1,k4=k2;
	k1=k4;k3^=(k3<<23);
	k2=k3^k4^(k3>>17)^(k4>>26);
	return k2+k4;
}
inline void getData()
{
	ull x,y;
	read(n,A,B,C,x,y);
	for(int i=1;i<=n;++i)
	{
		u[i]=rnd(x,y)%A+1;
		v[i]=rnd(x,y)%B+1;
		w[i]=rnd(x,y)%C+1;
		if(rnd(x,y)%3==0) u[i]=A;
		if(rnd(x,y)%3==0) v[i]=B;
		if((u[i]!=A)&&(v[i]!=B)) w[i]=C;
		// write(u[i],' ',v[i],' ',w[i],'\n');
	}
}
int Mx[N];
int main()
{
	// freopen("a.in","r",stdin);
	// freopen("a.out","w",stdout);
	getData();
	int maxW=0;
	for(int i=1;i<=n;++i) if(u[i]==A&&v[i]==B) checkMax(maxW,w[i]);
	int128 ans=(int128)A*B*maxW;
	for(int h=C;h>maxW;--h)
	{
		for(int i=1;i<=n;++i) if(w[i]==h) checkMax(Mx[u[i]],v[i]);
		for(int i=A;i>=1;--i) checkMax(Mx[i],Mx[i+1]);
		for(int i=1;i<=A;++i) ans+=Mx[i];
	}
	write(ans);
	return 0;
}
/*

*/

我是B题

形式化题意

有一个 的排列，一共 次操作，第 次操作会找到当前排列中最小的元素，以 的概率将其删去，否则以 的概率将其放过，然后找到次小元素执行上述操作。如果当前操作时只有一个元素，则必定删去。求操作结束后剩余元素的期望。对 取模。

数据范围：

考虑对剩余元素为 时分别 ，我们如果当前要剩 ，我们称 为目标元素。

定义 表示当前执行了 次操作，目标元素在整个排列中的排行为 。然后考虑转移。

如果当前操作删除的是比 小的元素，则前面至少会被删除一个：

如果当前操作删除的是比 大的元素，则前面的元素就不能被删除：

此时，我们求的是对目标元素的期望，所以 ，其余为 ，然后对所有目标元素求和 即可。

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
#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){ putchar(x?'1':'0'); }
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=3e2+10;
const int Mod=1e9+7;
int N,p[MAXN],ans;
int Dp[MAXN][MAXN],Inv[MAXN][MAXN];
inline void add(int &x,int y){ x=x+y>=Mod?x+y-Mod:x+y; }
inline int qPow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
int main()
{
	// freopen("b.in","r",stdin);
	// freopen("b.out","w",stdout);
	read(N);
	for(int i=1;i<N;++i) read(p[i]);
	for(int i=1;i<N;++i)
	{
		Inv[i][0]=1;
		for(int j=1;j<=N;++j) Inv[i][j]=(ll)Inv[i][j-1]*(1-p[i]+Mod)%Mod;
	}
	for(int rk=1;rk<=N;++rk)
	{
		std::memset(Dp,0,sizeof(Dp));
		Dp[1][rk]=1;
		for(int i=1;i<N;++i)
			for(int j=1;j<=N-i+1;++j)
			{
				add(Dp[i+1][j-1],(ll)Dp[i][j]*(1-Inv[i][j-1]+Mod)%Mod);
				if(j<N-i+1) add(Dp[i+1][j],(ll)Dp[i][j]*Inv[i][j]%Mod);
			}
		// for(int i=1;i<=N;++i,puts(""))
			// for(int j=1;j<=N;++j) write(Dp[i][j],' ');
		// puts("");
		add(ans,(ll)rk*Dp[N][1]%Mod);
	}
	write(ans);
	return 0;
}
/*

*/

我是C题

形式化题意

给定长度为 的序列 ，找到最大 使得在 中存在一个长度为 的区间使得这个区间内所有出现的数的出现次数至少为 。

数据范围：

开始把题读错了，想了一个比较优美的二分套二分，甚至还是均摊 的。

考虑一个比较奇葩的性质，那就是 是一个单调不上升序列。考虑对于相同的 ，如果 没有合法解，那对于所有 肯定也没有合法解。而如果对于区间 不合法，那么任意 肯定也不会合法。

所以考虑分治，每次找到这个区间中不合法的 ，然后将区间分为 递归求解，但容易发现这样肯定是可以被卡的，所以我们考虑启发式合并，每次先递归大的一边，这样得到更优答案的概率更大，然后适当剪枝，最后实现就可以做到 。

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
#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){ putchar(x?'1':'0'); }
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=1e6+10,MAXS=20;
int N,a[MAXN],b[MAXN],Cnt[MAXN],ans;
void solve(int l,int r)
{
	if(l>r||r-l+1<=ans)
	{
		for(int i=l;i<=r;++i) --Cnt[a[i]];
		return ;
	}
	if(l==r)
	{
		--Cnt[a[l]];
		if(b[1]==1) ans=1;
		return ;
	}
	int pos=-1,val=b[r-l+1];
	for(int i=l;i<=r;++i)
		if(Cnt[a[i]]<val){ pos=i;break; }
	if(!~pos)
	{
		ans=r-l+1;
		for(int i=l;i<=r;++i) --Cnt[a[i]];
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid)
	{
		for(int i=l;i<=pos;++i) --Cnt[a[i]];
		solve(pos+1,r);
		for(int i=l;i<pos;++i) ++Cnt[a[i]];
		solve(l,pos-1);
	}
	else
	{
		for(int i=pos;i<=r;++i) --Cnt[a[i]];
		solve(l,pos-1);
		for(int i=pos+1;i<=r;++i) ++Cnt[a[i]];
		solve(pos+1,r);
	}
}
int main()
{
	// freopen("c.in","r",stdin);
	// freopen("c.out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]),++Cnt[a[i]];
	for(int i=1;i<=N;++i) read(b[i]);
	solve(1,N);
	write(ans);
	return 0;
}
/*

*/

我是D题

形式化题意

给定一个长度为 的序列 ，值域为 ，若 ，则表示 在 中等概率随机，共 次操作：

  • 单点修改
  • 求

其中 表示区间中所有极长相等子段的长度的平方和。对 取模。

数据范围：

相关文章