首页 > 其他分享 >暑假集训CSP提高模拟16

暑假集训CSP提高模拟16

时间:2024-08-08 19:05:11浏览次数:13  
标签:lmy cnt 16 int sum CSP -- 众数 集训

1.九次九日九重色

一开始做的时候被题面给迷惑住了,没想到可以跳着 匹配(样例太水)。
那我们来考虑如何做,首先思路肯定是把能匹配的暴力求出来,根据不知道怎么搞的调和计数,这样的复杂度还不是很高,是\(O(NlogN)\),可以搞。
观察一下预处理出来的序列,是不是很熟悉。没错剩下的就是求最长上升子序列。

那求最长上升子序列有两种方法,一个是\(O(n^2)\)的DP,还有一个\(O(NlogN)\)的二分。
这里主要了解后面的(因为赛时我还不会)。
原理其实比较简单,看代码就能看懂。

点击查看代码
#include<bits/stdc++.h>
using namespace std;


const int N=2e5+107;

int n;
struct lmy
{
	int x,y;
}a[N];
bool comp(lmy a,lmy b)
{
	return a.x<b.x;
}
int s[N],tp;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+1+n,comp);
	for(int i=1;i<=n;i++)
	{
		if(s[tp]<a[i].y) s[++tp]=a[i].y;
		else
		{
			s[lower_bound(s+1,s+1+tp,a[i].y)-s]=a[i].y;
		}
	}
	printf("%d",tp);
}

2.天色天歌天籁音

简单理解一下题意,再自己手模一下,可以发现题目所求的是区间众数,然后它强调了一下各个互不影响,可以考虑莫队(其实挺套路的,但我不会莫队了,大悲)。
主要讲讲add和del的操作,
首先add比较好说,只需要直接计数。

del就需要分讨一下。
1.减之前比目前最大众数小,无影响。
2.本身是最大众数,减完之后还是,无影响。
3.本身为最大众数(但众数有很多个),减之后不为最大众数(主要的问题)。

关于这个问题,我们就可以开一个桶来记录每个数出现个数(众数)的个数(是有点绕,得理解一下),到这这个题就没什么了

点击查看代码
#include<bits/stdc++.h>
using namespace std;

const int N=3e5+107;
int n,m,a[N];

int li[N],ri[N],bg[N],tot;
struct lmy
{
	int x,y,id;
}q[N];
bool comp(lmy &a,lmy &b)
{
	int p=bg[a.x],q=bg[b.x];
	if(p!=q) return p<q;
	if(p&1) return a.y<b.y;
	else return a.y>b.y;
}

void fk()
{
	int sq=sqrt(n);
	for(int i=1;i<=sq;i++)
	{
		li[i]=ri[i-1]+1;
		ri[i]=sq*i;
		if(i==sq) ri[i]=n;
		for(int j=li[i];j<=ri[i];j++) bg[j]=i;
	}
}


map<int,int> mp;

int sum,t[N],cnt[N],ans[N];
void add(int i)
{
	t[cnt[a[i]]]--;
	t[++cnt[a[i]]]++;
	sum=max(sum,cnt[a[i]]);
}

void del(int i)
{
	t[cnt[a[i]]]--;
	if(cnt[a[i]]==sum&&!t[cnt[a[i]]]) sum--;
	t[--cnt[a[i]]]++;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		if(mp.find(a[i])==mp.end())
		{
			mp[a[i]]=++tot;
		}
		a[i]=mp[a[i]];
	}
	fk();
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		q[i]={l,r,i};
	}
	sort(q+1,q+1+m,comp);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(r<q[i].y) add(++r);
		while(r>q[i].y) del(r--);
		while(l<q[i].x) del(l++);
		while(l>q[i].x) add(--l);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++) printf("%d\n",-ans[i]);
}

标签:lmy,cnt,16,int,sum,CSP,--,众数,集训
From: https://www.cnblogs.com/zhengchenxi/p/18349428

