201709-3 JSON查询

原题链接：201709-3 JSON查询

问题描述

　　JSON (JavaScript Object Notation) 是一种轻量级的数据交换格式，可以用来描述半结构化的数据。JSON 格式中的基本单元是值 (value)，出于简化的目的本题只涉及 2 种类型的值：

• 字符串 (string)：字符串是由双引号 " 括起来的一组字符（可以为空）。如果字符串的内容中出现双引号 "，在双引号前面加反斜杠，也就是用 " 表示；如果出现反斜杠 \，则用两个反斜杠 \ 表示。反斜杠后面不能出现 " 和 \ 以外的字符。例如：""、"hello"、""\"。
• 对象 (object)：对象是一组键值对的无序集合（可以为空）。键值对表示对象的属性，键是属性名，值是属性的内容。对象以左花括号 { 开始，右花括号 } 结束，键值对之间以逗号 , 分隔。一个键值对的键和值之间以冒号 : 分隔。键必须是字符串，同一个对象所有键值对的键必须两两都不相同；值可以是字符串，也可以是另一个对象。例如：{}、{"foo": "bar"}、{"Mon": "weekday", "Tue": "weekday", "Sun": "weekend"}。
  除了字符串内部的位置，其他位置都可以插入一个或多个空格使得 JSON 的呈现更加美观，也可以在一些地方换行，不会影响所表示的数据内容。例如，上面举例的最后一个 JSON 数据也可以写成如下形式。
  　　　　{
  　　　　"Mon": "weekday",
  　　　　"Tue": "weekday",
  　　　　"Sun": "weekend"
  　　　　}
  　　　　给出一个 JSON 格式描述的数据，以及若干查询，编程返回这些查询的结果。

输入格式

　　第一行是两个正整数 n 和 m，分别表示 JSON 数据的行数和查询的个数。
　　接下来 n 行，描述一个 JSON 数据，保证输入是一个合法的 JSON 对象。
　　接下来 m 行，每行描述一个查询。给出要查询的属性名，要求返回对应属性的内容。需要支持多层查询，各层的属性名之间用小数点 . 连接。保证查询的格式都是合法的。

输出格式

　　对于输入的每一个查询，按顺序输出查询结果，每个结果占一行。
　　如果查询结果是一个字符串，则输出 STRING <string>，其中 <string> 是字符串的值，中间用一个空格分隔。
　　如果查询结果是一个对象，则输出 OBJECT，不需要输出对象的内容。
　　如果查询结果不存在，则输出 NOTEXIST。

样例输入

10 5
{
"firstName": "John",
"lastName": "Smith",
"address": {
"streetAddress": "2ndStreet",
"city": "NewYork",
"state": "NY"
},
"esc\\aped": "\"hello\""
}
firstName
address
address.city
address.postal
esc\aped

样例输出

STRING John
OBJECT
STRING NewYork
NOTEXIST
STRING "hello"

评测用例规模与约定

　　n ≤ 100，每行不超过 80 个字符。
　　m ≤ 100，每个查询的长度不超过 80 个字符。
　　字符串中的字符均为 ASCII 码 33-126 的可打印字符，不会出现空格。所有字符串都不是空串。
　　所有作为键的字符串不会包含小数点 .。查询时键的大小写敏感。
　　50%的评测用例输入的对象只有 1 层结构，80%的评测用例输入的对象结构层数不超过 2 层。举例来说，{"a": "b"} 是一层结构的对象，{"a": {"b": "c"}} 是二层结构的对象，以此类推。

题解

• 因为键值不同，所以很容易想到使用map，但值却有两种可能：字符串或者对象，因此需要将字符串或者对象合成为一个数据结构，设定一个鉴别变量type区分map的值为string还是对象，对象的值为对象，是一个迭代定义。
• 题意就是给一个JSON字符串，JSON字符串就是一个键值对的集合（对象），键一定是string，而值可能是string也可能也是一个对象。所以定义一个对象结构体，根据type值区分其值是对象还是字符串。一开始就是一个对象，然后搜索整个JSON字符串，当搜索到双引号时说明找到一个键值对，然后处理这个键值对，然后将这个键值对加入这个对象的map中，若值为对象则再处理。
• 查询则是使用vector存储需要查询的键，然后遍历键，当需要查询键但不是对象时或者没查到键则输出NOEXIST，处理完所有键之后看当前对象是字符串还是对象从而输出。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct OBJ{
    int type;
    string str;
    OBJ(){}
    OBJ(string _str){
        type=1;
        str=_str;
    }
    map<string,OBJ> obj;
};

string work_str(string& str,int& k){
    k++;
    string res;
    while(str[k]!='\"'){
        if(str[k]=='\\'){
            res+=str[k+1];  //取后面的字符
            k+=2;   //跳过转义字符和后面的字符
        }
        else res+=str[k++];
    }
    k++;    //过滤双引号
    return res;
}
OBJ work_obj(string& str,int& k);
void work_kv(OBJ& obj,string& str,int& k){
    auto key=work_str(str,k);
    while(k<str.size()&&str[k]!='\"'&&str[k]!='{')++k;
    if(str[k]=='{')obj.obj[key]=work_obj(str,k);
    else obj.obj[key]=work_str(str,k);
}

OBJ work_obj(string& str,int& k){
    OBJ obj;
    obj.type==2;
    while(k<str.size()&&str[k]!='{')k++;
    k++;
    while(str[k]!='}'){
        if(str[k]=='\"')work_kv(obj,str,k);
        else k++;
    }
    k++;    //过滤掉 }
    return obj;
}

void query(OBJ obj,vector<string>& q){
    for(auto& i:q){
        if( obj.type==1 || obj.obj.count(i)==0){ //obj为1说明不是对象，但却是查询对象，说明错误。不是1但没有这个键时也是错误
            cout << "NOTEXIST" << endl;
            return;
        }
        OBJ t=obj.obj[i];   //不能直接obj=obj.obj[i]
        obj=t;
    }
    if(obj.type==1)cout << "STRING " << obj.str << endl;
    else cout << "OBJECT" << endl; 
}

int main(){
    int n,m;
    cin >> n >> m;
    string str="";
    cin.ignore();
    while(n--){
        string t;
        getline(cin,t);
        str+=t;
    }
    int k=0;
    OBJ obj=work_obj(str,k);
    while(m--){
        getline(cin,str);
        int u=0,v=0;
        vector<string> q;
        while(u<str.size()&&v<str.size()){
            while(u<str.size()&&str[u]!='.')u++;
            q.push_back(str.substr(v,u-v));
            u++;
            v=u;
        }
        query(obj,q);
    }
    return 0;
}

---

201703-2 学生排队

问题描述

　　体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。
　　例如，下面给出了一组移动的例子，例子中学生的人数为8人。
　　0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；
　　1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；
　　2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；
　　3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
　　小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
　　请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。

输入格式

　　输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。
　　第二行包含一个整数m，表示调整的次数。
　　接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。

输出格式

　　输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。

样例输入

8
3
3 2
8 -3
3 -2

样例输出

1 2 4 3 5 8 6 7

评测用例规模与约定

　　对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。

题解

思路是使用list容器，首先使用迭代器for循环找到编号为指定编号的迭代器，然后删除迭代器所指定的元素，并得到下一个元素的迭代器，然后根据step的正负移动迭代器，再进行插入。

#include <iostream>222
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

