程序设计思维与实践 Week2 实验

A-化学

题意：
根据不同的烷烃基，通过5行a,b描述一个烷烃基。根据输入的烷烃基原子编号，甄别烷烃基的类别。组数T（1≤T≤200000），序号a，b(1≤a,b≤6,a ≤b)。数据保证输入的烷烃基是以上5种之一。
思路：
筛选不同的烷烃基，首先就需要理清不同的烷烃基之间的区别。简单分析后，发现不同烷烃基原子的度是不同的。因此可以采用图论的方法进行分析。

• n-hexane每个原子的度都小于等于2。
• 2-methylpentane和3-methylpentane都有且仅有一个3度节点。
  而这两种烷烃基的3度节点所连接的节点的度是不同的。
  2-methylpentane的三度节点连接了1个2度节点和2个1度节点。
  3-methylpentane的三度节点连接了2个2度节点和1个1度节点。
• 仅有2,2-dimethylbutane有4度节点。
• 2,3-dimethylbutane有2个3度节点。
  根据这种不同，可以很好的筛选出不同的烷烃基。采用数组描述图的方法，利用bfs计算图中每个原子的度，根据度的差异筛选烷烃基，顺利通过。

总结：
做这道题时，其实很容易想出根据原子的度不同对不同的烷烃基进行筛选，但是如何筛选2-methylpentane和3-methylpentane着实难到了我。刚开始我居然认为它们没有差别，仔细的思考才弄清了思路。得到了准确的思路后，写代码倒不是一件很难的事情。计算节点度数已是老生常谈的问题。

代码：

#include<iostream>
#include<cstdio>
int temp[6][6];
int main()
{
	int t;scanf("%d",&t);
	for(int k = 0;k < t;k++)
	{
		for(int i=0;i<6;i++)
			for(int j=0;j<6;j++)
				temp[i][j]=0;
		for(int j = 0;j<5;j++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			temp[x-1][y-1]=temp[y-1][x-1]=1;
		}
		int degree[6];
		for(int i=0;i<6;i++)
			degree[i]=0;
		for(int i= 0;i<6;i++)
			for(int j=0;j<6;j++)
				if(temp[i][j]==1)
				degree[i]++;
		int sum[4];
		for(int i=0;i<4;i++) sum[i]=0;
		for(int i=0;i<6;i++)
			sum[degree[i]-1]++;
		if(sum[2]==0&&sum[3]==0)
			printf("n-hexane\n");
		else if(sum[2]==1)
		{
			for(int i = 0;i<6;i++)
			{
				if(degree[i]==3)
				{
					int sum1=0,sum2=0;
					for(int j = 0;j<6;j++)
					{
						if(temp[i][j]==1)
						{
							if(degree[j]==1)
								sum1++;
							else if(degree[j]==2)
								sum2++;
						}
					}
					if(sum1==2)
						printf("2-methylpentane\n");
					else if(sum1==1)
						printf("3-methylpentane\n");
				}
			}
		}
		else if(sum[2]==2)
			printf("2,3-dimethylbutane\n");
		else if(sum[3]==1)
			printf("2,2-dimethylbutane\n");
	}
	
}

B - 爆零(×)大力出奇迹(√)

题意：
每个人做的题都在对应的题号下有个数量标记，负数表示该学生在该题上有过的错误提交次数但到现在还没有AC，正数表示AC所耗的时间，如果正数a跟上了一对括号，里面有个正数b,则表示该学生AC了这道题，耗去了时间a，同时曾经错误提交了b次。例子可见下方的样例输入与输出部分。

• Input
  输入数据包含多行，第一行是共有的题数n（1≤n≤12）以及单位罚时m（10≤m≤20），之后的每行数据描述一个学生的信息，首先是学生的用户名（不多于10个字符的字串）其次是所有n道题的得分现状，其描述采用问题描述中的数量标记的格式，见上面的表格。
• Output
  根据这些学生的得分现状，输出一个实时排名。实时排名显然先按AC题数的多少排，多的在前，再按时间分的多少排，少的在前，如果凑巧前两者都相等，则按名字的字典序排，小的在前。每个学生占一行，输出名字（10个字符宽），做出的题数（2个字符宽，右对齐）和时间分（4个字符宽，右对齐）。名字、题数和时间分相互之间有一个空格。数据保证可按要求的输出格式进行输出。

思路：
这个题看似题干很长，实则只需考虑两个方面：

1. 如何对不同的学生成绩进行排序？经过分析后发现，这是一个多关键字排序问题，只需要设计出关键字比较函数，再利用qsort函数进行排序即可。
2. 如何读入输出数据？在读入的时候，实际上不需要对括号进行处理，有无括号的实际区别即：没有括号，读入一个数；有括号，读入两个数。所以可以利用sscanf函数对读入了几个数进行判断，大大精简了代码。输出的时候，需要考虑对齐等因素，比较容易，不再赘述。

