bzoj 1483: [HNOI2009]梦幻布丁
2024-08-24 10:49:03
1483: [HNOI2009]梦幻布丁
Description
N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.
Input
第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变,其后的两个整数X,Y表示将所有颜色为X的变为Y,X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色,这时你应该输出一个整数. 0
Output
针对第二类操作即询问,依次输出当前有多少段颜色.
Sample Input
4 3
1 2 2 1
2
1 2 1
2
1 2 2 1
2
1 2 1
2
Sample Output
3
1
1
ACTY真大!!!
———————以下题解———————
链表加优化。。
每种颜色一条链
我们使用启发式合并,每次把元素少的链合并到元素多的链上去,但是有一个问题就是题目规定输入x,y,把x颜色的变为y。
假如颜色x的元素多于y,我们还是可以把y合并到x,只是再维护一个father数组,表示颜色x实际上表示什么。
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int M=;
const int N=;
int n,m,i,ans,x,y,p,a[N],s[M],head[M],last[M],Next[N],f[M];
int main()
{
scanf("%d%d",&n,&m);
ans=;
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
f[a[i]]=a[i];
s[a[i]]++;
Next[i]=last[a[i]];
last[a[i]]=i;
if(!head[a[i]]) head[a[i]]=i;
if(a[i]!=a[i-]) ans++;
}
while(m--)
{
scanf("%d",&p);
if(p==)
{
scanf("%d%d",&x,&y);
if(x==y) continue;
if(s[f[x]]>s[f[y]]) swap(f[x],f[y]);
x=f[x];y=f[y];
if(!s[x]) continue;
for(i=last[x];i;i=Next[i])
{
if(a[i-]==y) ans--;
if(a[i+]==y) ans--;
}
for(i=last[x];i;i=Next[i]) a[i]=y;
s[y]+=s[x];
s[x]=;
Next[head[y]]=last[x];
head[y]=head[x];
} else printf("%d\n",ans);
}
return ;
}
最新文章
- EntityFramework Core Raw SQL
- 时间戳 JavaScript parse() 方法 处理技巧
- NTDLL未文档化函数RtlGetNtVersionNumbers获取操作系统版本
- div,span,p等转换成可编辑
- centos6.6编译安装lnmp系列之nginx
- EntityFramework tt模板
- ava如何实现系统监控、系统信息收集、sigar开源API的学习(转)
- GO語言基礎教程:數組,切片,map
- eclipse 调试时出现 Error: [Errno 10013]
- struts2表单验证
- 武汉科技大学ACM:1005: 华科版C语言程序设计教程(第二版)例题5.8
- autoconfig操作小结
- laravel php artisan migrate 数据迁移时出现的[HY000][1045]错误
- 从 Spring 2.5 开始就可以使用注解来配置依赖注入,而不是采用 XML 来描述一个 bean。
- Ubuntu 16.04 安装和使用QQ最简洁的方式
- 为什么HTTPS比HTTP更安全?
- Windows安装docker (带安装包)
- Linux 出现telnet: 127.0.0.1: Connection refused错误解决办法
- 获取Gitlab项目的Token
- GUI_鼠标事件
热门文章
- 6.0docker Dockerfile文件
- Eclipse svn 忽略文件夹/ svn 设置不同步
- SD 模拟sip 读写子程序
- 利用keepalive+mysql replication 实现数据库的高可用
- 2017多校第4场 HDU 6078 Wavel Sequence DP
- 1.ubuntu的安装
- 手机meta标签(保存下来省的每次都找)
- leetcode 之Copy List with Random Pointer(23)
- ES6新数据结构Set让数组去重
- selenium+python自动化80-文件下载(不弹询问框)【转载】