int main()
{
    int n;
    cin >> n;
    list<int> stu(n);
    int id=0;
    for(auto &i:stu){
        i=++id;
    }

    int m;
    cin >> m;

    while(m--){
        int idx,step;
        cin >> idx >> step;
        list<int>::iterator iter;
        for(iter=stu.begin();iter!=stu.end();++iter){
            if(*iter==idx)
                break;
        }
        if (iter!=stu.end()){
            iter=stu.erase(iter);   //删除idx，并返回后一个迭代器
            if(step>0){
                for(int i=0;i<step;++i){
                    iter++;
                }
            }
            else{
                step=-1*step;
                for(int i=0;i<step;++i){
                    iter--;
                }
            }
            stu.insert(iter,idx);
        }
    }

    for(auto &i:stu){
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

 

201709-2 公共钥匙盒

问题描述

　　有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。
　　钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。
　　每次取钥匙的时候，老师们都会找到自己所需要的钥匙将其取走，而不会移动其他钥匙。每次还钥匙的时候，还钥匙的老师会找到最左边的空的挂钩，将钥匙挂在这个挂钩上。如果有多位老师还钥匙，则他们按钥匙编号从小到大的顺序还。如果同一时刻既有老师还钥匙又有老师取钥匙，则老师们会先将钥匙全还回去再取出。
　　今天开始的时候钥匙是按编号从小到大的顺序放在钥匙盒里的。有K位老师要上课，给出每位老师所需要的钥匙、开始上课的时间和上课的时长，假设下课时间就是还钥匙时间，请问最终钥匙盒里面钥匙的顺序是怎样的？

输入格式

　　输入的第一行包含两个整数N, K。
　　接下来K行，每行三个整数w, s, c，分别表示一位老师要使用的钥匙编号、开始上课的时间和上课的时长。可能有多位老师使用同一把钥匙，但是老师使用钥匙的时间不会重叠。
　　保证输入数据满足输入格式，你不用检查数据合法性。

输出格式

　　输出一行，包含N个整数，相邻整数间用一个空格分隔，依次表示每个挂钩上挂的钥匙编号。

样例输入

5 2
4 3 3
2 2 7

样例输出

1 4 3 2 5

样例说明

　　第一位老师从时刻3开始使用4号教室的钥匙，使用3单位时间，所以在时刻6还钥匙。第二位老师从时刻2开始使用钥匙，使用7单位时间，所以在时刻9还钥匙。
　　每个关键时刻后的钥匙状态如下（X表示空）：
　　时刻2后为1X345；
　　时刻3后为1X3X5；
　　时刻6后为143X5；
　　时刻9后为14325。

样例输入

5 7
1 1 14
3 3 12
1 15 12
2 7 20
3 18 12
4 21 19
5 30 9

样例输出

1 2 3 5 4

评测用例规模与约定

　　对于30%的评测用例，1 ≤ N, K ≤ 10, 1 ≤ w ≤ N, 1 ≤ s, c ≤ 30；
　　对于60%的评测用例，1 ≤ N, K ≤ 50，1 ≤ w ≤ N，1 ≤ s ≤ 300，1 ≤ c ≤ 50；
　　对于所有评测用例，1 ≤ N, K ≤ 1000，1 ≤ w ≤ N，1 ≤ s ≤ 10000，1 ≤ c ≤ 100。

题解

思路是使用vector存储钥匙箱，使用一个优先队列，优先级为时间，一个人会入队两次，一次为拿钥匙，一次为取钥匙，为了区分，设置一个变量status。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

//思路：使用vector存储钥匙箱，使用一个优先队列，优先级为时间，一个人会入队两次，一次为拿钥匙，一次为取钥匙，为了区分，设置一个变量

struct get_put_key{
    int w;
    int ktime;
    int status;     //0代表拿，1代表放
    bool operator<(const get_put_key &c) const {
        //当时间小于则放在前面，若相等放放在前面，若都相等则编号小的放前面
        if(ktime!=c.ktime)
            return ktime > c.ktime;
        if(status!=c.status) return status < c.status;
        return w > c.w;
    }
};

int main()
{
    int N,K;
    cin >> N >> K;
    vector<int> W(N);
    int count=0;
    for(auto &i:W){
        i=++count;
    }

    priority_queue<get_put_key> T;
    for(int i=0;i<K;++i){
        int w,s,c;
        cin >> w >> s >> c;
        get_put_key t1,t2;
        t1={w,s,0};
        t2={w,s+c,1};
        T.push(t1);
        T.push(t2);
    }

    while(!T.empty()){
        //有2K个操作
        get_put_key t=T.top();
        if(t.status==0){    //拿钥匙
            auto it=find(W.begin(),W.end(),t.w);
            if(it!=W.end()) *it=0;
        }
        else{
            //放钥匙
            auto it=find(W.begin(),W.end(),0);
            if(it!=W.end()) *it=t.w;
        }
        T.pop();
    }

    for(auto &i:W){
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

---

201703-3 Markdown（课设4）

问题描述

Markdown 是一种很流行的轻量级标记语言（lightweight markup language），广泛用于撰写带格式的文档。例如以下这段文本就是用 Markdown 的语法写成的：

这些用 Markdown 写成的文本，尽管本身是纯文本格式，然而读者可以很容易地看出它的文档结构。同时，还有很多工具可以自动把 Markdown 文本转换成 HTML 甚至 Word、PDF 等格式，取得更好的排版效果。例如上面这段文本通过转化得到的 HTML 代码如下所示：

本题要求由你来编写一个 Markdown 的转换工具，完成 Markdown 文本到 HTML 代码的转换工作。简化起见，本题定义的 Markdown 语法规则和转换规则描述如下：

• 区块：区块是文档的顶级结构。本题的 Markdown 语法有 3 种区块格式。在输入中，相邻两个区块之间用一个或多个空行分隔。输出时删除所有分隔区块的空行。

  • 段落：一般情况下，连续多行输入构成一个段落。段落的转换规则是在段落的第一行行首插入 <p>，在最后一行行末插入 </p>。
  • 标题：每个标题区块只有一行，由若干个 # 开头，接着一个或多个空格，然后是标题内容，直到行末。# 的个数决定了标题的等级。转换时，# Heading 转换为 <h1>Heading</h1>，## Heading 转换为 <h2>Heading</h2>，以此类推。标题等级最深为 6。
  • 无序列表：无序列表由若干行组成，每行由 * 开头，接着一个或多个空格，然后是列表项目的文字，直到行末。转换时，在最开始插入一行 <ul>，最后插入一行 </ul>；对于每行，* Item 转换为 <li>Item</li>。本题中的无序列表只有一层，不会出现缩进的情况。

• 行内：对于区块中的内容，有以下两种行内结构。

  • 强调：_Text_ 转换为 <em>Text</em>。强调不会出现嵌套，每行中 _ 的个数一定是偶数，且不会连续相邻。注意 _Text_ 的前后不一定是空格字符。
  • 超级链接：[Text](Link) 转换为 <a href="Link">Text</a>。超级链接和强调可以相互嵌套，但每种格式不会超过一层。

输入格式

输入由若干行组成，表示一个用本题规定的 Markdown 语法撰写的文档。

输出格式

输出由若干行组成，表示输入的 Markdown 文档转换成产生的 HTML 代码。

样例输入

Hello
Hello, world!

## 样例输出

<h1>Hello</h1>
<p>Hello, world!</p>

评测用例规模与约定

本题的测试点满足以下条件：

• 本题每个测试点的输入数据所包含的行数都不超过 100，每行字符的个数（包括行末换行符）都不超过 100。
• 除了换行符之外，所有字符都是 ASCII 码 32 至 126 的可打印字符。
• 每行行首和行末都不会出现空格字符。
• 输入数据除了 Markdown 语法所需，内容中不会出现 #、*、_、[、]、(、)、<、>、& 这些字符。
• 所有测试点均符合题目所规定的 Markdown 语法，你的程序不需要考虑语法错误的情况。

每个测试点包含的语法规则如下表所示，其中“√”表示包含，“×”表示不包含。

测试点编号	段落	标题	无序列表	强调	超级链接
1	√	×	×	×	×
2	√	√	×	×	×
3	√	×	√	×	×
4	√	×	×	√	×
5	√	×	×	×	√
6	√	√	√	×	×
7	√	×	×	√	√
8	√	√	×	√	×
9	√	×	√	×	√
10	√	√	√	√	√

提示

由于本题要将输入数据当做一个文本文件来处理，要逐行读取直到文件结束，C/C++、Java 语言的用户可以参考以下代码片段来读取输入内容。

题解

思路1：（得分10-40）

• 算法：
• 1.判断输入是否为空行
• 2.判断区块类型，按类型替换
• 3.循环查找"_"和"["并替换
• 4.按类型插入结尾
• 5.循环2-4，直到处理完所有

思路2：（得分（70-90））

• 算法：
• 1.将输入的每一行字符串存入vector中
• 2.处理第i行，判断区块类型，按类型替换
• 3.循环查找"_"和"["并替换
• 4.按类型插入结尾
• 5.循环2-4，直到处理完所有

思路3：（得分90）

• 算法：
• 1.将输入的每一行字符串存入vector中
• 2.处理第i行，判断区块类型，使用正则表达式进行提取文本
• 3.使用正则循环查找"_"和"["并替换文本
• 4.按类型插入结尾
• 5.循环2-4，直到处理完所有

思路4：（得分100）

• 算法：
• 1.将输入的每一行字符串存入vector中
• 2.处理第i行，判断区块类型，按类型替换
• 3.使用正则循环查找"_"和"["并替换文本
• 4.按类型插入结尾
• 5.循环2-4，直到处理完所有

//10分
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

string& replaceEm(string& str,int index_start){
    int index_end=str.find("_",index_start+1);
    string sub=str.substr(index_start+1,index_end-index_start-1);
    str.replace(index_start,index_end-index_start+1,"<em>"+sub+"</em>");
    return str;
}

string& replaceUrl(string& str,int index_start){
    int index_end_text=str.find("]",index_start);
    string text=str.substr(index_start+1,index_end_text-index_start-1);

    int index_start_url=str.find("(",index_end_text);
    int index_end_url=str.find(")",index_start_url);
    string url=str.substr(index_start_url+1,index_end_url-index_start_url-1);

    str.replace(index_start,index_end_url-index_start+1,"<a href=\""+url+"\">"+text+"</a>");
    return str;
}

void handle(string& line){
    int index=0;
    while((index=line.find("_",index))!=string::npos){
        replaceEm(line,index);
    }
    index=0;
    while((index=line.find("[",index))!=string::npos){
        replaceUrl(line,index);
    }
}

int main()
{
    string lines,line;
    bool is_start=false;    //判断是否无序列表是否开始，也可以判断是否需要结尾
    bool is_p_start=false;
    while(getline(cin,lines)){
        line=lines;
        if(lines.size()==0){
            if(is_start){
                line.insert(0,"/n</ul>");
                is_start=false;
            }
            if(is_p_start){
                line.insert(0,"</p>\n");
                is_p_start=false;
            }
            continue;
        }
        if(line[0]=='#'){
            int size=1;
            while(line[size]=='#') size++;
            int count=size;
            while(line[size]==' ') size++;
            line.replace(0,size,"<h"+to_string(count)+">");
            line+="</h"+to_string(count)+">";
            if(is_start){
                line.insert(0,"/n</ul>");
                is_start=false;
            }
            if(is_p_start){
                line.insert(0,"</p>\n");
                is_p_start=false;
            }
            cout << line << endl;
        }
        else if(line[0]=='*'){
            int size=1;
            while(line[size]==' ') size++;
            if(!is_start)
                line.replace(0,size,"<ul>\n<li>");
            else   
                line.replace(0,size,"<li>");
            is_start=true;
            if(is_p_start){
                line.insert(0,"</p>\n");
                is_p_start=false;
            }

            //处理行内语法
            handle(line);

            line+="</li>\n";
            cout << line;
        }
        else{
            if(!is_p_start){
                line.insert(0,"<p>");
                is_p_start=true;
            }
            else{
                line.insert(0,"\n");
            }

            if(is_start){
                line.insert(0,"</ul>\n");
                is_start=false;
            }
            //处理行内语法
            handle(line);

            cout << line;
        }
    }
    line="";
    if(is_start){
        line.insert(0,"/n</ul>");
        is_start=false;
    }
    if(is_p_start){
        line.insert(0,"</p>\n");
        is_p_start=false;
    }
    cout << line;
    return 0;
}

这里存在的问题有很多，首先就是题意的问题，标题也会有行内语法、无序列表的逻辑错误等，另外代码的逻辑过于繁琐，没有充分利用getline而导致需要很多的信号来进行处理上一行的问题。此外，直接在输入上进行修改等过于繁琐，insert，replace等需要的参数过多，需要计算才能准确得到，所以导致代码臃肿。

//70分
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

/**
 * 5中格式处理：markdown语法有个特点就是按行处理
 * 1. 段落：
 * 2. 标题：行首有"#"等格式，记得去除后面的空格
 * 3. 无序列表：行首"*"开头，记得去除后面的空格
 * 
 * 4. 强调：用"_"包裹
 * 5. 超链接："[test](link)"形式
 * 
 * 识别处理：
 * 对于每一行首先识别区块，即识别行首，确定是段落、标题还是无序列表
 * 然后识别每一行中的行内语法，即识别"-","["
 * 
 * 转化处理：
 * 对于区块：识别到后直接替换，然后识别行内语法，最后添加结尾
 * 对于行内语法：写两个函数单独处理，然后返回引用
 * 

 */

class markdown{
    friend void handle(string&);
public:
    string line;
    bool is_start=false;    //判断是否无序列表是否开始，也可以判断是否需要结尾
    bool is_p_start=false;

    static void markdownToHtml(markdown& input);               //对外接口

private:
    static string& replaceEm(string& str,int index_start);     //替换加粗
    static string& replaceUrl(string& str,int index_start);    //替换超链接
};

string& markdown::replaceEm(string& str,int index_start){
    int index_end=str.find("_",index_start+1);
    string sub=str.substr(index_start+1,index_end-index_start-1);
    str.replace(index_start,index_end-index_start+1,"<em>"+sub+"</em>");
    return str;
}

string& markdown::replaceUrl(string& str,int index_start){
    int index_end_text=str.find("]",index_start);
    string text=str.substr(index_start+1,index_end_text-index_start-1);

    int index_start_url=str.find("(",index_end_text);
    int index_end_url=str.find(")",index_start_url);
    string url=str.substr(index_start_url+1,index_end_url-index_start_url-1);

    str.replace(index_start,index_end_url-index_start+1,"<a href=\""+url+"\">"+text+"</a>");
    return str;
}

void handle(string& line){
    int index=0;
    while((index=line.find("_",index))!=string::npos){
        markdown::replaceEm(line,index);
    }
    index=0;
    while((index=line.find("[",index))!=string::npos){
        markdown::replaceUrl(line,index);
    }
}

void markdownToHtml(markdown& input){
    if(input.line.size()==0){
        return;
    }
    if(input.line[0]=='#'){
        int size=1;
        while(input.line[size]=='#') size++;
        int count=size;
        while(input.line[size]==' ') size++;
        input.line.replace(0,size,"<h"+to_string(count)+">");
        if(count>6){
            count=6;
        }
        input.line+="</h"+to_string(count)+">";
        if(input.is_start){
            input.line.insert(0,"</ul>");
            input.is_start=false;
        }

        cout << input.line << endl;
    }
    else if(input.line[0]=='*'){
        int size=1;
        while(input.line[size]==' ') size++;
        if(!input.is_start)
            input.line.replace(0,size,"<ul>\n<li>");
        else   
            input.line.replace(0,size,"<li>");
        input.is_start=true;

        //处理行内语法
        handle(input.line);

        input.line+="</li>\n";
        cout << input.line;
    }
    else{
        input.line.insert(0,"<p>");

        if(input.is_start){
            input.line.insert(0,"</ul>\n");
            input.is_start=false;
        }
        //处理行内语法
        handle(input.line);

        input.line+="</p>\n";
        cout << input.line;
    }
}

int main()
{
    markdown input;
    while(getline(cin,input.line)){
        markdownToHtml(input);
    }
    input.line="";
    if(input.is_start){
        input.line.insert(0,"</ul>");
        input.is_start=false;
    }
    cout << input.line;
    return 0;
}

这里处理了部分题目误解问题，但依旧存在嵌套问题。除此之外，代码还是过于臃肿，依旧在原输入上进行修改。

//80分，标题增加了处理行内语法功能
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

class markdown{
    friend void handle(string&);
public:
    string line;
    bool is_start=false;    //判断是否无序列表是否开始，也可以判断是否需要结尾
    bool is_p_start=false;

    static void markdownToHtml(markdown& input);               //对外接口

private:
    static string& replaceEm(string& str,int index_start);     //替换加粗
    static string& replaceUrl(string& str,int index_start);    //替换超链接
};

string& markdown::replaceEm(string& str,int index_start){
    int index_end=str.find("_",index_start+1);
    string sub=str.substr(index_start+1,index_end-index_start-1);
    str.replace(index_start,index_end-index_start+1,"<em>"+sub+"</em>");
    return str;
}

string& markdown::replaceUrl(string& str,int index_start){
    int index_end_text=str.find("]",index_start);
    string text=str.substr(index_start+1,index_end_text-index_start-1);

    int index_start_url=str.find("(",index_end_text);
    int index_end_url=str.find(")",index_start_url);
    string url=str.substr(index_start_url+1,index_end_url-index_start_url-1);

    str.replace(index_start,index_end_url-index_start+1,"<a href=\""+url+"\">"+text+"</a>");
    return str;
}

void handle(string& line){
    int index=0;
    while((index=line.find("_",index))!=string::npos){
        markdown::replaceEm(line,index);
    }
    index=0;
    while((index=line.find("[",index))!=string::npos){
        markdown::replaceUrl(line,index);
    }
}

void markdownToHtml(markdown& input){
    if(input.line.size()==0){
        return;
    }
    if(input.line[0]=='#'){
        int size=1;
        while(input.line[size]=='#') size++;
        int count=size;
        while(input.line[size]==' ') size++;
        if(count>6){
            count=6;
        }
        input.line.replace(0,size,"<h"+to_string(count)+">");
        input.line+="</h"+to_string(count)+">";
        handle(input.line);
        if(input.is_start){
            input.line.insert(0,"</ul>\n");
            input.is_start=false;
        }

        cout << input.line << endl;
    }
    else if(input.line[0]=='*'){
        int size=1;
        while(input.line[size]==' ') size++;
        if(!input.is_start)
            input.line.replace(0,size,"<ul>\n<li>");
        else   
            input.line.replace(0,size,"<li>");
        input.is_start=true;

        //处理行内语法
        handle(input.line);

        input.line+="</li>\n";
        cout << input.line;
    }
    else{
        input.line.insert(0,"<p>");

        if(input.is_start){
            input.line.insert(0,"</ul>\n");
            input.is_start=false;
        }
        //处理行内语法
        handle(input.line);

        input.line+="</p>\n";
        cout << input.line;
    }
}

int main()
{
    markdown input;
    while(getline(cin,input.line)){
        markdownToHtml(input);
    }
    input.line="";
    if(input.is_start){
        input.line.insert(0,"</ul>");
        input.is_start=false;
    }
    cout << input.line;
    return 0;
}

这里进一步的修改了题目误解问题，标题增加了处理行内语法功能。并且使用了类的形式修改了代码用于更好的理解代码，但还是上面的问题，代码过于臃肿，在原输入上进行修改。

//90分 回归c形式
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<string> lines;

int replaceEm(int pos,int index);
int replaceUrl(int pos,int index)
{
    int start=index+1;
    string text,url;
    for(index++;lines[pos][index]!=']';++index){
        if(lines[pos][index]=='_'){
            text+="<em>";
            while(lines[pos][++index]!='_'){
                text+=lines[pos][index];
            }
            text+="</em>";
        }else{
            text+=lines[pos][index];
        }
    }
    start=index+2;
    for(index+=2;lines[pos][index]!=')';++index)
        url+=lines[pos][index];
    printf("<a href=\"%s\">%s</a>",url.c_str(),text.c_str());
    return index;
}

int replaceEm(int pos,int index)
{
    printf("<em>");
    for(index++;index<lines[pos].size();++index){
        if(lines[pos][index]=='_'){
            break;
        }
        if(lines[pos][index]=='['){
            index=replaceUrl(pos,index);
            continue;
        }
        printf("%c",lines[pos][index]);
    }
    printf("</em>");
    return index;
}

void interior(int pos,int index)
{
    for(index;index<lines[pos].size();++index){
        if(lines[pos][index]=='_'){
            index=replaceEm(pos,index);
        }
        else if(lines[pos][index]=='['){
            index=replaceUrl(pos,index);
        }
        else{
            printf("%c",lines[pos][index]);
        }
    }
}

int markdownToHtml(int pos)
{
    if(lines[pos][0]=='#'){
        int count=1;
        while(lines[pos][count]=='#') count++;   //找出几级标题
        int size=count;
        while(lines[pos][size]==' ') size++;    //去除空格
        printf("<h%d>",count);

        //处理行内语法
        interior(pos,size);

        printf("</h%d>\n",count);
        return pos;
    }
    else if(lines[pos][0]=='*'){
        printf("<ul>\n");
        while(lines[pos][0]=='*'){
            int size=1;
            while(lines[pos][size]==' ') size++;
            printf("<li>");

            //处理行内语法
            interior(pos,size); 

            printf("</li>\n");
            pos++;
            if(pos>=lines.size())
                break;
        }

        printf("</ul>\n");
        return pos-1;
    }
    else{
        printf("<p>");
        interior(pos,0);
        printf("</p>\n");
        return pos;
    }
}

int main()
{
    //输入
    string line;
    while(getline(cin,line)){
        lines.push_back(line);
    }

    for(int i=0;i<lines.size();++i){
        if(lines[i].empty()) continue;  //去除空行
        i=markdownToHtml(i);
    }

    return 0;
}

这里进一步的修改了题目误解问题，强调与超链接嵌套问题得以处理，并理解了getline的作用，使用vector先存储输入，并且不是修改原输入而是提取原输入并且按形式输出，函数相互调用问题得以解决。

//90分正则表达式
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <regex>
using namespace std;

vector<string> lines;

void inner(string& str)
{
    regex pattern("(.*)_(.*)_(.*)");
    smatch strength;
    while(regex_search(str,strength,pattern))
        str=strength[1].str()+"<em>"+strength[2].str()+"</em>"+strength[3].str();

    regex p2("(.*)\\[(.*)\\]\\((.*)\\)(.*)");
    smatch res;
    while(regex_search(str,res,p2))
        str=res[1].str()+"<a href=\""+res[3].str()+"\">"+res[2].str()+"</a>"+res[4].str();
}

int markdownToHtml(int pos)
{
    if(lines[pos][0]=='#'){
        regex pattern("(#+ +)(.*)");
        smatch matches;
        regex_search(lines[pos],matches,pattern);
        int count=0;
        while(matches[1].str()[count]=='#')count++;
        string text="<h"+to_string(count)+">"+matches[2].str()+"</h"+to_string(count)+">";
        inner(text);
        cout << text << endl;
        return pos;
    }
    else if(lines[pos][0]=='*'){
        regex pattern("\\* +(.*)");
        smatch res;
        cout << "<ul>" << endl;
        while(lines[pos][0]=='*'){
            regex_search(lines[pos],res,pattern);
            string text="<li>"+res[1].str()+"</li>";
            inner(text);
            cout << text << endl;
            pos++;
            if(pos>=lines.size())
                break;
        }
        cout << "</ul>" << endl;
        return pos-1;
    }
    else{
        string text=lines[pos];
        inner(text);
        cout << "<p>" << text << "</p>" << endl;
        return pos;
    }
}

int main()
{
    string line;
    while(getline(cin,line))
        lines.push_back(line);

    for(int i=0;i<lines.size();++i){
        if(lines[i]=="")continue;
        i=markdownToHtml(i);
    }
    return 0;
}

由于找不到问题的解决，这里采用正则表达式进一步的修改代码，正则表达式将代码缩减至70行左右，代码可读性增强，但还是未解决问题。

//100分 换思路，处理每次输入，处理无序列表和段落时，直到下一行为空才结束，否则一直处理，行内使用正则表达式进行处理
#include <iostream>
#include <string>
#include <algorithm>
#include <regex>

using namespace std;

string inner(string str)
{
    regex pattern("(.*)_(.*)_(.*)");
    smatch strength;
    while(regex_search(str,strength,pattern))
        str=strength[1].str()+"<em>"+strength[2].str()+"</em>"+strength[3].str();

    regex p2("(.*)\\[(.*)\\]\\((.*)\\)(.*)");
    smatch res;
    while(regex_search(str,res,p2))
        str=res[1].str()+"<a href=\""+res[3].str()+"\">"+res[2].str()+"</a>"+res[4].str();

    return str;
} 
int main() {
    string s;
    while(getline(cin,s)) {
        if(s.size()>0) {
            if(s[0]=='#') {
                //处理标题
                int i=0;
                while(s[i]=='#')
                    i++;
                cout<<"<h"<<i<<">"<<inner(s.substr(i+1))<<"</h"<<i<<">"<<endl;

            } else if(s[0]=='*') {
                //处理无序列表
                cout<<"<ul>"<<endl;
                cout<<"<li>"<<inner(s.substr(2))<<"</li>"<<endl;
                while(getline(cin,s) && s.size()!=0)
                    cout<<"<li>"<<inner(s.substr(2))<<"</li>"<<endl;
                cout<<"</ul>"<<endl;

            } else {
                //处理段落
                cout<<"<p>"<<inner(s);
                while(getline(cin,s) && s.size()!=0)
                    cout<<endl<<inner(s);
                cout<<"</p>"<<endl;
            }
        }
    }
    return 0;
}

这里换思路，处理每次输入，处理无序列表和段落时，直到下一行为空才结束，否则一直处理，行内使用正则表达式进行处理。代码正确得分100。

201712-1 最小差值

问题描述

　　给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。

输入格式

　　输入第一行包含一个整数n。
　　第二行包含n个正整数，相邻整数之间使用一个空格分隔。

输出格式

　　输出一个整数，表示答案。

样例输入

5
1 5 4 8 20

样例输出

1

样例说明

　　相差最小的两个数是5和4，它们之间的差值是1。

样例输入

5
9 3 6 1 3

样例输出

0

样例说明

　　有两个相同的数3，它们之间的差值是0.

数据规模和约定

　　对于所有评测用例，2 ≤ n ≤ 1000，每个给定的整数都是不超过10000的正整数。

题解

• 第一次提交：思路为暴力破解，因为n<=1000,时间复杂度为O(n²)，可以通过

  /**
   * n个数找出差值最小的两个数
   * 输出绝对值
   * 思路：
   * 1.暴力破解：O(n^2),n<=1000
   * 2.先对数组进行排序，再相邻两个做差比较，时间复杂度O(n)
   */
  
  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <math.h>
  using namespace std;
  
  const int NaN=10010;
  
  int main()
  {
      int n;
      cin >> n;
      vector<int> arr(n);
      for(int i=0;i<n;++i){
          cin >> arr[i];
      }
      int sub_min=NaN;
      for(int i=0;i<n;++i){
          for(int j=i+1;j<n;++j){
              if(abs(arr[i]-arr[j])<sub_min){
                  sub_min=abs(arr[i]-arr[j]);
              }
          }
      }
      cout << sub_min;
      return 0;
  }
  

• 第二次提交：思路是先对数组进行排序，再相邻两个做差比较，时间复杂度O(nlogn)

  /**
   * n个数找出差值最小的两个数
   * 输出绝对值
   * 思路：
   * 1.暴力破解：O(n^2),n<=1000
   * 2.先对数组进行排序，再相邻两个做差比较，时间复杂度O(n)
   */
  
  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <math.h>
  using namespace std;
  
  const int NaN=10010;
  
  int main()
  {
      int n;
      cin >> n;
      vector<int> arr(n);
      for(int i=0;i<n;++i){
          cin >> arr[i];
      }
      sort(arr.begin(),arr.end());
      int sub_min=NaN;
      for(int i=0;i<n;++i){
          if(abs(arr[i+1]-arr[i])<sub_min){
              sub_min=abs(arr[i+1]-arr[i]);
          }
      }
      cout << sub_min;
      return 0;
  }
  

---

201712-2 游戏

问题描述

　　有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。
　　游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。
　　例如，当n=5, k=2时：
　　1号小朋友报数1；
　　2号小朋友报数2淘汰；
　　3号小朋友报数3；
　　4号小朋友报数4淘汰；
　　5号小朋友报数5；
　　1号小朋友报数6淘汰；
　　3号小朋友报数7；
　　5号小朋友报数8淘汰；
　　3号小朋友获胜。

　　给定n和k，请问最后获胜的小朋友编号为多少？

输入格式

　　输入一行，包括两个整数n和k，意义如题目所述。

输出格式

　　输出一行，包含一个整数，表示获胜的小朋友编号。

样例输入

5 2

样例输出

3

样例输入

7 3

样例输出

4

数据规模和约定

　　对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

题解

第一次提交：思路是使用一个键值对存储小朋友，键是编号，值是是否淘汰。一直遍历，知道淘汰个数为n-1为止。

#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

const int N = 1010;
int main()
{
    pair<int,bool> child[N];
    int fault=0,count=1;    //fault是淘汰个数，count是当前报数
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;++i){
        child[i-1].first=i;
        child[i-1].second=true;
    }
    int it=0;
    while(fault!=n-1){
        if(child[it].second){
            if(count%k==0 || count%10==k){
                child[it].second=false;
                ++fault;
            }
            ++count;
        }
        it=(it+1)%n;    //循环访问
    }
    for(int i=0;i<n;++i){
        if(child[i].second){
            cout << child[i].first;
            break;
        }
    }
}

第二次提交：第一次提交有个误区，任务vector存储删除需要记录编号，忘记是显示存储其编号，删除完后，其值就是编号。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> child;
    for(int i=1;i<=n;++i){
        child.push_back(i);  //初始化编号
    }

    int pos=0;
    for(int count=1;child.size()>1;++count){
        if(count%k==0 || count%10==k){
            child.erase(child.begin()+pos);
            --pos;          //删除一个元素后，移动指针重新指向当前元素而不后移
        }
        pos=(pos+1)%child.size();
    }
    cout << child[0]<< endl;
    return 0;
}

---

201612-2 工资计算

问题描述

　　小明的公司每个月给小明发工资，而小明拿到的工资为交完个人所得税之后的工资。假设他一个月的税前工资（扣除五险一金后、未扣税前的工资）为S元，则他应交的个人所得税按如下公式计算：
　　1） 个人所得税起征点为3500元，若S不超过3500，则不交税，3500元以上的部分才计算个人所得税，令A=S-3500元；
　　2） A中不超过1500元的部分，税率3%；
　　3） A中超过1500元未超过4500元的部分，税率10%；
　　4） A中超过4500元未超过9000元的部分，税率20%；
　　5） A中超过9000元未超过35000元的部分，税率25%；
　　6） A中超过35000元未超过55000元的部分，税率30%；
　　7） A中超过55000元未超过80000元的部分，税率35%；
　　8） A中超过80000元的部分，税率45%；
　　例如，如果小明的税前工资为10000元，则A=10000-3500=6500元，其中不超过1500元部分应缴税1500×3%=45元，超过1500元不超过4500元部分应缴税(4500-1500)×10%=300元，超过4500元部分应缴税(6500-4500)×20%=400元。总共缴税745元，税后所得为9255元。
　　已知小明这个月税后所得为T元，请问他的税前工资S是多少元。

输入格式

　　输入的第一行包含一个整数T，表示小明的税后所得。所有评测数据保证小明的税前工资为一个整百的数。

输出格式

　　输出一个整数S，表示小明的税前工资。

样例输入

9255

样例输出

10000

评测用例规模与约定

　　对于所有评测用例，1 ≤ T ≤ 100000。

题解

• 每个档都有一个最高税费，算出每档的税后最高工资，然后则只要算出最高档的税前+低档税前工资（交满了，所以已知）即可。

/*
<3500 则是税后
<4955 则是（税后-3500）/0.97+3500
<7655 则是(税后-4955)/0.9+3500+1500
<11255 则是(税后-7655)/0.8+3500+4500
<30755 则是(税后-11255)/0.75+3500+9000
<44755 则是(税后-30755)/0.7+3500+35000
<61005 则是(税后-44755)/0.65+55000
>61005 则是(税后-61005)/0.55+80000
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int T;
    cin >> T;
    if(T<=3500){
        cout << T;
    }
    else if(T<=4955){
        cout << (T-3500)/0.97+3500;
    }
    else if(T<=7655){
        cout << (T-4955)/0.9+3500+1500;

    }
    else if(T<=11255){
        cout << (T-7655)/0.8+3500+4500;
    }
    else if(T<=30755){
        cout << (T-11255)/0.75+3500+9000;
    }
    else if(T<=44755){
        cout << (T-30755)/0.7+3500+35000;
    }
    else if(T<=61005){
        cout << (T-44755)/0.65+3500+55000;
    }
    else{
        cout << (T-61005)/0.55+3500+80000;
    }
    return 0;
}

---

201612-3 权限查询

原题链接：201612-3 权限查询

问题描述

　　授权 (authorization) 是各类业务系统不可缺少的组成部分，系统用户通过授权机制获得系统中各个模块的操作权限。

　　本题中的授权机制是这样设计的：每位用户具有若干角色，每种角色具有若干权限。例如，用户 david 具有 manager 角色，

manager 角色有 crm:2 权限，则用户 david 具有 crm:2 权限，也就是 crm 类权限的第 2 等级的权限。

　　具体地，用户名和角色名称都是由小写字母组成的字符串，长度不超过 32。权限分为分等级权限和不分等级权限两大类。分等级权.

限由权限类名和权限等级构成，中间用冒号“:”分隔。其中权限类名也是由小写字母组成的字符串，长度不超过 32。权限等级是一位数

字，从 0 到 9，数字越大表示权限等级越高。系统规定如果用户具有某类某一等级的权限，那么他也将自动具有该类更低等级的权限。例

如在上面的例子中，除 crm:2 外，用户 david 也具有 crm:1 和 crm:0 权限。不分等级权限在描述权限时只有权限类名，没有权限等级

（也没有用于分隔的冒号）。

　　给出系统中用户、角色和权限的描述信息，你的程序需要回答多个关于用户和权限的查询。查询可分为以下几类：

• 不分等级权限的查询：如果权限本身是不分等级的，则查询时不指定等级，返回是否具有该权限；
• 分等级权限的带等级查询：如果权限本身分等级，查询也带等级，则返回是否具有该类的该等级权限；
• 分等级权限的不带等级查询：如果权限本身分等级，查询不带等级，则返回具有该类权限的等级；如果不具有该类的任何等级权限则返回“否”。

输入格式

　　输入第一行是一个正整数 p，表示不同的权限类别的数量。紧接着的 p 行被称为 P 段，每行一个字符串，描述各个权限。对于分等级

权限，格式为 <category>:<level>，其中 <category> 是权限类名，<level> 是该类权限的最高等级。对于不分等级权限，字符串

只包含权限类名。

　　接下来一行是一个正整数 r，表示不同的角色数量。紧接着的 r 行被称为 R 段，每行描述一种角色，格式为

　　<role> <s> <privilege 1> <privilege 2> ... <privilege s>

　　其中 <role> 是角色名称，<s> 表示该角色具有多少种权限。后面 <s> 个字符串描述该角色具有的权限，格式同 P 段。

　　接下来一行是一个正整数 u，表示用户数量。紧接着的 u 行被称为 U 段，每行描述一个用户，格式为

　　<user> <t> <role 1> <role 2> ... <role t>

　　其中 <user> 是用户名，<t> 表示该用户具有多少种角色。后面 <t> 个字符串描述该用户具有的角色。

　　接下来一行是一个正整数 q，表示权限查询的数量。紧接着的 q 行被称为 Q 段，每行描述一个授权查询，格式为 <user>

<privilege>，表示查询用户 <user> 是否具有 <privilege> 权限。如果查询的权限是分等级权限，则查询中的 <privilege> 可指

定等级，表示查询该用户是否具有该等级的权限；也可以不指定等级，表示查询该用户具有该权限的等级。对于不分等级权限，只能查询

该用户是否具有该权限，查询中不能指定等级。

输出格式

　　输出共 q 行，每行为 false、true，或者一个数字。false 表示相应的用户不具有相应的权限，true 表示相应的用户具有相应的权限。

对于分等级权限的不带等级查询，如果具有权限，则结果是一个数字，表示该用户具有该权限的（最高）等级。如果用户不存在，或者查

询的权限没有定义，则应该返回 false。

样例输入

3
crm:2
git:3
game
4
hr 1 crm:2
it 3 crm:1 git:1 game
dev 2 git:3 game
qa 1 git:2
3
alice 1 hr
bob 2 it qa
charlie 1 dev
9
alice game
alice crm:2
alice git:0
bob git
bob poweroff
charlie game
charlie crm
charlie git:3
malice game

样例输出

false
true
false
2
false
true
false
true
false

样例说明

　　样例输入描述的场景中，各个用户实际的权限如下：

• 用户 alice 具有 crm:2 权限
• 用户 bob 具有 crm:1、git:2 和 game 权限
• 用户 charlie 具有 git:3 和 game 权限
• 用户 malice 未描述，因此不具有任何权限

评测用例规模与约定

　　评测用例规模：

• 1 ≤ p, r, u ≤ 100
• 1 ≤ q ≤ 10 000
• 每个用户具有的角色数不超过 10，每种角色具有的权限种类不超过 10
  约定：
• 输入保证合法性，包括：

1. 角色对应的权限列表（R 段）中的权限都是之前（P 段）出现过的，权限可以重复出现，如果带等级的权限重复出现，以等级最高的为准
2. 用户对应的角色列表（U 段）中的角色都是之前（R 段）出现过的，如果多个角色都具有某一分等级权限，以等级最高的为准
3. 查询（Q 段）中的用户名和权限类名不保证在之前（U 段和 P 段）出现过

• 前 20% 的评测用例只有一种角色
• 前 50% 的评测用例权限都是不分等级的，查询也都不带等级

题解

• 此题其实就是给出角色和其拥有的权限，然后给出用户以及其拥有的角色，然后问此用户是否有某种权限，可以将角色拥有的权限全部复制到用户上来，然后遍历用户所拥有的权限即可。
• 根据题意首先会输入各种权限，但题目又没说权限仅此，而角色又会重新输入其权限，所以我认为这输入没啥用，直接滤过。
• 然后输入角色以及其权限，因为用户要查询角色，所以我采用映射，以角色名作为键，值为权限向量，因为角色拥有的权限个数不知，而且权限分为带等级和不带等价，因此权限可以用pair<string, int>类型存储，first为权限名，second为等级（不带等级设为-1），再用vector存储权限。
• 接下来就是输入用户以及其角色，因为查询用的是用户名，因此同样使用用户名作为键，值为权限向量，权限如上一样使用vector<pair<string, int>>存储。通过其角色名将角色所带的权限全部复制到用户的权限上。【但注意，权限可能重复】
• 最后就是查询了，因为权限名可能重复，因此会导致带等级的权限的等级不同而造成先搜索到等级低的因此而直接输出false，故因此我设了一个is_true变量，来检测是否找到，一个t变量来找出其最高等级。
• 注意：这只是这道题的取巧解法，工程上是不能这样的。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm> 
using namespace std;

int main(){
    int p;
    cin >> p;
    for(int i=0;i<p;++i){
        string t;
        cin >> t;
    }

    int r;
    map<string,vector<pair<string,int>>> roles;
    cin >> r;
    for(int i=0;i<r;++i){
        string role_name;
        int s;
        cin >> role_name >> s;
        vector<pair<string,int>> privileges;
        for(int j=0;j<s;++j){
            string str;
            cin >> str;
            int type=-1;
            if(str[str.size()-2]==':'){
                type=str[str.size()-1]-'0';
                str=str.substr(0,str.size()-2);
            }
            privileges.push_back(make_pair(str,type));
        }
        roles.insert(make_pair(role_name,privileges));
    }

    int u;
    cin >> u;
    map<string,vector<pair<string,int>>> users;
    for(int i=0;i<u;++i){
        string user_name;
        int t;
        cin >> user_name >> t;
        vector<pair<string,int>> privileges;
        for(int j=0;j<t;++j){
            string role_name;
            cin >> role_name;
            if(roles.count(role_name)){
                for(int k=0;k<roles[role_name].size();++k){
                    privileges.push_back(roles[role_name][k]);
                }
            }
        }
        users.insert(make_pair(user_name,privileges));
    }

    int q;
    cin >> q;
    for(int i=0;i<q;++i){
        string user_name,str_privilege,privilege;
        cin >> user_name >> str_privilege;
        int type;
        if(str_privilege[str_privilege.size()-2]==':'){
            privilege=str_privilege.substr(0,str_privilege.size()-2);
            type=str_privilege[str_privilege.size()-1]-'0';
        }
        else{
            privilege=str_privilege;
            type=-1;
        }
        bool is_true=false;
        int t=-1;
        if(users.count(user_name)){
            for(int j=0;j<users[user_name].size();++j){
                if(users[user_name][j].first==privilege){
                    if(type==-1){
                        if(users[user_name][j].second!=-1){
                            t=t>=users[user_name][j].second?t:users[user_name][j].second;
                            is_true=true;
                        }
                        else{
                            is_true=true;
                        }

                    }
                    else{
                        if(type<=users[user_name][j].second){
                            is_true=true;
                        }
                    }
                }
            }
        }
        else{
            is_true=false;
        }
        if(is_true){
            if(t!=-1){
                cout << t << endl;
            }
            else{
                cout << "true" << endl;
            }
        }
        else{
            cout << "false" << endl;
        }
    }
    return 0;
}

---

201609-3 炉石传说

问题描述

　　《炉石传说：魔兽英雄传》（Hearthstone: Heroes of Warcraft，简称炉石传说）是暴雪娱乐开发的一款集换式卡牌游戏（如下图所示）。游戏在一个战斗棋盘上进行，由两名玩家轮流进行操作，本题所使用的炉石传说游戏的简化规则如下：

• 玩家会控制一些角色，每个角色有自己的生命值和攻击力。当生命值小于等于 0 时，该角色死亡。角色分为英雄和随从。
• 玩家各控制一个英雄，游戏开始时，英雄的生命值为 30，攻击力为 0。当英雄死亡时，游戏结束，英雄未死亡的一方获胜。
• 玩家可在游戏过程中召唤随从。棋盘上每方都有 7 个可用于放置随从的空位，从左到右一字排开，被称为战场。当随从死亡时，它将被从战场上移除。
• 游戏开始后，两位玩家轮流进行操作，每个玩家的连续一组操作称为一个回合。
• 每个回合中，当前玩家可进行零个或者多个以下操作：

1. 召唤随从：玩家召唤一个随从进入战场，随从具有指定的生命值和攻击力。
2. 随从攻击：玩家控制自己的某个随从攻击对手的英雄或者某个随从。
3. 结束回合：玩家声明自己的当前回合结束，游戏将进入对手的回合。该操作一定是一个回合的最后一个操作。

• 当随从攻击时，攻击方和被攻击方会同时对彼此造成等同于自己攻击力的伤害。受到伤害的角色的生命值将会减少，数值等同于受到的伤害。例如，随从 X 的生命值为 HX、攻击力为 AX，随从 Y 的生命值为 HY、攻击力为 AY，如果随从 X 攻击随从 Y，则攻击发生后随从 X 的生命值变为 HX - AY，随从 Y 的生命值变为 HY - AX。攻击发生后，角色的生命值可以为负数。
  本题将给出一个游戏的过程，要求编写程序模拟该游戏过程并输出最后的局面。

输入格式

　　输入第一行是一个整数 n，表示操作的个数。接下来 n 行，每行描述一个操作，格式如下：
　　 ...
　　其中表示操作类型，是一个字符串，共有 3 种：summon表示召唤随从，attack表示随从攻击，end表示结束回合。这 3 种操作的具体格式如下：

• summon ：当前玩家在位置召唤一个生命值为、攻击力为的随从。其中是一个 1 到 7 的整数，表示召唤的随从出现在战场上的位置，原来该位置及右边的随从都将顺次向右移动一位。
• attack ：当前玩家的角色攻击对方的角色 。是 1 到 7 的整数，表示发起攻击的本方随从编号，是 0 到 7 的整数，表示被攻击的对方角色，0 表示攻击对方英雄，1 到 7 表示攻击对方随从的编号。
• end：当前玩家结束本回合。
  注意：随从的编号会随着游戏的进程发生变化，当召唤一个随从时，玩家指定召唤该随从放入战场的位置，此时，原来该位置及右边的所有随从编号都会增加 1。而当一个随从死亡时，它右边的所有随从编号都会减少 1。任意时刻，战场上的随从总是从1开始连续编号。

输出格式

　　输出共 5 行。
　　第 1 行包含一个整数，表示这 n 次操作后（以下称为 T 时刻）游戏的胜负结果，1 表示先手玩家获胜，-1 表示后手玩家获胜，0 表示游戏尚未结束，还没有人获胜。
　　第 2 行包含一个整数，表示 T 时刻先手玩家的英雄的生命值。
　　第 3 行包含若干个整数，第一个整数 p 表示 T 时刻先手玩家在战场上存活的随从个数，之后 p 个整数，分别表示这些随从在 T 时刻的生命值（按照从左往右的顺序）。
　　第 4 行和第 5 行与第 2 行和第 3 行类似，只是将玩家从先手玩家换为后手玩家。

样例输入

8
summon 1 3 6
summon 2 4 2
end
summon 1 4 5
summon 1 2 1
attack 1 2
end
attack 1 1

样例输出

0
30
1 2
30
1 2

样例说明

　　按照样例输入从第 2 行开始逐行的解释如下：

1. 先手玩家在位置 1 召唤一个生命值为 6、攻击力为 3 的随从 A，是本方战场上唯一的随从。
2. 先手玩家在位置 2 召唤一个生命值为 2、攻击力为 4 的随从 B，出现在随从 A 的右边。
3. 先手玩家回合结束。
4. 后手玩家在位置 1 召唤一个生命值为 5、攻击力为 4 的随从 C，是本方战场上唯一的随从。
5. 后手玩家在位置 1 召唤一个生命值为 1、攻击力为 2 的随从 D，出现在随从 C 的左边。
6. 随从 D 攻击随从 B，双方均死亡。
7. 后手玩家回合结束。
8. 随从 A 攻击随从 C，双方的生命值都降低至 2。

评测用例规模与约定

• 操作的个数0 ≤ n ≤ 1000。
• 随从的初始生命值为 1 到 100 的整数，攻击力为 0 到 100 的整数。
• 保证所有操作均合法，包括但不限于：

1. 召唤随从的位置一定是合法的，即如果当前本方战场上有 m 个随从，则召唤随从的位置一定在 1 到 m + 1 之间，其中 1 表示战场最左边的位置，m + 1 表示战场最右边的位置。
2. 当本方战场有 7 个随从时，不会再召唤新的随从。
3. 发起攻击和被攻击的角色一定存在，发起攻击的角色攻击力大于 0。
4. 一方英雄如果死亡，就不再会有后续操作。

• 数据约定：
  前 20% 的评测用例召唤随从的位置都是战场的最右边。
  　　　　　　　　　　　　　　　　　　前 40% 的评测用例没有 attack 操作。
  　　　　　　　　　　　　　　　　　　前 60% 的评测用例不会出现随从死亡的情况。

题解

我看到题我就想着用面向对象的思想来做，然后看见随从必须是连续的，我就想着用链表来连（因为链表的移动更好，用vector不好移动）。我觉得还是做成类的方式更好。虽然过了，但确实代码有些许长了，但题目确实不难，挖坑少。收获：我本来想用switch来判断输入的动作，但发现不能判断string类型，后查资料，补习了原来switch 语句中的 expression 必须是一个整型或枚举类型，或者是一个 class 类型，其中 class 有一个单一的转换函数将其转换为整型或枚举类型。

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
using ll = long long;

struct value{
    int life;
    int attack;
    value(int _life,int _attack):life(_life),attack(_attack){}
};

int turn=0;

class attendant{
public:
    int count=0;
    list<value> atd;
};

class player{
public:
    int hero=30;
    attendant atdant;
    //召唤随从
    void summon(int pos,int life,int attack){
        atdant.count++;
        auto it=atdant.atd.begin();
        for(int i=1;i<pos;++i){it++;}
        atdant.atd.insert(it,value(life,attack));
        if(atdant.count>7){
            atdant.atd.erase(--atdant.atd.end());
            atdant.count--;
        }
    }
    //攻击
    void attack(int attacker,int defender,player& target){
        auto attacker_iter=atdant.atd.begin();
        auto defender_iter=target.atdant.atd.begin();
        for(int i=1;i!=attacker;++i){
            ++attacker_iter;
        }
        if(defender==0){
            target.hero-=attacker_iter->attack;
            return;
        }
        for(int i=1;i!=defender;++i){
            ++defender_iter;
        }
        attacker_iter->life-=defender_iter->attack;
        defender_iter->life-=attacker_iter->attack;

        if(attacker_iter->life<=0){
            atdant.atd.erase(attacker_iter);
            atdant.count--;
        }
        if(defender_iter->life<=0){
            target.atdant.atd.erase(defender_iter);
            target.atdant.count--;
        }
    }
    //结束
    void end(){
        if(turn==0){
            turn=1;
        }
        else{
            turn=0;
        }
    }
};

void whoWin(const player& p1,const player& p2){
    if(p1.hero>0 && p2.hero>0){
        cout << 0 << endl;
    }
    else if(p1.hero>0 && p2.hero<=0){
        cout << 1 <<endl;
    }
    else if(p1.hero<=0 && p2.hero>0){
        cout << -1 << endl;
    }
}

void outputAttendant(const player& p){
    cout << p.hero << endl;

    cout << p.atdant.count << " ";
    for(auto &it:p.atdant.atd){
        cout << it.life << " ";
    }
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    player p1,p2;
    while(n--){
        string action;
        cin >> action;
        if(action=="summon"){
            int position,attack,health;
            cin >> position >> attack >> health;
            if(turn==0){
                p1.summon(position,health,attack);
            }
            else{
                p2.summon(position,health,attack);
            }
        }
        else if(action=="attack"){
            int attacker,defender;
            cin >> attacker >> defender;
            if(turn==0){
                p1.attack(attacker,defender,p2);
            }
            else{
                p2.attack(attacker,defender,p1);
            }
        }
        else if(action=="end"){
            if(turn==0){
                p1.end();
            }
            else{
                p2.end();
            }
        }
    }
    whoWin(p1,p2);
    outputAttendant(p1);
    outputAttendant(p2);
    return 0;
}

---

201604-2 俄罗斯方块

问题描述

　　俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
　　游戏在一个15行10列的方格图上进行，方格图上的每一个格子可能已经放置了方块，或者没有放置方块。每一轮，都会有一个新的由4个小方块组成的板块从方格图的上方落下，玩家可以操作板块左右移动放到合适的位置，当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时，板块不再移动，如果此时方格图的某一行全放满了方块，则该行被消除并得分。
　　在这个问题中，你需要写一个程序来模拟板块下落，你不需要处理玩家的操作，也不需要处理消行和得分。
　　具体的，给定一个初始的方格图，以及一个板块的形状和它下落的初始位置，你要给出最终的方格图。

输入格式

　　输入的前15行包含初始的方格图，每行包含10个数字，相邻的数字用空格分隔。如果一个数字是0，表示对应的方格中没有方块，如果数字是1，则表示初始的时候有方块。输入保证前4行中的数字都是0。
　　输入的第16至第19行包含新加入的板块的形状，每行包含4个数字，组成了板块图案，同样0表示没方块，1表示有方块。输入保证板块的图案中正好包含4个方块，且4个方块是连在一起的（准确的说，4个方块是四连通的，即给定的板块是俄罗斯方块的标准板块）。
　　第20行包含一个1到7之间的整数，表示板块图案最左边开始的时候是在方格图的哪一列中。注意，这里的板块图案指的是16至19行所输入的板块图案，如果板块图案的最左边一列全是0，则它的左边和实际所表示的板块的左边是不一致的（见样例）

输出格式

　　输出15行，每行10个数字，相邻的数字之间用一个空格分隔，表示板块下落后的方格图。注意，你不需要处理最终的消行。

样例输入

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0
3

样例输出

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 0 0 0 0

题解

• 第一种方法（模拟方块下移）：首先使用数组模拟方格图，将初始化的图存储，再用一个数组存储方块，然后确定方块每列的最下方的竖坐标，循环判断每列最下方的下一格是否有方块或者是否超过方格图，有方块或者超过方格图说明方块需要停止，然后在方块图上将方块绘制出来，若没有则将坐标增加。注意没有方块的列不能增加，还有记得判断越界。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int piture[15][10];     
    for(int i=0;i<15;++i){
        for(int j=0;j<10;++j){
            cin >> piture[i][j];
        }
    }
    int block[4][4];
    for(int i=0;i<4;++i){
        for(int j=0;j<4;++j){
            cin >> block[i][j];
        }
    }
    int col;
    cin >> col;
    col-=1;
    int mcol[4]={-1,-1,-1,-1};  //每列方块最低坐标
    for(int i=0;i<4;++i){
        for(int j=0;j<4;++j){
            if(block[j][i]==1){
                mcol[i]=j;
            }
        }
    }
    int count=0;
    while(true){
        int tag=0;
        for(int i=0;i<4;++i){
            if(mcol[i]==-1)continue;
            if(piture[mcol[i]+1][col+i]==1){    //判断是否碰撞到方块
                tag=1;
                break;
            }
            if(mcol[i]>=14){    //判断是否越界
                tag=1;
                break;
            }
        }
        if(tag==0){     //方块还能下移，坐标增加
            for(int i=0;i<4;++i){
                if(mcol[i]==-1)continue;
                mcol[i]++;
            }
            count++;
        }
        else{   //方块停止，绘画到画板上
            for(int i=count;i<count+4;++i){ 
                for(int j=col;j<col+4;++j){
                    if(piture[i][j]==0){
                        piture[i][j]=block[i-count][j-col];
                    }
                }
            }
            break;
        }    
    }
    for(int i=0;i<15;++i){
        for(int j=0;j<10;++j){
            cout << piture[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

• 第二种方法（碰撞检测）：因为方块只会在同一竖线上移动，因此可以将方块一直下移，直到画布和方块有重叠部分，则绘画出上一时刻即可

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;

bool draw(int row,int col,int piture[20][20],int block[4][4]){
    for(int i=row;i<row+4;++i){
        for(int j=col;j<col+4;++j){
            if(piture[i][j]==1 && block[i-row][j-col]==1){
                return false;
            }
        }
    }
    return true;
}

int main(){
    int piture[20][20];
    int block[4][4];
    for(int i=0;i<15;++i){
        for(int j=0;j<10;++j){
            cin >> piture[i][j];
        }
    }
    for(int i=0;i<10;++i){  
        piture[15][i]=1;    //将画布界外最下层设为1，以方便判断
    }
    for(int i=0;i<4;++i){
        for(int j=0;j<4;++j){
            cin >> block[i][j];
        }
    }
    int col,row=0;
    cin >> col;
    col--;  

    while(true){    //注意是true，而不是row+4<=15,因为不知道最下行是否是空行
        if(draw(row,col,piture,block)){
            //可以绘制
            row++;
        }
        else{
            //碰撞，回退
            row--;
            break;
        }
    }

    for(int i=row;i<row+4;++i){
        for(int j=col;j<col+4;++j){
            if(block[i-row][j-col]!=0)  //注意不等于0时才覆盖
                piture[i][j]=block[i-row][j-col];
        }
    }
    for(int i=0;i<15;++i){
        for(int j=0;j<10;++j){
            cout << piture[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

---

201604-3 路径解析

原题链接：201604-3 路径解析

问题描述

　　在操作系统中，数据通常以文件的形式存储在文件系统中。文件系统一般采用层次化的组织形式，由目录（或者文件夹）和文件构成，形成一棵树的形状。文件有内容，用于存储数据。目录是容器，可包含文件或其他目录。同一个目录下的所有文件和目录的名字各不相同，不同目录下可以有名字相同的文件或目录。
　　为了指定文件系统中的某个文件，需要用路径来定位。在类 Unix 系统（Linux、Max OS X、FreeBSD等）中，路径由若干部分构成，每个部分是一个目录或者文件的名字，相邻两个部分之间用 / 符号分隔。
　　有一个特殊的目录被称为根目录，是整个文件系统形成的这棵树的根节点，用一个单独的 / 符号表示。在操作系统中，有当前目录的概念，表示用户目前正在工作的目录。根据出发点可以把路径分为两类：
　　Ÿ 绝对路径：以 / 符号开头，表示从根目录开始构建的路径。
　　Ÿ 相对路径：不以 / 符号开头，表示从当前目录开始构建的路径。

　　例如，有一个文件系统的结构如下图所示。在这个文件系统中，有根目录 / 和其他普通目录 d1、d2、d3、d4，以及文件 f1、f2、f3、f1、f4。其中，两个 f1 是同名文件，但在不同的目录下。

　　对于 d4 目录下的 f1 文件，可以用绝对路径 /d2/d4/f1 来指定。如果当前目录是 /d2/d3，这个文件也可以用相对路径 ../d4/f1 来指定，这里 .. 表示上一级目录（注意，根目录的上一级目录是它本身）。还有 . 表示本目录，例如 /d1/./f1 指定的就是 /d1/f1。注意，如果有多个连续的 / 出现，其效果等同于一个 /，例如 /d1///f1 指定的也是 /d1/f1。
　　本题会给出一些路径，要求对于每个路径，给出正规化以后的形式。一个路径经过正规化操作后，其指定的文件不变，但是会变成一个不包含 . 和 .. 的绝对路径，且不包含连续多个 / 符号。如果一个路径以 / 结尾，那么它代表的一定是一个目录，正规化操作要去掉结尾的 /。若这个路径代表根目录，则正规化操作的结果是 /。若路径为空字符串，则正规化操作的结果是当前目录。

输入格式

　　第一行包含一个整数 P，表示需要进行正规化操作的路径个数。
　　第二行包含一个字符串，表示当前目录。
　　以下 P 行，每行包含一个字符串，表示需要进行正规化操作的路径。

输出格式

　　共 P 行，每行一个字符串，表示经过正规化操作后的路径，顺序与输入对应。

样例输入

7
/d2/d3
/d2/d4/f1
../d4/f1
/d1/./f1
/d1///f1
/d1/
///
/d1/../../d2

样例输出

/d2/d4/f1
/d2/d4/f1
/d1/f1
/d1/f1
/d1
/
/d2

评测用例规模与约定

　　1 ≤ P ≤ 10。
　　文件和目录的名字只包含大小写字母、数字和小数点 .、减号 - 以及下划线 _。
　　不会有文件或目录的名字是 . 或 .. ，它们具有题目描述中给出的特殊含义。
　　输入的所有路径每个长度不超过 1000 个字符。
　　输入的当前目录保证是一个经过正规化操作后的路径。
　　对于前 30% 的测试用例，需要正规化的路径的组成部分不包含 . 和 .. 。
　　对于前 60% 的测试用例，需要正规化的路径都是绝对路径。

题解

• 模拟题，给一个路径，将其转化为正规化的形式。

• 数据结构选择：

  • 存储当前路径：vector<string>
  • 存储给定路径：vector<string>

• 解题思想：因为路径是由/隔开，不易存取，因此都将其存储到vector容器中。根据是绝对路径还是相对路径，设定当前路径为空vector和开始给定的当前路径vector，遍历给定路径vector，根据其值对当前路径vector进行删除末尾元素（回上一位置）和增加元素操作。然后根据当前路径vector进行输出结果。

• 收获：

  1. 当遇到处理字符串题目时，能分割存储在vector中就尽量处理，这样能够随机访问就更加容易处理题目。
  2. 当使用getline时，需要清空缓冲区。getchar将换行符滤过即可。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> get(string str){
    int u=0,v=0;
    vector<string> ans;
    while(u<str.size()){
        while(v<str.size() && str[v]!='/')++v;
        if(u!=v) ans.push_back(str.substr(u,v-u));  //这很rong
        v++;u=v;
    }
    return ans;
}

void walk(vector<string> cur,vector<string> path){
    for(auto &it:path){
        if(it==".")continue;
        if(it==".."){
            if(cur.size())cur.pop_back();
        }
        else cur.push_back(it);
    }
    if(cur.empty()){
        cout << "/" << endl;
        return;
    }
    for(auto &p:cur){
        cout << "/" << p;
    }
    cout << endl;
}

int main()
{
    int n;
    string str;
    cin >> n >> str;
    vector<string> cur=get(str),root; //当前路径和根路径对应的vector

    getchar();  //用getline时即想到需要过滤掉换行符
    for(int i=0;i<n;++i){
        getline(cin,str);
        vector<string> path=get(str);
        if(str.size() && str[0]=='/') walk(root,path);
        else walk(cur,path);
    }
    return 0;
}

---

201512-2 消除类游戏

问题描述

　　消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。
　　现在给你一个n行m列的棋盘，棋盘中的每一个方格上有一个棋子，请给出经过一次消除后的棋盘。
　　请注意：一个棋子可能在某一行和某一列同时被消除。

输入格式

　　输入的第一行包含两个整数n, m，用空格分隔，分别表示棋盘的行数和列数。
　　接下来n行，每行m个整数，用空格分隔，分别表示每一个方格中的棋子的颜色。颜色使用1至9编号。

输出格式

　　输出n行，每行m个整数，相邻的整数之间使用一个空格分隔，表示经过一次消除后的棋盘。如果一个方格中的棋子被消除，则对应的方格输出0，否则输出棋子的颜色编号。

样例输入

4 5
2 2 3 1 2
3 4 5 1 4
2 3 2 1 3
2 2 2 4 4

样例输出

2 2 3 0 2
3 4 5 0 4
2 3 2 0 3
0 0 0 4 4

样例说明

　　棋盘中第4列的1和第4行的2可以被消除，其他的方格中的棋子均保留。

样例输入

4 5
2 2 3 1 2
3 1 1 1 1
2 3 2 1 3
2 2 3 3 3

样例输出

2 2 3 0 2
3 0 0 0 0
2 3 2 0 3
2 2 0 0 0

样例说明

　　棋盘中所有的1以及最后一行的3可以被同时消除，其他的方格中的棋子均保留。

评测用例规模与约定

　　所有的评测用例满足：1 ≤ n, m ≤ 30。

题解

第一次提交：思路是使用两个数组，一个来存储数据，一个来记录是否要被消除。首先初始化exist为true，并输入数据。扫描是否要被消除的思路是先从行开始，若有三个及以上相同的数据则记录消除（false），再从列开始扫描。最后根据记录数组打印结果

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> matrx(n,vector<int>(m));
    vector<vector<bool>> exist(n,vector<bool>(m));

    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin >> matrx[i][j];
            exist[i][j]=true;
        }
    }
    for(int i=0;i<n;++i){
        int count=1;
        for(int j=1;j<m;++j){
            if(matrx[i][j]==matrx[i][j-1]){
                count++;
            }
            else{
                count=1;
            }
            if(count>=3){
                int count2=0;
                for(int k=j;count2<count;k--,count2++){
                    exist[i][k]=false;
                }
            }
        }
    }
    for(int j=0;j<m;++j){
        int count=1;
        for(int i=1;i<n;++i){
            if(matrx[i][j]==matrx[i-1][j]){
                count++;
            }
            else{
                count=1;
            }
            if(count>=3){
                int count2=0;
                for(int k=i;count2<count;k--,count2++){
                    exist[k][j]=false;
                }
            }
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(exist[i][j])
                cout << matrx[i][j] << " ";
            else
                 cout << 0 << " ";
        }
        cout << endl;
    }
    return 0;
}

第二次提交：修改思路是直接遍历数组，当存在连续三个的数据时，将这三个记录为false。从而减少了代码量。但要注意当扫描行的时候列j只能到到倒数第3个，同样，扫描列的时候行i也只能到倒数第3个。切记不能直接限制i和j的范围，不然会少扫描几行和几列。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> matrx(n,vector<int>(m));
    vector<vector<bool>> exist(n,vector<bool>(m));

    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin >> matrx[i][j];
            exist[i][j]=true;
        }
    }

    for(int i=0;i<n;++i){  //注意越界
        for(int j=0;j<m;++j){
            if(j+2<m && matrx[i][j]==matrx[i][j+1] && matrx[i][j]==matrx[i][j+2]){
                //行 三个相同
                exist[i][j]=false;
                exist[i][j+1]=false;
                exist[i][j+2]=false;
            }
            if(i+2<n && matrx[i][j]==matrx[i+1][j] && matrx[i][j]==matrx[i+2][j]){
                //列 三个相同
                exist[i][j]=false;
                exist[i+1][j]=false;
                exist[i+2][j]=false;
            }
        }
    }

    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(exist[i][j])
                cout << matrx[i][j] << " ";
            else
                 cout << 0 << " ";
        }
        cout << endl;
    }
    return 0;
}

---

201512-3 画图

问题描述

　　用 ASCII 字符来画图是一件有趣的事情，并形成了一门被称为 ASCII Art 的艺术。例如，下图是用 ASCII 字符画出来的 CSPRO 字样。

　　..____.____..____..____...___..
　　./.___/.___||.._.\|.._.\./._.\.
　　|.|...\___.\|.|_).|.|_).|.|.|.|
　　|.|___.___).|..__/|.._.<|.|_|.|
　　.\____|____/|_|...|_|.\_\\___/.

　　本题要求编程实现一个用 ASCII 字符来画图的程序，支持以下两种操作：
　　0 画线：给出两个端点的坐标，画一条连接这两个端点的线段。简便起见题目保证要画的每条线段都是水平或者竖直的。水平线段用字符 - 来画，竖直线段用字符 | 来画。如果一条水平线段和一条竖直线段在某个位置相交，则相交位置用字符 + 代替。
　　1 填充：给出填充的起始位置坐标和需要填充的字符，从起始位置开始，用该字符填充相邻位置，直到遇到画布边缘或已经画好的线段。注意这里的相邻位置只需要考虑上下左右 4 个方向，如下图所示，字符 @ 只和 4 个字符 * 相邻。

　　.*.
　　*@*
　　.*.

输入格式

　　第1行有三个整数m, n和q。m和n分别表示画布的宽度和高度，以字符为单位。q表示画图操作的个数。
　　第2行至第q + 1行，每行是以下两种形式之一：
　　0 x1 y1 x2 y2：表示画线段的操作，(x1, y1)和(x2, y2)分别是线段的两端，满足要么x1 = x2 且y1 ≠ y2，要么 y1 = y2 且 x1 ≠ x2。
　　1 x y c：表示填充操作，(x, y)是起始位置，保证不会落在任何已有的线段上；c 为填充字符，是大小写字母。
　　画布的左下角是坐标为 (0, 0) 的位置，向右为x坐标增大的方向，向上为y坐标增大的方向。这q个操作按照数据给出的顺序依次执行。画布最初时所有位置都是字符 .（小数点）。

输出格式

　　输出有n行，每行m个字符，表示依次执行这q个操作后得到的画图结果。

样例输入

4 2 3
1 0 0 B
0 1 0 2 0
1 0 0 A

样例输出

AAAA
A--A

样例输入

16 13 9
0 3 1 12 1
0 12 1 12 3
0 12 3 6 3
0 6 3 6 9
0 6 9 12 9
0 12 9 12 11
0 12 11 3 11
0 3 11 3 1
1 4 2 C

样例输出

................
...+--------+...
...|CCCCCCCC|...
...|CC+-----+...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC+-----+...
...|CCCCCCCC|...
...+--------+...
................

评测用例规模与约定

　　所有的评测用例满足：2 ≤ m, n ≤ 100，0 ≤ q ≤ 100，0 ≤ x < m（x表示输入数据中所有位置的x坐标），0 ≤ y < n（y表示输入数据中所有位置的y坐标）。

题解

• 这题是在一个画布上进行绘画填充，总共两种操作：画线和填充；画线就很简单，根据行相同还是列相同画不同的线即可。填充就得使用广度优先搜索算法将其填充，这里采用队列将需要填充的坐标压入队列中，然后出队列填充并将新填充坐标压入队列中，这样就可以填充完。
• 这题有个注意点就是坐标系给定的是数学坐标系，而不是数组坐标系，所以其给的x坐标是列坐标，而y坐标是行坐标。

#include <iostream>
#include <vector> 
#include <queue>
#include <algorithm>
using namespace std;

const int W=100,H=100,Q=100;

class axi{
public:
    int x,y;
    axi(int _x,int _y){
        x=_x;
        y=_y;
    }
};

int main(){
    int w,h,q;
    cin >> w >> h >> q;
    char piture[W][H];
    for(int i=0;i<W;++i){
        for(int j=0;j<H;++j){
            piture[i][j]='.';
        }
    }

    for(int k=0;k<q;++k){
        int type;
        cin >> type;
        if(type==0){
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            //x相同代表列一致，遍历行
            if(x1==x2){
                if(y1>y2){
                    int t=y1;
                    y1=y2;
                    y2=t;
                }
                for(int j=y1;j<=y2;++j){
                    if(piture[j][x1]!='-'&&piture[j][x1]!='+'){
                        piture[j][x1]='|';
                    }
                    else{
                        piture[j][x1]='+';
                    }
                }
            }
            //y相同代表行一致，遍历列
            else{
                if(x1>x2){
                    int t=x1;
                    x1=x2;
                    x2=t;
                }
                for(int j=x1;j<=x2;++j){
                    if(piture[y1][j]!='|'&&piture[y1][j]!='+'){
                        piture[y1][j]='-';
                    }
                    else{
                        piture[y1][j]='+';
                    }
                }
            }
        }
        else{
            int x,y;
            char c;
            cin >> x >> y >> c;
            queue<axi> q;
            q.push(axi(x,y));
            while(!q.empty()){
                int x1,y1;
                x1=q.front().x;
                y1=q.front().y;
                if(x1+1 < w && piture[y1][x1+1]!='-' && piture[y1][x1+1]!='|' && piture[y1][x1+1]!='+' && piture[y1][x1+1]!=c){
                    piture[y1][x1+1]=c;
                    q.push(axi(x1+1,y1));
                }
                if(x1-1 >= 0 && x-1 < w && piture[y1][x1-1]!='-'&&piture[y1][x1-1]!='|'&&piture[y1][x1-1]!='+'&&piture[y1][x1-1]!=c){
                    piture[y1][x1-1]=c;
                    q.push(axi(x1-1,y1));
                }
                if(y1+1 < h && piture[y1+1][x1]!='-'&&piture[y1+1][x1]!='|'&&piture[y1+1][x1]!='+'&&piture[y1+1][x1]!=c){
                    piture[y1+1][x1]=c;
                    q.push(axi(x1,y1+1));
                }
                if(y1-1 >=0 && y1-1 < h && piture[y1-1][x1]!='-'&&piture[y1-1][x1]!='|'&&piture[y1-1][x1]!='+'&&piture[y1-1][x1]!=c){
                    piture[y1-1][x1]=c;
                    q.push(axi(x1,y1-1));
                }
                q.pop();
            }
        }
    }

    //数组的x轴与题意一致，y轴不一致，注意外层遍历行，内层遍历列
    for(int i=h-1;i>=0;--i){
        for(int j=0;j<w;++j){
            cout << piture[i][j];
        }
        cout << endl;
    }
    return 0;
}

 

 

 

201509-3 模板生成系统

问题描述

　　成成最近在搭建一个网站，其中一些页面的部分内容来自数据库中不同的数据记录，但是页面的基本结构是相同的。例如，对于展示

用户信息的页面，当用户为 Tom 时，网页的源代码是

　　而当用户为 Jerry 时，网页的源代码是

　　这样的例子在包含动态内容的网站中还有很多。为了简化生成网页的工作，成成觉得他需要引入一套模板生成系统。

　　模板是包含特殊标记的文本。成成用到的模板只包含一种特殊标记，格式为 {{ VAR }}，其中 VAR 是一个变量。该标记在模板生成时

会被变量 VAR 的值所替代。例如，如果变量 name = "Tom"，则 {{ name }} 会生成 Tom。具体的规则如下：

• 变量名由大小写字母、数字和下划线 (_) 构成，且第一个字符不是数字，长度不超过 16 个字符。
• 变量名是大小写敏感的，Name 和 name 是两个不同的变量。
• 变量的值是字符串。
• 如果标记中的变量没有定义，则生成空串，相当于把标记从模板中删除。
• 模板不递归生成。也就是说，如果变量的值中包含形如 {{ VAR }} 的内容，不再做进一步的替换。

输入格式

　　输入的第一行包含两个整数 m, n，分别表示模板的行数和模板生成时给出的变量个数。

　　接下来 m 行，每行是一个字符串，表示模板。

　　接下来 n 行，每行表示一个变量和它的值，中间用一个空格分隔。值是字符串，用双引号 (") 括起来，内容可包含除双引号以外的任

意可打印 ASCII 字符（ASCII 码范围 32, 33, 35-126）。

输出格式

　　输出包含若干行，表示模板生成的结果。

样例输入

11 2
<!DOCTYPE html>
<html>
<head>
<title>User {{ name }}</title>
</head>
<body>
<h1>{{ name }}</h1>
<p>Email: <a href="mailto:{{ email }}">{{ email }}</a></p>
<p>Address: {{ address }}</p>
</body>
</html>
name "David Beckham"
email "david@beckham.com"
样例输出
<!DOCTYPE html>
<html>
<head>
<title>User David Beckham</title>
</head>
<body>
<h1>David Beckham</h1>
<p>Email: <a href="mailto:david@beckham.com">david@beckham.com</a></p>
<p>Address: </p>
</body>
</html>

评测用例规模与约定

　　0 ≤ m ≤ 100

　　0 ≤ n ≤ 100

　　输入的模板每行长度不超过 80 个字符（不包含换行符）。

　　输入保证模板中所有以 {{ 开始的子串都是合法的标记，开始是两个左大括号和一个空格，然后是变量名，结尾是一个空格和两个右

大括号。

　　输入中所有变量的值字符串长度不超过 100 个字符（不包括双引号）。

　　保证输入的所有变量的名字各不相同。

题解

很容易想到使用 vector 容器来存储输入的模板行，哈希表来存储变量以及其值。然后根据每一行进行替换输出即可。这里的字符串处理可以学习一下。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main(){
    int m,n;
    cin >> m >> n;
    getchar();
    vector<string> strs;
    while(m--){
        string str;
        getline(cin,str);
        strs.push_back(str);
    }
    map<string,string> vars;
    while(n--){
        string var,key="";
        cin >> var;
        char c;
        while(c=getchar(),c!='\"');
        while(c=getchar(),c!='\"')
            key+=c;
        vars[var]=key;
    }

    for(auto& str:strs){
        int u=0;
        while(u<str.size()){
            if(u+3<str.size() && str[u]=='{' && str[u+1]=='{' && str[u+2]==' '){
                int v=u+3;
                while(v+3<str.size() && str[v]!=' ' && str[v+1]!='}')v++;
                string key=str.substr(u+3,v-u-3);
                if(vars.count(key)){
                    cout << vars[key];
                }
                u=v+3;
            }
            else{
                cout << str[u];
                u++;
            }
        }
        cout << endl;
    }
    return 0;
}

---

201503-1 图像旋转

问题描述

　　旋转是图像处理的基本操作，在这个问题中，你需要将一个图像逆时针旋转90度。
　　计算机中的图像表示可以用一个矩阵来表示，为了旋转一个图像，只需要将对应的矩阵旋转即可。

输入格式

　　输入的第一行包含两个整数n, m，分别表示图像矩阵的行数和列数。
　　接下来n行每行包含m个整数，表示输入的图像。

输出格式

　　输出m行，每行包含n个整数，表示原始矩阵逆时针旋转90度后的矩阵。

样例输入

2 3
1 5 3
3 2 4

样例输出

3 4
5 2
1 3

评测用例规模与约定

　　1 ≤ n, m ≤ 1,000，矩阵中的数都是不超过1000的非负整数。

题解

• 此题非常简单，找到规律即可，输出是从输入的最左边的一列开始从上往下输出。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n, m;
const int N = 1010;
int matrix[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    for (int col = m-1; col >= 0; col--) {
        for (int row = 0; row < n; row++) {
            cout << matrix[row][col] << " ";
        }
        cout << endl;
    }
    return 0;
}

这个版本是我以前做的，存存就是c语言版。当然这个也是没问题的，思路就是倒过来输出

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    int L=max(n,m);
    vector<vector<int>> matrx(L,vector<int>(L));

    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            cin >> matrx[i][j];
        }
    }
    for(int y=m-1;y>=0;--y){
        for(int x=0;x<n;++x){
            cout << matrx[x][y] << " "; 
        }
        cout << endl;
    }
    return 0;
}

收获与心得：学会了vector容器的二维形式，并且学会了vector的这种形式的含参构造。

---

201503-2 数字排序

问题描述

　　给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。

输入格式

　　输入的第一行包含一个整数n，表示给定数字的个数。
　　第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。

输出格式

　　输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。

样例输入

12
5 2 3 3 1 3 4 2 5 2 3 5

样例输出

3 4
2 3
5 3
1 1
4 1

评测用例规模与约定

　　1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。

题解

• 此题随不难，但有巧妙解法，很值得看一看
• 使用sort和运算符重载巧妙排序，sort默认排序是从小到大，可以重载小于号使得排序重大到小（反着返回），而且可以排序结构体
• 重载小于号：bool operator<(const 类型&t)const{代码};
• sort(first_pointer,first_pointer+n),第一个参数是数组名（开始地址），第二个参数是数组名+长度（最后一个地址的后一个地址）【所以可以排序数组的中间部分】，而且sort的算法很优，会根据情况使用快排、堆排等

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int cnt[N];
struct Data
{
    int val;
    int ct;
    /*绝妙之处，sort的排序为重小到大，而ct需要重大到小，当ct相同时，再由val重小到大，所以前者反，后者正来重载小于符号*/
    bool operator < (const Data& t)const {
        if (ct != t.ct) {
            return ct > t.ct;
        }
        return val < t.val;
    }
}q[N];
int n;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    n = 0;
    /*注意这里，是大N，哈希表必须遍历大N*/
    for (int i = 0; i < N; i++) {
        if (cnt[i] > 0)
            q[n++] = { i,cnt[i] };
    }
    sort(q, q + n);
    for (int i = 0; i < n; i++) {
        cout << q[i].val << " " << q[i].ct << endl;
    }
    return 0;
}

