2020 字节跳动Byte Camp夏令营 笔试题交流
笔试一共150分钟，从9点到11点半，有单选、不定项选择、填空和编程四道。
回忆中。。。
单选飞速过了，所以题目记不清了。多选第一题是从归并排序、冒泡排序、直接选择排序、堆排序、快速排序、希尔排序选出稳定的排序算法；第二题好像是个操作系统多线程的问题，具体记不得了。
填空第一题是有1、2、、、101共101个数，甲乙两个人轮流取9个数，最后剩两个数，问这两数的绝对值之差S是多少（假设甲乙都足够聪明，甲要使S尽可能大，乙要使S尽可能小） 我也不知道乱猜的55。
填空第二题是a+b+c+d=20的正整数解有多少组。我觉得就是19个空插3个隔板的问题，直接C19、3=969了
接下来是编程题：（前三题比较简单都过了，最后一题暴力O(n2)超时过了50%，如果哪个大佬会请留言，感激不尽）
第一题
给定两维数组，数组中为0或1,1为障碍。给定初始坐标(x,y)，给目的地坐标(X,Y)，每一步可以上下左右移动，求出初始到结束的最短路径。
直接从初始坐标开始广搜即可。
#include<iostream>
#include<queue>
using namespace std;
struct point{
int x,y,s;
};
int a[105][105],n,m,x1,y1,x2,y2,v[105][105];
queue<point> q;
int main(){
int t; cin>>t;
while(t--){
cin>>m>>n>>y1>>x1>>y2>>x2;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
v[i][j]=0;
}
}
while(!q.empty()) q.pop();
if(x1==x2&&y1==y2){
cout<<"1"<<endl; continue;
}
point p;
p.x=x1; p.y=y1; p.s=1;
q.push(p);
bool flag=false;
while(!q.empty()){
p=q.front();
q.pop();
if(p.x<0||p.x>=n||p.y<0||p.y>=m) continue;
if(v[p.x][p.y]||a[p.x][p.y]) continue;
//cout<<p.x<<" "<<p.y<<endl;
if(p.x==x2&&p.y==y2){
flag=true;
cout<<p.s<<endl;
break;
}
v[p.x][p.y]=1;
point p1; p1.x=p.x+1; p1.y=p.y; p1.s=p.s+1; q.push(p1);
point p2; p2.x=p.x-1; p2.y=p.y; p2.s=p.s+1; q.push(p2);
point p3; p3.x=p.x; p3.y=p.y+1; p3.s=p.s+1; q.push(p3);
point p4; p4.x=p.x; p4.y=p.y-1; p4.s=p.s+1; q.push(p4);
}
if(!flag) cout<<-1<<endl;
}
} 第二题
给定n，两个人每次从中减去1到m任意数，有多组数据，问第一个人能赢的次数。
这个题以前看过的话应该很容易想到，就是看n%(m+1)是否等于0，如果等于0第二个人必赢，否则第一个人必赢。
#include<iostream>
using namespace std;
int main(){
long long t,m,n,ans=0;
cin>>t;
while(t--){
cin>>n>>m;
if(n%(m+1)!=0) ans++;
}
cout<<ans;
} 第三题
第三题就是将json字符串中的注释去掉，注释有//和/* */两种。
这个题主要就是分情况讨论了，用scan.nextLine()依次读取每一行，然后分情况//和/*以及是否在多行注释之间和*/这几种情况讨论，对应输出即可。最后记得每一行最后要System.out.println("");否则直接报PE。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String s;
boolean flag=false;
while(scan.hasNext()) {
s=scan.nextLine();
if(flag) {
int index2=s.indexOf("*/");
if(index2==-1) continue;
flag=false;
System.out.print(s.substring(index2+2));
}
int index2=s.indexOf("/*");
if(index2!=-1) {
System.out.print(s.substring(0,index2));
flag=true;
int index3=s.indexOf("*/");
if(index3!=-1) {
flag=false;
System.out.print(s.substring(index3+2));
}
}
else if(!flag) {
int index=s.indexOf("//");
if(index!=-1) {
System.out.print(s.substring(0,index));
}else {
System.out.print(s);
}
}
System.out.println("");
}
}
} 第四题
给定一个n节点的树，gcd(x,y)表示树的x节点到y节点的一条路径上所有节点的最大公约数，dist(表示路径的长度（节点数）。求gcd(x,y)>1的所有路径中最大的dist(x,y)。就是求一条路径上所有节点的公约数值大于1的最长路径。
我直接从所有结点都作为开始，暴力深搜，过了50%。
#include<iostream>
#include<vector>
using namespace std;
vector<int> e[200005];
int n,a[200005],v[200005],ans=1,k[200005];
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
void f(int i,int now,int p){
v[i]=1;
if(now>ans) ans=now;
for(int j=0;j<e[i].size();j++){
if(!v[e[i][j]]&&k[e[i][j]]){
int pp=gcd(p,gcd(a[i],a[e[i][j]]));
if(pp>1) f(e[i][j],now+1,pp);
else f(e[i][j],1,a[e[i][j]]);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
k[i]=0;
}
for(int i=0;i<n-1;i++){
int x,y; cin>>x>>y;
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=n;i++){
for(int j=0;j<e[i].size();j++){
if(gcd(a[i],a[e[i][j]])>1){
k[i]=1; k[e[i][j]]=1;
break;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) v[j]=0;
if(k[i]&&e[i].size()==1) f(i,1,a[i]);
}
if(ans==1) cout<<0;
else cout<<ans;
} 
