字节跳动2023秋招研发第五场笔试【客户端方向】

T1 求和为0的最长连续序列

通过：100%

思路

定义一个pre[i] 表示从第一个元素到第 $i$ 个元素的影响和即前缀和思想，然后我们枚举左右区间即可，复杂度 $n^2$

代码

#include 

using namespace std;

const int N = 1e3+10;

int pre[N];

int main()
{
	int n = 0;
	int t;
	while(cin>>t) {
		pre[++n] = t;
		pre[n] = pre[n-1] + pre[n];
	}
	int ans = 0;
	for(int l = 1;l <= n; ++l) {
		for(int r = l + 1;r <= n; ++r) {
			if(pre[r] - pre[l - 1] == 0) 
				ans = max(ans,r-l+1);
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

T2 族谱还原

通过：100%

思路

思路就是并查集，维护父子关系即可，主要麻烦再输入的处理上面

代码

#include 
using namespace std;

const int N = 5e2+10;

map<string,string> fa;
map<int,int> height;
vector<string> sum;

int n,m;

string find(string x) {
	while(x != fa[x]) x = fa[x];
	return x;
}

int Get_height(string x) {
	int h = 1;
	while(x != fa[x]) {
		x = fa[x];
		h++;
	}
	return h;
}


void fixit(string str) {
	vector<string> tt;
	str.push_back(' ');
	tt.clear();
	int len = 0;
	int l = str.size();
	string tmp = "";
	for(int i = 0;i < l; ++i) {
		if(str[i] == ' ') {
			tt.push_back(tmp);
			len++;
			if(fa[tmp] == "") {
				fa[tmp] = tmp;
				sum.push_back(tmp);
			}
			if(len != 1) {
				string lef = (tt[len - 2]);
				string rig = (tt[len - 1]);
				fa[rig] = lef;
			}
			tmp = "";
			
			
		} else {
			tmp.push_back(str[i]);
		}
	}
}



int main()
{
	cin>>n;
	getchar();
	string tmp;
	for(int i = 1;i <= n; ++i) {
		vector<string> tt;
		tt.clear();
		int len = 0;
		getline(cin,tmp);
//		cout<
		fixit(tmp);
	}
	cin>>m;
	for(auto it : sum) {
		height[Get_height(it)]++;
	}
	cout<<find(sum[0])<<endl;
	cout<<height[m]<<endl;
	
	return 0;
}

T3 二次方程租

通过：100%

思路

对每一个位置我们定义一个影响 $b[i]$ ，如果当前位置 $b[i]$ 乘二大于前一个位置（除开第一个位置），那么当前的状态就定义为 $0$ 否则定义为 $1$ ，那么我们在对这个状态进行一个前缀和处理 $pre[i]$，这样我们就能快速求出一个子区间里面是否有违规定义，即区间和大于0，当然这里有个例外就是如果区间的第一个状态为 $1$ 的话也是满足二次方程组的，所以这里特判一下即可，然后又加上区间长度固定 $k+1$ ，所以从前往后扫一遍即可

代码

#include 

using namespace std;

#define ll long long

const int N = 1e5+10;

ll t;

ll a[N],pre[N];

void slove() {
	int n,k;
	cin>>n>>k;
	for(int i = 1;i <= n; ++i) {
		cin>>a[i];
		if(i == 1) pre[i] = 0;
		else {
			pre[i] = (a[i] * 2 <= a[i-1]) + pre[i-1];
		}
	}
	ll ans = 0;
	for(int i = 1;i <= n - k; ++i) {
		int l = i,r = i + k;
		ll res = pre[r] - pre[l - 1];
		if(a[l] * 2 <= a[i-1]) res--;
		if(res == 0) ans++;
	}
	cout<<ans<<endl;
	
}

int main()
{
	cin>>t;
	while(t--) {
		slove();
	}
	
	
	return 0;
}

T4 AB实验室同学冲刺

通过：10%

思路

思路一：想的是写一个BFS，但是感觉会T，于是就没写

思路二：讨论了一下奇偶的情况，发现没有找到啥关系，就硬算了等差数列求和

代码

#include 

using namespace std;

#define ll long long

ll n,x,y;

struct Node{
	int loc;
	int lsize;
	int ttimes;
};

void slove() {//通过率10%
	ll dis = abs(x - y);
	ll lef = (((dis + 1) / 2.0)) * 2;
	ll rig = ((dis)/2) * 2;
	ll ans = (ll)(((sqrt(4.0 * lef + 1.0) - 1.0))/2.0);
	ll ans2 = (ll)(((sqrt(4.0 * rig + 1.0) - 1.0))/2.0);
	ans = max(ans,ans2);
	cout<<(ans * 2) + 2<<endl;
}

void bfs() {
	int begin = min(x,y);
	
	queue<Node> que;
	//que.push({})
}

int main()
{
	cin>>n;
	while(n--) {
		cin>>x>>y;
		slove();
	}
	
	
	return 0;
}