总结：
刚开始做的时候，没有考虑到sscanf函数，笨笨的对字符串每一个字符都进行分析，非常愚蠢。想到了sscanf函数后，这个题目就迎刃而解。

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
struct T{
	char a[10];
	int count=0;
	int time=0;
}student[1001];
int cmp(T x,T y)
{
	return((x.count>y.count)||(x.count==y.count&&x.time<y.time)
	||(x.count==y.count&&x.time==y.time&&strcmp(x.a,y.a)<0));
}
int main()
{
	int n,m,t,f,i=-1;
	scanf("%d%d",&n,&m);
	while(scanf("%s",&student[++i].a)!=EOF)
	{
		for(int j=0;j<n;j++)
		{
			char ch[10];scanf("%s",&ch);
			int res=sscanf(ch,"%d(%d)",&t,&f);//sscanf()函数--读取格式化字符串，返回成功赋值的个数
			if(res==2)//读取到两个数
				student[i].count++,student[i].time+=t+f*m;
			else if(res==1&&t>0)//读取到一个正数
			{
				student[i].count++,student[i].time+=t;
			}
		}
		//if(i==6) break;
	}
	
	sort(student,student+i,cmp);
	for(int k=0;k<i;k++)
	printf("%-10s %2d %4d\n",student[k].a,student[k].count,student[k].time);
}

C - 瑞神打牌

题意：
我们称四个方向为北 东 南 西。对应的英文是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的结果，每位玩家先输出一行即玩家名称（东南西北），接下来五行，第一行和第五行输出固定格式（见样例），第二行和第四行按顺序和格式输出数值（见样例），第三行按顺序和格式输出花色（见样例）。

思路：
这题就是典型的新瓶装旧酒。实际上和上一题没什么差别。也运用了多关键字排序。唯一的区别就是这个题涉及到了map思想，将不同的J Q K全都映射为数字，方便排序操作。由于该题不支持c++11，所以采用了函数，将J Q K等映射为数字。还需要注意因为发牌员的位置不同，每个人得到牌的顺序也不同，所以需要记录发牌员的位置，防止把牌发错人。
总结：

1. map思想的利用。
2. 细心一些，考虑清楚怎么发牌。

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using std::cin;
using std::sort;
struct T
{
    char color;
    char num;
} card[4][13];
int color2number(char x)
{
    if (x == 'C')
        return 1;
    else if (x == 'D')
        return 2;
    else if (x == 'S')
        return 3;
    else if (x == 'H')
        return 4;
}
int num2number(char num)
{
    if (num <= 57 && num >= 48)
        return num - 48;
    else if (num == 'T')
        return 10;
    else if (num == 'J')
        return 11;
    else if (num == 'Q')
        return 12;
    else if (num == 'K')
        return 13;
    else if (num == 'A')
        return 14;
}
int cmp(T x, T y)
{
    int a1 = color2number(x.color);
    int b1 = color2number(y.color);
    int a2 = num2number(x.num);
    int b2 = num2number(y.num);
    return ((a1 < b1) || (a1 == b1) && (a2 < b2));
}
int main()
{
    char n;
    int count;
    while (scanf("%s", &n) && n != '#')
    {
        char ch[2][52];
        if (n == 'N')
            count = 3;
        else if (n == 'E')
            count = 0;
        else if (n == 'S')
            count = 1;
        else if (n == 'W')
            count = 2;
        for (int i = 0; i < 52; i++)
        {
            char c1, c2;
            cin >> c1 >> c2;
            card[count][i / 4].color = c1;
            card[count][i / 4].num = c2;
            count++;
            count %= 4;
        }
        for (int i = 0; i < 4; i++)
            sort(card[i], card[i] + 13, cmp);
        for (int i = 0; i < 4; i++)
        {
            if (i == 0)
                printf("South player:\n");
            else if (i == 1)
                printf("West player:\n");
            else if (i == 2)
                printf("North player:\n");
            else if (i == 3)
                printf("East player:\n");
            printf("+---+---+---+---+---+---+---+---+---+---+---+---+---+\n");
            for (int j = 0; j < 13; j++)
                printf("|%c %c", card[i][j].num, card[i][j].num);
            printf("|\n");
            for (int j = 0; j < 13; j++)
                printf("| %c ", card[i][j].color);
            printf("|\n");
            for (int j = 0; j < 13; j++)
                printf("|%c %c", card[i][j].num, card[i][j].num);
            printf("|\n");
            printf("+---+---+---+---+---+---+---+---+---+---+---+---+---+\n");
        }
        printf("\n");
    }
}