腾讯 0823 技术研究数据分析笔试题&题解 4.9分

第一题

题目描述

现在给你一个只包含""括号的字符串，问你至少加多少个字符是合法的，对于字符串合法的定义为：

字符串为空是合法的
若字符串A合法，则字符串(A), [A]也是合法的
若字符串A和字符串B均合法，则AB合法
输入
第一行输入一个字符串s，保证只有题目要求的字符
1 <= len(s) <= 200
输出
输出最少需要添加几个字符可以构成合法的字符串
样例输入
样例输出
1
样例输入
)(][][)(
样例输出
3
分析
如果只有一种括号的话就是leetcode921的原题

有2种括号的话需要用DP去搞。我们先求出来通过添加字符，从i到j能构成的合法串的最短长度是多少。然后状态转移一波(分情况讨论)。

解法

#include <bits/stdc++.h>
using namespace std;
int dp[205][205];
int main(){
  string s;
  int i,j,k,p;
  while(cin>>s){
      memset(dp,0,sizeof(dp));
      if(s.size()==1){
          puts("1");
          continue;
      }
      for(i=0;i+1<s.size();i++){
          if((s[i]=='('&&s[i+1]==')')||(s[i]=='['&&s[i+1]==']'))
          dp[i][i+1]=2;
      }
      for(i=3;i<=s.size();i++){
          for(j=0;j+i-1<s.size();j++){
              k=j+i-1;
              dp[j][k]=max(dp[j][k],dp[j+1][k-1]);
              dp[j][k]=max(dp[j][k],max(dp[j+1][k],dp[j][k-1]));
              if((s[j]=='('&&s[k]==')')||(s[j]=='['&&s[k]==']')){
                  dp[j][k]=max(dp[j][k],dp[j+1][k-1]+2);
              }
              for(p=j+1;p<k;p++){
                  dp[j][k]=max(dp[j][k],dp[j][p]+dp[p+1][k]);
              }
          }
      }
      cout<<s.size()-dp[0][s.size()-1]<<endl;
  }
  return 0;
}

第二题

题目描述

求抛物线 $y=Ax^2+x+B$ 与直线 $x=C$ ，直线 $x=D$ 以及x轴所围成的封闭图形的面积。
输入
第一行为一个整数T，表示测试数据的组数
接下来每行输入四个整数A, B, C, D
1 <= T <= 1000, 1 <= A, B <= 100, -100 <= C <= 100
输出
每组测试数据输出一个答案，为封闭图形的面积
样例输入
1
2 3 1 2
样例输出
9.16667
分析
简单的微积分，也可以用辛普森公式直接计算：

在平面直角坐标系中，由任意三点(x1, y1), (x2, y2), (x3, y3)（x1<x2<x3，x2 = (x1 + x3)/2）确定的抛物线y= f(x)在[x1, x3]的定积分为

$1/6(x_3-x_1)(y_1+4y_2+y_3)$

解法

#include <bits/stdc++.h>
using namespace std;
double calc(int a, int b, double x) {
return 1.0 * a * x * x + x + b;
}
int main() {
int T; cin >> T;
while (T--) {
    int a, b, c,d;
    cin >> a >> b >> c >> d;
    double mid = (c + d) / 2.0;
    double y1 = calc(a, b, c);
    double y2 = calc(a, b, mid);
    double y3 = calc(a, b, d);
    printf("%.6lf\n", 1.0/6 * (d - c) * (y1 + 4 * y2 + y3));
}
return 0;
}

第三题

题目描述

小Q所在的部门有n个人，要从这n个人中选任意数量的人组成一只队伍，再在这些人中选出一名队长，求不同的方案数对1e9+7取模的结果。如果两个方案选取的人的集合不同或者选出的队长不同，则认为这两个方案是相同的。
输入
一行一个数字n，1<=n <= 1e9
输出
一行一个数字表示答案
样例输入
2
样例输出
4
分析

一个组合数学题，如果不选队长的话选出k个人的方案数就是 $C_n^k$ ，要考虑队长的话方案数就是 $k*C_n^k$ ，最终的方案数为 $\sum_{k=1}^nkC_n^k$ 。经过一顿推导可以得到最终的结果为 $n*2^{n-1}$ 。

解法

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1000000000 + 7;
ll poww(ll base, ll a) {
  ll ans = 1;
  while (a != 0) {
      if (a & 1) {
          ans *= base;
          ans %= mod;
      }
      base *= base;
      base %= mod;
      a >>= 1; 
  }
  return ans;
}
int main() {
  int n;
  while (cin >> n) {
      cout << (n* poww(2, n-1)) % mod << endl;
  }
  return 0;
}

第四题

题目描述

我们定义集合g(x)为：与x相邻的节点的集合；从而定义图的价值为：图中满足g(x)=g(y)这样的点对(x,y)的数量
现在给定一个n个节点和m条边的无向联通图，请你计算出当前图的价值
输入
第一行输入两个正整数n和m，表示点的数量和边的数量
接下来m行，每行输入两个整数x和y，表示x和y之间连边
2<=n<=100000, 1<=m <= 200000, 1 <= x, y <= n
输入保证图连通，且没有重边和环
输出
输出结果
样例输入
4 3
1 2
2 3
2 4
样例输出
3
分析

对于每一个顶点，可以得到它相邻的点的集合，将相邻的点的列表做个哈希，最后直接判断即可过90%。

解法

#include <bits/stdc++.h>
using namespace std;
const int siz=100005;
vector<int> G[siz];
map<int,int> mp;
int main(){
  int n,m,i,j,k,x,y,ans,tmp;
  while(scanf("%d%d",&n,&m)!=EOF){
      for(i=0;i<=n;i++)
      G[i].clear();
      for(i=0;i<m;i++){
          cin>>x>>y;
          G[x].push_back(y);
          G[y].push_back(x);
      }
      ans=0;
      mp.clear();
      for(i=1;i<=n;i++){
          for(j=0;j<G[i].size();j++)
          mp[i]+=(G[i][j]*G[i][j]);
      }
      for(i=1;i<=n;i++){
          if(G[i].size()<=1)
          continue;
          for(j=0;j<G[i].size();j++){
              for(k=j+1;k<G[i].size();k++){
                  if(G[G[i][j]].size()!=G[G[i][k]].size())
                  continue;
                  if(mp[G[i][j]]==mp[G[i][k]])
                  ans++;
              }
          }
      }
      printf("%lld\n",ans);
  }
  return 0;
}

第五题

题目描述

现在有n个点，有m条双向路径，其中有一个宝物在n点，已知有k个传送门，每一个传送门可以从x点到达y点，传送门单向的，通过传送门传送不算距离，现在从1点开始，若能拿到宝物，输出走过的最短距离，若无法拿到，请输出-1。

输入
第一样输入3个数n, m 和k，代表有n个点，m条双向路径以及k个传送门
接下来m行，每一行输入三个数x,y,l代表双向路径从x到y的距离是l
接下来k行，每一行输入两个数x,y表示x和y之间有传送门
1<=n<=2000, 1<=m<=50000, 1<=k<=100, 1<=x,y<=n, 1<=l<=100

输出
对于每一组数据，输出一个答案代表拿到宝物走过的最短距离

样例输入
5 3 2
1 2 1
2 3 1
3 4 1
4 5
1 2

样例输出
2

分析

最直接的最短路，直接建图跑dijkstra即可

解法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2002;
const int INF = 0x3f3f3f3f;
struct Edge {
  int u, v, w;
  int next;
}E[maxn *100];
int head[maxn];
int cnt;
void init() {
  memset(head, -1, sizeof(head));
  cnt = 0;
}
void add_edge(int u, int v, int w) {
  E[cnt].u = u;
  E[cnt].v = v;
  E[cnt].w = w;
  E[cnt].next = head[u];
  head[u] = cnt++;
}
int n;
int vis[maxn];
int dis[maxn];
int gao(int s, int t){
  for(int i = 1;i <= n;i++) vis[i] = 0;
  for(int i = 1;i <= n;i++) dis[i] = (i == s ? 0 : INF);
  dis[1] = 0;
  for(int i = 1;i <= n;i++) {
      int x, minn = INF;
      for(int j = 1;j <= n;j++){
          if(!vis[j] && dis[j] <= minn){
              x = j;
              minn = dis[j];
          }
      }
      vis[x] = 1;
      for(int j = head[x]; j != -1; j = E[j].next){
          int y = E[j].v;
          int w = E[j].w;
          dis[y] = min(dis[y], dis[x] + w);
      }
  }
  if (dis[n] == INF) return -1;
  return dis[n];
}
int main() {
  int m, k;
  while (cin >> n >> m >> k) {
      init();
      int a, b, w;
      while (m--) {
          cin >> a >> b >> w;
          add_edge(a, b, w);
          add_edge(b, a, w);
      }
      while (k--) {
          cin >> a >> b;
          add_edge(a, b, 0);
      }

      cout << gao(1, n) << endl;
  }
  return 0;
}

文章首发于公众号“面鲸”，欢迎关注～

#笔试题目#