C - C
Description
Your task is counting the segments of different colors you can see at last.
Input
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
x1 x2 c
x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.
All the numbers are in the range [0, 8000], and they are all integers.
Input may contain several data set, process to the end of file.
Output
If some color can't be seen, you shouldn't print it.
Print a blank line after every dataset.
Sample Input
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1
Sample Output
2 1
3 1
1 1
0 2
1 1
题意:
在n个区间中填色,x1代表起点,x2代表终点,c代表颜色的名字(或者说第c种颜色),填的颜色后面的可以覆盖前面的,求最后可看到的颜色一共被分成几段。
思路:
用数组模拟染色的情况,从 [ X1 , X2 )(X1是可取的,X2是不可取的),每次从下标为X1循环到X2-1,都赋值为这次要染的颜色的名字。最后通过判断每个数字有多少截就能对应输出相应的颜色有多少截了。
Wrong and test:
#include<stdio.h> #include<string.h> #include<algorithm> #include<stdlib.h> using namespace std; int main() { int N,color,from,to,i,sum,max,j,temp; int number[8005]; int co[8005]; while(scanf("%d",&N)!=EOF) { memset(number,0,sizeof(number)); memset(co,0,sizeof(co)); max=0; i=0; while(N--) { scanf("%d%d%d",&from,&to,&color); if(to>max) max=to; for(from;from<to;from++) { number[from]=color; } co[i++]=color; } sum=i; //一开始忘了sum的初始化 sort(co,co+sum); number[max]=-1; max++; //测试数据 // printf("\nThe number's color is:\n"); // for(i=0;i<max;i++) // printf("%d ",number[i]); // printf("\n"); // system("pause"); // printf("\nThe color is:\n"); // for(i=0;i<sum;i++) // printf("%d ",co[i]); // printf("\n"); // system("pause"); temp=0; for(j=1;j<max;j++) if(number[j]!=co[0]&&number[j-1]==co[0]) temp++; if(temp) printf("%d %d\n",co[0],temp); for(i=1;i<sum;i++) { temp=0; if(co[i]!=co[i-1]) { for(j=1;j<max;j++) if(number[j]!=co[i]&&number[j-1]==co[i]) temp++; if(temp) printf("%d %d\n",co[i],temp); } } if(i==sum) printf("\n"); } } 错误说明: 1.当例子为 5 1 3 0 2 3 0 1 2 1 5 6 3 3 5 2 的时候,模拟的线段应该是(0)1 0 2 2 3但是1前面还有个0,这个0是初始化的时候设置的,所以这里存在着盲点,所以要将颜色的0和初始化的0区分开,用颜色-1来代表0; 2.还有每个CASE之间要空一行; 3.填完色后要在最后加个-1(因为判断number[j]!=co[i]&&number[j-1]==co[i]是后一个与前一个对比判断的,所以为了保证最后一个数能被判断到,所以要最后加个-1。
AC:
#include<stdio.h> #include<string.h> #include<algorithm> #include<stdlib.h> using namespace std; int main() { int N,color,from,to,i,sum,max,j,temp; int number[8005]; int co[8005]; while(scanf("%d",&N)!=EOF) { memset(number,0,sizeof(number)); memset(co,0,sizeof(co)); max=0; i=0; while(N--) { scanf("%d%d%d",&from,&to,&color); if(to>max) max=to; for(from;from<to;from++) { if(color==0) number[from]=-1; else number[from]=color; } if(color==0) co[i++]=-1; else co[i++]=color; } sum=i; sort(co,co+sum); number[max]=-10; max++; temp=0; for(j=1;j<max;j++) if(number[j]!=co[0]&&number[j-1]==co[0]) temp++; if(temp) { if(co[0]==-1) printf("%d %d\n",co[0]+1,temp); else printf("%d %d\n",co[0],temp); } for(i=1;i<sum;i++) { temp=0; if(co[i]!=co[i-1]) { for(j=1;j<max;j++) if(number[j]!=co[i]&&number[j-1]==co[i]) temp++; if(temp) { if(co[i]==-1) printf("%d %d\n",co[i]+1,temp); else printf("%d %d\n",co[i],temp); } } } if(i==sum) printf("\n"); } }
总结:
当时比赛的时候,连题目都不敢看,因为坚信自己是做不出来的。今天要不是师兄叫我再看下这题的话,我估计还不敢做这题。虽然不是用线段树做的,而且神奇的做出来之后才知道这是暴力。分析时间复杂度,然后根据时间来选择最适合最快速的方法解决题目真的很重要,又学到东西了。因为练得实在太少了,没有实力就没有信心,没有信心就没有勇气去坚持完一场比赛。这道题还需要用线段树来做一遍(迟点再添加),虽然这样子水过去了,但是还是有点不太踏实。
相关推荐
用于施工安全设施计算,施工方案,技术交底,应急预案、可以计算模板支架体系,高支模,地基承载力,边坡承载力,卸料平台安全计算等,网络收集,请支持正版
linux 流程图工具,可以选择语言, 类图,uml, 免费版,可以用 linux 流程图工具,可以选择语言, 类图,uml, 免费版,可以用
autoitV3.2.13.7 版本,提供下载,汉化版本包括帮助文档
xcode真机 13.7.zip
Location-cleaned13.7.rar
北京鼎汉通技术有限公司无线测温说明书_13.7.10.doc
绘图软件、Draw.io-13.7.9、.drawio文件格式
高中物理 13.7.8 光的颜色 色散 激光课件 新人教选修34 .ppt
朋友圈广告助手最新版13.7.0需要最新版请看安装说明,支持二次开发,有需要的可以联系
opencv2版本以上,需要额外编译所需要的文件,该版本为opencv-2.4.13.7,没有opencv_contrib版本。
可上传下载。作网站必备。FlashFXPV3.8Beta13.7.9Build1348烈火汉化绿色版功能强大FXP FTP工具绿色版
资源分类:Python库 所属语言:Python 资源全名:pyginx-0.1.13.7.7-cp36-cp36m-macosx_10_13_x86_64.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
SDK 13.7
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...
DeviceSupport 13.7
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 ...