快手2020校园招聘秋招笔试--算法C试卷 练习 解题报告 Apare_xzc

快手2020校园招聘秋招笔试–算法C试卷 解题报告 Apare_xzc

2020/4/10

---

网页链接：牛客链接

---

题型分布：

        选择题(2分/道*20道)
        编程题(15分/道*4道)

---

选择题中的知识点学习回顾：

线性回归中的残差服从均值（期望）为0的高斯分布（正态分布）。

---

一次不定方程解的个数：m个盒子放入n个小球
盒子非空：插板法：C(n-1,m-1)
盒子可空：先转化为等价非空：C(m+n-1,m-1)

---

直线切分平面：n*(n+1)/2+1
平面分割空间：(n^3+5n+6)/6

---

---

编程题有4道

21. 运动会

输入例子1

3
3 10
1 5
4 6

输出例子1

1

分析：

        加油的时长为(ed-st)/2+1, 每个节目我们可以计算出最少加油时长和最晚开始时间。
        按照最晚开始时间排序，然后贪心检查

代码：

#include <bits/stdc++.h>
using namespace std;
struct Node{
	int st,ed,x,t; //最迟开始时间
	void getx() {
		t = (ed-st)/2+1;
		x = t+st;
	} 
	bool operator < (const Node& rhs) const {
		return x < rhs.x;
	}
}node[20]; 
int main(void) {
	int n;
	cin>>n;
	for(int i=0;i<n;++i)
		scanf("%d%d",&node[i].st,&node[i].ed),node[i].getx();
	sort(node,node+n);
	int p = node[0].st+node[0].t;
	bool ok = true;
	for(int i=1;i<n;++i) {
		if(p>node[i].x) {
			ok = false;break;
		}
		p = p+node[i].t;
	}
	if(ok) puts("1");
	else puts("-1");
	return 0;
} 

---

22. 小游戏

        有位老铁设计了一个跳格子游戏，游戏有N个格子顺序排成一行，编号从1到N，每个格子有点数Qi，有标记Li（标记的范围是1-M），每次跳格子，要选择一个格子a，以任意正偶数距离x跳到格子b，如果格子b在游戏区域内，且La=Lb，则称为一次合法跳跃，获得的分数是(a + b) * (Qa + Qb)。
在继续设计游戏玩法时，这位老铁纠结了很久，于是他决定放弃……但是他想知道所有合法跳跃总共能获得多少分。

数据范围：

    这题不给数据范围，交上去RE的RE, TLE的TLE, 试了几次才试出来…
n<=1E5
m<=1E4

分析：

        每次只能跳到相距偶数个的，Lb相同的格子。开始不知道数据范围，写了一发n^2的暴力，结果T了50%的数据。
        我们把可以互相转移的格子分到一组里，这样的话，在组内，不同的格子之间两两都对分数有贡献。我们分组的时候奇数格子和偶数格子要分开。
        如果x和y可以相互到达，那么(x,y)这对位置对于分数的贡献就是(x+y)*(Qx+Qy) = x*Qx + y*Qx + y*Qy + x*Qy。我们可以计算一下Qx对于答案的贡献。如果组内有m个元素，那么x就要和m-1个位置相互可达。m-1个位置每个贡献都有xQx, 每个y都有yQx。所以Qx的贡献就为x * Qx * (m-1) + Qx * (Qy1 + Qy2 + ... + Qym-1) , 我们可以维护组内Q值的和sum。这样的话Qx的贡献就是x * Qx + Qx * (sum - Qx)。
        我们可以开两个数组分别记录一下每个标志位L的组元素的个数与Q的和，然后计算即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100000+10; 
