Week2EXP2&HomeWork2
第一次写博客，第一次把自己的思路挂网上，各方面都不太熟，惶恐至极QAQ....代码写的比较散乱、啰嗦确实有很多有待改进的地方QAQ......从来没有接触过程序竞赛，码力不足，各路大佬多多包涵，如果观众大佬看出哪里有错的不要奇怪，博主小白...希望不要误导大家....
第一题：
化学很神奇，以下是烷烃基
假设如上图，这个烷烃基有6个原子和5个化学键，6个原子分别标号1~6，然后用一对数字 a,b 表示原子a和原子b间有一个化学键。这样通过5行a,b可以描述一个烷烃基
你的任务是甄别烷烃基的类别。
原子没有编号方法，比如
1 2
2 3
3 4
4 5
5 6
和
1 3
2 3
2 4
4 5
5 6
是同一种，本质上就是一条链，编号其实是没有关系的，可以在纸上画画就懂了
Input
输入第一行为数据的组数T（1≤T≤200000）。每组数据有5行，每行是两个整数a, b(1≤a,b≤6,a ≤b)
数据保证，输入的烷烃基是以上5种之一
Output
每组数据，输出一行，代表烷烃基的英文名
思路分析：
题目的本质是要我们区分化学中的同分异构体，我们知道同分异构体的本质区别是各个原子的连接方式不同，因此我们可以把每个原子看成一个节点，把化学键看成连接每个节点的边，计算每个节点的度数，按照不同的度数组合来区分各个同分异构体。
我们根据观察n-hexane的每个原子度数为1、1、2、2、2、2。2,2-dimethylbutane为1、1、1、2、4，2,3-dimethylbutane为1、1、1、3、3，而2-methylpentane和3-methylpentane都是1、1、1、2、2、3。对于前三个，我们总是能够根据他们的度数序列进行正确区分，而后两个，则需要我们进一步区分，观察这两个同分异构体，我们发现他们度数为3的节点所连接的三个节点的度数是不同的（一个为1、1、2另一个为1、2、2），所以我们就可以根据这个进行区分。
有了思路之后就可以写代码了，我们根据输入就可以统计出每个节点的度数（输入每出现一次该节点，就表示该节点的度数加一），由于每个节点地位相等，所以我们把收集的节点序列排序，然后送入分析节点序列的程序即可。
一下为源代码（略为混乱....）
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int a,b;
};
void fuc(){
int count[7];
int temp[7];
for(int i=0;i<7;i++){
count[i]=0;
}
node list[5];
for(int i=0;i<5;i++){
cin>>list[i].a>>list[i].b;
count[list[i].a]++;
count[list[i].b]++;
}
for(int i=0;i<7;i++){
temp[i]=count[i];
}
/*
for(int i=0;i<5;i++){
cout<<list[i].a<<" "<<list[i].b<<endl;
}
*/
sort(count,count+7);
// for(int i=1;i<=6;i++){
// cout<<count[i]<<endl;
// }
if(count[6]==4){
cout<<"2,2-dimethylbutane"<<endl;
return;
}
if(count[3]==2){
cout<<"n-hexane"<<endl;
return;
}
if(count[5]==3){
cout<<"2,3-dimethylbutane"<<endl;
return;
}
int sum=0;
// cout<<" "<<endl;
// for(int i=1;i<=6;i++){
// cout<<temp[i]<<endl;
// }
// cout<<endl;
for(int i=1;i<=6;i++){
if(temp[i]==3){
// cout<<"i="<<i<<endl;
for(int j=0;j<5;j++){
if(list[j].a==i){
// cout<<"j.a="<<j<<endl;
sum=sum+temp[list[j].b];
// cout<<sum<<endl;
}
if(list[j].b==i){
// cout<<"j.b"<<j<<endl;
sum=sum+temp[list[j].a];
// cout<<sum<<endl;
}
}
break;
}
}
if(sum==5){
cout<<"3-methylpentane"<<endl;
return;
}
//cout<<sum<<endl;
cout<<"2-methylpentane"<<endl;
return;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
fuc();
}
}
第二题：
程序设计思维作业和实验使用的实时评测系统，具有及时获得成绩排名的特点，那它的功能是怎么实现的呢？我们千辛万苦怼完了不忍直视的程序并提交以后，评测系统要么返回AC，要么是返回各种其他的错误，不论是怎样的错法，它总会给你记上一笔，表明你曾经在这儿被坑过，而当你历经千辛终将它AC之后，它便会和你算笔总账,表明这题共错误提交了几次。
在岁月的长河中，你通过的题数虽然越来越多，但通过每题时你所共花去的时间（从最开始算起，直至通过题目时的这段时间）都会被记录下来，作为你曾经奋斗的痕迹。特别的，对于你通过的题目，你曾经的关于这题的每次错误提交都会被算上一定的单位时间罚时，这样一来，你在做出的题数上，可能领先别人很多，但是在做出同样题数的人中，你可能会因为罚时过高而处于排名上的劣势。
例如某次考试一共八道题（A,B,C,D,E,F,G,H），每个人做的题都在对应的题号下有个数量标记，负数表示该学生在该题上有过的错误提交次数但到现在还没有AC，正数表示AC所耗的时间，如果正数a跟上了一对括号，里面有个正数b,则表示该学生AC了这道题，耗去了时间a，同时曾经错误提交了b次。例子可见下方的样例输入与输出部分。
Input输入数据包含多行，第一行是共有的题数n（1≤n≤12）以及单位罚时m（10≤m≤20），之后的每行数据描述一个学生的信息，首先是学生的用户名（不多于10个字符的字串）其次是所有n道题的得分现状，其描述采用问题描述中的数量标记的格式，见上面的表格。
Output根据这些学生的得分现状，输出一个实时排名。实时排名显然先按AC题数的多少排，多的在前，再按时间分的多少排，少的在前，如果凑巧前两者都相等，则按名字的字典序排，小的在前。每个学生占一行，输出名字（10个字符宽），做出的题数（2个字符宽，右对齐）和时间分（4个字符宽，右对齐）。名字、题数和时间分相互之间有一个空格。数据保证可按要求的输出格式进行输出。
思路分析：
这道题是制作一个简单的排名，仔细阅读题面，知道了排名规则后，就可以开始解题了。大致的思路是按照一行为一个单元处理一个选手的成绩统计。
首先创建一个结构体，用于储存一个选手的AC题目数，罚时和选手姓名。读入题目数量N和单位罚时M。然后开始处理一个选手的成绩统计（不知道有多少选手，要一直读直到文件末尾），为了方便后续排名，记下选手数量c。下面开始以一行为单位处理数据，先读入每个选手的名字，再读入该选手每一行的N个数据段，使用for循环，我们都拿他当作字符串读取，首先判断这个字符串是“0”或是第一个字符是‘-’，若是，表示对我们要统计的数据无影响，直接contiune。反之，则说明选手在这个题目AC了。AC++，然后在读取这个字符串，并转换成数字，在读取的过程中每次都判断一下有没有读到‘（’，若有这个，在读入括号里面的内容，使用零时变量记录下来。最后再计算总的罚时时间。
成绩处理完了就可以排序输出了。在使用STL sort之前，我们要自定义比较规则，即如下comp函数段。
源代码如下（又是比较凌乱....以及要注意输出格式问题）（为什么用C++ setiosflags总是PE？？迷惑....）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<iomanip>
using namespace std;
struct Node{
int AC;
int time;
char name[10];
};
bool comp(Node a,Node b){
if(a.AC!=b.AC){
return a.AC>b.AC;
}
if(a.time!=b.time){
return a.time<b.time;
}
return a.name<b.name;
}
int main(){
int n,m;
cin>>n;
cin>>m;
Node player[1000];
int c=0;
string s;
// Node *player=new Node[n];
bool t=cin>>player[c].name;
while(t){
player[c].AC=0;
player[c].time=0;
// cout<<" ijijij"<<endl;
for(int i=0;i<n;i++){
cin>>s;
// cout<<s<<endl;
if(s[0]=='-'){
continue;
}
if(s[0]=='0'){
continue;
}
player[c].AC++;
// cout<<player[c].AC<<endl;
int tempt=0;int temp=0;
for(int j=0;j<s.length();j++){
if(s[j]!='('){
tempt=tempt*10+(s[j]-'0');
}else{
for(int jj=j+1;jj<s.length()-1;jj++){
temp=temp*10+(s[jj]-'0');
}
break;
}
}
player[c].time=player[c].time+temp*m+tempt;
// cout<<player[c].time<<endl;
}
c++;
t=cin>>player[c].name;
}
//cout<<c<<endl;
// cout<<player[0].name<<endl;
sort(player,player+c,comp);
//这个 输出究竟出了什么问题？为什么PE
// for(int i=0;i<c;i++){
// cout<<setiosflags(ios::left)<<setw(10)<<player[i].name<<" ";
// cout<<resetiosflags(ios::right)<<setw(2)<<player[i].AC<<" ";
// cout<<resetiosflags(ios::right)<<setw(4)<<player[i].time<<endl;
// }
for(int i=0;i<c;i++){
printf("%-10s %2d %4d\n",player[i].name,player[i].AC,player[i].time);
}
}
第三题：
瑞神HRZ因为疫情在家闲得无聊，同时他又非常厉害，所有的课对他来说都是水一水就能拿A+，所以他无聊，找来了另外三个人：咕咕东，腾神以及zjm来打牌（天下苦瑞神久矣）。显然，牌局由四个人构成，围成一圈。我们称四个方向为北 东 南 西。对应的英文是North，East，South，West。游戏一共由一副扑克，也就是52张构成。开始，我们指定一位发牌员（东南西北中的一个，用英文首字母标识）开始发牌，发牌顺序为顺时针，发牌员第一个不发自己，而是发他的下一个人（顺时针的下一个人）。这样，每个人都会拿到13张牌。
现在我们定义牌的顺序，首先，花色是（梅花）<（方片）<（黑桃）<（红桃），（输入时，我们用C,D,S,H分别表示梅花，方片，黑桃，红桃，即其单词首字母）。对于牌面的值，我们规定2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A。
现在你作为上帝，你要从小到大排序每个人手中的牌，并按照给定格式输出。（具体格式见输出描述和样例输出）。
Input
输入包含多组数据每组数据的第一行包含一个大写字符，表示发牌员是谁。如果该字符为‘#’则表示输入结束。
接下来有两行，每行有52个字符，表示了26张牌，两行加起来一共52张牌。每张牌都由两个字符组成，第一个字符表示花色，第二个字符表示数值。
Output
输出多组数据发牌的结果，每组数据之后需要额外多输出一个空行！！！！！每组数据应该由24行的组成，输出按照顺时针方向，始终先输出South Player的结果，每位玩家先输出一行即玩家名称（东南西北），接下来五行，第一行和第五行输出固定格式（见样例），第二行和第四行按顺序和格式输出数值（见样例），第三行按顺序和格式输出花色（见样例）。
Sample Input
N CTCAH8CJD4C6D9SQC7S5HAD2HJH9CKD3H6D6D7H3HQH4C5DKHKS9 SJDTS3S7S4C4CQHTSAH2D8DJSTSKS2H5D5DQDAH7C9S8C8S6C2C3 #
Sample Output
South player: +---+---+---+---+---+---+---+---+---+---+---+---+---+ |6 6|A A|6 6|J J|5 5|6 6|7 7|9 9|4 4|5 5|7 7|9 9|T T| | C | C | D | D | S | S | S | S | H | H | H | H | H | |6 6|A A|6 6|J J|5 5|6 6|7 7|9 9|4 4|5 5|7 7|9 9|T T| +---+---+---+---+---+---+---+---+---+---+---+---+---+ West player: +---+---+---+---+---+---+---+---+---+---+---+---+---+ |2 2|5 5|9 9|K K|5 5|7 7|9 9|4 4|T T|J J|A A|8 8|A A| | C | C | C | C | D | D | D | S | S | S | S | H | H | |2 2|5 5|9 9|K K|5 5|7 7|9 9|4 4|T T|J J|A A|8 8|A A| +---+---+---+---+---+---+---+---+---+---+---+---+---+ North player: +---+---+---+---+---+---+---+---+---+---+---+---+---+ |3 3|4 4|J J|2 2|3 3|T T|Q Q|K K|8 8|Q Q|K K|2 2|3 3| | C | C | C | D | D | D | D | D | S | S | S | H | H | |3 3|4 4|J J|2 2|3 3|T T|Q Q|K K|8 8|Q Q|K K|2 2|3 3| +---+---+---+---+---+---+---+---+---+---+---+---+---+ East player: +---+---+---+---+---+---+---+---+---+---+---+---+---+ |7 7|8 8|T T|Q Q|4 4|8 8|A A|2 2|3 3|6 6|J J|Q Q|K K| | C | C | C | C | D | D | D | S | S | H | H | H | H | |7 7|8 8|T T|Q Q|4 4|8 8|A A|2 2|3 3|6 6|J J|Q Q|K K| +---+---+---+---+---+---+---+---+---+---+---+---+---+
解题思路：
作为一个初学者，看到这么复杂的输出和规则，一开始看到这个题的时候我内心还是挺崩溃的。仔细阅读了几遍题目，大致了解了题目意思，就慢慢开始有了头绪。
首先这道题本质上是一个根据输入进行分组，然后再排序输出。，关键是要得到一个有序数组，后面的输出规则其实是好解决的。因为要根据花色和牌面比较，花色和牌面又不是按照字符顺序来的，
我们就考虑使用map来实现对应字符向数字转化，方便后续排序。如下代码：
char pai[]={'2','3','4','5','6','7','8','9','T','J','Q','K','A'};
char huase[]={'C','D','S','H'};
map<char,int> pmap;
map<char,int> smap;
for(int i=0;i<13;i++){
pmap[pai[i]]=i;
}
for(int i=0;i<4;i++){
smap[huase[i]]=i;
}
然后我们就可以考虑把数据存入优先级队列之中去了，自定义比较规则。
struct compare{
bool operator()(poke a,poke b){
if(a.h!=b.h){
return a.h<b.h;
}else{
return a.p<b.p;
}
}
};
这样的话把字符映射到数字就好比较了。然后考虑发牌顺序的问题，因为要等到用户输入，才知道先发给哪一个人，我想到的是先开4个优先级队列，默认按照S、W、N、E的顺序，然后再根据用户输入，转化为一个偏离量，%4输入各自数组即可。具体代码如下：
switch(a){
case 'S' :{
c=0;
break;
}
case 'W':{
c=1;
break;
}
case 'N':{
c=2;
break;
}
case 'E':{
c=3;
break;
}
}
char ta,tb;
int tema,temb;
poke pai[52];
for(int i=0;i<52;i++){
cin>>ta;cin>>tb;
tema=smap[ta];
temb=pmap[tb];
pai[i].reset(tema,temb);
pai[i].HUA=ta;
pai[i].PAI=tb;
player[(c+i+1)%4].push(pai[i]);
}
输入完成后就自动排序了，接下来就要注意输出格式问题了，（输出格式真的需要仔仔细细看好QAQ......）,以下为源代码：
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
char pai[]={'2','3','4','5','6','7','8','9','T','J','Q','K','A'};
char huase[]={'C','D','S','H'};
class poke{
public:
int h;
int p;
char HUA;
char PAI;
poke(){}
poke(int a,int b){
h=a;p=b;
}
void reset(int a,int b){
h=a;p=b;
}
// bool operator < (poke &a){
// if(this->th!=a.th){
// return this->th<a.th;
// }else{
// return this->tn<a.tn;
// }
// }
};
struct compare{
bool operator()(poke a,poke b){
if(a.h!=b.h){
return a.h<b.h;
}else{
return a.p<b.p;
}
}
};
int main(){
map<char,int> pmap;
map<char,int> smap;
for(int i=0;i<13;i++){
pmap[pai[i]]=i;
}
for(int i=0;i<4;i++){
smap[huase[i]]=i;
}
char a;
cin>>a;
while(a!='#'){
priority_queue<poke,vector<poke>,compare> player[4];
int c=0;
switch(a){
case 'S' :{
c=0;
break;
}
case 'W':{
c=1;
break;
}
case 'N':{
c=2;
break;
}
case 'E':{
c=3;
break;
}
}
//发牌
char ta,tb;
int tema,temb;
poke pai[52];
for(int i=0;i<52;i++){
cin>>ta;cin>>tb;
tema=smap[ta];
temb=pmap[tb];
pai[i].reset(tema,temb);
pai[i].HUA=ta;
pai[i].PAI=tb;
player[(c+i+1)%4].push(pai[i]);
}
cin>>a;
string temstr[]={"South player:","West player:","North player:","East player:"};
for(int j=0;j<4;j++){
char tempcharH[13];
char tempcharP[13];
for(int i=0;i<13;i++){
tempcharH[i] =player[j].top().HUA;
tempcharP[i] =player[j].top().PAI;
player[j].pop();
}
cout<<temstr[j]<<endl;
cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+"<<endl;
for(int i=0;i<13;i++){
cout<<"|"<<tempcharP[12-i]<<" "<<tempcharP[12-i];
}
cout<<"|"<<endl;
for(int i=0;i<13;i++){
cout<<"| "<<tempcharH[12-i]<<" ";
}
cout<<"|"<<endl;
for(int i=0;i<13;i++){
cout<<"|"<<tempcharP[12-i]<<" "<<tempcharP[12-i];
}
cout<<"|"<<endl;
if(a!='#'||j<3) cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+"<<endl;
else cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+";
if(a!='#'){
cout<<endl;
}
}
}
Week2作业题:
A-Maze：
东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。既然已经知道了地图，那么东东找到妹纸就不难了，请你编一个程序，写出东东找到妹纸的最短路线。
Input
输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。
Output
输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。
Sample Input0 1 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 1 0
Sample Output(0, 0)
(1, 0)
(2, 0)
(3, 0)
(3, 1)
(3, 2)
(2, 2)
(1, 2)
(0, 2)
(0, 3)
(0, 4)
(1, 4)
(2, 4)
(3, 4)
(4, 4)
Hint
坐标(x, y)表示第x行第y列，行、列的编号从0开始，且以左上角为原点。
另外注意，输出中分隔坐标的逗号后面应当有一个空格。
思路分析：
这道题是典型的BFS的问题，也可以用DFS做，但是我感觉我对递归还是没有那么熟练的，加之BFS选出最短的路径更方便，于是选用BFS。首先创建两个数组，一个是visit用于记录已经到达的轨迹，另一个是maze用于记录迷宫的情况。但是这道题要输出路径，于是使用回溯的方法，在到达一个顶点的时候用另一个数组记录它上一个节点的情况。以后在输出的时候只要逆向输出一下就可以了。
首先创建数组，每次BFS的时候有↑→↓←四个方向一次经行，为了使每个节点的操作都是一致的，我们在原来迷宫的基础上加了一层围墙。每次判断是不是走到了终点，若是，则搜索成功，返回，若不是继续进行，然后按照BFS的方法走就可以了。
输出的时候要注意因为是从最后一个开始向前找，所以要注意数据此时是逆序的，先要把数据存起来，然后再按照格式顺序输出。
以下是源代码：
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
int d[]={-1,1};
int maze[6][6];
int visit[6][6];
class node{
public:
int x,y;
node(int a,int b){
x=a;
y=b;
}
node(){
}
void set(int a,int b){
x=a;
y=b;
}
};
int main(){
// node *parent=new node[6];
//
// for(int i=0;i<6;i++){
// parent[i]=new node[6];
// }
node parent[6][6];
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
cin>>maze[i][j];
}
}
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
visit[i][j]=0;
}
}
node tem(1,1);
parent[1][1]=tem;
queue<node> q;
q.push(tem);
while(1){
tem=q.front();
if(tem.x==5&&tem.y==5) {
break;
}
q.pop();
visit[tem.x][tem.y] = 1;
node temp;
int c;
for(int j=0;j<2;j++) {
c=tem.x+d[j];
if(visit[c][tem.y]||maze[c][tem.y]==1){
continue;
}
if(c>=1&&c<=5&&tem.y>=1&&tem.y<=5){
parent[c][tem.y] = tem;
temp.set(c,tem.y);
q.push(temp);
}
}
c=0;
for(int j=0;j<2;j++) {
c=tem.y + d[j];
if(visit[tem.x][c]||maze[tem.x][c]==1){
continue;
}
if(tem.x>=1&&tem.x<=5&&c>=1&&c<=5){
parent[tem.x][c]=tem;
temp.set(tem.x,c);
q.push(temp);
}
}
}
stack<node> path;
node out(5,5);
path.push(out);
do{
out=parent[out.x][out.y];
path.push(out);
// cout<<out.x<<" "<<out.y<<endl;
}while(out.x!=1||out.y!=1);
// cout<<path.size()<<endl;
while(!path.empty()){
out=path.top();
path.pop();
cout<<"("<<out.x-1<<", "<<out.y-1<<")"<<endl;
}
}
B-Pour Water：
倒水问题 "fill A" 表示倒满A杯，"empty A"表示倒空A杯，"pour A B" 表示把A的水倒到B杯并且把B杯倒满或A倒空。Input
输入包含多组数据。每组数据输入 A, B, C 数据范围 0 < A <= B 、C <= B <=1000 、A和B互质。Output
你的程序的输出将由一系列的指令组成。这些输出行将导致任何一个罐子正好包含C单位的水。每组数据的最后一行输出应该是“success”。输出行从第1列开始，不应该有空行或任何尾随空格。Sample Input
2 7 5 2 7 4
Sample Output
fill B pour B A success fill A pour A B fill A pour A B success
Notes如果你的输出与Sample Output不同，那没关系。对于某个"A B C"本题的答案是多解的，不能通过标准的文本对比来判定你程序的正确与否。 所以本题由 SPJ（Special Judge）程序来判定你写的代码是否正确。
思路分析：
本题是隐式图的问题。根据百度百科定义，隐式图是仅给出初始结点、目标结点以及生成子结点的约束条件（题意隐含给出），要求按扩展规则应用于扩展结点的过程，找出其他结点，使得隐式图的足够大的一部分编程显式，直到包含目标结点为止。之前从来就没有听说这类的问题，在做这一道题的时候我还是费了点心思的。这道题TA在课上讲过，但是我基础太差了，上课其实没怎么听明白，好在TA给了源代码的