2018腾讯秋招笔试题解

第一题

第一题思路是区间LCM,网上均有各种各样的题解,可以搜搜看看不同做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int BORDER = 1e6+6;
bool visit[BORDER];
int prime[BORDER];
int len = 0;
//count if is prime,and record the prime in prime array
void countPrime(){
for(int i=2;i<BORDER;i++){
if(!visit[i]){
prime[len++]=i;
for(int j=i+i;j<BORDER;j+=i){
visit[j]=true;
}
}
}
}
int main(){
int n;
countPrime();
while(cin>>n){
long long maxPrime = 1;
for(int i = 0; prime[i] <= n; i++){
long long k = prime[i];
//prime^k
while( k*prime[i] <= n){
k *= prime[i];
}
maxPrime = max(maxPrime,k);
}
cout<<2*maxPrime<<endl;
}
return 0;
}

第二题

思路就是每次输入一条新的边时,同时获取以起点为终点的城市集合v1,和以终点为起点的城市集合v2,然后任意v1到任意v2设置为true即可,最后统计一下入度出度,满足条件计数器+1,返回结果即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//100%
#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main(){
int n,m;
while(cin>>n>>m){
vector<vector<bool>> city(n+1,vector<bool>(n+1,false));
for(int i=0;i<m;i++){
int from,to;
cin>>from>>to;
city[from][to] = true;
vector<int> start,end;
for(int j=1;j<=n;j++){
if(city[to][j]){
end.push_back(j);
city[from][j] = true;
}
if(city[j][from]){
start.push_back(j);
city[j][to] = true;
}
}
for(auto st:start){
for(auto ed:end){
city[st][ed] = true;
}
}
}
int res = 0;
for(int i=1;i<=n;i++){
int in = 0,out = 0;
for(int j =1;j<=n;j++){
if(city[i][j]){
out++;
}
if(city[j][i]){
in++;
}
}
if(in>out){
res++;
}
}
cout<<res<<endl;
}
return 0;
}

第三题

思路就是暴力,枚举A的倍数到B-1,然后每个都按照公式判断一次即可,没找对应的数学解释,因为B<100所以一般不会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
if(c==0){
cout<<"YES"<<endl;
continue;
}
bool flag = false;
for(int i=1;i<=b-1;i++){
if((a*i)%b==c){
cout<<"YES"<<endl;
flag = true;
break;
}
}
if(!flag){
cout<<"NO"<<endl;
}
}
}
return 0;
}