CF1335 E1&E2 题解

题目链接：https://codeforces.ml/contest/1335/problem/E2
div3的E题其实并不难。
（57min的时候做出E1，并且可以过E2，结果1h33min时才交o(╥﹏╥)o，并且D取错题了，导致小号勉强上蓝）
首先像这种可以直接枚举元素大小的，有一个经典模型，就是像选择客栈那样的前缀和。
直接枚举元素大小。
而这题还要有两边的枚举。
实际上，对于两边元素必须相同，且个数相等这个约束就帮了大忙。
可以直接用链表，把相同元素左右相连。（写法类似链式前向星）
然后枚举元素，将其最左最右指针同时跳，保证两边个数，元素都相同。
然后再枚举中间的元素，用前缀和直接求出中间相同元素的最大数量为多少。
再加上两边跳过的元素数量即可。
而这种方法巧又巧在时间方面。
（一开始算错时间，后来算对了结果看错了数据范围，导致迟A了那么久）
因为实际上指针总共只会跳\(n/2\)次，所以带上枚举中间元素的k。
总时间为：\(O(nk)\)
也就可以通过了。
而这种时间的优越性在于每次枚举的指针都不重复。
利用双链表的形式免去了浪费时间的暴力枚举元素。
代码：

#include
#include
#include
#include
#include
#include
#include 
#include
#include
using namespace std;
//#define int long long
#define re register int
inline int read(){
    int x=0,ff=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*ff;
}
int t,n,a[200005],s[200002][202],h[202],hh[202];
int nt[200005],ntt[200005],ans;
signed main(){
//	freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);
	t=read();
	while(t--){
		n=read();memset(h,0,sizeof(h));memset(hh,0,sizeof(hh));
		ans=1;
		for(re i=1;i<=n;i++){
			a[i]=read();
			for(re j=1;j<=200;j++)s[i][j]=s[i-1][j];
			s[i][a[i]]++;nt[i]=h[a[i]];h[a[i]]=i;
		}
		for(re i=n;i;i--){
			ntt[i]=hh[a[i]];hh[a[i]]=i;
		}
		for(re i=1;i<=200;i++){
			int l=hh[i],r=h[i],k=1;
			while(l

话说我还真不会只能过E1,但过不了E2的做法

题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签