[数据结构与算法]二刷系列:PATadvanced:1012、1013(暴力美学+深优统计连通图数量)

鸽子又来了啊

今天是一道bf加一道dfs，意外的顺利

一.1012The Best Rank

题目大意就是说，给你一些学生的C语言、微积分、英语成绩，然后根据一组query，按要求(优先级:A >C>M>E)输出其单科最高排名及那科的缩写

需要注意的地方大概就是数据结构的设计以及对于排名的统计(我菜，暴力做了)

对于数据结构设计，为了统计时方便索引我开辟了很大的数组(学生id是6位那么就是100000-1000000)设置为全局变量(懂得都懂)

vector<student> stu(1000000);	//意外的没有内存超限

//详细数据结构设计
using ll = long long;
struct student
{
	bool exist = false;
	ll a,c,m,e;	//平均成绩，c语言，数学，英语
};

对于排名统计，我采用了分别对单科成绩进行遍历统计，如果当前遍历学生的单科成绩高于被问询的学生的单科成绩，则该科rank+1(rank初始值为1)

具体代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, q, id, a, c, m, e;
struct student
{
    bool exist = false;
    ll id, a, c, m, e;
};
string rk[] = {"A", "C", "M", "E"};
vector<student> stu(1000000);
int main(void)
{
    cin>>n>>q;
    for (ll i = 0; i < n; ++i)
    {
        cin>>id>>c>>m>>e;
        stu[id].a = (c + m + e) / 3;
        stu[id].c = c;
        stu[id].m = m;
        stu[id].e = e;
        stu[id].exist = true;
    }
    while (q--)
    {
        cin>>id;
        if (!stu[id].exist) {cout<<"N/A"<<endl;continue;}
        else //若所查的人存在
        {
            ll r1=1, r2=1, r3=1, r4=1;
            ll a = stu[id].a, c = stu[id].c, m = stu[id].m, e = stu[id].e;
            for (ll i = 100000; i < 1000000; ++i)
            {
                if (stu[i].exist and i != id and stu[i].a > a) {r1 += 1;}
            }
            for (ll i = 100000; i < 1000000; ++i)
            {
                if (stu[i].exist and i != id and stu[i].c > c) {r2 += 1;}
            }
            for (ll i = 100000; i < 1000000; ++i)
            {
                if (stu[i].exist and i != id and stu[i].m > m) {r3 += 1;}
            }
            for (ll i = 100000; i < 1000000; ++i)
            {
                if (stu[i].exist and i != id and stu[i].e > e) {r4 += 1;}
            }
            ll fin = r1, idx = 1;
            if (fin > r2) {fin = r2; idx = 2;}
            if (fin > r3) {fin = r3; idx = 3;}
            if (fin > r4) {fin = r4; idx = 4;}
            cout<<fin<<' '<<rk[idx - 1]<<endl;
        }
    }
    return 0;
}

二.1013 Battle Over Cities

题目花里胡哨，我去年甚至刚开始没有读懂题。
一言以蔽之：求去除点之后连通子图数减一

直接上代码，这个题dfs挺好写的

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<ll>> r(1001);
bool visited[1001];
ll n,m,q,c1,c2;
void dfs(ll curcity)
{
    if (visited[curcity]) {return;}
    else 
    {
        visited[curcity] = true;
        ll l = r[curcity].size();
        for (ll i = 0; i < l; ++i) 
        {
            dfs(r[curcity][i]);
        }
    }
}
int main(void)
{
    cin>>n>>m>>q;
    for (int i = 0; i < m; ++i)
    {
        cin>>c1>>c2;
        r[c1].push_back(c2);
        r[c2].push_back(c1);
    }
    while (q--)
    {
        cin>>c1;
        for (ll j = 1; j <= n; ++j) {visited[j] = false;}
        visited[c1] = true;
        ll count = 0;
        for (ll j = 1; j <= n; ++j)
        {
            if (!visited[j]) {count += 1; dfs(j);}
        }
        cout<<count - 1<<endl;
    }
    return 0;
}

睡了睡了，好困