HDU 4868 Information Extraction(2014 多校联合第一场 H)

时间：2022-09-23 15:55:18

看到这道题时我的内心是奔溃的，没有了解过HTML，只能靠窝的渣渣英语一点一点翻译啊TT、

Information Extraction

题意：（纯手工翻译，有些用词可能在html中不是一样的，还多包涵）
从HTML文档中提取信息，用一种特殊的格式输出。
HTML文件的定义如下：
HTML:
   是一种超文本标记语言。标记语言是由一系列的标记组成的。

　标签描述文档内容。HTML文件由标签和文本组成。
标签：
   HTML使用标签来实现他的语法。

标签由特殊的字符（如： ‘<’, ‘>’ and ‘/’）组成。

标签通常成对出现，起始标签和结束标签。起始标签以<开头，>结尾。

结束标签以</开头，以>结尾。文件的其他地方不会出现尖括号。

标签名是只含有小写字母的字符串。标签中没有行中断。

除了标签，文件中出现的其他东西都被认为是文本内容。

标签名的长度不超过30.
元素：
   元素是起始标签和相对应的终止标签之间的任何内容，包括标签在内。

元素内容是开始标签和结束标签之间的内容。

有些元素没有内容，我们叫它空元素，如 <hr></hr>。

空元素可以被关在一个打开标签内，以/>结尾，而不是>。

所有元素都可以被关闭用关闭标签或者在开始标签里面。

元素可以有属性。

元素可以被嵌套，即一个元素可以包含另一个元素。

<html>元素师其他所有元素的容器，他不包含任何属性。
属性：
   属性为元素提供额外信息。

属性总是在开始标签中被规定，在标签名的后面。

标签名和属性由一个空格隔开。

一个元素可以有多个属性。

属性以这样的形式出现：name="value" class="icpc"，等号两边没有空格。

所有的属性名都是小写的。

id属性的值是唯一的，长度小于等于30.

题目中还给了几个例子，我们来看一下：

sample 1：

<html><body>  //<html>是总容器，<body>是标签
<h3 id="header" class="style1">this is a test</h3>   //<h3 id="header" class="style1">是起始标签，标签名是h3，有两个属性，id和class。“this is a test”是元素。</h3>是结束标签。
<div id="content" class="style2">   //<div> 标签，同上。
this is content<br/>
<pre>var x = 1111; </pre>
</div>
</body></html>  //结束标签

由结构到输出格式的映射如下：

id属性的值-输出格式的标签名

输入：

T：代表有几组样例。

每一个样例都在前面规定它的输出格式。

n：有几种html文件

每一种类型的l结构在之前的html文件中

m: 有几种映射从结构到输出结果

m行映射

最后是html测试案例

输出：

每一组样例，第一行输出“Case #x”

如果存在这种结构的html文件，按格式输出，否则，输出“Can't Identify”如果有多种结构，使用最早输入的结构。

下面我们来分析一样题目给出的测试数据：

input：

2 <news> <title>default title</title> <content width="1000px"></content> </news> 1 <html><h3 id="header"></h3> <div id="content"></div></html> 2 header-title content-content <html><h3 id="header" class="style1"> this is a test</h3> <div id="content" class="style2"> this is content<br/> <pre>var x = 1111;</pre> </div> </html> <xxx> <title>default title</title> </xxx> 1 <html><h3 id="header"></h3></html> 1 header-title <html><h3 id="tmp">xxxx</h3></html>

output：

Case #1: <news> <title> this is a test</title> <content width="1000px"> this is content<br/> <pre>var x = 1111;</pre> </content> </news>

Case #2: Can't Identify

输入分析：

蓝色部分规定了输出格式，绿色部分规定了html文件的结构，红色部分为m种映射，紫色部分是需要提取信息的文本。