---

 

201412-1 门禁系统

问题描述

　　涛涛最近要负责图书馆的管理工作，需要记录下每天读者的到访情况。每位读者有一个编号，每条记录用读者的编号来表示。给出读者的来访记录，请问每一条记录中的读者是第几次出现。

输入格式

　　输入的第一行包含一个整数n，表示涛涛的记录条数。
　　第二行包含n个整数，依次表示涛涛的记录中每位读者的编号。

输出格式

　　输出一行，包含n个整数，由空格分隔，依次表示每条记录中的读者编号是第几次出现。

样例输入

5
1 2 1 1 3

样例输出

1 1 2 3 1

评测用例规模与约定

　　1≤n≤1,000，读者的编号为不超过n的正整数。

题解

此题比较简单，看到统计次数只要想到哈希表即可。

#include <iostream>
using namespace std;
int visitors[1000 + 10];

int main()
{
    int n;
    cin >> n;
    while (n--) {
        int temp;
        cin >> temp;
        visitors[temp]++;
        cout << visitors[temp] << " ";
    }
    return 0;
}

---

201412-2 Z字形扫描

问题描述

　　在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵，Z字形扫描的过程如下图所示：

　　对于下面的4×4的矩阵，
　　1 5 3 9
　　3 7 5 6
　　9 4 6 4
　　7 3 1 3
　　对其进行Z字形扫描后得到长度为16的序列：
　　1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
　　请实现一个Z字形扫描的程序，给定一个n×n的矩阵，输出对这个矩阵进行Z字形扫描的结果。

