admin管理员组

文章数量:829158

WaWa的奇妙冒险(第二周集训自闭现场)

第二周周记

  • (一)例题记录
    • A-简单计算器 (水题,栈的运用) HDU - 1237
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • B-计算 (逆波兰表达式天下第一)
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • C-中缀表达式值 (栈的运用)
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • D-图形面积 (水题,栈的运用or搜索?)
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • E-The Blocks Problem (模拟,map AND vector) UVA - 101
      • Input
      • Output
      • Sample Input
      • 理解
      • AC代码
    • F-Ananagrams (水题,二重映射) UVA - 156
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • G-Team Queue (分支队列) UVA - 540
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • H-Database (map 查找) UVA - 1592
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • I-Unix ls (水题,排版) UVA - 400
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • J-对称轴 (水题,map AND pair) UVA - 1595
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • K-打印队列 (水题,模拟,队列) UVA - 12100
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • L-图书管理系统 (模拟,set) UVA - 230
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • M-找Bug (模拟,递归写栈) UVA - 1596
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • N- Web中搜索,有意义 (模拟) UVA - 1597
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • O-更新字典 (水题) UVA - 12504
      • Input
      • Output
      • Sample Input
      • Sample Output
      • 理解
      • AC代码
    • P-Gathering Children (水题,思维题) atcoder
      • Input
      • 理解
      • AC代码
  • (二)一些收获
    • 关于STL
    • 关于模拟题
  • (三)感想
  • (四)附录[学习笔记]

(一)例题记录

A-简单计算器 (水题,栈的运用) HDU - 1237

读入一个只包含 +, -, *, / 的非负整数计算表达式,计算该表达式的值。

Input

测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输出。

Output

对每个测试用例输出1行,即该表达式的值,精确到小数点后2位。

Sample Input

1 + 2
4 + 2 * 5 - 7 / 11
0

Sample Output

3.00
13.36

理解

	因为暴力模拟过一元一次方程,所以写这题的时候没啥感觉,但因为要用上栈,所以还是做了一些思考得出来的解决方案是用栈存储“+”和“-”,在优先完成“*”和“/”之后出栈完成最终计算(这个地方的构思还是不够巧妙,对于第二天写升级版的计算器影响挺大的,后面学了中缀转后缀,以及后缀的计算之后,才惊觉对于中缀表达式的计算用栈可以达到一个很巧妙的地步,善用栈解决 “优先级” 的问题)

AC代码

#include <bits/stdc++.h>
using namespace std;int main()  ##  代码思路比较简单,就不做注释了
{	string s;while(getline(cin,s) && s != "0"){int l = s.size();stack <double> a;stack <char> b;double tsum = 0;for(int i = 0;i < l;i++){if(s[i] >= '0' && s[i] <= '9'){tsum = tsum * 10 + s[i] - '0';}else if(s[i] == '*' || s[i] == '/'){char k = s[i];double tsum2 = 0;for(i = i + 1;s[i] != '+' && s[i] != '-' && s[i] != '*' && s[i] != '/' && i < l;i++){if(s[i] >= '0' && s[i] <= '9') tsum2 = tsum2 * 10 + s[i] - '0';}i--;if(k == '/' && tsum2 != 0) tsum /= tsum2;else tsum *= tsum2;}else if(s[i] == '+' || s[i] == '-'){a.push(tsum);tsum = 0;b.push(s[i]);}}a.push(tsum);tsum = 0;double sum = 0;while(!b.empty()){double tsum3 = a.top();a.pop();char k = b.top();b.pop();if(k == '-') tsum3 = -tsum3;sum += tsum3;}sum += a.top();a.pop();printf("%.2f\n",sum);}return 0;
}

但是这题实际上的运算只要两个优先级,而且输入上大有文章可做,所以看到了大佬的神奇代码

这种写法确实十分厉害,一种非常巧妙的思想,后面也是用这种思想封装过简单的计算,但放优先级层次多了之后,我借用这种巧妙的想法无法完成更难的题(高概率是个人实力不行),而逆波兰表达式(后缀表达式)此时便凸显出了作用,能对这类型的题目完成一种模板式的通杀。
个人认为栈的写法(不是我简单计算器的ac代码),确实是对于算式题优先级的解决提供了一个良好的解决方案,虽然打起模板来代码量比较大,但胜在大部分人学习后能够使用(愚蠢的我选择栈),后面题目会贴出类似模板。

B-计算 (逆波兰表达式天下第一)

小明在你的帮助下,破密了Ferrari设的密码门,正要往前走,突然又出现了一个密码门,门上有一个算式,其中只有“(”,“)”,“0-9”,“+”,“-”,“*”,“/”,“^”求出的值就是密码。小明数学学得不好,还需你帮他的忙。(“/”用整数除法,取商)

Input

输入共1行,为一个算式。

Output

输出共1行,就是密码。

Sample Input

1+(3+2)(7^2+69)/(2)

Sample Output

258

理解

	最开始是用了类似上面大佬的思路,封装了计算函数,来处理()内的算式,所以,蒟蒻的我成功wa了,关键点在于处理多重(),到最后我都没能想出来,在百度完中缀表达式转后缀表达式之后,我仿佛找到了a题的途径,因为后缀表达式的计算只需要从左往右进行一个循序计算即可,敲了一晚上的模板,成功把题a了,也对这种题型有了一个较好解题思路。

AC代码

#include <bits/stdc++.h>
using namespace std;
map <char,int> p;struct node{int num;char cmd;bool f;
};stack <node> a;
queue <node> b;void change(string s){  ## 将中缀表达式转成后缀表达式node temp;for(int i = 0; i < s.length();i++){if(s[i] == '('){  ## 当压入栈的符号为(时,无视前面的优先级temp.f = false;temp.cmd = s[i];a.push(temp);}else if(s[i] == ')'){  ## 当压入栈的符号位)时,压出到(为止while (!a.empty() && a.top().cmd != '('){b.push(a.top());a.pop();}a.pop();}else if(s[i] >= '0'&&s[i] <= '9'){  ## 是数字符号的话要转化成数字然后放入队列temp.f = true;temp.num = s[i] - '0';i++;while (i < s.length() && s[i] >= '0'&&s[i] <= '9'){temp.num = temp.num * 10 + (s[i] - '0');i++;}i--;b.push(temp);}else{  ## 其他运算符根据优先级进行压栈和出栈操作temp.f = false;while (!a.empty() && p[a.top().cmd]>=p[s[i]]){b.push(a.top());a.pop();}temp.cmd = s[i];a.push(temp);}}while (!a.empty()){b.push(a.top());a.pop();}
}int cal(){  ## 计算后缀表达式,此处不再赘述,推荐看blog了解,肯定比我讲的好stack <node> a1;node temp,temp2;while(!b.empty()){temp = b.front();b.pop();if(temp.f == true) a1.push(temp);else{int nb = a1.top().num;a1.pop();int na = a1.top().num;a1.pop();temp2.f = true;if(temp.cmd == '+') temp2.num = na + nb;if(temp.cmd == '-') temp2.num = na - nb;if(temp.cmd == '*') temp2.num = na * nb;if(temp.cmd == '/') temp2.num = na / nb;if(temp.cmd == '^') temp2.num = pow(na,nb);a1.push(temp2);}}return a1.top().num;
}int main()
{p['+'] = p['-'] = 1;p['*'] = p['/'] = 2;p['^'] = 3;string s;cin >> s;change(s);
//  while(!b.empty()){
//      node temp = b.front();
//      if(temp.f == true) cout << temp.num << ' ';
//      else cout << temp.cmd << ' ';
//      b.pop();
//  }int ans = cal();cout << ans << endl;return 0;
}

后来第二天在思考的时候,感觉中缀转后缀,后缀的计算,实质上就是一个中缀表达式利用栈按优先级进行计算的拆分,然后改出了下面这份代码

## 在理解上面代码的情况下很容易能懂下面的代码,此处也不再赘述
#include <bits/stdc++.h>
using namespace std;
map <char,int> p;stack <int> a;
stack <char> b;int cal(char k){int nb = a.top();a.pop();int na = a.top();a.pop();if(k == '+') return na + nb;if(k == '-') return na - nb;if(k == '*') return na * nb;if(k == '/') return na / nb;if(k == '^') return pow(na,nb);
}void change(string s){for(int i = 0; i < s.length();i++){if(s[i] == '(') {b.push(s[i]);}else if(s[i] == ')'){while (!b.empty() && b.top() != '('){int temp = cal(b.top());a.push(temp);b.pop();}b.pop();}else if(s[i] >= '0'&&s[i] <= '9'){int temp = s[i] - '0';i++;while (i < s.length() && s[i] >= '0'&&s[i] <= '9'){temp = temp * 10 + (s[i] - '0');i++;}i--;a.push(temp);}else{while (!b.empty() && p[b.top()]>=p[s[i]]){int temp = cal(b.top());a.push(temp);b.pop();}b.push(s[i]);}}while (!b.empty()){int temp = cal(b.top());a.push(temp);b.pop();}
}int main()
{p['('] = 1;p['+'] = p['-'] = 2;p['*'] = p['/'] = 3;p['^'] = 4;string s;cin >> s;change(s);cout << a.top() << endl;return 0;
}

