CCF 201809-3元素选择器

2023-05-16

分析:

这题超级坑,当时考试时只得了50分,现在重新做一直卡在80分,各种复杂情况都考虑到了,还是不能ac,于是尝试三种不同办法解决,也均不能AC,最后发现是题目写错了。

也就是说后代选择器只能是多个id或者是多个label,不会出现二者都有的情况,然而ccf后台的测试数据最后两个用例就是二者的嵌套,超级坑。

相反,很多复杂的情况用例并未考虑,以至于很多很水的代码都可以ac。

下面介绍本题解题思路。

第一步,弄清题目让我们干什么。

题目需要我们写一个选择器,不论输入的是标签,id还是后代选择器,都能得到文档中所有被选择的行以及行的个数。

第二步,确定存储结构。

一般大模拟都是需要定义一个结构体来存储输入文档,结构体有几个成员变量代表我们将输入的一行行字符串怎么切割,切割成几部分。既然文档由一些点,标签,id组成,点代表级数,那么至少我们应该存储层级,label和id,我在代码里还加了一个变量-father,代表某一行父结点的行数。

不设置father也可以,但将复杂很多,为什么呢?在实行后代选择器时,一个结点有多个不同级别的后代,我们遍历这颗树,迭代写法的话需要不停回溯,递归写法也就是dfs超级消耗时间和空间。我最后通过的代码用时几十毫秒,然而dfs则花费数秒。(这些解法我都实现了,但是鉴于遍历回溯时很复杂,这里先不赘述),那么设置了father会怎样呢,一个结点可以有多个孩子,却只有唯一的父结点,我们不断延父结点往上遍历,很快就能找到结果。

结构体构造完了,文档各行就构成了一个向量,向量的下标与行数有关。

第三步,处理输入的文档。

这里要注意,如果用cin直接读入一行,它固然会遇见回车就截止读入,但是本题文档各行可能含有空格,cin遇见空格也是会终止读入的,我们采用getline(cin,s)读入一行,这里有个常见的错误就是往往主函数最开始读入cin>>n>>m;然后紧接着一个换行再读入文档,那么getline第一个读入的就是回车,所以我们在读入文档前一般用getchar()处理掉回车。

处理文档各行:各行之前的点数除以二代表层级数,各行往上遍历找到的第一个层级高于它的就是它的父结点,再用若干行代码将各行的id和label分别存进结构体就ok了,处理文档比较简单。

第四步,编写元素选择器。

下面处理要求查询的各个元素选择器。这里一个技巧是遍历字符串,遇见空格或者字符串末尾就终止,如果到字符串结尾才终止,则不含空格,也就是单一的id或者label选择器,直接与doc各行比较即可,否则就是后代选择器。

处理后代选择器时,注意一定要将选择器原样存进向量,当然除掉空格,从最后的选择器进行比较,不等就往上继续,相等则文档指针继续向父结点回溯,选择器指针也减减,注意,此时语句二者不等不可停止回溯,因为后代选择器只要它的祖先结点包含那个选择器就可以了,而不一定要是父结点,一直回溯到最上层的结点才终止。

最后要注意的是标签不区分大小写,而id区分,即使在二者混杂的后代选择器中也要分开处理,将标签一律转化为小写;另一个即使处理后代选择器时我们是自下而上,自后向前,所以需要将存储几个的向量倒着输出。