输入格式

　　输入的第一行包含一个整数n，表示矩阵的大小。
　　输入的第二行到第n+1行每行包含n个正整数，由空格分隔，表示给定的矩阵。

输出格式

　　输出一行，包含n×n个整数，由空格分隔，表示输入的矩阵经过Z字形扫描后的结果。

样例输入

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

样例输出

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

评测用例规模与约定

　　1≤n≤500，矩阵元素为不超过1000的正整数。

题解

• 此题有点难，需要动手并且有想法
• 若给二维数组标号从0开始，并且将二维表扩展成2n*2n的，则可以看出当行号为偶数时扫描往右上，奇数时往右下，并且行号与列号之和有个固定的值（最大行号）（1）
• 需要一个移动标尺，记为i，当i为偶数时，此时为偶数行，记行标为j，此时需要往右上扫描，行j需要从i->0，而列则是i-j（由1推出，此时i就是最大行号，j就是行号），当i为奇时，行j需要从0->i，而列则是i-j
• 因为扩展成2n*2n的二维表了，所以输出需要在n*n二维表的限制下输出

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 500 + 10;
int n;
int q[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> q[i][j];
        }
    }
    for (int i = 0; i < 2 * n; i++) {
        if (i % 2 == 0) {
            for (int j = i; j >= 0; j--) {
                if (j >= 0 && j < n && i - j >= 0 && i - j < n) {
                    cout << q[j][i - j] << " ";
                }
            }
        }
        else {
            for (int j = 0; j < n; j++) {
                if (j >= 0 && j < n && i - j >= 0 && i - j < n) {
                    cout << q[j][i - j] << " ";
                }
            }
        }
    }
    return 0;
}