拿case 1 来看，<html><h3 id="header" class="style1"> this is a test</h3> <div id="content" class="style2"> this is content<br/> <pre>var x = 1111;</pre> </div> </html>   从中我们可以得出的信息为 标签h3,它的属性id的值为header,上述header的映射为title,所以用标签为title 的格式输出“<title> this is a test</title>”  接下来是div标签，它的属性id的值为content,上述content的映射为content，所以用标签为content的格式输出“ <content width="1000px"> this is content<br/> <pre>var x = 1111;</pre> </content>”，在前后分别加上<news></news>;

case 2:找不到属性值为tmp的映射，所以不能定义。

题意，样例都说完了，下面来看看代码吧（不是本人写的）：

 #include<iostream>

 #include<cstdio>

 #include<string.h>

 using namespace std;

 const int N=;

 const int M=;

 char html[M][N],stored[M][N],sta1[N][M];

 char mapping[M][M][][M];//存储映射情况

 int mapNum[M],sta2[N];

 void getHtmlFormat(int n)//读取html的格式

 {

     int j,i=,flag=;

     char beginTag[M];//存储开始标签

     char tag[M];//存储标签

     getchar();

     while()

     {

         html[n][i]=getchar();//读取第n个html

         if(html[n][i]=='<')

         {

             j=;

             while(html[n][++i]=getchar())

             {

                 if(html[n][i]=='/')

                     continue;

                 if(html[n][i]==' '||html[n][i]=='>')

                     break;

                 tag[j++]=html[n][i];

             }

             tag[j]='\0';

             if(flag==)

             {

                 strcpy(beginTag,tag);

                 flag=;

             }

             else if(!strcmp(tag,beginTag))//表示读到结束标签，读取结束

             {

                 html[n][++i]='\0';

                 return;

             }

         }

         i++;

     }

 }

 void getMapping(int n,int m)

 {

     int i,j;

     char mp[];

     cin>>mp;

     for(i=; mp[i]!='-'; i++)

         mapping[n][m][][i]=mp[i];

     mapping[n][m][][i]='\0';

     for(j=,i++; i<strlen(mp); i++,j++)

         mapping[n][m][][j]=mp[i];

     mapping[n][m][][j]='\0';

 }

 void getTag(int n,int i,char tag[])

 {

     int j=;

     while()

     {

         i++;

         if(html[n][i]=='/')

             continue;

         if(html[n][i]==' '||html[n][i]=='>')

             break;

         tag[j++]=html[n][i];

     }

     tag[j]='\0';

 }

 int getId(int n,int i,char id[])

 {

     int j;

     id[]='\0';

     char tmp[M];

     while(html[n][i]==' ')

     {

         j=;

         while(html[n][++i]!='=')

             tmp[j++]=html[n][i];

         tmp[j]='\0';

         if(!strcmp(tmp,"id"))

         {

             i++;

             j=;

             while(html[n][++i]!='"')

                 id[j++]=html[n][i];

             id[j]='\0';

         }

         else

         {

             i++;

             while(html[n][++i]!='"');

         }

         i++;

     }

     return i;

 }

 void store(int n,int i,int j,char tag[])

 {

     stored[j][]='\0';

     int k,y=,flag=,len=strlen(tag);

     for(i++;; i++)

     {

         k=;

         if(html[n][i]=='<')

             for(; k<len; k++)

                 if(tag[k]!=html[n][i++k])break;

         if(k==len)flag++;

         k=;

         if(html[n][i]=='<'&&html[n][i+]=='/')

             for(; k<len; k++)

                 if(tag[k]!=html[n][i++k])break;

         if(k==len)

         {

             if(!flag)

             {

                 stored[j][y]='\0';

                 return;

             }

             else flag--;

         }

         stored[j][y++]=html[n][i];

     }

 }

 bool isStructure(int n,int m)

 {

     int i,j,k,ii,flag=,top=-;

     char tag[M],id[M],tag2[M],id2[M];

     int len1=strlen(html[n]);

     for(i=k=; i<len1;)

     {

         ii=i;

         while(html[n][i]==' '||html[n][i]=='\n')

             i++;

         while(html[m][k]!='<')

             k++;

         getTag(n,i,tag);//获取标签

         getTag(m,k,tag2);

         if(strcmp(tag,tag2)||html[n][i+]!=html[m][k+])

         {

             if(!strcmp(tag,tag2))

                 sta2[top]++;

             if(!flag)

             {

                 return false;

             }

             while(html[m][k]!='>')

                 k++;

             i=ii;

             continue;

         }

         if(html[n][i+]=='/') //</xx>

         {

             if(!sta2[top])

             {

                 i+=strlen(tag)+;

                 flag--;

             }

             else sta2[top]--;

             k+=strlen(tag)+;

         }

         else  //<xx>或者<xx/>

         {

             i+=strlen(tag)+;

             k+=strlen(tag2)+;

             if(html[n][i]==' ') //有id

             {

                 if(html[m][k]!=' ')

                 {

                     if(!flag)

                     {

                         return false;

                     }

                     while(html[m][k]!='>')k++;

                     i=ii;

                     continue;

                 }

                 i=getId(n,i,id);

                 k=getId(m,k,id2);

                 if(strcmp(id,id2))

                 {

                     if(!flag)

                     {

                         return false;

                     }

                     while(html[m][k]!='>')k++;

                     i=ii;

                     continue;

                 }

             }

             for(j=; j<mapNum[n]; j++)

                 if(!strcmp(id,mapping[n][j][]))

                     break;

             if(html[n][i]=='/') //<xx/>

             {

                 i+=;

                 k+=;

             }

             else  //<xx>

             {

                 if(j!=mapNum[n]) //需映射的id

                 {

                     strcpy(sta1[++top],tag);

                     flag++;

                     sta2[top]=;

                     for(j=; j<mapNum[n]; j++)

                         if(!strcmp(id,mapping[n][j][]))

                             store(m,k,j,tag);

                 }

                 i++;

                 k++;

             }

         }

     }

     return true;

 }

 void output(int n)

 {

     int i,j,k,ii;

     char tag[M];

     int len1=strlen(html[]);

     for(i=; i<len1;)

     {

         while(i<len1&&html[][i]!='<')

             putchar(html[][i++]);

         if(i==len1)break;

         getTag(,i,tag);

         for(j=; j<mapNum[n]; j++)

             if(!strcmp(tag,mapping[n][j][]))

                 break;

         if(j==mapNum[n])

         {

             putchar(html[][i++]);

             continue;

         }

         else

         {

             int len=strlen(tag);

             ii=i;

             for(i+=len+;; i++)

             {

                 k=;

                 if(html[][i]=='<'&&html[][i+]=='/')

                     for(; k<len; k++)

                         if(tag[k]!=html[][i++k])

                             break;

                 if(k==len)

                     break;

             }

             while(html[][ii]!='>')

                 putchar(html[][ii++]);

             putchar(html[][ii++]);

             cout<<stored[j];

             while(html[][i]!='>')

                 putchar(html[][i++]);

             putchar(html[][i++]);

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int cases=;cases<=T;cases++)

     {

         int i,j,n,m;

         getHtmlFormat();

         scanf("%d",&n);

         for(i=; i<=n; i++)

         {

             getHtmlFormat(i);

             scanf("%d",&mapNum[i]);

             for(j=; j<mapNum[i]; j++)

                 getMapping(i,j);

         }

         getHtmlFormat(n+);// 待处理的html文件

         printf("Case #%d:\n",cases);

         for(i=; i<=n; i++)

             if(isStructure(i,n+))

             {

                 output(i);

                 break;

             }

         if(i==n+)

             printf("Can't Identify");

         putchar('\n');

     }

     return ;

 }

HDU 4868 Information Extraction(2014 多校联合第一场 H)的更多相关文章

  1. hdu 4869 Turn the pokers （2014多校联合第一场 I）

    Turn the pokers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  2. hdu 4865 Peter&amp&semi;&num;39&semi;s Hobby（2014 多校联合第一场 E）

    Peter's Hobby Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) To ...

  3. HDU 4870 Rating &lpar;2014 多校联合第一场 J&rpar;&lpar;概率&rpar;

    题意: 一个人有两个TC的账号,一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛,每次比赛有p的概率+1分,有1-p的概率-2分,当然如果本身是<=2分的 ...

  4. HDU 4869 Turn the pokers &lpar;2014 多校联合第一场 I&rpar;

    HDOJ--4869--Turn the pokers[组合数学+快速幂] 题意:有m张扑克,开始时全部正面朝下,你可以翻n次牌,每次可以翻xi张,翻拍规则就是正面朝下变背面朝下,反之亦然,问经过n次 ...

  5. HDU 4865 Peter&&num;39&semi;s Hobby&lpar;2014 多校联合第一场 E&rpar;&lpar;概率dp&rpar;

    题意:已知昨天天气与今天天气状况的概率关系(wePro),和今天天气状态和叶子湿度的概率关系(lePro)第一天为sunny 概率为 0.63,cloudy 概率 0.17,rainny 概率 0.2 ...

  6. hdu 5288&vert;&vert;2015多校联合第一场1001题

    pid=5288">http://acm.hdu.edu.cn/showproblem.php?pid=5288 Problem Description OO has got a ar ...

  7. HDU 5724 Chess &lpar;状态压缩sg函数博弈&rpar; 2016杭电多校联合第一场

    题目:传送门. 题意:有n行,每行最多20个棋子,对于一个棋子来说,如果他右面没有棋子,可以移动到他右面:如果有棋子,就跳过这些棋子移动到后面的空格,不能移动的人输. 题解:状态压缩博弈,对于一行2^ ...

  8. HDU 5289 Assignment（多校联合第一场1002）

    Assignment Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total ...

  9. hdu5294&vert;&vert;2015多校联合第一场1007 最短路&plus;最大流

    http://acm.hdu.edu.cn/showproblem.php? pid=5294 Problem Description Innocent Wu follows Dumb Zhang i ...

随机推荐

  1. C&num; 模板列在绑定的时候取文本值

    查了很多资料,都说模板列无法取文本值, 需要使用FindControl, 对于列数很多的情况就要命了, 使用以下方式, 可以循环列的索引,获取到文本值 前台 <asp:TemplateField ...

  2. 蚂蚁金服寒泉子：JVM源码分析之临门一脚的OutOfMemoryError完全解读

    ➠更多技术干货请戳:听云博客 概述 OutOfMemoryError,说的是java.lang.OutOfMemoryError,是JDK里自带的异常,顾名思义,说的就是内存溢出,当我们的系统内存严重 ...

  3. jquery的height&lpar;&rpar;和javascript的height总结，js获取屏幕高度

    jquery的height()和javascript的height总结,js获取屏幕高度 2014年9月18日 15048次浏览 引子 今天是九一八事变八十三周年,大家勿忘国耻!加油学习!经济和技术等 ...

  4. frameset框架下，刷新整个页面

    <a href="index.jsp" target="_parent">  index.jsp主frameset页面

  5. Services学习（一）

    对于需要长期运行,例如播放音乐.长期和服务器的连接,即使已不是屏幕当前的activity仍需要运行的情况,采用服务方式.服务将通过API触发启动或者通过IPC(Interprocess Communi ...

  6. Styling FX Buttons with CSS

    http://fxexperience.com/2011/12/styling-fx-buttons-with-css/ ——————————————————————————————————————— ...

  7. Django admin进阶

    1. ModelAdmin.inlines 将有外键的子类包含进视图 ,实例: class Author(models.Model): name = models.CharField(max_leng ...

  8. Web学习

    http://book.2cto.com/201309/31936.html http://alvinalexander.com/ 查看锁表进程SQL语句1: select sess.sid,     ...

  9. Tomcat 80 端口被占，解决方案

    Windows 平台下Tomcat启动不起,显示 SEVERE: Failed to initialize end point associated with ProtocolHandler [&qu ...

  10. java 文件操作 读取字节级数据（读取）

    package com.swust; import java.io.*; /* * 功能:按照双精度浮点型.整型.布尔型.字符型.和字符串型的顺序从名为sample.dat文件读取数据 * 分析:用F ...

相关文章