The Note of Tencent Autumn Recruitment

2018-09-16

今天早上写了腾讯秋招的题目。第一次写腾讯的笔试题，题型跟今日头条的有些不同。

笔试包括20道选择题（60分）及3道编程题（60分）。

选择题涉及计算机网络、操作系统（页面交换）、数据库（sql语法）、数据结构（出栈序列、搜索算法、B树和B+树、哈夫曼编码）、C++等知识。第一道选择题考了函数指针，然后也有一些知识点是没有见过的，像MapReduce、JVM等。（先记下关键字，具体的并不了解）

第一道编程题只通过了20%的样例，第二道是40%，第三道编程题终于过了。感觉腾讯的编程题的测试样例的数据规模不会像字节跳动的题目一样大。（不过学渣本人还是没能写出来）

编程题的具体题目如下。

第一题

小Q在学校学习了最小公倍数的求法：

LCM(2) = 2, LCM(4, 6) = 12, LCM(1, 2, 3, 4, 5, 6) = 60

为了检验小Q学习得怎么样，牛牛出了一个算法题给小Q：

牛牛给出一个正整数n，让小Q计算出最小的大于n的正整数m，使其满足：LCM(n + 1, n + 2, … , m) = LCM(1, 2, …, m)

例如，牛牛给出的正整数n = 3，那么m = 6，因为LCM(4, 5, 6) = LCM(1, 2, 3, 4, 5, 6) = 60，并且这个m是最小的大于n的正整数。

输入描述：

输入包括一个正整数 n (1 <= n <= $10^6$)

输出描述

输出一个正整数，即最小的满足条件的m

示例1：

输入： 3

输出： 6

思路：

好久没有看到求最小公倍数了。现场想了一下，但是没想好m值要怎么修改，所以直接粗暴得 ”m++“ .

总的思路就是，因为LCM(n + 1, n + 2, … , m) = LCM(1, 2, …, m)，而LCM(1, 2, …, m)则是LCM(1, 2, …, n)及LCM(n + 1, n + 2, … , m)的最小公倍数，因此LCM(1, 2, …, n)必定是LCM(n + 1, n + 2, … , m) 的约数。

先把考试的时候的代码贴出来。之后牛客网的真题出来，我再去测吧。

C++代码：

#include<iostream>
#include<vector>
using namespace std;

long long LCM(vector<int> input) {
	int len = input.size();
	//cout<<len<<endl; 
	int max = input[len - 1];
	//cout<<max<<endl;
	long long result = max;
	for (int i = len - 2; i >= 0; i--) {
		int temp = result;
		while (result%input[i] != 0) {
			result += temp;
		}
	}
	return result;
}

int main() {
	int n;
	cin>>n;
	int m = n + 1;
	vector<int> temp1;
	for (int i = 1; i <= n; i++) temp1.push_back(i);
	long long num = LCM(temp1);
	while(1) {
		vector<int> temp2;
		for (int i = n + 1; i <= m; i++) temp2.push_back(i);
		if (LCM(temp2) % num == 0) break;
		m++;
	}
	cout<<m<<endl;
	return 0;
}

第二题

小Q所在的王国有n个城市，城市之间有m条单向道路连接起来。

对于一个城市v，从城市v出发可以到达的城市数量为x，从某个城市出发可以达到城市v的城市数量为y，如果 y > x，则城市v是一个重要城市（间接可达也算可以到达）

小Q希望你能帮他计算一下王国中一共有多少个重要的城市。

输入描述：

输入包括 m + 1行

第一行包括两个数 n 和 m （1 <= n, m <= 1000），分别表示城市数和道路数

接下来m行，每行两个数 u, v（1 <= u, v <= n），表示一条从u到v的有向道路，输入中可能包括重边和自环。

输出描述：

输出一个数，重要节点的个数

示例1：

输入：

４　３

２　１

３　２

４　３

输出：

2

思路：

最近几乎每次机试都碰上了邻接图，中大夏令营碰上了，字节跳动的笔试也有遇到。但我还是屡屡栽跟头，还是因为太菜了吧，哎。

