网站建设中需要注意的问题,唐山自助建站模板,音乐网站制作php,织梦茶叶网站模板正题
题目链接:https://www.luogu.com.cn/problem/P8330 题目大意
给出一个长度为nnn的序列aaa#xff0c;你可以选择其中一个区间将其加上任意整数#xff0c;要求这个序列的众数出现次数最多。
输出最多次数和可能的众数。 1≤n≤2105,1≤ai≤109,∑n≤51051\leq n\leq …正题
题目链接:https://www.luogu.com.cn/problem/P8330 题目大意
给出一个长度为nnn的序列aaa你可以选择其中一个区间将其加上任意整数要求这个序列的众数出现次数最多。
输出最多次数和可能的众数。
1≤n≤2×105,1≤ai≤109,∑n≤5×1051\leq n\leq 2\times 10^5,1\leq a_i\leq 10^9,\sum n\leq 5\times 10^51≤n≤2×105,1≤ai≤109,∑n≤5×105保证不所有数都相等。 解题思路
相当于找到一个区间使得区间外和区间内的众数次数和最大。
这个和出现次数挂钩考虑根号分治。对于出现次数大于n\sqrt nn的数字这种数字不会超过n\sqrt nn个可以考虑对每个数字暴力做。
假设在区间外的数字是xxx区间内的是yyy那么我们区间中每个xxx会令答案−1-1−1每个yyy会令答案111。将xxx的位置视为−1-1−1yyy的位置视为111那么最大答案就是xxx的出现次数加最大子段和。
这个复杂度可以做到min(cx,cy)min(c_x,c_y)min(cx,cy)其中cxc_xcx表示xxx的出现次数。
那对于每个cxnc_x\sqrt ncxn的我们都可以O(n)O(n)O(n)解决它在外或者在内的情况。
然后考虑cx≤nc_x\leq \sqrt ncx≤n且cy≤nc_y\leq \sqrt ncy≤n的情况先把所有cxnc_x\sqrt ncxn的xxx给去掉此时注意到任何区间的众数个数都是≤n\leq \sqrt n≤n的那么我们预处理出fl,if_{l,i}fl,i表示一个最小的rrr满足[l,r][l,r][l,r]的众数出现次数为iii这样我们对于每个在外面的xxx枚举两个xxx的位置作为端点然后单指针移动计算他们之间区间的众数出现次数即可。
时间复杂度O(nn)O(n\sqrt n)O(nn) 解题思路
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includevector
#includecmath
using namespace std;
const int N2e510,M450;
int n,T,a[N],b[N],r[N][M],s[N];
vectorint v[N],pr[N];
int read(){int x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-f;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void calc(int x,int y){int ans10,ans20,now10,now20,las0;for(int i0;iv[y].size();i){now1max(now1s[v[y][i]]-s[las],0);ans1max(ans1,now1);now1max(now1-1,0);now2max(now2-s[v[y][i]]s[las],1);ans2max(ans2,now2);lasv[y][i];}pr[ans1v[y].size()].push_back(y);pr[ans2v[x].size()].push_back(x);return;
}
int main()
{
// freopen(mode_ex2.in,r,stdin);int casread();while(cas--){nread();T445;for(int i1;in;i)pr[i].clear(),v[i].clear();for(int i1;in1;i)for(int j0;jT;j)r[i][j]n1;for(int i1;in;i)a[i]read(),b[i]a[i];sort(b1,b1n);int munique(b1,b1n)-b-1;for(int i1;in;i){a[i]lower_bound(b1,b1m,a[i])-b;v[a[i]].push_back(i);}for(int x1;xm;x){pr[v[x].size()].push_back(x);if(v[x].size()T){for(int i1;in;i)s[i]0;for(int i0;iv[x].size();i)s[v[x][i]];for(int i1;in;i)s[i]s[i-1];for(int i1;im;i)if(i!x)calc(x,i);}}for(int x1;xm;x){if(v[x].size()T){for(int i0;iv[x].size();i)for(int ji;jv[x].size();j)r[v[x][i]][j-i]v[x][j];}}for(int in;i1;i--)for(int j0;jT;j)r[i][j]min(r[i][j],r[i1][j]);for(int x1;xm;x){if(v[x].size()T){for(int i-1;i(int)v[x].size();i){int l(i-1)?0:v[x][i];l;for(int j0,zi1;jT;j){if(r[l][j]n)break;while(zv[x].size()v[x][z]r[l][j])z;pr[v[x].size()j1-(z-i-1)].push_back(x);}}}}int ans0;for(int in;i1;i--)if(pr[i].size()){ansi;break;}printf(%d\n,ans);sort(pr[ans].begin(),pr[ans].end());printf(%d\n,b[pr[ans][0]]);for(int i1;ipr[ans].size();i)if(pr[ans][i-1]!pr[ans][i])printf(%d\n,b[pr[ans][i]]);}return 0;
}
