招商银行研发岗 第一次笔试
第一题就是RL的问题，这题仔细想想应该算是个思维题吧。
这是第一题的AC代码，只要判断RL不同的时候两边的数量就可以啦。
#include <bits/stdc++.h>
using namespace std;
string s;
int an[100005]={0};
int main(){
cin >> s;
int cnt = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'R')
cnt++;
else{
int cnt1 = 0;
int x = i;
while(i < s.length()&&s[i] == 'L'){
cnt1++;
i++;
}
i--;
an[x-1] = max((cnt+1)/2 + cnt1/2, an[i-1]);
an[x] = max(cnt/2 + (cnt1+1)/2, an[i]);
cnt = 0;
}
}
for(int i = 0; i < s.length(); i++){
printf("%d%c", an[i], i == s.length()-1 ? '\n':' ');
}
return 0;
} AC代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, x, y, z;
vector<pair<ll,ll> > v[500005];
ll val[500005], vis[500005];
ll dfs(ll x){
ll sum = 0;
vis[x] = 1;
for(int i = 0; i < v[x].size(); i++){
if(vis[v[x][i].first]) continue;
sum = max(sum, dfs(v[x][i].first)+v[x][i].second);
}
val[x] = sum;
return sum;
}
int main(){
cin >> n;
for(int i = 0; i < n-1; i++){
cin >> x >> y >> z;
v[x].push_back(make_pair(y, z));
v[y].push_back(make_pair(x, z));
}
dfs(1);
for(int i = 1; i <= n; i++){
printf("%lld%c", val[i], i == n?'\n':' ');
}
return 0;
} 
百威成长空间 50人发布