骷髅打金题

经 int_R 指正，我原来的题解有一部分在狗叫，已于 5 月 30 日修正。

暴力

因为暴力比较有意思就简单说一下。

Sub #2

固定左端点，枚举右端点，动态使用桶维护所有出现过的元素的种类数

V

和众数出现次数

T

，如果

V\times T

等于区间长度

l

，则该区间合法。

由此得到小常数

O(n^2)

做法。Sub #1 是给大常数做法和复杂度更高的做法留的。

Sub #3

考虑枚举出现过的元素集合

S

，进行和哈希，给原序列中出现的元素随机赋权，同种元素权值相同。

如果区间所有元素的哈希值总和能被

S

中元素的哈希值总和

W_S

整除即为合法。这个可以转成前缀和模

W_S

相等，然后拿哈希表存储前缀和的哈希值就行了。

Sub #4

每一种元素的期望出现次数很少。

将每个区间

[l,r]

转成平面上的点

(l,r)

，将每一种元素的贡献转成矩形取 max 然后扫描线即可。

具体可以去问验题人 cdx123456，我没写过这个做法。

正解

对原序列分治，考虑如何拼合左半边和右半边。

首先考虑和哈希，给原序列中出现的元素随机赋权，同种元素权值相同。

对“是否存在某种元素完全出现在左半边/右半边”进行分讨：

（给个图，看下面的文字感觉恶心看不懂可以看图）

如果没有任何一种元素完全出现在左半边/右半边，则每一种元素必须在左半边和右半边同时出现，此时满足条件当且仅当：

左边出现过的所有元素种类的哈希值和 $L_a$ 等于右边出现过的所有元素种类的哈希值和 $R_a$ ；
左边和右边所有元素的哈希值总和 $L_h+R_h$ 能被 $L_a$ 整除，换句话说，就是 $L_h\bmod L_a=(-R_h)\bmod R_a$ 。

如果有某几种元素完全出现在左半边，没有元素完全出现在右半边，此时满足条件当且仅当：

如果要在左边加入最少的元素使得左边所有元素的出现次数相同，加入的元素哈希值总和记作

L_r

。

有 $L_r=R_h$ 。

如果有某几种元素完全出现在右半边，没有元素完全出现在左半边，此时同上。

如果有某几种元素完全出现在左半边，有某几种元素完全出现在右半边，此时满足条件当且仅当：

左边所有出现次数严格小于众数的出现次数的元素哈希值总和记作

L_z

，同理定义

R_z

。

如果想要添加尽量少的元素使得左边所有元素出现次数相同，需添加的元素哈希值总和记作

L_x

，同理定义

R_x

。

左边所有众数在右边首次出现的位置记作

K

。

左右两边众数出现次数相同。
有 $L_z=R_x$ 。
$K$ 大于右边的右端点 $r$ 。换句话说，就是左边的所有众数均不在右边出现。

上述变量均可以线性预处理，由此得到枚举左右端点然后 check 是否满足上述四种条件其中之一的

O(n^2)

做法。

观察到上述四种情况是独立的，也就是说不可能存在区间同时满足两种或更多情况。所以可以把四种情况拆开算。

观察到上述条件大多都是检验若干个二元组或三元组完全相等，最复杂的第四种情况也只是加了一维偏序，因此可以拿哈希表直接维护，偏序可以基数排序后离线双指针，动态加动态查。

时间复杂度

O(n\log n)

。哈希表需要手写。

随机赋权单个元素权值值域使用

10^9

级别冲突概率极大，使用

10^{12}

级别即可轻松通过。

代码

贺题的小先生太多了，目前已通过的提交中绝大多数都是直接复制粘贴我的题解，故于 2025/5/27 删除所有

O(n\log n)

代码。

下面是一种手写哈希表的实现：

CPP

//Hash_Table
const int MASK = (1<<19)-1;
int Hd[MASK+1],Idx;
int Ne[maxn],C[maxn];
XI Wx[maxn];
inline void Insert(const XI &X){
	const int p=X&MASK;
	for(int i=Hd[p];i!=-1;i=Ne[i])
		if(Wx[i]==X)
			return C[i]++,void();
	C[++Idx]=1,Wx[Idx]=X,Ne[Idx]=Hd[p],Hd[p]=Idx;
}
inline void Reset(const XI &X){
	Hd[X&MASK]=-1;
}
inline int Query(const XI &X){
	const int p=X&MASK;
	for(int i=Hd[p];i!=-1;i=Ne[i])
		if(Wx[i]==X)
			return C[i];
	return 0;
}

O(n^2)

的代码如下：

CPP

#include"bits/stdc++.h"
using namespace std;
const int maxn = 1e6+10;
int T,n,m;
int Ap[maxn],a[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(nullptr);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		long long Ans=0;
		for(int l=1;l<=n;l++){
			for(int r=l,Mx_=0,Cc_=0;r<=n;r++){
				if(!(Ap[a[r]]++))Cc_++;
				Mx_=max(Mx_,Ap[a[r]]);
				if(Mx_*Cc_==(r-l+1))Ans++;
			}
			for(int r=l;r<=n;r++)Ap[a[r]]=0;
		}
		cout<<Ans<<'\n';
	}
}

文章操作

暴力

Sub #2

Sub #3

Sub #4

正解

代码

相关推荐

评论

骷髅打金题