• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

杭电多校第五场1009 (hdu7020

admin

11月 28, 2021

题意:

给一个数组a,求区间内众数的数字个数大于区间长度一半的区间个数。

如众数是ai,ai个数>(r-l+1)/2符合题意。

思路:

因为我们每次只要看众数,所以可以根据出现的每个数来做。

对于一个数cnt[i],如果他在原串里的这个位置出现了,那就让这个位置为1,否则为-1。

那么对于这个东西我们就可以求前缀和,如果sum[i]-sum[j]>0,说明这段区间里的这个数比其他数总和多。

所以就变成了对于上面定义的这样一个数组,求前缀和sum[i]>sum[j]的个数(i>j)

定义两个数组f1[sum]为前缀和为sum的点的个数。

f2[sum]为差分数组来维护f1。

对于1我们只需要线性扫描+维护就行了。

特殊情况是对于前缀和为当前最小时的连续-1,因为这个时候不会产生新解,所以可以利用刚才的f2数组来做差分,快速实现对于f1某一段的+1

注意点:这里初始时有一个前缀和为0,但是不能直接用进去,因为后续如果到过负数,那么开始i=0时的0是不能被计算进后面的答案里的。

因此维护几个值的时候要前移一下,先计算这个点之前上一次的信息,来内含i=0时的信息。

下附代码:

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 vector<ll> cnt;
 5 vector<ll> G[1000005];
 6 ll res,n,a[1000005];
 7 ll flag[1000005];
 8 ll find(ll x){
 9     ll ans=0;
10     ll sum=0,minn=0;
11     unordered_map<ll,ll> f1,f2;
12     G[x].push_back(n+1);
13     ll k=0;
14     for (ll i=1; i<=n; i++){
15         if (i>G[x][k]) k++;
16         if (a[i]!=x && sum==minn){
17             ll len=G[x][k]-i-1;
18             f2[sum+1]--;
19             f2[sum-len]++;
20             i=G[x][k]-1;
21             sum=sum-len-1;
22         }
23         else if (a[i]==x) {
24             f1[sum]=f1[sum]+f2[sum];
25             f2[sum+1]+=f2[sum];
26             f2[sum]=0;
27             f1[sum]++;
28             ans+=f1[sum];
29             res+=ans;
30             sum++;
31             
32         }
33         else {
34             f1[sum]++;
35             sum--;
36             ans-=f1[sum];
37             res+=ans;
38         }
39         if (sum<minn) minn=sum;
40     }
41 }
42 int main(){
43     ll T;
44     scanf("%lld",&T);
45     while (T--){
46         scanf("%d",&n);
47         cnt.clear();
48         memset(flag,0,sizeof(flag));
49         for (ll i=1; i<=n; i++){
50             scanf("%lld",&a[i]);
51             if (!flag[a[i]]) cnt.push_back(a[i]),flag[a[i]]=1;
52             G[a[i]].push_back(i);
53         }
54         res=0;
55         for (auto i:cnt){
56             find(i);
57             G[i].clear();
58         }
59         printf("%lld
",res);
60     }
61 }

View Code

赛场上看到ai的范围,有因为题目性质提炼出来是看众数的个数,所以其实只要看一个数就行了。

自然而然想到能不能枚举每一个出现的ai,然后快速维护出个数大于一半的区间数。

当时时间复杂度搞错了,感觉前缀和会T,但是其实这是个只有1和-1的前缀和,可以通过差分数组跳过一段-1来优化。

下次抓到灵感还是要多挖掘一下,不能轻易否决

发表评论

您的电子邮箱地址不会被公开。