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;
} 