---

201412-3 集合竞价

问题描述

　　某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
　　该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种：

1. buy p s 表示一个购买股票的买单，每手出价为p，购买股数为s。

   2. sell p s 表示一个出售股票的卖单，每手出价为p，出售股数为s。

      3. cancel i表示撤销第i行的记录。
         如果开盘价为p0，则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。因此，此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。
         　　　　　　　　　　　　　　　　你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。

输入格式

　　输入数据有任意多行，每一行是一条记录。保证输入合法。股数为不超过108的正整数，出价为精确到恰好小数点后两位的正实数，且不超过10000.00。

输出格式

　　你需要输出一行，包含两个数，以一个空格分隔。第一个数是开盘价，第二个是此开盘价下的成交量。开盘价需要精确到小数点后恰好两位。

样例输入

buy 9.25 100
buy 8.88 175
sell 9.00 1000
buy 9.00 400
sell 8.92 400
cancel 1
buy 100.00 50

样例输出

9.00 450

评测用例规模与约定

　　对于100%的数据，输入的行数不超过5000。

题解

• 此题还是模拟题，但需要读懂题目，此题意思就是找一个开盘价，使得愿意出价比这个高的股票与愿意出售比这个价格低的股票数量的最小值最大
• 这个价格就是在出价和售价之中的一个，因为在某个价格的区间内，成交量是不变的。（但还是感觉应该是下一出现价格的左极限，但不可能是这个答案，所以还是直接用给的就行）
• 现在就是需要设计一个数据结构，属性有类型、价格、股数以及是否被删除，并且用这个数据结构开一个数组存放指令
• 存入数组中之后就进行判定了，枚举每个价格（未被删除），然后统计出售股和购买股，并计算最小值，计算完后与原先的成交股比较，若大则直接更新价格和成交股，若相等则判断价格是否变大，变大则更新价格

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;  //以后除了确定的用int，否则用long long
const int N = 5010;
struct recode
{
    int type;
    double p;
    LL s;
    bool is_del;
};
recode d[N];