#include <iostream>
#include <vector>
#include <cctype>
using namespace std;
struct html{
	int level,father;//层级和父结点行号
	string label,id;
};
vector<html> doc;//文档向量
vector<int> num;//结果向量
int main(){
	int n,m,fa,le;
	cin>>n>>m;
	getchar();
	while(n--){//处理文档
		string s,la,id;
		getline(cin,s);
		int p = 0;
		while(s[p] == '.')	p++;
		le = p / 2;
		if(p == 0 || !doc.size())	fa = -1	;
		else{
			for(int i = doc.size() - 1;i >= 0;i--){
				if(doc[i].level == le - 1){
					fa = i;
					break;
				}
			}
		}
		bool flag = false;
		while(p < s.size()){
			if(s[p] == ' '){
				p++;
				continue;
			}
			if(s[p] == '#'){
				flag = true;
				id += s[p];
				p++;
				continue;
			}
			if(flag)	id += s[p];
			else	la += tolower(s[p]);
			p++;
		}
		doc.push_back({le,fa,la,id});
	}
	while(m--){//选择
		string s;
		getline(cin,s);
		int p = 0;
		while(p != s.size() - 1 && s[p] != ' ')	p++;
		if(p == s.size() - 1){//单一选择器
			if(s[0] == '#'){
				for(int i = 0;i < doc.size();i++){
					if(s == doc[i].id)	num.push_back(i+1);	
				}	
			}
			else{
				for(int i = 0;i < s.size();i++)	s[i] = tolower(s[i]);				
				for(int i = 0;i < doc.size();i++){
					if(s == doc[i].label)	num.push_back(i+1);	
				}
			}
			cout<<num.size()<<" ";
			for(int i = 0;i < num.size();i++)	cout<<num[i]<<" ";
		}
		else{
			int j = 0;
			vector<string> v;
			p = 0;
			bool flag = true;
			while(p < s.size()){
			if(s[p] == '#')	flag = false;
			if(s[p] == ' '){
				flag = true;//还原标志变量
				v.push_back(s.substr(j,p-j));
				j = p + 1;
			}
			if(flag)	s[p] = tolower(s[p]);
			p++;
			}
			v.push_back(s.substr(j,p-j));
			for(int i = doc.size() - 1;i > 0;i--){
				int q = v.size() - 1;
				if(v[q] != doc[i].label && v[q] != doc[i].id)	continue;
				p = doc[i].father,q--;
				while(q >= 0 && p >= 0){
					if(doc[p].label == v[q] || doc[p].id == v[q])	q--;		
					p = doc[p].father;
				}
				if(q == -1)	num.push_back(i+1);
			}
			cout<<num.size()<<" ";
			for(int i = num.size()-1;i >= 0;i--)	cout<<num[i]<<" ";
		}
		cout<<endl;
		num.clear();
	}
	return 0;
}

 

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

CCF 201809-3元素选择器 的相关文章

