精华 VMware2017春招在线编程题解
发布于 2017-03-29 18:36 5924 次浏览 3 赞 最后一次编辑是 2017-03-29 18:56 来自 笔试面试  

新奇的函数:

数论问题,只要考虑2和5这两个素因子出现的次数。(后导零,指末尾0的个数,例如:12000后导零是3, 106500后导零是2)

示例代码:

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cassert>

#pragma warning( disable : 4996)

using namespace std;

int count(int n, int m) {
	int sum = 0;
	while (n) {
		sum += n / m;
		n /= m;
	}
	return sum;
}

int bin(int x) {
	int left = 1, right = 1000000000; //10^9
	int ret = -1;
	while (left <= right) {
		int mid = (left + right) >> 1;
		int c = count(mid, 5);
		if (c == x) {
			ret = mid;
			right = mid - 1;
		}
		else if (c > x) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	return ret;
}
int main() {
	//freopen("func_10.in", "r", stdin);
	//freopen("func_10.out", "w", stdout);
	int x;
	while (cin >> x) {
		assert(x >= 1 && x <= 100000000);
		cout << bin(x) << endl;
	}
}


修路:

枚举一条边,把一颗树拆成两颗,两棵树各取一条路径即可。

示例代码:

#include <cstdio>
#include <cmath>
#include <vector>
#define maxn 309
using namespace std;
vector<int>G[maxn];
int n;
int X[maxn],Y[maxn];
int color[maxn];

void dfs(int u, int fa, int c){
 color[u] = c;
 for(auto v: G[u]){
  if(v == fa)
   continue;
  dfs(v, u, c);
 }
}

int dfs_max(int u, int fa){
 int ans = 0;
 for(auto v: G[u]){
  if(color[v] != color[u])
   continue;
  if(v == fa)
   continue;
  ans = max(ans, dfs_max(v, u) + 1);
 }
 return ans;
}

int solve(int c){
 int ans = 0;
 for(int i = 1; i <= n; i++){
  if(color[i] == c){
   ans = max(ans, dfs_max(i, -1));
  }
 } 
 return ans;
}

int main(){
 while(scanf("%d", &n) != EOF){
  for(int i = 1; i <= n; i++)
   G[i].clear();
   
  for(int i = 0; i < n - 1; i ++){
   scanf("%d%d", &X[i], &Y[i]);
   G[X[i]].push_back(Y[i]);
   G[Y[i]].push_back(X[i]);
  }
  
  int ans = 0;
  for(int i = 0; i < n - 1; i++){
   int u = X[i];
   int v = Y[i];
   dfs(u, v, 1);
   dfs(v, u, 2);
   ans = max(solve(1) * solve(2), ans);
  }
  printf("%d\n", ans);
 }
 return 0;
}


括号序列:

把左括号看成+1,右括号看成-1,一段合法的括号序列任意前缀和大于等于0,且最后求和为0。dp[i][j]表示前i和数的前缀和为j的最高价值,答案为dp[n][0]。

示例代码:

#include <bits/stdc++.h>
#define maxn 2009
using namespace std;
const int INF=1e9;
int a[maxn],b[maxn],n;
int dp[maxn][maxn];
int main(){
	scanf("%d",&n);
	n*=2;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n+1;i++)
		dp[0][i]=-INF;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			if(j){
				dp[i][j]=max(dp[i-1][j-1]+a[i],dp[i-1][j+1]+b[i]);
			}
			else{
				dp[i][j]=dp[i-1][j+1]+b[i];
			}
		}
	}
	printf("%d\n",dp[n][0]);
	//system("pause");
	return 0;
}


3 条回复

请问有原题可以提供吗?

2017-03-30 08:49
小码快跑 回复 coder_VYN7KR6J

同学你好,我们会和VMware沟通,尽快把原题提供给同学重新尝试。

2017-03-30 08:54

请问这个题解是官方的吗,标准测试结果用的是这个生成吗?

2017-04-01 19:13
添加回复
回到顶部