4.7 华为机试题

三道题比较基础，全程暴力，一个小时全部AC……

1. 第一题，并查集，处理一下就好。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

map<string, string> pre;
string findp(const string str1)
{
    if(pre[str1] == "")
    {
        pre[str1] = str1;
        return str1;
    }
    else
    {
        string tmp = str1;
        while(pre[tmp] != tmp)
        {
            tmp = pre[tmp];
        }
        return tmp;
    }
}
int main()
{

    int n;
    cin>>n;
    string str1, str2;
    while(n--)
    {
        cin>>str1>>str2;
        string p1 = findp(str1);
        string p2 = findp(str2);
        if(p1 < p2)
            swap(p1, p2);
        if(p1 != p2)
        {
            pre[p1] = pre[p2];
        }

    }
    set<string> s;
    for(auto it = pre.begin(); it != pre.end(); it++)
    {
        string tmp = findp(it->first);
        s.insert(tmp);
    }
    cout<<s.size()<<endl;
    return 0;
}

2. 暴力模拟，每次看有没有依赖，没有就记录，有的话就继续循环。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

const int maxn = 1001;
vector<vector<int>> mp;
vector<int> t;
vector<bool> visted;
vector<int> tt;
int main()
{
    string str;
    getline(cin, str);
    int now = 0;
    for(int i=0; i<str.size(); i++)
    {
        if(str[i] != ',')
        {
            now *= 10;
            now += str[i]-'0';
        }
        else
        {
            t.push_back(now);
            now = 0;
        }
    }
    if(str.size() > 0)
    {
        t.push_back(now);
    }
    int n = t.size();
    visted.resize(n, 0);
    mp.resize(n, vector<int>(n));
    tt.resize(n, 0);

    getline(cin, str);
    bool vis = 0;
    int x, y;
    now = 0;
    for(int i=0; i<str.size(); i++)
    {
        if(str[i] == ',')
        {
            y = now;

            mp[x][y] = 1;
            now = 0;
        }
        else if(str[i] == '-')
        {
            x = now;
            now = 0;
        }
        else if(str[i] == '>')
        {
            continue;
        }
        else
        {
            now *= 10;
            now += str[i] - '0';
        }
    }
    if(str.size() > 0)
    {
        y = now;
        mp[x][y] = 1;
    }

    int cnt = 0;
    int sum = 0;
    while(cnt < n)
    {
        for(int i=0; i<n; i++)
        {
            if(!visted[i])
            {
                vis = true;
                for(int j=0; j<n; j++)
                {
                    if(mp[i][j] != 0)
                    {
                        vis = false;
                        break;
                    }
                }
                if(vis)
                {
                    visted[i] = 1;
                    tt[i] = t[i] + sum;
                    sum = tt[i];
                    cnt++;
                    for(int j=0; j<n; j++)
                    {
                        mp[j][i] = 0;
                    }
                }
            }
        }
    }
    if(n > 0)
        cout<<tt[0];
    for(int i=1; i<n; i++)
        cout<<','<<tt[i];
    cout<<endl;
    return 0;
}

3. dfs暴力+剪枝，数据范围13，2^13次方感觉不会不过。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

vector<vector<int>> mp;
int maxx = -1;
int n,m,t;
void dfs(int x, int y, int now)
{
    if(now > t)
        return;
    if(x == n-1 && y == m-1)
    {
        maxx = max(now, maxx);
        return;
    }
    if(x+1 < n)
    {
        dfs(x+1, y, now + mp[x+1][y]);
    }
    if(y+1 < m)
    {
        dfs(x, y+1, now + mp[x][y+1]);
    }
}
int main()
{

    
    cin>>n>>m>>t;
    mp.resize(n, vector<int>(m));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>mp[i][j];
        }
    }
    dfs(0, 0, mp[0][0]);
    cout<<maxx<<endl;
    return 0;
}

#笔试题目##华为#