好的，牢骚完了。老实说我也不知道这道题我错在哪里。先根据输入确定邻接图，再遍历每一索引对应的行和列，如果符合 y > x 就再最终结果上加一。但是只是通过40%的案例，我猜应该还是邻接图的问题。等我找到错误原因再来补充吧，先贴出考试时的代码。

C++代码：

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

int main() {
	int n, m;
	cin>>n;
	cin>>m;
	vector<vector<int> > way;
	for (int i = 0; i < n; i++) {
		vector<int> temp;
		for (int i = 0; i < n; i++) temp.push_back(0);
		way.push_back(temp);
	} 
	for (int i = 0; i < n; i++) {
		way[i][i] = 1;
	}
	int t = m;
	while(t--) {
		int u, v;
		cin>>u;
		cin>>v;
		u--;
		v--;
		if (way[u][v]) continue;
		stack<int> reach;
		reach.push(v);
		while (!reach.empty()) {
			int x = reach.top();
			way[u][x] = 1;
			reach.pop();
			for (int i = 0; i < n; i++) {
				if (way[x][i] && way[u][i] == 0) reach.push(i);
			}
		}
		stack<int> reach2;
		reach2.push(u);
		while (!reach2.empty()) {
			int x = reach2.top();
			way[x][v] = 1;
			reach2.pop();
			for (int i = 0; i < n; i++) {
				if (way[i][x] && way[i][v] == 0) reach2.push(i);
			}
		}
	}
	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout<<way[i][j]<<" ";
		}
		cout<<endl;
	}
	*/
	//统计重要城市
	int result = 0;
	for (int i = 0; i < n; i++) {
		int x = 0;
		int y = 0;
		for (int j = 0; j < n; j++) {
			if (way[i][j]) x++;  //可以到达的城市
			if (way[j][i]) y++;  //可以到达该城市的城市 
		}
		if (y > x) result++;
	}
	cout<<result<<endl;
	return 0;
}

第三题

妞妞是一个漂亮的女孩，她有很多仰慕者，小Q是其中一个。一天小Q向妞妞表白了，但是妞妞希望她的伴侣是一个聪明的男孩，所以她给小Q出了一道题作为考验：

给出三个数字A，B，C，小Q可以选择若干数字，但是这些数字必须是A的倍数，并且至少得选择一个数字。问是否存在一种选择方案使得这些数字的和对B取余的结果为C，如果存在输出 ”YES“，否则输出 ”NO“。

小Q觉得妞妞这道题目很难，所以找来了学过算法的你，希望你能为他解决这个难题。

输入描述：

输入的以第一行为整数t（1 <= t <= 20），表示测试情况数

接下来 t 行每行3个数字 A， B，C，以空格分割

1 <= A <= 100

1 <= B <= 100

0 <= C < B

输出描述：

对于每行，输出 ”YES“ 或者 ”NO“ （不带引号）

示例1：

输入：

3

91　16　５

58　16　０

96　12　４

输出：

YES

YES

NO

思路：

因为每个数字都是A的倍数，因此这些数的和也必定是A的倍数。A mod B 的结果 num 是固定的（0 <= num < B），而 A 的倍数 mod B 的结果也是在 [0, B)范围内。在 [A, A B]中，经过了 A 的倍数 mod B 的所有结果。循环有两种情况，得到完全不重复的元素，即[0, B)范围内的所有整数；或者，序列的某个元素开始重复，一旦第一个元素开始重复，后面的所有元素也必定会重复。因此 [A, A B]保证我们经过了所有结果。

C++代码：

#include<iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--) {
		int a, b, c;
		cin>>a;
		cin>>b;
		cin>>c;
		int mod = a%b;
		int n = mod;
		int result = 0; //初始时认为不存在 
		for (int i = 0; i < b; i++) {
			if (n == c) {
				result = 1;
				break;
			}
			n = n + mod >= b ? n + mod - b : n + mod;
		}
		if (result) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}