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;
}

#笔试题目##笔经#