首页 > 其他分享 >CF1446D Frequency Problem

CF1446D Frequency Problem

时间:2023-12-19 21:12:47浏览次数:34  
标签:int ans tp Frequency 众数 Problem include CF1446D 根号

题意

给定 \(n\) 个数。

求最长的子段使得子段内有两个众数。

Sol

考虑全局众数对于子段的众数的影响。

注意到对于答案有贡献的子段一定包含全局众数,读者自证不难。

考虑对于每个数出现的次数根号分治。

对于出现次数大于根号的数:

种类不超过根号。

考虑暴力对于每一种数,考虑她成为众数的情况。

具体地,将全局众数看为 \(+1\),她看为 \(-1\)。类似用前缀和的东西来判断。

对于出现次数小于根号的数:

考虑枚举出现的次数。

对于每种出现的次数跑双指针。

时间复杂度 \(O(n \sqrt n)\)

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 2e5 + 5;
array <int, N> s, h;

array <int, 2 * N> isl;

int main() {
	int n = read(), pos = 0;
	for (int i = 1; i <= n; i++) {
		s[i] = read();
		h[s[i]]++;
		if (h[s[i]] > h[pos]) pos = s[i];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (h[i] <= 450 || i == pos) continue;
		int tp = 0;
		for (int j = 1; j <= n; j++) {
			if (s[j] == i) tp--;
			if (s[j] == pos) tp++;
			if (isl[tp + n] || !tp)
				ans = max(ans, j - isl[tp + n]);
			else
				isl[tp + n] = j;
		}
		tp = 0;
		for (int j = 1; j <= n; j++) {
			if (s[j] == i) tp--;
			if (s[j] == pos) tp++;
			isl[tp + n] = 0;
		}
	}
	for (int i = 1; i <= 450; i++) {
		int tp = 1, res = 0; h.fill(0);
		for (int j = 1; j <= n; j++) {
			h[s[j]]++;
			if (h[s[j]] == i) res++;
			while (tp <= j && h[s[j]] > i) {
				if (h[s[tp]] == i) res--;
				h[s[tp]]--;
				tp++;
			}
			if (res >= 2) ans = max(ans, j - tp + 1);
		}
	}
	write(ans), puts("");
	return 0;
}

标签:int,ans,tp,Frequency,众数,Problem,include,CF1446D,根号
From: https://www.cnblogs.com/cxqghzj/p/17914725.html

相关文章

  • CF1913 E Matrix Problem 题解
    LinkCF1913EMatrixProblemQuestion给定一个\(n\timesm\)的01矩阵,你可以把矩阵中的任意一个元素01翻转需要最后的矩阵满足,每行\(1\)的个数有\(A[i]\)个,每列\(1\)的个数有\(B[i]\)个Solution这貌似是一道非常经典的费用流题目我们建立\(n\)个行节点,\(m......
  • [ABC318G] Typical Path Problem 题解
    原题链接:ABC318G显然是圆方树。点双缩点过后建立一颗以点\(c\)为根节点的圆方树,考虑什么情况是合法的。从点\(a\)开始往上跳直到跳到点\(c\),如果中间走过了某一个方点并且这个方点与\(b\)点有直接连边,那么就是合法的;否则不合法。证明:如果路径中所经过的方点和\(b\)点......
  • A. Constructive Problems
    原题链接思路历程1.一开始我不知道具体该怎么放,于是我按照样例2的顺序手画了一遍。2.然后发现,对于一个n*n的矩形,再放一个格子最大能使其达到(n+1)*(n+1)3.1*1时,放了1个格子,2*2时放了2个格子,由此可以推出放n个格子时最大能达到n*n4.这道题就变成了,找出k使得k*k刚好能覆盖n*m,也就......
  • POLIR-Management-TYPES of decisions{Structured(routine+familiar)Problems: Progra
    Inaverysimplesense,theproblemsmanagersencountercanbeclassifiedas:routineandfamiliar;newandunusual.Inresponse,managerswilluseoneoftwodifferenttypesofdecisions:StructuredProblemsandProgrammedDecisions;UnstructuredP......
  • [ARC111F] Do you like query problems?
    题意:给出三个数\(n,m,q\)。你有一个长度为\(n\)的序列\(a\),初始全为为\(0\),你有三种操作:操作\(1\):给出\(l,r,v\),让区间\([l,r]\)对\(v\)取\(\min\)。操作\(2\):给出\(l,r,v\),让区间\([l,r]\)对\(v\)取\(\max\)。操作\(3\),给出\(l,r\),求区间和,将其累加进......
  • A Pattern to Solve Backtracking Problems
    Thebacktrackingsolutionsofmostleetcode-problemshaveasimilarpattern.Let'stakealookonit.Subset1.Recursion(Backtrack)-TimecomplexityisO(2^n),andthedepthofrecursionisO(n).classSolution{public:vector<vector<in......
  • [CF1603E] A Perfect Problem
    APerfectProblem题面翻译一个序列是好的当且仅当集合最大值乘上集合最小值大于等于集合元素的加和;一个序列是完美的,当且仅当这个序列的任何子序列都是好的(包括自己不包括空集);你要求的是:长度为\(n\)的并且每一个元素都大于等于\(1\)并且小于等于\(n+1\)的完美序列的......
  • 【UVA 101】The Blocks Problem 题解(模拟+向量)
    计算机科学的许多领域使用简单、抽象的领域进行分析和实证研究。例如,早期的人工智能规划和机器人研究(STRIPS)使用了一个区块世界,其中机器人arm执行涉及块操作的任务。在这个问题中,您将在某些规则和约束下对一个简单的块世界进行建模。相当地与确定如何达到指定状态相比,您将“编程......
  • uva101The Blocks Problem
    原题链接TheBlocksProblem-洛谷|计算机科学教育新生态(luogu.com.cn)一道模拟题。(水题) 但模拟过程很有意思,怎么样才能用最短的代码完成所有操作,使代码更简洁是很考验技术的。 #include<bits/stdc++.h>usingnamespacestd;vector<int>block[30];vector<int>m;......
  • 2023ICCV_FSI Frequency and Spatial Interactive Learning for Image Restoration in
     三.Network 1.  2.FLB:没看懂是怎么分离的水平和竖直方向 3.SLB:每一层保留一半的通道特征用于细化,其余的在特征重构后输出(没看懂)。Multi-distillationNetwork 超分辨网络的Multi-distillationNetwork(2019ACMMM_LightweightImageSuper-ResolutionwithIn......