随机推荐

  • Undo Log学习

    一 Undo Log的作用 数据库故障恢复机制的前世今生中提到过 xff0c Undo Log用来记录每次修改之前的历史值 xff0c 配合Redo Log用于故障恢复 这也就是InnoDB中Undo Log的第一个作用 xff1a 1 事
  • 慢SQL解决方案

    一 全表扫描 1 案例 span class token keyword SELECT span span class token function count span span class token punctuation span
  • JAVA17新特性

    2022 年 7 月底 xff0c 甲骨文正式停止对Java SE 7的扩展支持 xff0c 一个有着近 11 年历史的 Java 标准版本迎来生命周期结束 目前最新版本的 Java18 于今年 3 月正式发布 xff0c 并将于 2022
  • 测试——单元测试,集成测试,系统测试,白盒,黑盒

    一 单元测试 1 何为单元测试 单元测试 xff08 unit testing xff09 xff0c 是指对软件中的最小可测试单元进行检查和验证 单元测试通常和白盒测试联系到一起 xff0c 如果单从概念上来讲两者是有区别的 xff0c
  • java对多媒体处理工具

    简介 JAVE Java Audio Video Encoder 类库是一个 ffmpeg 项目的 Java 语言封装 开发人员可以使用 JAVE 在不同的格式间转换视频和音频 例如将 AVI 转成 MPEG 动画 xff0c 等等 ffm
  • 线程池不允许使用Executors创建原因

    1 FixedThreadPool 和 SingleThreadPool 允许的请求队列长度为 Integer MAX VALUE xff0c 可能会堆积大量的请求 xff0c 从而导致 OOM span class token keywo
  • 高分子结晶的新进展、新模型

    高分子结晶的新进展 新模型 高分子的结晶结构与形态对高分子材料的物理机械性能具有重要影响 xff0c 高分子结晶过程的分子机理 结晶热力学 结晶动力学等构成了高分子物理的重要内容 高分子结晶的研究经历了从溶液培养单晶 xff0c 确定折迭链
  • wsl安装图形界面——体验有脸有面的图形界面

    不得不说 xff0c 自动windows支持linux子系统之后 xff0c 这又使其成为一大卖点 首先 Linux 的分发版本非常多 xff0c 例如有 xff1a Ubuntu openSUSE SUSE Linux Fedora Ka
  • E: 有未能满足的依赖关系。请尝试不指明软件包的名字来运行“apt --fix-broken install”(也可以指定一个解决办法)。

    国产银河麒麟系统下在使用apt install xxxxxxx 出现如下错误 正在读取软件包列表 完成 正在分析软件包的依赖关系树 正在读取状态信息 完成 您也许需要运行 apt fix broken install 来修正上面的错误 下列
  • 【CCF CSP-20160903】炉石传说

    CCF CSP 20160903 炉石传说 C 43 43 代码 span class token macro property span class token directive hash span span class token d
  • 树莓派介绍

    文章目录 一 树莓派介绍二 树莓派分类 一 树莓派介绍 树莓派 xff0c xff08 英语 xff1a Raspberry Pi xff0c 简写为RPi xff0c 别名为RasPi RPI xff09 是为学习计算机编程教育而设计 x
  • Docker核心技术-联合文件系统

    联合文件系统 xff08 UnionFS xff09 是一种分层 轻量级并且高性能的文件系统 xff0c 它支持对文件系统的修改作为一次提交来一层层的叠加 xff0c 同时可以将不同目录挂载到同一个虚拟文件系统下 联合文件系统是 Docke
  • Spark SQL与Hive SQL解析执行流程

    转载专用 xff1a 读到了好文章 xff0c 用于分享收藏 xff0c 侵权删 转发自大佬 xff1a 数据人生coding xff0c https yuanmore blog csdn net type 61 blog 转发自大佬 xf
  • 银河麒麟V10服务器系统安装教程及注意事项

    系统安装 1 引导安装 从U盘引导安装时首先进入的是安装引导页面 xff0c 如下图 xff1a 使用向上方向键 lt gt 选择 Install Kylin Linux Advanced Server V10 xff0c 按进入安装过程
  • 1012 - iOS之View Controllers的理解

    需求现在只是把navigationController的导航栏字体给去掉 xff0c 不过既然都看了 xff0c 那就直接刚一下吧 阅读官网文档的顺序 xff1a Managing Content in Your App 39 s Wind
  • CentOS7 linux下yum安装redis以及使用 及 外网访问

    一 安装redis 1 检查是否有redis yum 源 1 yum install redis 2 下载fedora的epel仓库 1 yum install epel release 3 安装redis数据库 1 yum install
  • MySQL8.0忘记密码后重置密码(亲测有效)

    实测 xff0c 在mysql8系统下 xff0c 用mysqld console skip grant tables shared memory可以无密码启动服务 服务启动后 xff0c 以空密码登入系统 mysql exe u root
  • My uBlock static filters

    My uBlock static filters 2022 百度 2022 06 https pan baidu com pan baidu com bpapi analytics pan baidu com rest 2 0 pcs ad
  • conda安装包报错:The current user does not have write permissions to the target environment(当前用户没有写入权限)

    问题 xff1a 在Winodws 10下使用conda安装第三方包时报错 xff1a EnvironmentNotWritableError The current user does not have write permissions
  • CCF 201809-3元素选择器

    分析 xff1a 这题超级坑 xff0c 当时考试时只得了50分 xff0c 现在重新做一直卡在80分 xff0c 各种复杂情况都考虑到了 xff0c 还是不能ac xff0c 于是尝试三种不同办法解决 xff0c 也均不能AC xff0c