int main()
{
    string type;
    int i = 0;
    /*使用cin >> type，当是预计类型时返回true,其他类型返回false,在windows中需要ctrl+z进行中断*/
    while (cin >> type) {
        if (type == "buy") {
            double p;
            LL s;
            cin >> p >> s;
            d[i++] = { 1,p,s ,false};
        }
        else if (type == "sell") {
            double p;
            LL s;
            cin >> p >> s;
            d[i++] = { 2,p,s ,false};
        }
        else if (type=="cancel") {
            int j;
            cin >> j;
            d[j-1].is_del = true;
            d[i++].is_del = true;
        }
    }
    double resp = 0;
    LL ress = 0;
    for (int q = 0; q < i; q++) {
        if (d[q].is_del == false) {
            LL all_b = 0;
            LL all_s = 0;
            for (int j = 0; j < i; j++) {
                if (d[j].type == 1 && d[j].p>=d[q].p && d[j].is_del==false) {
                    all_b += d[j].s;
                }
                else if (d[j].type == 2 && d[j].p <= d[q].p && d[j].is_del == false) {
                    all_s += d[j].s;
                }
            }
            LL _all = min(all_b,all_s);
            if (_all > ress) {
                resp = d[q].p;
                ress = _all;
            }
            else if (_all == ress) {
                if (resp < d[q].p)
                    resp = d[q].p;
            }
        }
    }
    printf("%.2f %lld",resp,ress);
    return 0;
}

