Week 1--A - 化学 (编译器选 GNU G++)

化学很神奇，以下是烷烃基。

烷烃.jpg

假设如上图，这个烷烃基有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)

Output
每组数据，输出一行，代表烷烃基的英文名
数据保证，输入的烷烃基是以上5种之一

Example
Input
2
1 2
2 3
3 4
4 5
5 6
1 4
2 3
3 4
4 5
5 6
Output
n-hexane
3-methylpentane

解题思路：
可以算是暴力解题，将五种烷烃依次分类。
观察图中五种烷烃可以发现，有两种烷烃最大节点连接边数不为三，其中n-hexane节点连接边数最多为2条，2,2-dimethybutane节点连接边数最多为4条，记录最大节点连接边数，即可率先区分这两种烷烃。
对于剩下的三种，其节点连接边数最多为三条，若称连接边数为2的节点为B，称连接边数为3的节点为A，则三种烷烃中与A相邻的B的个数均不相同，可依此区分（但我最后通过计算整个烷烃中B的个数先区分了2,3-dimethybutane,再用判断相邻B个数的方法区分剩下的两个烷烃）。

代码实现如下：

#include<cstdio>
#include<iostream>
using namespace std;
//结构体储存五条边
struct line {
    int a,
        b;
    line() {}
    line(int &_a, int &_b)
    {
        a = _a;
        b = _b;
    }
    void operator=(line &x)
    {
        a = x.a;
        b = x.b;
    }
};
//计算一个节点最多连接边数
int largest(int a[], int n) {
    int mx=0;
    for (int i = 1; i < n; i++) {
        mx = max(mx, a[i]);
    }
    return mx;
}
int main()
{
    int n;
    cin >> n;
    int c, d, i, j;
    line lines[5];
    while (n--)
    {
    
      int count[7];
    for (i = 0; i < 7; i++)
        count[i] = 0;//存储六个节点连接边数
        for (i = 0; i < 5; i++)//读入数据
        {
            cin >> c >> d;
            line t(c, d);
            lines[i] = t;
        }
        for (i = 0; i < 5; i++)//计算各节点连接边数
        {
            if (lines[i].a == 1 || lines[i].b == 1)
                ++count[1];
            if (lines[i].b == 2 || lines[i].a == 2)
                ++count[2];
            if (lines[i].b == 3 || lines[i].a == 3)
                ++count[3];
            if (lines[i].b == 4 || lines[i].a == 4)
                ++count[4];
            if (lines[i].b == 5 || lines[i].a == 5)
                ++count[5];
            if (lines[i].b == 6 || lines[i].a == 6)
                    ++count[6];
        }
        int _count = largest(count,7), y = 0;//求取A
        int s=0;//存储整个烷烃中B个数

        for (i = 1; i < 7; i++)
        {
            if (count[i] == 2)
                s++;
            else if (count[i] == 3&&_count==3)
            {
                for (j = 0; j < 5; j++)
                {   
                                  //if语句判断与A相邻顶点中B的个数，并存入y中
                    if (lines[j].b == i)
                    {
                        for (int k = 1; k < 7; k++)
                            if (lines[j].a == k && count[k] == 2)
                                y++;
                        }
                    else if(lines[j].a==i)
                    for (int k = 1; k < 7; k++)
                            if (lines[j].b == k && count[k] == 2)
                                y++;
                }
            }
        }
    
        switch (_count)
        {
        case 2:
            cout << "n-hexane" << endl;
            break;
        case 3:

                if (s == 0)
                    cout << "2,3-dimethylbutane" << endl;
                else if(s==2)
                {
                    if (y == 2)
                        cout << "3-methylpentane" << endl;
                    else if (y == 1)
                        cout << "2-methylpentane" << endl;
                }

            break;
        case 4:
            cout << "2,2-dimethylbutane" << endl;
            break;
        }
    }
    return 0;
}

解题总结：拿到题最好先过滤一遍，如果这题我把剩下的三种烷烃用一种方法判断，就不用计算整个烷烃结构中B的个数S了。