int Q[N];
int L[N];
int cnt1[10000+10],cnt2[10000+10];
long long sum1[10000+10],sum2[10000+10];
int main(void) {
	int n,m;
	cin>>n>>m;
	assert(m<=10000);
	for(int i=1;i<=n;++i)
		scanf("%d",Q+i);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",L+i);
		if(i&1) cnt1[L[i]]++,sum1[L[i]]+=i;
		else cnt2[L[i]]++,sum2[L[i]]+=i;
	}
	long long ans = 0;
	for(int i=1;i<=n;++i) {
		if(i&1) {
			int m = cnt1[L[i]];
			if(m<=1) continue; //没人和它配对
			ans = (ans+1ll*i*Q[i]*(m-1)+1ll*Q[i]*(sum1[L[i]]-i))%10007; 
		} else {
			int m = cnt2[L[i]];
			if(m<=1) continue;
			ans = (ans+1ll*i*Q[i]*(m-1)+1ll*Q[i]*(sum2[L[i]]-i))%10007;
		}
	}
	cout<<ans<<endl;
	return 0;
} 

---

23. 丢手绢

分析：

        说白了就是一个有向图，每个节点只有一个出度。找出这个图中长度最小的环，输出这个长度。(题目说保证有答案，就是保证有环）
        注意，这个图可能是不连通的，可能有很多子图，所以我们要从每个点出发都dfs一次才能确保能找到最优答案。
        这个题每个结点出度为1，我们甚至不用dfs，直接循环就好了，但是dfs更好写一点，代码更简洁。我们可以从每个点出发dfs，沿着箭头走。然后标记每个结点在这一趟中出现的次序。如果在这一趟中，某个结点出现了两次，那么就说明沿着环走到了之前走过的结点，那么环的大小就为这个结点先后两次的次序只差，我们就结束这趟dfs, 因为再搜下去也是一样的路线。
        我们要注意，前几趟dfs中走过的结点，在后面是不需要走的，因为之前走过的环，从外部进入不会得到更小的环。所以，我们每个结点走一次即可。复杂度O(n)。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int to[N],vis[N],cntt[N];
int ans;
void dfs(int x,int id,int cnt) {//当前结点，在这一轮中的标号，轮数 
	if(vis[x]) {
		if(cntt[x]<cnt) return;
		ans = min(ans,id-vis[x]);
		return;
	}
	vis[x] = id;
	cntt[x] = cnt;
	dfs(to[x],id+1,cnt);
} 
int main(void) {
	ans = 1e7;
	int n;cin>>n;
	for(int i=1;i<=n;++i)
		scanf("%d",to+i);
	for(int i=1;i<=n;++i) {
		if(!vis[i]) dfs(i,1,i);
	}
	cout<<ans<<endl;
	return 0;
} 

---

24. 有趣的最大池化

样例输入1

5
31 24 21 14 22
1

样例输出1

31 24 21 14 22

样例输入2

5
18 14 31 1 26
2

样例输出2

18 31 31 26

样例输入3

16
61 53 2 13 51 30 48 44 58 46 36 8 2 8 34 10
7

样例输出3

61 53 58 58 58 58 58 58 58 46

分析：

        经典单调队列问题，解决滑动窗口的最大值。我们可以维护一个单调的队列，队列从队首到队尾(从左到右)存储的元素单调递减。队首元素即为该区间的最大元素。
        我们从1到n遍历原数列中的数，到a[i]，我们先去尾, 如果队尾(最右边)的元素比a[i]小的话，它对后面所有长度为len的区间的最大值都是没有意义的。去尾之后我们将a[i]从队尾加入到队列之中。然后我们删头，如果队首代表的元素的位置比队尾的还小len-1, 那么说明已经在窗口左区间的左边了，没有意义，我们要去掉这个没有意义的元素。然后此时的队首就是以i为区间右端点，长度为len的区间(窗口)中最大的元素了。
        队列中只需要存数组元素的下表即可。手动模拟队列比STL::queue要快一点。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5; 
int a[N],S[N];//单调队列，记录id，队尾维护最大值， 
int main(void) {
	int n,len;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	scanf("%d",&len);
	int pa = 1,pb = 0;
	for(int i=1;i<=n;++i) {
		while(pb>=pa&&a[S[pb]]<=a[i]) --pb;//
		S[++pb] = i;
		while(i-S[pa]+1>len) ++pa;
		if(i>=len) printf("%d ",a[S[pa]]);
	}
	return 0;
} 

---

2020/4/10 23:28
xzc

---