---

201403-3 命令行选项

问题描述

　　请你写一个命令行分析程序,用以分析给定的命令行里包含哪些选项。每个命令行由若干个字符串组成,它们之间恰好由一个空格分隔。这些字符串中的第一个为该命令行工具的名字,由小写字母组成,你的程序不用对它进行处理。在工具名字之后可能会包含若干选项,然后可能会包含一 些不是选项的参数。
　　选项有两类:带参数的选项和不带参数的选项。一个合法的无参数选项的形式是一个减号后面跟单个小写字母,如"-a" 或"-b"。而带参数选项则由两个由空格分隔的字符串构成,前者的格式要求与无参数选项相同,后者则是该选项的参数,是由小写字母,数字和减号组成的非空字符串。
　　该命令行工具的作者提供给你一个格式字符串以指定他的命令行工具需要接受哪些选项。这个字符串由若干小写字母和冒号组成,其中的每个小写字母表示一个该程序接受的选项。如果该小写字母后面紧跟了一个冒号,它就表示一个带参数的选项,否则则为不带参数的选项。例如, "ab:m:" 表示该程序接受三种选项,即"-a"(不带参数),"-b"(带参数), 以及"-m"(带参数)。
　　命令行工具的作者准备了若干条命令行用以测试你的程序。对于每个命令行,你的工具应当一直向后分析。当你的工具遇到某个字符串既不是合法的选项,又不是某个合法选项的参数时,分析就停止。命令行剩余的未分析部分不构成该命令的选项,因此你的程序应当忽略它们。

