实验
A题
题意
假设如上图，这个烷烃基有6个原子和5个化学键，6个原子分别标号1~6，然后用一对数字 a,b 表示原子a和原子b间有一个化学键。这样通过5行a,b可以描述一个烷烃基。
你的任务是甄别烷烃基的类别。
标号不唯一，根据形状区分。
共五种形状
Input
输入第一行为数据的组数T（1≤T≤200000）。每组数据有5行，每行是两个整数a, b(1≤a,b≤6,a ≤b)
数据保证，输入的烷烃基是以上5种之一
Output
每组数据，输出一行，代表烷烃基的英文名
做法
观察五种图的结构，发现可以根据顶点的度数（连接了几个其余点）区分。
发现
n-hexane 有2个一度节点
2,2-dimethylbutane 有4个一度节点，1个二度节点
2,3-dimethylbutane 有4个一度节点，0个二度节点
而最难区分的两个（均有3个一度节点）：
2-methylpentane 三度节点邻接两个一度节点
3-methylpentane 三度节点邻接一个一度节点。
根据以上思路，首先统计i 度节点的个数。
根据一度节点和二度节点，可仅剩最后两个区分不出。
根据初始给出的边信息，可以找到三度节点邻接的三个点分别为几度，从而区分最后两个节点。
代码
#include<iostream>
using namespace std;
int main()
{
int T;
cin>>T;
for(int i=1;i<=T;i++)
{ int count[7],num[7],a[7],b[7];// count:dushu num:geshu
for(int k=1;k<=6;k++)
{
count[k]=0;
num[k]=0;
}
for(int j=1;j<=5;j++)
{
cin>>a[j]>>b[j];
count[a[j]]++;
count[b[j]]++;
}
int temp;
for(int j=1;j<=6;j++)
{
num[count[j]]++;
if(count[j]==3)temp=j;
}
if(num[1]==2)cout<<"n-hexane"<<endl;
else if(num[1]==3)
{ int count2[4],cnt2=1;//count num 3
for(int u=1;u<=5;u++)
{
if(a[u]==temp)
{
count2[cnt2]=b[u];
cnt2++;
}
else if(b[u]==temp)
{
count2[cnt2]=a[u];
cnt2++;
}
}
int ans=0;
for(int u=1;u<=3;u++)
{
if(count[count2[u]]==2)ans++;
}
if(ans==1)cout<<"2-methylpentane"<<endl;
else if(ans==2)cout<<"3-methylpentane"<<endl;
}
else if(num[1]==4)
{
if(num[2]==1)cout<<"2,2-dimethylbutane"<<endl;
else cout<<"2,3-dimethylbutane"<<endl;
}
}
}
参考答案：
参考答案：区分i度节点邻接的j度节点的个数
优化与总结
1、初始化数组memset更简单。
用法：memset（a,val,sizeof(a)）注意：是每八位相同。-1 0 或比较大的书常作为初始化数。
2、用邻接矩阵作为储存结构，形式上方便最后的查找3度节点的2度邻接点的个数。
B题
题意
程序设计思维作业和实验使用的实时评测系统，具有及时获得成绩排名的特点，那它的功能是怎么实现的呢？
我们千辛万苦怼完了不忍直视的程序并提交以后，评测系统要么返回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个字符宽，右对齐）。名字、题数和时间分相互之间有一个空格。数据保证可按要求的输出格式进行输出。
Sample Input
8 20
GuGuDong 96 -3 40(3) 0 0 1 -8 0
hrz 107 67 -3 0 0 82 0 0
TT 120(3) 30 10(1) -3 0 47 21(2) -2
OMRailgun 0 -99 -8 0 -666 -10086 0 -9999996
yjq -2 37(2) 13 -1 0 113(2) 79(1) -1
Zjm 0 0 57(5) 0 0 99(3) -7 0
Sample Output
TT 5 348
yjq 4 342
GuGuDong 3 197
hrz 3 256
Zjm 2 316
OMRailgun 0 0
做法
本题主要是考察读入和输出和排序。
将每个同学的当前做题情况读入到一个结构体中。
另外，储存一个ac题目数和时耗。
每个同学的分有三种情况：
1、负数
2、正数 ac数++；时耗+=本题时耗；
3、正数带括号 ac数++；时耗+=本题时耗+错误数*罚时
代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct stu{
char name[10];
int time[13];
int history[13];
int timescore;
int number;
bool operator<(const stu& p)const
{
if(number!=p.number)return number>p.number;
if (timescore!=p.timescore)return timescore<p.timescore;
if(name[0]!=name[0])return name[0]<p.name[0];
}
};
stu s[5000];
string score[13];
int main()
{int i=1;
int n,m;
cin>>n>>m;
while(cin>>s[i].name)
{
for(int j=1;j<=n;j++)
{
cin>>score[j];
// cout<<score[j].find(')')<<"^^^^^^^^^^^^";
if(score[j].find(')')==score[j].size()-1)
{ int k=score[j].size()-2;
int wa=0,fen=0;
for(;k!=score[j].find('(');k--)
{
wa+=(score[j][k]-'0')*pow(10,(score[j].size()-2-k));
}
s[i].history[j]=wa;
k--;
for(int l=k;l>=0;l--)
{
fen+=(score[j][l]-'0')*pow(10,k-l);
}
s[i].time[j]=fen;
// cout<<s[i].time[j]<<"#"<<endl;//tiaos
// cout<<wa<<"$"<<endl;
}
else if (score[j].find('-')==0)
{
int fen=0;
int k=score[j].size()-1;
for(;k>0;k--)
{
fen-=(score[j][k]-'0')*pow(10,(score[j].size()-1-k));
}
s[i].time[j]=fen;
//cout<<s[i].time[j]<<"#"<<endl;//tiaos
}
else
{
int fen=0;
int k=score[j].size()-1;
for(;k>=0;k--)
{
fen+=(score[j][k]-'0')*pow(10,(score[j].size()-1-k));
}
s[i].time[j]=fen;
// cout<<s[i].time[j]<<"#"<<endl;//tiaos
}
if(s[i].time[j]>0)//算分
{ s[i].number++;
// cout<<s[i].number<<"%%"<<endl;
s[i].timescore+=(s[i].time[j]+s[i].history[j]*(m));
}
}
//cout<<s[i].name<<" "<<s[i].number<<" "<<s[i].timescore<<endl;
i++;
}
sort(s+1,s+i);
for(int o=1;o<i;o++)
{
printf("%-10s ",s[o].name);
printf("%2d ",s[o].number);
printf("%4d\n",s[o].timescore);
}
}
学习参考答案的读入方式。
优化与总结
1、string的find是找到第一个为’c’的位置
2、string是没法直接比较当个字符是否相等（报错.jpg）
3、sscanf 超好用。
C题 打牌
题意
瑞神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|
±–±--±–±--±–±--±–±--±–±--±–±--±–+
做法
记录一下顺时针的顺序。
对于两行数据，每两个是一组，分别代表花色和大小。
每八个是一轮，代表这一轮中，四个人分别抽的4张牌。
对每个人手牌排序。
接下来，我们首先找到第一个抽牌的人对应我们顺时针的顺序的编号是几。
再沿着顺时针方向（计数++）查找间隔几个是South Player。
从South Player 顺时针按照标准输出即可。
注意顺时针寻找下一个时取模防止溢出
代码
```cpp
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
char sx[4]={'N','E','S','W'};
map <char,int> numbers;
map<int,string> sxx;
map<char,int> pnumbers;
struct pai{
char hs;
char dx;
bool operator <(const pai &m) const
{
if(pnumbers[hs]!=pnumbers[m.hs])return pnumbers[hs]<pnumbers[m.hs];
if(numbers[dx]!=numbers[m.dx]) return numbers[dx]<numbers[m.dx];
}
};
pai p[4][13];
int main()
{
numbers['2']=0;
numbers['3']=1;
numbers['4']=2;
numbers['5']=3;
numbers['6']=4;
numbers['7']=5;
numbers['8']=6;
numbers['9']=7;
numbers['T']=8;
numbers['J']=9;
numbers['Q']=10;
numbers['K']=11;
numbers['A']=12;
sxx[0]="North player";
sxx[1]="East player";
sxx[2]="South player";
sxx[3]="West player";
pnumbers['C']=0;
pnumbers['D']=1;
pnumbers['S']=2;
pnumbers['H']=3;
char first;
string s1,s2;
while(cin>>first&&first!='#')
{ //cout<<first<<"$"<<endl;
cin>>s1>>s2;
for(int i=0;i<=50;i+=2)
{
p[(i/2)%4][(i/2)/4].hs=s1[i];
p[(i/2)%4][(i/2)/4].dx=s1[i+1];
}
for(int i=52;i<=103;i+=2)
{
p[(i/2)%4][(i/2)/4].hs=s2[i-52];
p[(i/2)%4][(i/2)/4].dx=s2[i+1-52];
}
for(int i=0;i<=3;i++)sort(p[i],p[i]+13);
int mm=0,i=0;
for(;mm<4;mm++)
{
if(sx[mm]==first)break;
}
for(;i<4;i++)
{
if(sx[(mm+1+i)%4]=='S')break;
}
//cout<<i<<"#####";
for(int k=0;k<4;k++,i++)
{
cout<<sxx[(k+2)%4]<<":"<<endl;
cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+"<<endl;
for(int u=0;u<13;u++)
{
cout<<"|"<<p[i%4][u].dx<<" "<<p[i%4][u].dx;
}
cout<<"|"<<endl;
for(int u=0;u<13;u++)
{
cout<<"| "<<p[i%4][u].hs<<" ";
}
cout<<"|"<<endl;
for(int u=0;u<13;u++)
{
cout<<"|"<<p[i%4][u].dx<<" "<<p[i%4][u].dx;
}
cout<<"|"<<endl;
cout<<"+---+---+---+---+---+---+---+---+---+---+---+---+---+"<<endl;
}
cout<<endl;
}
}
参考答案用的比我好多了。
总结
1、仅c++11里支持map通过{}初始化
作业 bfs问题
A
题意
东东有一张地图，想通过地图找到妹纸。地图显示，0表示可以走，1表示不可以走，左上角是入口，右下角是妹纸，这两个位置保证为0。既然已经知道了地图，那么东东找到妹纸就不难了，请你编一个程序，写出东东找到妹纸的最短路线。
Input
输入是一个5 × 5的二维数组，仅由0、1两数字组成，表示法阵地图。
Output
输出若干行，表示从左上角到右下角的最短路径依次经过的坐标，格式如样例所示。数据保证有唯一解。
Sample Input
0 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)
做法
用结构体储存点信息，加个N编号记录是第几个，pre记录父节点编号
用vis标记是否经过。
vector 记录经过的每个点。
bfs遍历一遍
输出路径方式：
1、一开始就把终点作为起点，逆向跑bfs，输出时逆了两次于是直接可以正向输出
2、通过递归输出
3、通过栈压入，然后输出
代码
#include <iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int a[6][6];
bool vis[6][6];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct point{
int x,y,step;
int N,pre;
};
queue<point>q;
vector<point> v;
void output(int N)
{
if(N==0){
cout<<"(0, 0)"<<endl;
return;
}
output(v[N].pre);
cout<<"("<<v[N].x<<", "<<v[N].y<<")"<<endl;
}
void bfs()
{
vis[0][0]=1;
point n1;
n1.x=0,n1.y=0,n1.N=0,n1.pre=0;
q.push(n1);
v.push_back(n1);
int N=0;
while(!q.empty())
{ //cout<<"Asd";
point n2=q.front();
q.pop();
for(int i=0;i<4;i++)
{
n1.x=n2.x+dx[i];
n1.y=n2.y+dy[i];
if(n1.x>=0&&n1.y>=0&n1.x<=4&&n1.y<=4&&!vis[n1.x][n1.y]&&!a[n1.x][n1.y])
{
vis[n1.x][n1.y]=true;
n1.step=n2.step+1;
n1.N=++N;
n1.pre=n2.N;
q.push(n1);
v.push_back(n1);
if(n1.x==4&&n1.y==4)
{
output(n1.N);
//cout<<n1.step<<endl;
return ;
}
}
}
}
}
int main()
{
memset(vis,false,sizeof(vis));
memset(a,-1,sizeof(a));
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
cin>>a[i][j];
}
}
bfs();
return 0;
}
B 倒水
题意
倒水问题 “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
做法
倒水有6种情况
1、a倒满
2、b倒满
3、a倒空
4、b倒空
5、 a倒进b
（1）a的水比b的空余多
（2）a的水比b的空余少
6、b倒进a
（1）b的水比a的空余多
（2）b的水比a的空余少
标记 a的水量和b的水量作为当前状态
结束状态为 a的水量=c的水量或者b 的水量=c的水量
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
struct node{
int x,y,N,pre,type,step;
};
bool vis[1010][1010];
queue<node> q;
vector<node> v;
int a,b,c;
void output(int N)
{
if(N==0)return;
// cout<<N<<"*****"<<endl;
output(v[N].pre);
switch(v[N].type){
case 1: printf("fill A\n");break;
case 2: printf("fill B\n");break;
case 3: printf("empty A\n");break;
case 4: printf("empty B\n");break;
case 5: printf("pour A B\n");break;
case 6: printf("pour B A\n");break;
}
}
void bfs()
{ int N=0;
vis[0][0]=1;
node temp;
temp.x=0;
temp.y=0;
temp.N=0;
temp.pre=0;
q.push(temp);
v.push_back(temp);
while(!q.empty())
{
node temp2,temp3;
temp2=q.front();
q.pop();
for(int i=1;i<=6;i++)
{
switch(i)
{
case 1:
temp3.x=a;
temp3.y=temp2.y;
temp3.type=1;
break;
case 2:
temp3.x=temp2.x;
temp3.y=b;
temp3.type=2;
break;
case 3:
temp3.x=0;
temp3.y=temp2.y;
temp3.type=3;
break;
case 4:
temp3.x=temp2.x;
temp3.y=0;
temp3.type=4;
break;
case 5:
if(temp2.x>b-temp2.y)
{
temp3.x=temp2.x-(b-temp2.y);
temp3.y=b;
}
else{
temp3.x=0;
temp3.y=temp2.x+temp2.y;
}
temp3.type=5;
break;
case 6:
if(temp2.y>a-temp2.x)
{
temp3.x=a;
temp3.y=temp2.y-(a-temp2.x);
}
else{
temp3.y=0;
temp3.x=temp2.x+temp2.y;
}
temp3.type=6;
break;
}
if(temp3.x!=c&&temp3.y!=c&&!vis[temp3.x][temp3.y])
{
vis[temp3.x][temp3.y]=true;
temp3.step=temp2.step+1;
temp3.N=++N;
// cout<<N<<"+++"<<endl;
temp3.pre=temp2.N;
q.push(temp3);
v.push_back(temp3);
}
// cout<<temp3.x<<" "<<temp3.y<<" number:"<<temp3.N<<" pre:"<<temp3.pre<<" type:"<<temp3.type<<"{}"<<endl;
// cout<<v.front().x<<" "<<v.front().y<<" number:"<<v.front().N<<" pre:"<<v.front().pre<<" type:"<<v.front().type<<"{}"<<endl;
if(temp3.x==c||temp3.y==c)
{ //cout<<temp3.N<<" asd"<<endl;
vis[temp3.x][temp3.y]=true;
temp3.step=temp2.step+1;
temp3.N=++N;
// cout<<N<<"+++"<<endl;
temp3.pre=temp2.N;
q.push(temp3);
v.push_back(temp3);
output(temp3.N);
cout<<"success"<<endl;
return;
}
}
}
}
int main()
{
while(~scanf("%d%d%d",&a,&b,&c))
{//cout<<a<<b<<c;
while(!q.empty())q.pop();
v.clear();
memset(vis,false,sizeof(vis));
bfs();
}
}