相关文章

  • Xcode 16 beta 5 (16A5221g) 发布 - Apple 平台 IDE
    Xcode16beta5(16A5221g)发布-Apple平台IDEIDEforiOS/iPadOS/macOS/watchOS/tvOS/visonOS请访问原文链接:https://sysin.org/blog/apple-xcode-16/,查看最新版。原创作品,转载请保留出处。Xcode16的新功能使用预测代码补全功能和更快的预览功能,将奇思妙想转化为代码......
  • CSP模拟 小 trick 总结 (持续施工中)
    虽然这篇博客来的有点晚,但还是写了,欢迎dalao补充(1、分块、莫队有关:(1):一个真正的回滚莫队(感谢Qyun的讲解)$\\\\\\\\$学习回滚莫队的时候,我们经常会在回滚时使用memcpy来恢复以前的版本,但众所周知--memset和memcpy常数巨大,破坏了莫队$O(n\sqrtn)$的时间复杂度,导......
  • 暑假集训csp提高模拟16
    赛时rank38,T120,T250,T30,T40T2挂分原因:莫队n,m写反了,但样例中这俩一样,遂寄T1九次九日九重色\[\color{Green}{\Huge{!!!!!!!!!九日\,!!!!!!!!!}}\]\[\color{Red}{\Huge{!!!!!!!!!九日\,!!!!!!!!!}}\]\[\color{Blue}{\Huge{!!!!!!!!!九日\,!!!!!!!!!}}\]\[\color{Yellow}{\......
  • 「模拟赛」暑期集训CSP提高模拟15(8.7)
    赛时记录:开场看T1,一眼\(manacher\)求子串回文串,听课是听了,但是不会啊。跳了。看T2,发现结论题,推了会结论打上走了。打完T2想了会T3、T4,无思路,回来打了T1暴力和特殊性质,\(30pts\),又去想T3,还是不会,这时还剩一个小时。不行,现在才\(130pts\),包打祭的啊,能不能翻盘看我T1......
  • 暑假集训CSP提高模拟16
    暑假集训CSP提高模拟16组题人:@Muel_imj\(T1\)P216.九次九日九重色\(100pts\)部分分\(30pts\):设\(f_{i,j}\)表示当前处理到\(P\)的第\(i\)位,\(Q\)的第\(j\)位时最大的\(k\),状态转移方程为\(f_{i,j}=\begin{cases}\max(f_{i,j-1},f_{i-1,j})&p_{i}\nmid......
  • SublimeText 4.4169 中文授权版
    SublimeText是编辑器中的一款神级IDE,非常有名,虽然比较轻量,但是呢软件拓展性非常强大,适用于多种编程语言,当然,当一个编辑器,也是非常不错的。SublimeText支持但不限于C,C++,C#,CSS,D,Erlang,HTML,Groovy,Haskell,HTML,Java,JavaScript,LaTeX,Lisp,Lua,Markdown,......
  • [CSP-J 2023] 小苹果
    [CSP-J2023]小苹果【官方数据】题目描述小Y的桌子上放着 nn 个苹果从左到右排成一列,编号为从 11 到 nn。小苞是小Y的好朋友,每天她都会从中拿走一些苹果。每天在拿的时候,小苞都是从左侧第 11 个苹果开始、每隔 22 个苹果拿走 11 个苹果。随后小苞会将剩下......
  • [CSP-S 2023] 密码锁
    题目描述小Y有一把五个拨圈的密码锁。如图所示,每个拨圈上是从 00 到 99 的数字。每个拨圈都是从 00 到 99 的循环,即 99 拨动一个位置后可以变成 00 或 88,因为校园里比较安全,小Y采用的锁车方式是:从正确密码开始,随机转动密码锁仅一次;每次都是以某个幅度仅转......
  • 169.254.x.x是什么地址
    ‌APIPA169.254.x.x地址是一个特殊的IP地址范围,被称为“APIPA”(AutomaticPrivateIPAddressing)地址,主要用于在网络通信设置不当时确保最基本的计算机网络连接性。这种地址是由操作系统自动分配给计算机的私有IP地址,当计算机无法通过‌DHCP(动态主机配置协议)服务......
  • 预训练大语言模型综述来了!中国人民大学教授发表包含了416个参考文献的大语言模型综述
    尽管大语言模型在最近今年发展十分迅速,但是相关的综述却相对比较落后。本文是由中国人民大学教授WayneXinZhao等人前几天刚公开的关于大语言模型的综述,论文正文部分共32页,包含了416个参考文献。内容十分详实。这份大模型综述我已经打包好了,还有完整版的大模型AI学习资......