输入格式

　　输入的第一行是一个格式字符串,它至少包含一个字符,且长度不超过 52。格式字符串只包含小写字母和冒号,保证每个小写字母至多出现一次,不会有两个相邻的冒号,也不会以冒号开头。
　　输入的第二行是一个正整数 N(1 ≤ N ≤ 20),表示你需要处理的命令行的个数。
　　接下来有 N 行,每行是一个待处理的命令行,它包括不超过 256 个字符。该命令行一定是若干个由单个空格分隔的字符串构成,每个字符串里只包含小写字母,数字和减号。

输出格式

　　输出有 N 行。其中第 i 行以"Case i:" 开始,然后应当有恰好一个空格,然后应当按照字母升序输出该命令行中用到的所有选项的名称,对于带参数的选项,在输出它的名称之后还要输出它的参数。如果一个选项在命令行中出现了多次,只输出一次。如果一个带参数的选项在命令行中出 现了多次,只输出最后一次出现时所带的参数。

样例输入

albw:x
4
ls -a -l -a documents -b
ls
ls -w 10 -x -w 15
ls -a -b -c -d -e -l

样例输出

Case 1: -a -l
Case 2:
Case 3: -w 15 -x
Case 4: -a -b

题解

• 模拟题，给一个字符串，字符串中的每一个字母都是一个选项，选项有两种形式，带参数和不带参数。然后给定一行命令，解读这个命令。

• 数据结构选择：

  • 存储选项：map，因为选项需要确定是否带参数，因此可以使用map映射。
  • 存储命令中的选项：vector，因为命令中的选项个数是不确定的，因此使用vector可以很好的扩展。
  • 存储结果：字符串数组，这是一个巧妙点，首先输出的结果需要去重，并且按照字母升序输出，这里可能会想到set容器，但是由于选项都是小写字母，小写字母只有26个，因此可以采用hash表，比集合更加容易实现。

• 算法：

  1. 读入给定字符串，并遍历，根据后一个是否有冒号存储在map容器rules中。
  2. 读入需要解读的命令个数n
  3. 读入一行命令（cin），再使用stringstream初始化这行命令的流ss。
  4. 将将流ss中的选项存储到vector容器ops中。
  5. 遍历ops（滤过第一个），判断是否是选项（以减号开头，紧跟一个小写字母）
  6. 若是选项，则继续，否则break跳入9
  7. 判断是否有这个选项，若有则继续，否则break跳入9
  8. 判断这个选项是否带参数，若带则将ops的下一个存储到答案中（若不存在则break跳入9），并跳过下一个；若不带则将*存储到答案中。
  9. 遍历答案数组，按要求输出即可。

• 收获：

  • 选择需要用set容器时，进一步想一想是否可以使用哈希表（个数一定）。
  • 当出现需要读取一行然后一行中需要根据空格继续输入时使用stringstream
  • string类型不能使用%s

#include <iostream>
#include <map>
#include <vector>
#include <sstream>
#include <set>
#include <algorithm>
using namespace std;

//1.字符串中的第一个为该命令行工具的名字
//2.在工具名字之后可能会包含若干选项,然后可能会包含一 些不是选项的参数。
//2.1一个合法的无参数选项的形式是一个减号后面跟单个小写字母
//2.2带参数选项则由两个由空格分隔的字符串构成,前者的格式要求与无参数选项相同,后者则是该选项的参数,是由小写字母,数字和减号组成的非空字符串。
//3.这个字符串由若干小写字母和冒号组成,其中的每个小写字母表示一个该程序接受的选项
//3.1如果该小写字母后面紧跟了一个冒号,它就表示一个带参数的选项,否则则为不带参数的选项

int main()
{
    string str;
    cin >> str;
    map<char,bool> rules;
    for(int i=0;i<str.size();++i){
        if(i+1<str.size() && str[i+1]==':'){
            rules.insert(make_pair(str[i],true));
            ++i;
        }
        else{
            rules.insert(make_pair(str[i],false));
        }
    }
    int n;
    cin >> n;
    getchar();
    for(int i=0;i<n;++i){
        cout << "Case " << i+1 << ": ";
        getline(cin,str);
        stringstream ss(str);
        string ans[30];    //巧妙点
        vector<string> ops;
        while(ss >> str) ops.push_back(str);    
        for(int j=1;j<ops.size();++j){
            if(ops[j][0]!='-' || ops[j][1] < 'a' || ops[j].size()!=2) break;
            int k=ops[j][1]-'a';    //巧妙点
            if(rules.find(ops[j][1])!=rules.end()){
                if((*rules.find(ops[j][1])).second){
                    if(j+1<ops.size()){
                        ans[k]=ops[j+1];
                        ++j;
                    }
                    else{
                        break;
                    }
                }
                else{
                    ans[k]="*";
                }
            }
            else{
                break;
            }
        }
        //string类型不能使用%s
        for(int j=0;j<26;++j){
            if(ans[j].size()){
                if(ans[j]!="*"){
                    printf("-%c ",j+'a');
                    cout << ans[j] << " ";
                }
                else{
                    printf("-%c ",j+'a');
                }
            }
        }
        cout << endl;
    }
    return 0;
}

---

 

201312-4 有趣的数

问题描述

　　我们把一个数称为有趣的，当且仅当：

1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
3. 最高位数字不为0。
   因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
   　　　　　　　　　　　　　　　　　　请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。

输入格式

　　输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。

输出格式

　　输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。

样例输入

4

样例输出

3

题解

由题意可知：0在1前面，2在3前面，但01和23没有其他关系。位置个数是一定的，所以可以先将01排好，那么剩下的就是23的位置。

算法：取 k 位用于01进行插入，那么有 n-k 位用于23进行插入。因为首位不能是0，所以01只能从n-1位里面取出k位，即$C_{n-1}^k$；01内部进行排，取t个0，k-t个1，则有k-1种可能【最多k-1个0，最少1个0】，同样，23则是n-k-1种可能。故答案为$\sum\limits_{k=2}^{n-1}C_{n-1}^k*(k-1)*(n-k-1)$

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int N=1010;

ll C[N][N],mod = 1000000007;

int main(){
    int n;
    cin >> n;
    for(int i=0;i<=n;++i){
        for(int j=0;j<=i;++j){
            if(j==0) C[i][j]=1;
            else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;   //注意，组合数可能会很大，所以需要取mod
        }
    }

    ll sum=0;
    for(int k=2;k<n;++k){
        sum+=(k-1)*(n-k-1)*C[n-1][k];
    }
    cout << sum % mod << endl;

    return 0;
}