参考的大佬blog
中缀转后缀
后缀的计算

C-中缀表达式值 (栈的运用)

输入一个中缀表达式(由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志,表达式以“@”作为结束符),判断表达式是否合法,如果不合法,请输出“NO”;否则请把表达式转换成后缀形式,再求出后缀表达式的值并输出。

  注意:必须用栈操作,不能直接输出表达式的值。如果再考虑是实数运算呢?

Input

输入的第一行为一个以@结束的字符串。

Output

如果表达式不合法,请输出“NO”,要求大写。

如果表达式合法,请输出计算结果。

Sample Input

1+2*8-9@

Sample Output

8

理解

	在做完计算之后看这道题,明显就有了思路,因为你知道中缀转后缀和后缀的计算了,剩下需要解决的也就只剩下  “负数的处理”  和  “判断中缀表达式是否合法” 两项内容。1.负数的处理:这一项比较简单,选择性地往表达式里面插入0就好了2.中缀的判断:总体可以归纳为:(1)对(在末尾以及(前后字符的判断(2)对)在开头以及)前后字符的判断(3)对运算符前后的字符判断以及其在开头和结尾的判断

AC代码

#include <bits/stdc++.h>
using namespace std;
map <char,int> p;stack <int> a;
stack <char> b;int cal(char k){int nb = a.top();a.pop();int na = a.top();a.pop();if(k == '+') return na + nb;if(k == '-') return na - nb;if(k == '*') return na * nb;if(k == '/') return na / nb;
}void change(string s){for(int i = 0; i < s.length();i++){if(s[i] == '(') {b.push(s[i]);}else if(s[i] == ')'){while (!b.empty() && b.top() != '('){int temp = cal(b.top());a.push(temp);b.pop();}b.pop();}else if(s[i] >= '0'&&s[i] <= '9'){int temp = s[i] - '0';i++;while (i < s.length() && s[i] >= '0'&&s[i] <= '9'){temp = temp * 10 + (s[i] - '0');i++;}i--;a.push(temp);}else{while (!b.empty() && p[b.top()]>=p[s[i]]){int temp = cal(b.top());a.push(temp);b.pop();}b.push(s[i]);}}while (!b.empty()){int temp = cal(b.top());a.push(temp);b.pop();}
}int ss(string a){  ## 判断这一块是关键,一个好的判断思路能轻松的判断出结果if(a[0]=='+' || a[0]=='*'|| a[0]=='/') return 0;stack <char> temp;for(int i = 0;i < a.size();i++){if(a[i] == '('){if((i == a.size()-1 || a[i+1]=='+' || a[i+1]=='*' || a[i+1]=='/' || a[i+1]==')')||(i!=0&&'0'<=a[i-1]&&a[i-1]<='9'))return 0;temp.push(a[i]);}if(a[i]==')'){if((i==0 || a[i-1]=='+' || a[i-1]=='*'|| a[i-1]=='/' || a[i-1]=='-')||(i!=a.size()-1&&'0'<=a[i+1]&&a[i+1]<='9'||a[i+1]=='('))return 0;if(temp.empty()) return 0;temp.pop();}if(i == a.size()-1 && (a[i]=='+' || a[i]=='*'|| a[i]=='/' || a[i]=='-'))return 0; if(i<a.size()-1&&(a[i]=='+'||a[i]=='*'||a[i]=='/'||a[i]=='-')&&(a[i+1]=='+'||a[i+1]=='*'||a[i+1]=='/'||a[i+1]=='-'))return 0; }
}int main()
{p['+'] = p['-'] = 1;p['*'] = p['/'] = 2;string s;cin >> s;s.assign(s.begin(),--s.end());if(!ss(s)) cout << "NO" << endl;else{      for(int i = 0;i < s.size();i++){  ## 对负数的情况进行处理,补0if(s[i] == '-'){if(i == 0) s.insert(0,1,'0');else if(s[i - 1] == '(') s.insert(i,1,'0');}}change(s);cout << a.top() << endl;}return 0;
}

写这道题也是有点惨,一直运行错误,理了很久的思路才明白是判断写的有问题(存在漏网之鱼),导致运算过程中出现访问空的栈顶元素以及删除的操作导致re,后面也是看了老师的代码,才惊觉自己写的判断少了连续出现运算符以及空括号这两种情况的判断。
现在的判断也是照抄了老师的判断思路,以字符为准进行选择判断(反正比我之前的判断思路优越许多)。

D-图形面积 (水题,栈的运用or搜索?)

编程计算由“”号围成的下列图形的面积。面积计算方法是统计号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示,在1010的二维数组中,有“”围住了15个点,因此面积为15。

Input

输入0-1矩阵(1表示*)

Output

输出面积。

Sample Input

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

Sample Output

15

理解

	一道简单的水题,没啥好讲的,记录一下的原因也只是这貌似可以用搜索做,但我是拿栈a掉的

AC代码

#include <bits/stdc++.h>
using namespace std;int main()
{   string s[12];int sum = 0;for(int i = 0;i < 10;i++) getline(cin,s[i]);for(int i = 0;i < 10;i++){stack <char> a;for(int j = 0;j < s[i].size();j++){if(s[i][j] != ' ') a.push(s[i][j]);}int f = 0,ts = 0;while(!a.empty()){  ## 从左往右找,找到贴着0的那个1,记录大小在找到第二个1,计算差值得到0的数量char k = a.top();a.pop();if(f && k == '1'){sum += ts - a.size() - 1;f = 0;continue;}if(!f && k == '1'){while(k == '1' && a.top() == '1' && a.size() > 1){a.pop();}f = 1;ts = a.size();}}}cout << sum << endl;return 0;
}

方法也是比较差,就不多讲了。
网上没找到这题。。。也就没有搜索的写法,以后有空自己试着写一份吧,貌似感觉是dfs???

E-The Blocks Problem (模拟,map AND vector) UVA - 101

    Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies.For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks.
    In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will “program” a robotic arm to respond to a limited set of commands.
    The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a flat table. Initially there are n blocks on the table (numbered from 0 to n − 1) with block bi adjacent to block bi+1 for all 0 ≤ i < n − 1 as shown in the diagram below:

    The valid commands for the robot arm that manipulates blocks are:
    • move a onto b
    where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.
    • move a over b
    where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions.
    • pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their
    initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
    • pile a over b
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
    • quit
    terminates manipulations in the block world.
    Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.

Input

    The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.
    The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.
    You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

Output

    The output should consist of the final state of the blocks world. Each original block position numbered i (0 ≤ i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don’t put any trailing spaces on a line.
    There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).

Sample Input

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
Sample Output
0: 0
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9:

理解

	一道有趣的模拟题,给你各种指令,然后要求你输出执行完所有指令之后各个位置上的数字有什么因为各个位置上还有各有队列,姑且把他看成二维数值,再用map标记这个数字当前在哪一个数组里方便查找,很容易就能模拟出来此题的难点在于题意的理解,那几个指令刚开始看把我看傻了,看翻译都看不懂是什么意思

然后指令翻译完之后
1.move a onto b,把a和b上面的木块全都放回原来的位置,然后把a放到b上面。
2.move a over b,把a上面的木块放回原来的位置,然后把a放到b所在的木块堆的最上面
3.pile a onto b,把b上面的木块放回原来的位置然后把a以及a上面的木块全部放到b上
4.pile a over b,把a以及a上面的木块全部放到b所在的木块堆上.
5.quit 结束,然后输出操作完之后的结果

AC代码

#include <bits/stdc++.h>
using namespace std;
vector <int> a[100];
map <int,int> p;void gw(int x){  ##  归位操作,把x以上的数字全部归位int k = p[x];vector<int>::iterator result = find(a[k].begin(),a[k].end(),x);int start =  result - a[k].begin();for(int i = start + 1;i < a[k].size();){a[a[k][i]].push_back(a[k][i]);p[a[k][i]] = a[k][i];a[k].erase(a[k].begin() + i);}
}
##  注:万能头文件中,有move这个函数,不能写move不然会报错
void movex(int x,int y){  ##  移动操作,移动a及a以上的所有数字int k = p[x],k2 = p[y];vector<int>::iterator result = find(a[k].begin(),a[k].end(),x);int start =  result - a[k].begin();for(int i = start;i < a[k].size();){a[k2].push_back(a[k][i]);p[a[k][i]] = k2;a[k].erase(a[k].begin() + i);}
}
##  关于erase,我这边是边移动边操作,大佬实际上用了resize直接全部截断,一种非常优越的想法,因为比较容易改,后面就不贴出resize的代码了int main()
{		int n;cin >> n;for(int i = 0;i < n;i++){  ##  预处理,把图弄好a[i].push_back(i);p[i] = i;}string s1,s2;int x,y;while(cin >> s1 && s1 != "quit"){  ##  quit退出cin >> x >> s2 >> y;if(p[x] == p[y]) continue;##  下面四个就是按指令来操作if(s1 == "move" && s2 == "onto"){gw(x);gw(y);a[p[y]].push_back(x);a[p[x]].erase(a[p[x]].end() - 1);p[x] = p[y];}if(s1 == "move" && s2 == "over"){gw(x);a[p[y]].push_back(x);a[p[x]].erase(a[p[x]].end() - 1);p[x] = p[y];}if(s1 == "pile" && s2 == "onto"){gw(y);movex(x,y);}if(s1 == "pile" && s2 == "over"){movex(x,y);}}##  打印结果图for(int i = 0;i < n;i++){cout << i << ":";for(int j = 0;j < a[i].size();j++){cout << ' ' << a[i][j];}cout << endl;}return 0;
}

F-Ananagrams (水题,二重映射) UVA - 156

    Most crossword puzzle fans are used to anagrams — groups of words with the same letters in different orders — for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams, an example is QUIZ.
    Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE.
    Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be “rearranged” at all. The dictionary will contain no more than 1000 words

Input

    Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus ‘tIeD’ and ‘EdiT’ are anagrams. The file will be terminated by a line consisting of a single ‘#’.

Output

    Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram.

Sample Input

ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb eye Rides dealer NotE derail LaCeS drIed
noel dire Disk mace Rob dries

Sample Output

Disk
NotE
derail
drIed
eye
ladder
soon

理解

	比较简单的水题,看两个单词想不想同只要全部大写或小写,然后用sort排序,最后用map计数即可记录这道题是因为,写这题的时候,因为要处理原单词和处理过后单词的关系,想了一个二重映射,感觉算是开阔了思路

AC代码

#include <bits/stdc++.h>
using namespace std;
map <string,int> p;  ##  计数处理过后单词的出现次数
map <string,string> k;  ##  原单词映射处理过后的单词
vector <string> a;string change(string s){for(int i = 0;i < s.size();i++){s[i] = tolower(s[i]);}sort(s.begin(),s.end());return s;
}int main()
{string s;while(cin >> s && s != "#"){string temp(change(s));p[temp]++;k[s] = temp;a.push_back(s);}sort(a.begin(),a.end());vector <string> :: iterator it;for(it = a.begin();it != a.end();it++){if(p[k[*it]] == 1) cout << *it << endl;  ##  如果只出现过一次,说明没有相同单词,输出它}return 0;
}

G-Team Queue (分支队列) UVA - 540

    Queues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunch time the queue in front of the Mensa is a team queue, for example.
    In a team queue each element belongs to a team. If an element enters the queue, it first searches the queue from head to tail to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind them. If not, it enters the queue at the tail and becomes the new last element (bad luck). Dequeuing is done like in normal queues: elements are processed from head to tail in the order they appear in the team queue.
    Your task is to write a program that simulates such a team queue.

Input

    The input file will contain one or more test cases. Each test case begins with the number of teams t (1 ≤ t ≤ 1000). Then t team descriptions follow, each one consisting of the number of elements belonging to the team and the elements themselves. Elements are integers in the range 0…999999. A team may consist of up to 1000 elements.
    Finally, a list of commands follows. There are three different kinds of commands:
        • ENQUEUE x — enter element x into the team queue
        • DEQUEUE — process the first element and remove it from the queue
        • STOP — end of test case
    The input will be terminated by a value of 0 for t.
    Warning: A test case may contain up to 200000 (two hundred thousand) commands, so the implementation of the team queue should be efficient: both enqueing and dequeuing of an element should only take constant time.

Output

    For each test case, first print a line saying ‘Scenario #k’, where k is the number of the test case. Then,for each ‘DEQUEUE’ command, print the element which is dequeued on a single line. Print a blank line after each test case, even after the last one.

Sample Input

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

Sample Output

Scenario #1
101
102
103
201
202
203
Scenario #2
259001
259002
259003
259004
259005
260001

理解

	一道很有意思的题,大意是叫你模拟插队的情况:如果现在的队列中有他认识的人,他插在他认识的人群的最后面,否则他乖乖去队列尾部排队这道题有着先进先出的原则,在容器的使用上肯定以queue优先但是要处理好插队的情况,而queue不能随意删改,只能对队首进行操作所以建立两个队列,将其分为主干和分支主干:排队的队列,记录哪些团队在队列里有人分支:团体队列,记录这个团体中的先来后到在某个团体的人在主队列中走光之后,弹出主队列的队首元素,让下一个团队上某个团队的人还为在主队列中出现时,将新出现的团体排在主队列队尾

AC代码

#include <bits/stdc++.h>
using namespace std;int main()
{int t,cnt = 0;while(cin >> t && t){map <int,int> p;  ##  标记,表示某个人属于哪个团体queue <int> td;  ##  主队列,记录团体的先来后到queue <int> gr[t];  ##  团体队列,根据团体数量创建for(int i = 0;i < t;i++){  ##  把统一团体的人标相同的序号int k,x;cin >> k;for(int j = 0;j < k;j++){cin >> x;p[x] = i;}}printf("Scenario #%d\n",++cnt);string s;while(1){cin >> s;if(s == "STOP") break;if(s == "DEQUEUE"){int k = td.front();cout << gr[k].front() << endl;gr[k].pop();if(gr[k].empty()) td.pop();  ##  如果这个团体的人已经走空了,将这个团体的序号从主队列中弹出}if(s == "ENQUEUE"){int x;cin >> x;int k = p[x];if(gr[k].empty()) td.push(k);  ##  如果这个团体的队列中没人,说明他们还没有人进入主队列中,将他们团队的序号放入主队列gr[k].push(x);}}cout << endl;}return 0;
}

H-Database (map 查找) UVA - 1592

    Peter studies the theory of relational databases. Table in the relational database consists of values that are arranged in rows and columns.
    There are different normal forms that database may adhere to. Normal forms are designed to minimize the redundancy of data in the database. For example, a database table for a library might have a row for each book and columns for book name, book author, and author’s email.
    If the same author wrote several books, then this representation is clearly redundant. To formally define this kind of redundancy Peter has introduced his own normal form. A table is in Peter’s Normal Form (PNF) if and only if there is no pair of rows and a pair of columns such that the values in the corresponding columns are the same for both rows.

    The above table is clearly not in PNF, since values for 2rd and 3rd columns repeat in 2nd and 3rd rows. However, if we introduce unique author identifier and split this table into two tables — one containing book name and author id, and the other containing book id, author name, and author email,then both resulting tables will be in PNF.

    Given a table your task is to figure out whether it is in PNF or not.

Input

    Input contains several datasets. The first line of each dataset contains two integer numbers n and m(1 ≤ n ≤ 10000, 1 ≤ m ≤ 10), the number of rows and columns in the table. The following n lines contain table rows. Each row has m column values separated by commas. Column values consist of ASCII characters from space (ASCII code 32) to tilde (ASCII code 126) with the exception of comma (ASCII code 44). Values are not empty and have no leading and trailing spaces. Each row has at most 80 characters (including separating commas).

Output

    For each dataset, if the table is in PNF write to the output file a single word “YES” (without quotes).
    If the table is not in PNF, then write three lines. On the first line write a single word “NO” (without quotes). On the second line write two integer row numbers r1 and r2 (1 ≤ r1, r2 ≤ n, r1 ̸= r2), on the third line write two integer column numbers c1 and c2 (1 ≤ c1, c2 ≤ m, c1 ̸= c2), so that values in columns c1 and c2 are the same in rows r1 and r2.

Sample Input

3 3
How to compete in ACM ICPC,Peter,peter@neerc.ifmo.ru
How to win ACM ICPC,Michael,michael@neerc.ifmo.ru
Notes from ACM ICPC champion,Michael,michael@neerc.ifmo.ru
2 3
1,Peter,peter@neerc.ifmo.ru
2,Michael,michael@neerc.ifmo.ru

Sample Output

NO
2 3
2 3
YES

理解

	这题的大意就是,叫你看看输入的东西里面有没有两列在两行中时相等的即((r1,c1) == (r1,c2) && (r2,c1) == (r2,c2))但这道题恶心就恶心在你要以列开始找,然后确认两行(简单的说,就是优先输出列最小的重复项)而且直接比较字符串会tle(所以map是必备的,从比较字符串变成比较数字是否相同,能节省很多时间)

AC代码

#include <bits/stdc++.h>
using namespace std;int cnts = 1;  ## cnts用于打标记(注意,因为我用的是!来判断这个字符串是否被赋值过,如果从0开始,赋值0会影响判断,在这错了改了好久)
map <string,int> p;  ##  用于给书名,作者,邮箱啥的打标记号
map <pair<int,int>,int> ss;  ##  用于表示(r,c)是否出现过,若出现两次,则表示这两列是存在两行重复的void save(string s,int n,int *a){  ##  将打完标记的数字存进二维数组内int start = 0,cnt = 1;  ##  start记录上一个","之后一个下标的位置,cnt表示其为该数组的第几个元素(a[i][cnt])for(int i = 0;i < s.size();i++){if(s[i] == ','){string temp = s.substr(start,i - start);if(!p[temp]){p[temp] = cnts;cnts++;}a[cnt++] = p[temp];start = i + 1;}}string temp = s.substr(start,s.size() - start);  ## 因为最后一个元素尾部没有",",所以要单独拎出来处理if(!p[temp]){p[temp] = cnts;cnts++;}a[cnt] = p[temp];
}int main(){
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);int r,c;while(cin >> r >> c){cnts = 1;getchar();string s;int sv[r + 10][c + 10];for(int i = 1;i <= r;i++){getline(cin,s);save(s,i,sv[i]);}//		for(int i = 1;i <= r;i++){
//			for(int j = 1;j <= c;j++){
//				cout << sv[i][j] << ' ';
//			}
//			cout << endl;
//		}int f = 0;for(int i = 1;i <= c - 1;i++){for(int j = i + 1;j <= c;j++){ss.clear();  ## 每次要把判断是否的重复的标记清零,防止影响后面的判断for(int k = 1;k <= r;k++){int a = sv[k][i],b = sv[k][j];
//                	cout << a << ' ' << b << ' ' << ss[make_pair(a,b)] << endl;if(!ss[make_pair(a,b)]){ss[make_pair(a,b)] = k;  ## 如果这个组合还没出现过,就将行号(r)赋值给他,方便后面输出是第几行和第几行重复(此处k不能为0,原因与cnts一致)}else{cout << "NO" << endl;cout << ss[make_pair(a,b)] << ' ' << k << endl;cout << i << ' ' << j << endl;f = 1;break;}}if(f) break;}if(f) break;}if(!f) cout << "YES" << endl;ss.clear();p.clear();}return 0;
}

这道题走了不少弯路,刚开始理解的太简单了,先找行后找列,虽然好写,但题意就理解错了,wa得很流畅。
后面写的时候,因为"!0"这种方式也走了不少弯路,幸好改起来不难。
后来在大佬的代码中看见了count这个函数,给map使用正好能规避这个问题,拿小本本记下来。

I-Unix ls (水题,排版) UVA - 400

    The computer company you work for is introducing a brand new computer line and is developing a new Unix-like operating system to be introduced along with the new computer. Your assignment is to write the formatter for the ls function.
    Your program will eventually read input from a pipe (although for now your program will read from the input file). Input to your program will consist of a list of (F) filenames that you will sort (ascending based on the ASCII character values) and format into © columns based on the length (L) of the longest filename. Filenames will be between 1 and 60 (inclusive) characters in length and will be formatted into left-justified columns. The rightmost column will be the width of the longest filename and all other columns will be the width of the longest filename plus 2. There will be as many columns as will fit in 60 characters. Your program should use as few rows ® as possible with rows being filled to capacity from left to right.

Input

    The input file will contain an indefinite number of lists of filenames. Each list will begin with a line containing a single integer (1 ≤ N ≤ 100). There will then be N lines each containing one left-justified filename and the entire line’s contents (between 1 and 60 characters) are considered to be part of the filename. Allowable characters are alphanumeric (a to z, A to Z, and 0 to 9) and from the following set {._-} (not including the curly braces). There will be no illegal characters in any of the filenames and no line will be completely empty.Immediately following the last filename will be the N for the next set or the end of file. You should read and format all sets in the input file.

Output

For each set of filenames you should print a line of exactly 60 dashes (-) followed by the formatted columns of filenames. The sorted filenames 1 to R will be listed down column 1; filenames R + 1 to 2R listed down column 2; etc.

Sample Input

10
tiny
2short4me
very_long_file_name
shorter
size-1
size2
size3
much_longer_name
12345678.123
mid_size_name
12
Weaser
Alfalfa
Stimey
Buckwheat
Porky
Joe
Darla
Cotton
Butch
Froggy
Mrs_Crabapple
P.D.
19
Mr._French
Jody
Buffy
Sissy
Keith
Danny
Lori
Chris
Shirley
Marsha
Jan
Cindy
Carol
Mike
Greg
Peter
Bobby
Alice
Ruben

Sample Output

理解

	一道水题,就考一下排版,总共60列,除了最右边的为单词最长长度之外,其他列都是最长长度+2,记录这道题是因为他让我看见了两道做过的PTA题目的影子,感觉题目有强烈的相似性,所以做一下记录(1)L1-039 古风排版(2)L1-032 Left-pad

AC代码

#include <bits/stdc++.h>
using namespace std;void sc(string s,int l){  ##  输出的东西,因为要左对齐和空位补零,这个得自己写cout << s;for(int i = s.size();i < l;i++) cout << ' ';
}int main()
{
//	freopen("test.out","w",stdout);int n;while(cin >> n){int maxl = 0;string s[n];for(int i = 0;i < n;i++){cin >> s[i];int l = s[i].size();maxl = max(maxl,l);}sort(s,s+n);int csum = (60 - maxl)/(maxl + 2) + 1;  ##  计算列数int rsum = (n - 1)/csum + 1;  ##  计算行数cout << "------------------------------------------------------------" << endl;for(int i = 0;i < rsum;i++){for(int j = 0;j < csum;j++){int k = i + j * rsum;int l = j == csum - 1 ?maxl :maxl+2;if(k < n) sc(s[k],l);  ##  注意,不能让数组下标越界,第一次因为这个没写re了一次}cout << endl;}}return 0;
}

J-对称轴 (水题,map AND pair) UVA - 1595

    The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along a vertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on the right is not left-right symmetric as it is impossible to find such a vertical line.

    Write a program that determines whether a figure, drawn with dots, is left-right symmetric or not.
The dots are all distinct.

Input

    The input consists of T test cases. The number of test cases T is given in the first line of the input file.
    The first line of each test case contains an integer N, where N (1 ≤ N ≤ 1, 000) is the number of dots in a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Both x-coordinates and y-coordinates are integers between −10, 000 and 10, 000, both inclusive.

Output

    Print exactly one line for each test case. The line should contain ‘YES’ if the figure is left-right symmetric,and ‘NO’, otherwise.

Sample Input

3
5
-2 5
0 0
6 5
4 0
2 3
4
2 3
0 4
4 0
0 0
4
5 14
6 10
5 10
6 14

Sample Output

YES
NO
YES

理解

	一道水题,就考一下找对称轴,记录这道题的原因是,在当时忘记用浮点数耳朵情况下,推数学公式推出了一点好玩的东西,姑且算是有点收获设对称轴为k,由题意可得k = sum / n  &&  k = (a + b) / 2结合一下两个公式可以得到2 * sum = a * n + b * n  完美地避过了整除将会带来的数据误差问题(也完美地带来了数据过大可能gg的问题【狗头】)

AC代码

##  代码及其简单,就不做注释了
#include <bits/stdc++.h>
using namespace std;int main()
{int t;cin >> t;while(t--){int n,k = 0;cin >> n;map <pair<int,int>,int> p;pair <int,int> a[n];for(int i = 0;i < n;i++){cin >> a[i].first >> a[i].second;k += a[i].first;a[i].first *= n;p[a[i]]++;}int f = 1;for(int i = 0;i < n;i++){if(!p[make_pair(k*2 - a[i].first,a[i].second)]){
//				cout << a[i].first << ' ' << a[i].second << endl;
//				cout << k*2 - a[i].first << ' ' << a[i].second << endl; cout << "NO" << endl;f = 0;break;}}if(f) cout << "YES" << endl;}return 0;
}

K-打印队列 (水题,模拟,队列) UVA - 12100

    The only printer in the computer science students’union is experiencing an extremely heavy workload.
    Sometimes there are a hundred jobs in the printer queue and you may have to wait for hours to get a
single page of output.
    Because some jobs are more important than others,the Hacker General has invented and implemented a
simple priority system for the print job queue. Now,each job is assigned a priority between 1 and 9 (with 9 being the highest priority, and 1 being the lowest), and the printer operates as follows.
        • The first job J in queue is taken from the queue.
        • If there is some job in the queue with a higher priority than job J, then move J to the end of the queue without printing it.
        • Otherwise, print job J (and do not put it back in the queue).
    In this way, all those important muffin recipes that the Hacker General is printing get printed very quickly. Of course, those annoying term papers that others are printing may have to wait for quite some time to get printed, but that’s life.
    Your problem with the new policy is that it has become quite tricky to determine when your print job will actually be completed. You decide to write a program to figure this out. The program will be given the current queue (as a list of priorities) as well as the position of your job in the queue, and must then calculate how long it will take until your job is printed, assuming that no additional jobs will be added to the queue. To simplify matters, we assume that printing a job always takes exactly one minute, and that adding and removing jobs from the queue is instantaneous.

Input

    One line with a positive integer: the number of test cases (at most 100). Then for each test case:
        • One line with two integers n and m, where n is the number of jobs in the queue (1 ≤ n ≤ 100) and m is the position of your job (0 ≤ m ≤ n − 1). The first position in the queue is number 0,the second is number 1, and so on.
        • One line with n integers in the range 1 to 9, giving the priorities of the jobs in the queue. The first integer gives the priority of the first job, the second integer the priority of the second job, and so on.

Output

For each test case, print one line with a single integer; the number of minutes until your job is completely
printed, assuming that no additional print jobs will arrive.

Sample Input

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

Sample Output

1
2
5

理解

	一道水题,如果不是为了松饼配方我是不会记录这道题的(滑稽)简单介绍一下题意,你的文件处在打印队列中的某个位置,这个打印队列有一个优先级,如果有优先级更高的文件在队列中,队首文件会被移到队尾,直到那份优先级最高的文件被打印出来,再继续下一个优先级次一级的文件,且只有打印会消耗时间,移动操作不会耗时。代码也是十分的暴力,模拟一下就a掉了题

AC代码

#include <bits/stdc++.h>
using namespace std;int main(){int t;cin >> t;while(t--){queue <int> a;  ##  队列,用于模拟打印队列priority_queue <int,vector<int>,less<int> > b;  ##  优先队列,确认优先级,其实写个vector排序也可以,这边用优先队列只是为了熟悉一下int n,m,temp;cin >> n >> m;for(int i = 0;i < n;i++){cin >> temp;a.push(temp);b.push(temp);}int time = 0;  ##  计时while(1){if(a.front() != b.top()){a.push(a.front());a.pop();m = (m + a.size() - 1) % a.size();  ##  m用于表示你的文件现在在队列的哪个位置,因为下标是0到n-1,善用取模来更新位置}else{a.pop();b.pop();time++;if(!m) break;  ##  如果这份被删掉的是你的文件,那模拟就可以结束了m = (m + a.size() - 1) % a.size();}}cout << time << endl;}return 0;
}

L-图书管理系统 (模拟,set) UVA - 230

        I mean your borrowers of books — those mutilators of collections, spoilers of the symmetry of shelves, and creators of odd volumes.
        – (Charles Lamb, Essays of Elia (1823) ‘The Two Races of Men’)
    Like Mr. Lamb, librarians have their problems with borrowers too. People don’t put books back where they should. Instead, returned books are kept at the main desk until a librarian is free to replace them in the right places on the shelves. Even for librarians, putting the right book in the right place can be very time-consuming. But since many libraries are now computerized, you can write a program to
help.
    When a borrower takes out or returns a book, the computer keeps a record of the title. Periodically, the librarians will ask your program for a list of books that have been returned so the books can be returned to their correct places on the shelves. Before they are returned to the shelves, the returned books are sorted by author and then title using the ASCII collating sequence. Your program should output the list of returned books in the same order as they should appear on the shelves. For each book, your program should tell the librarian which book (including those previously shelved) is already on the shelf before which the returned book should go.

Input

    First, the stock of the library will be listed, one book per line, in no particular order. Initially, they are all on the shelves. No two books have the same title. The format of each line will be:title" by author
    The end of the stock listing will be marked by a line containing only the word:
END
    Following the stock list will be a series of records of books borrowed and returned, and requests from librarians for assistance in restocking the shelves. Each record will appear on a single line, in one of the following formats:
BORROW title
RETURN title
SHELVE
    The list will be terminated by a line containing only the word:
END

Output

    Each time the SHELVE command appears, your program should output a series of instructions for the librarian, one per line, in the format:
Put title1 after title2
    or, for the special case of the book being the first in the collection:
Put title first
    After the set of instructions for each SHELVE, output a line containing only the word:
END
Assumptions & Limitations:

  1. A title is at most 80 characters long.
  2. An author is at most 80 characters long.
  3. A title will not contain the double quote (") character.

Sample Input

“The Canterbury Tales” by Chaucer, G.
“Algorithms” by Sedgewick, R.
“The C Programming Language” by Kernighan, B. and Ritchie, D.
END
BORROW “Algorithms”
BORROW “The C Programming Language”
RETURN “Algorithms”
RETURN “The C Programming Language”
SHELVE
END

Sample Output

Put “The C Programming Language” after “The Canterbury Tales”
Put “Algorithms” after “The C Programming Language”
END

理解

	一道有一点难度的模拟题,题目大意为告诉你一个图书馆有什么书,然后有被借走和归还的操作,被归还的书会放到书桌上,当要放回书架时,应先按作者和书名进行排序,然后放回书架,并且要输出,这本书应该放在哪本书后面,如果它应该被放在开头,则输出它在开头位置。坑点:借书和还书貌似会有重复操作,还书可以用set完美避免,借书一定要先检查这本书在不在书架上,不然会re写这题时的不足之处:当时对pair运用不太了解,强行自己写了一个book结构体,然后重载了()运算符,实际上,用pair把作者放第一个元素,书名放第二个元素就能让set按优先级自动排序,比自己写重载好的多

AC代码

#include <bits/stdc++.h>
using namespace std;struct book{  ##  书,每本书包括书名和作者,都要记录string tle,ath;
};struct strcomp{  ##  重载()写的比较函数,使set能自动排序bookbool operator () (book i,book j) const {if(i.ath == j.ath) return i.tle < j.tle;return i.ath < j.ath;}
};set <book, strcomp> lib;  ##  书架
set <book, strcomp> desk;  ##  还书时暂时存书的书桌
map <string,string> p;  ##  标记,方便根据书名找作者,在还书到桌子上时,要形成一个完整的book存入set里int chr(string s){  ##  搜索"字符的位置,方便从字符串中分割出书名和作者int i;for(i = 1;i < s.size();i++){if(s[i] == '"') break;}return i == s.size() ?NULL :i;
}void borrow(string s){  ##  借书操作set <book> :: iterator it;for(it = lib.begin();it != lib.end();it++){if((*it).tle == s) break;}if(it != lib.end()) lib.erase(it);  ##  切记,要注意书架上有没有这本书,如果没有,就不能执行操作,不然会re(此处其实使用find函数更佳,因为打的代码会短点,当时对find函数还不了解)
}int main(){	string s;while(getline(cin,s) && s != "END"){  ##  对输入的书进行处理book temp;int k = chr(s);temp.tle = s.substr(0,k + 1);temp.ath = s.substr(k + 5,s.size());p[temp.tle] = temp.ath;lib.insert(temp);}while(getline(cin,s) && s != "END"){if(s[0] == 'B' || s[0] == 'R'){int k = chr(s);string temp = s.substr(k,s.size() - k);if(s[0] == 'B') borrow(temp);  ##  借书操作else{  ##  还书操作book temp1;temp1.tle = temp;temp1.ath = p[temp];desk.insert(temp1); }}if(s[0] == 'S'){  ##  将书放回书架的操作while(!desk.empty()){book temp = *desk.begin();desk.erase(desk.begin());lib.insert(temp);set <book> :: iterator it;for(it = lib.begin();it != lib.end();it++){if((*it).tle == temp.tle && (*it).ath == temp.ath) break;  ##  找他放回书架后的位置,方便知道他前面的书是啥,这边貌似可以用lower_bound函数代替,但当时不会用}if(it == lib.begin()) cout << "Put " << temp.tle << " first" << endl;else{it--;cout << "Put " << temp.tle << " after " << (*it).tle << endl;}}cout << "END" << endl;}}return 0;
}

M-找Bug (模拟,递归写栈) UVA - 1596

    In this problem, we consider a simple programming language that has only declarations of onedimensional integer arrays and assignment statements. The problem is to find a bug in the given program.
    The syntax of this language is given in BNF as follows:
        ⟨program⟩ ::= ⟨declaration⟩|⟨program⟩⟨declaration⟩|⟨program⟩⟨assignment⟩
        ⟨declaration⟩ ::= ⟨array name⟩ [⟨number⟩]⟨new line⟩
        ⟨assignment⟩ ::= ⟨array name⟩ [⟨expression⟩]= ⟨expression⟩⟨newline⟩
        ⟨expression⟩ ::= ⟨number⟩|⟨array name⟩ [⟨expression⟩]
        ⟨number⟩ ::= ⟨digit⟩|⟨digit positive⟩⟨digit string⟩
        ⟨digit string⟩ ::= ⟨digit⟩|⟨digit⟩⟨digit string⟩
        ⟨digit positive⟩ ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
        ⟨digit⟩ ::= 0 | ⟨digit positive⟩
        ⟨array name⟩ ::= a | b | c | d | e | f | g | h | i | j | k | l | m |
                                    n | o | p | q | r | s | t | u | v | w | x | y | z |
                                    A | B | C | D | E | F | G | H | I | J | K | L | M |
                                    N | O | P | Q | R | S | T | U | V | W | X | Y | Z
    where ⟨new line⟩ denotes a new line character (LF).
    Characters used in a program are alphabetical letters, decimal digits, =, [, ] and new line characters.
    No other characters appear in a program.
    A declaration declares an array and specifies its length. Valid indices of an array of length n are integers between 0 and n − 1, inclusive. Note that the array names are case sensitive, i.e. array a and array A are different arrays. The initial value of each element in the declared array is undefined.
    For example, array a of length 10 and array b of length 5 are declared respectively as follows.
a[10]
b[5]
    An expression evaluates to a non-negative integer. A ⟨number⟩ is interpreted as a decimal integer.
    An ⟨array name⟩ [⟨expression⟩] evaluates to the value of the ⟨expression⟩-th element of the array.
    An assignment assigns the value denoted by the right hand side to the array element specified by the
    left hand side.
    Examples of assignments are as follows.
a[0]=3
a[1]=0
a[2]=a[a[1]]
a[a[0]]=a[1]
    A program is executed from the first line, line by line. You can assume that an array is declared once and only
    once before any of its element is assigned or referred to.
    Given a program, you are requested to find the following bugs.
    • An index of an array is invalid.
    • An array element that has not been assigned before is referred to in an assignment as an index of array or as the value to be assigned.
    You can assume that other bugs, such as syntax errors, do not appear. You can also assume that integers represented by ⟨number⟩s are between 0 and 231 − 1 (= 2147483647), inclusive.

Input

    The input consists of multiple datasets followed by a line which contains only a single ‘.’ (period).
    Each dataset consists of a program also followed by a line which contains only a single ‘.’ (period).
    A program does not exceed 1000 lines. Any line does not exceed 80 characters excluding a new line character.

Output

    For each program in the input, you should answer the line number of the assignment in which the first bug appears. The line numbers start with 1 for each program. If the program does not have a bug,you should answer zero. The output should not contain extra characters such as spaces.

Sample Input

a[3]
a[0]=a[1]
.
x[1]
x[0]=x[0]
.
a[0]
a[0]=1
.
b[2]
b[0]=2
b[1]=b[b[0]]
b[0]=b[1]
.
g[2]
G[10]
g[0]=0
g[1]=G[0]
.
a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.
.

Sample Output

2
2
2
3
4
0

理解

	本题大意就是找出哪一行的代码开始出错。实际上模拟起来也是比较简单的,对各种情况做一个分治就好了1.定义操作这个操作时不可能出bug的,文中貌似也没提到重复定义这个操作的存在,但我们要用定义时数组的大小来约束赋值时数组的下标,防止下标越界2.赋值操作这个操作又可以分为两种情况,直接赋值和间接赋值(1)直接赋值例如a[1]=1,右边的值是数字,那我们只需要判断左边的数组和下标是否合法即可(2)间接赋值例如a[1]=b[1],右边的值是数字和下标,这时我们要判断两边的是否都合法难点:如何处理多重括号,其实经历过“计算”这种题目的洗礼,对于这种规律性极强的括号,处理起来就比较方便了,列出下列两个方法[1]采用递归的思路,模拟一个栈,层层分解多重括号[2]采用stl内的stack,不断把数组名称压栈,知道压倒纯数字,再出栈到空我的代码采用了第一种思路(我能说写计算那题的栈有心理阴影,不想再用stack了吗)

AC代码

#include <bits/stdc++.h>
using namespace std;map <string,int> def;  ##  定义操作,用map来标记这个数组的大小
map <pair<string,int>,int> at;  ##  赋值操作,用map来标记这个数组位置的值(经过学习,此时已经会用pair了【狗头】)int change(string s){  ##  递归转换多重括号if(s[0] >= '0' && s[0] <= '9'){  ##  如果已经是存数字,那转成整数返回即可int temp = 0;for(int i = 0;i < s.size();i++)temp = temp * 10 + s[i] - '0';return temp;}else{  ##  如果是数组下标,就将其分成数组名称和下标两部分,继续递归int k = s.find("[");string sz = s.substr(0,k);string xb = s.substr(k+1,s.size() - k - 2);int txb = change(xb);if(txb == -1) return -1;  ##  如果返回的值是-1,说明已经非法,继续返回-1if(!def.count(sz)) return -1;  ##  如果这个数组名称没有被定义过,也是非法,返回-1if(txb >= def[sz]) return -1;  ##  如果这个值超过了这个数组的大小,非法pair <string,int> temp;temp = make_pair(sz,txb);if(!at.count(temp)) return -1;  ##  如果这个数组下标没被赋值过,非法return at[temp];  ##  如果都合法,返回这个数组下标的值}
}int main()
{	int f = 0,step = 0,f2 = 0;string s;while(cin >> s){if(!f && s == ".") break;  ##  这道题输入的处理也是比较麻烦,采用开关的方式,推荐自己写的时候先尝试把输入写好if(f && s == "."){  ##  如果结束了输入,记得清空map,毕竟是多组样例输入if(!f2) cout << 0 << endl;f2 = 0;f = 0;step = 0;def.clear();at.clear();}if(s != "."){f++;if(!f2){if(s.find("=") == string::npos){  ##  字符串的find函数,找不到就是string::npos,写成s.npos也是可以的,实际上返回的值是-1,但显示为2^32-1,如果没找到,就进行定义操作int k = s.find("[");string sz = s.substr(0,k);string size1 = s.substr(k+1,s.size() - k - 2);int temp = change(size1);def[sz] = temp;}else{  ##  如果找到了,实行赋值操作int k = s.find("=");string temp1 = s.substr(0,k);string temp2 = s.substr(k + 1,s.size() - k - 1);int k1 = temp1.find("[");string sz1 = temp1.substr(0,k1);string xb1 = temp1.substr(k1 + 1,temp1.size() - k1 - 2);int txb1 = change(xb1);if(txb1 == -1 || txb1 >= def[sz1]) f2 = 1;  ##  左边数组下标是否合法需要自己在判断一次else{  ##  右边的话直接扔到change里即可,毕竟右边的元素实际上就是要转成纯数字的int temp = change(temp2);if(temp == -1) f2 = 1;else{at[make_pair(sz1,txb1)] = temp;}}}if(f2) cout << f << endl;}}}return 0;
}

N- Web中搜索,有意义 (模拟) UVA - 1597

    The word “search engine” may not be strange to you. Generally speaking, a search engine searches the web pages available in the Internet, extracts and organizes the information and responds to users’ queries with the most relevant pages. World famous search engines, like GOOGLE, have become very important tools for us to use when we visit the web. Such conversations are now common in our daily life:
    “What does the word like ∗ ∗ ∗ ∗ ∗∗ mean?”
    “Um. . . I am not sure, just google it.”
    In this problem, you are required to construct a small search engine. Sounds impossible, does it?Don’t worry, here is a tutorial teaching you how to organize large collection of texts efficiently and respond to queries quickly step by step. You don’t need to worry about the fetching process of web pages, all the web pages are provided to you in text format as the input data. Besides, a lot of queries are also provided to validate your system.
    Modern search engines use a technique called inversion for dealing with very large sets of documents.The method relies on the construction of a data structure, called an inverted index, which associates terms (words) to their occurrences in the collection of documents. The set of terms of interest is called the vocabulary, denoted as V . In its simplest form, an inverted index is a dictionary where each search key is a term ω ∈ V . The associated value b(ω) is a pointer to an additional intermediate data structure,called a bucket. The bucket associated with a certain term ω is essentially a list of pointers marking all the occurrences of ω in the text collection. Each entry in each bucket simply consists of the document identifier (DID), the ordinal number of the document within the collection and the ordinal line number of the term’s occurrence within the document.
    Let’s take Figure-1 for an example, which describes the general structure. Assuming that we only have three documents to handle, shown at the right part in Figure-1; first we need to tokenize the text for words (blank, punctuations and other non-alphabetic characters are used to separate words) and construct our vocabulary from terms occurring in the documents. For simplicity, we don’t need to consider any phrases, only a single word as a term. Furthermore, the terms are case-insensitive (e.g. we consider “book” and “Book” to be the same term) and we don’t consider any morphological variants (e.g. we consider “books” and “book”, “protected” and “protect” to be different terms) and hyphenated words (e.g. “middle-class” is not a single term, but separated into 2 terms “middle” and “class” by the hyphen). The vocabulary is shown at the left part in Figure-1. Each term of the vocabulary has a pointer to its bucket. The collection of the buckets is shown at the middle part in Figure-1. Each item in a bucket records the DID of the term’s occurrence.
    After constructing the whole inverted index structure, we may apply it to the queries. The query is in any of the following formats:
term
term AND term
term OR term
NOT term
    A single term can be combined by Boolean operators: ‘AND’, ‘OR’ and ‘NOT’ (‘term1 AND term2’ means to query the documents including term1 and term2; ‘term1 OR term2’ means to query the documents including term1 or term2; ‘NOT term1’ means to query the documents not including term1). Terms are single words as defined above. You are guaranteed that no non-alphabetic characters appear in a term, and all the terms are in lowercase. Furthermore, some meaningless stop words (common words such as articles, prepositions, and adverbs, specified to be “the, a, to, and, or, not” in our problem) will not appear in the query, either.
    For each query, the engine based on the constructed inverted index searches the term in the vocabulary,compares the terms’ bucket information, and then gives the result to user. Now can you construct the engine?

Input

Output

Sample Input

Sample Output

理解

	本题大意根据你要查找的单词,找到哪边文章有或没有,然后选择性输出,不同文章直接用---------分割,不同查询直接用=========分割,而找不到就输出Sorry,I found nothing.注意:此处的单词的大小写都要考虑在内模拟起来也是有一点复杂,你要先看这篇文章里有没有这个词,再输出这个词所在的那一行话,虽然繁琐,但还是可以模拟的

下面是一些命令
term 输出有term这个单词的行
term AND term 输出同时有前者和后者的文章里存在两者之一的行
term OR term 输出只要有前者和后者的文章里存在两者之一的行
NOT term 输出没有这个单词的文章里所有的行

AC代码

#include <bits/stdc++.h>
using namespace std;vector <string> sen[105];  ##  存储原文章里的行,开二维是为了区分文章
set <string> sk[105];  ##  表明这个词在这篇文章中,为了后面判断这篇文章含不含这个单词
map <string,set<int> > wd[105];  ##  记录这个单词在这篇文章中的第几行,为了后面输出行方便string change(string s){  ##  对原字符串进行处理,全部小写,并且把非字母的字符处理掉for(int i = 0;i < s.size();i++){if(!isalpha(s[i])) s[i] = ' ';else s[i] = tolower(s[i]);}return s;
}void AND(string a,string b,int n){  ##  AND操作int f = 0,f2 = 0;for(int i = 0;i < n;i++){if(sk[i].count(a) && sk[i].count(b)){  ##  如果这篇文章存在这两个单词set <int> temp;set_union(wd[i][a].begin(),wd[i][a].end(),wd[i][b].begin(),wd[i][b].end(),inserter(temp,temp.begin()));  ##  取交集if(f2) cout << "----------" << endl;  ##  控制---------的输出f = 1;set <int> :: iterator it;for(it = temp.begin();it != temp.end();it++){cout << sen[i][*it] << endl;}f2 = 1;}}if(!f) cout << "Sorry, I found nothing." << endl;cout << "==========" << endl;
}void OR(string a,string b,int n){  ##  OR操作,大致与上面相同int f = 0,f2 = 0;for(int i = 0;i < n;i++){if(sk[i].count(a) || sk[i].count(b)){set <int> temp;set_union(wd[i][a].begin(),wd[i][a].end(),wd[i][b].begin(),wd[i][b].end(),inserter(temp,temp.begin()));if(f2) cout << "----------" << endl;f = 1;set <int> :: iterator it;for(it = temp.begin();it != temp.end();it++){cout << sen[i][*it] << endl;}f2 = 1;}}if(!f) cout << "Sorry, I found nothing." << endl;cout << "==========" << endl;
}void NOT(string a,int n){  ##  NOT操作,大致与上面相同int f = 0,f2 = 0;for(int i = 0;i < n;i++){if(!sk[i].count(a)){if(f2) cout << "----------" << endl;f = 1;for(int j = 0;j < sen[i].size();j++){cout << sen[i][j] << endl;}f2 = 1;}}if(!f) cout << "Sorry, I found nothing." << endl;cout << "==========" << endl;
}void chr(string a,int n){  ##  单个单词查找操作,大致与上面相同int f = 0,f2 = 0;for(int i = 0;i < n;i++){if(sk[i].count(a)){set <int> temp(wd[i][a]);if(f2) cout << "----------" << endl;f = 1;set <int> :: iterator it;for(it = temp.begin();it != temp.end();it++){cout << sen[i][*it] << endl;}f2 = 1;}}if(!f) cout << "Sorry, I found nothing." << endl;cout << "==========" << endl;
}int main(){int n;cin >> n;getchar();for(int i = 0;i < n;i++){string s;while(getline(cin,s) && s[0] != '*'){  ##  对原行进行处理,存储sen[i].push_back(s);int rank = sen[i].size() - 1;string temp = change(s),str;stringstream ss(temp);while(ss >> str){sk[i].insert(str);  ##  表明这篇文章里有这个单词wd[i][str].insert(rank);}}}int t;cin >> t;getchar();string s;while(t--){getline(cin,s);if(s.find("AND") != string::npos){int k = s.find("AND");string temp1 = s.substr(0,k - 1);string temp2 = s.substr(k + 4,s.size() - k - 4);AND(temp1,temp2,n);}else if(s.find("OR") != string::npos){int k = s.find("OR");string temp1 = s.substr(0,k - 1);string temp2 = s.substr(k + 3,s.size() - k - 3);OR(temp1,temp2,n);}else if(s.find("NOT") != string::npos){string temp1 = s.substr(4,s.size() - 4);NOT(temp1,n);}else{chr(s,n);}}return 0;
}

代码也是写的比较臃肿,模拟的能力还是比较差,有大量相似度极高的代码

O-更新字典 (水题) UVA - 12504

    In this problem, a dictionary is collection of key-value pairs, where keys are lower-case letters, and values are non-negative integers. Given an old dictionary and a new dictionary, find out what were changed.
    Each dictionary is formatting as follows:
                                            {key:value,key:value,…,key:value}
    Each key is a string of lower-case letters, and each value is a non-negative integer without leading zeros or prefix ‘+’. (i.e. -4, 03 and +77 are illegal). Each key will appear at most once, but keys can appear in any order.

Input

    The first line contains the number of test cases T (T ≤ 1000). Each test case contains two lines. The first line contains the old dictionary, and the second line contains the new dictionary. Each line will contain at most 100 characters and will not contain any whitespace characters. Both dictionaries could be empty.
WARNING: there are no restrictions on the lengths of each key and value in the dictionary. That means keys could be really long and values could be really large.

Output

    For each test case, print the changes, formatted as follows:
    • First, if there are any new keys, print ‘+’ and then the new keys in increasing order (lexicographically),separated by commas.
    • Second, if there are any removed keys, print ‘-’ and then the removed keys in increasing order (lexicographically), separated by commas.
    • Last, if there are any keys with changed value, print ‘*’ and then these keys in increasing order (lexicographically), separated by commas.
    If the two dictionaries are identical, print ‘No changes’ (without quotes) instead.Print a blank line after each test case.

Sample Input

3
{a:3,b:4,c:10,f:6}
{a:3,c:5,d:10,ee:4}
{x:1,xyz:123456789123456789123456789}
{xyz:123456789123456789123456789,x:1}
{first:1,second:2,third:3}
{third:3,second:2}

Sample Output

+d,ee
-b,f
*c
No changes
-first

理解

	很简单的题目,找找差集就结束了,写完前面的题目写这题感觉在玩一样【狗头】大意就是看新的密钥串中,新出现的,消失的,以及值改变的密钥

AC代码

#include <bits/stdc++.h>
using namespace std;int main(){int t;cin >> t;while(t--){set <string> ans[3];  ##  记录变化的东西set <string> keys;  ##  原来的密钥set <string> chs;  ##  改变之后的密钥map <string,string> value;  ##  密钥对应的值string a,b;cin >> a >> b;for(int i = 0;i < a.size();i++){if(a[i] == '{' || a[i] == '}' || a[i] == ',') a[i] = ' ';}for(int i = 0;i < b.size();i++){if(b[i] == '{' || b[i] == '}' || b[i] == ',') b[i] = ' ';}stringstream ss(a);string str;while(ss >> str){int k = str.find(":");string tkey = str.substr(0,k);string tvalue = str.substr(k + 1,str.size() - k - 1);value[tkey] = tvalue;keys.insert(tkey);}stringstream ss2(b);while(ss2 >> str){int k = str.find(":");string tkey = str.substr(0,k);string tvalue = str.substr(k + 1,str.size() - k - 1);if(value.count(tkey) && value[tkey] != tvalue) ans[2].insert(tkey);  ##  检查密钥的值是否有变化if(!value.count(tkey)) ans[0].insert(tkey);  ##  检查是否出现密钥chs.insert(tkey);}set <string> :: iterator it;for(it = keys.begin();it != keys.end();it++){  ##  检查新的串中有没有老的密钥if(!chs.count(*it)) ans[1].insert(*it);}##  输出结果,结束if(ans[0].empty() && ans[1].empty() && ans[2].empty()) cout << "No changes" << endl;else{for(int i = 0;i < 3;i++){if(!ans[i].empty()){if(i == 0) cout << "+";if(i == 1) cout << "-";if(i == 2) cout << "*";int f = 0;set <string> :: iterator it;for(it = ans[i].begin();it != ans[i].end();it++){if(f) cout << ',';cout << *it;f = 1;}cout << endl;}}}cout << endl;}return 0;
}

P-Gathering Children (水题,思维题) atcoder

Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 400 points

Problem Statement
Given is a string S consisting of L and R.
Let N be the length of S. There are N squares arranged from left to right, and the i-th character of S from the left is written on the i-th square from the left.

The character written on the leftmost square is always R, and the character written on the rightmost square is always L.

Initially, one child is standing on each square.

Each child will perform the move below 10^100 times:

        Move one square in the direction specified by the character written in the square on which the child is standing. L denotes left, and R denotes right.

Find the number of children standing on each square after the children performed the moves.

Constraints
        S is a string of length between 2 and 10^5 (inclusive).
        Each character of S is L or R.
        The first and last characters of S are R and L, respectively.

Input

Input is given from Standard Input in the following format:

S



理解

	这应该是遇见过的最简单的第四题了(上周数位dp写的我想死,后来看大佬代码和题解也看不懂。。。暴风哭泣)先说说这道题的大意,有数量为s的方块,每个方块上有一个小孩和一个字母,小孩会根据方块上的字母移动,R为往右移动,L为往左移动,他们每个人都会移动10^100次,求最后每个方块上有多少个小孩(左右两端封闭R和L),不用担心小孩跑出去。简单的找一下规律可以发现,小孩最后必然陷入L和R之间的循环,我们完全可以通过小孩的原位置和最终会陷入循环的下标来判断小孩最后呆在哪里举个栗子:RRL,找原坐标为0的孩子最后在那,对于0坐标的R,第一次遇到L在下标2的地方,进行一个简单的计算(2 - 0) % 2 == 0 所以他最后会呆在下标为2的地方而原坐标为1的R,(1 - 0) % 2 != 0 所以他最后会想下标2 - 1的地方所以我们只要找到每个L和R最近的陷入循环的R和L,然后计算最后小孩会呆在哪就ok了

k代表陷入循环的下标,i代表当前下标
R的位置公式
if((k - i) % 2 == 0) ans[k]++;
if((k - i) % 2 != 0) ans[k - 1]++;

L的位置公式
if((i - k) % 2 != 0) ans[k + 1]++;
if((i - k) % 2 == 0) ans[k]++;

AC代码

#include <bits/stdc++.h>
using namespace std;int main()
{	string s;cin >> s;int a[100005] = {0};  ##  存相对下标陷入循环的下标位置int ans[100005] = {0};  ##  存最终结果,每个位置上多少个小孩(第一次数组开小了re就很气)int k = s.size() - 1;for(int i = s.size() - 1;i >= 0;i--){  ##  反向遍历一遍找R陷入循环的L的坐标if(s[i] == 'L') k = i;if(s[i] == 'R') a[i] = k;}k = 0;for(int i = 0;i < s.size();i++){  ##  正向遍历一遍找L陷入循环的R的坐标if(s[i] == 'R') k = i;if(s[i] == 'L') a[i] = k;}	for(int i = 0;i < s.size();i++){  ##  判断原位置小孩最终跑哪去了if(s[i] == 'R'){if((a[i] - i) % 2 == 0) ans[a[i]]++;if((a[i] - i) % 2 != 0) ans[a[i] - 1]++;}if(s[i] == 'L'){if((i - a[i]) % 2 != 0) ans[a[i] + 1]++;if((i - a[i]) % 2 == 0) ans[a[i]]++;}}cout << ans[0];  ##  输出结果for(int i = 1;i < s.size();i++){cout << ' ' << ans[i];}cout << endl;
}

(二)一些收获

关于STL

说实话,STL的学习感觉还是太急促了,感觉就是刚讲完加减乘除,你就要硬着头皮上去写积分了一半(苦笑)
下面就写一点点关于STL的想法吧

	1.STL在解题上确实起到了极大的帮助,对于一些本来处理起来很复杂的模拟题,我们用简短的代码就能写出答案2.STL单纯的使用并不难,真正的难点在于容器的叠加使用,在后面一些比较复杂的模拟题里面,单纯的容器显然是不够用的,而在结合使用这一块确实是有难度,需要有一个慢慢练习的过程3.不能过分依赖于STL,对于一些题目,模板式的STL可能还没自己写的代码方便4.一定要充分掌握STL容器和string类型里面大部分基础函数的用法,并且使用熟练,这样写题时很多操作才能快速想到(这两天写题疯狂查函数太累了人,好在在这过程中也学了不少东西)

关于模拟题

在学习玩STL之后,写之前难写的模拟题写起来不要太轻松,但也引出了真正的难题(反正课后习题训练,后面几个难的模拟题把我看自闭了,不是看不懂,就是完全没有模拟的思路,蒟蒻的我望题自闭)

	1.写模拟题的时候注意分块写,一点一点来不容易出错,这一点上周也说过了,只是这周感觉更深了2.很多模拟题的输入和预处理相当麻烦,这一块优先处理,再慢慢考虑后面模拟的事3.可以每写完一小块模拟,先运行看看这一块写的是否可行(我这么写的时候,明显的减少了wa次数),因有错也可以及时找出。但也会造成写题速度较慢的缺点(比较写一块调整一块,肯定没有人家大佬一次写对来的快),目前蒟蒻的我还是很喜欢这种方法的

(三)感想

大概就以下几点
1.对STL有一定学习之后,写一些难点的模拟题确实也是更加得心应手了,但也认识到了真正难的模拟会难到什么程度,模拟这一块还要继续联系

2.对STL里容器的叠加运用掌握实在是太少,很多题目对于这方面要求较高,还是要自己慢慢摸索

3.写题目时还是要注意容器的选择,合适的容器模拟起来会简单很多

4.感觉对于长代码的构架能力强了不少,一些稍微有点复杂的模拟是能慢慢敲出来了,但不足之处也很明显,很多时候敲出来的代码很臃肿,重复内容有点多

总结:经过这一周的学习,是对STL有了一定的掌握,在各种容器的帮助下,能够写出一些原来写起来很费力的题目了。构架代码的能力也算有点增强,对于模拟的题目更加得心应手了一点。读题能力貌似增强不多(大部分时候谷歌翻译或者直接找中文题意),真的长篇题目读起来太累了,英语水平确实太低了,还有待增强。

(革命尚未成功,同志尚需努力[狗头])

(四)附录[学习笔记]

另写了一片blog记载,放一起堆着太多了,就贴一下地址

本文标签: WaWa的奇妙冒险(第二周集训自闭现场)