北航算法第二次上机题解 | Eternal_zttz

北航算法第二次上机题解

北航第二次算法上机,就分数和排名而言,自己还算是不错的。然而,对于自己的上机,其实自己是不满意的,出现了不该出现的错误以及没写出来本可写出来的题。在这里写下题解,希望下次上机DP能以此为戒,冷静处理。

A: ModricWang’s Real QuickSort Query

解题思路

这是一道考察快排的题,题目的意思对照案例看一下,也表述的很清楚了。事实上,按照题目给出的提示一步一步写,基本上核心代码就齐了,剩下的就是需要自己判断和输出做一些调整,然而我还是没过

我们来看看如何按照提示写代码:

1
2
for (int i = 0;i<n;i++)
scanf("%d",&a[i]);//设数组为arr[n] ,元素从0开始存储

1
2
3
4
5
6
7
8
9
10
11
int mid = (right+left+1)/2;
int key = a[mid];//令i=0,j=n−1,mid=arr[n/2],这里我传入的是left和right。
int i = left, j = right;
while(i<=j){//如果i≤j,转到4,否则转到步骤7
while(a[i]<key) i++; //如果arr[i]<mid,i++ ,重复执行直到arr[i]≥mid
while(a[j]>key) j--; //如果arr[j]>mid,j−− ,重复执行直到arr[j]≤mid
if(i<=j){ //如果i≤j, 交换arr[i] 和arr[j],i++,j−− , 转到步骤4
swap(a[i], a[j]);
i++;j--;
}
}
1
quicksort(left, i-1);//数组被分为左右两个部分:[0,i)和[i,n) 我们要左边部分,所以选择left到i-1

好了,事实上,需要自己写的代码也就10行左右,我们所需要做的便是在函数递归的时候,留下一个计数器,一旦达到两次,我们就可以从标志元素开始进行输出

另外,在函数结束的时候,我们可以使用exit(0);表示直接退出程序,因为如果仅仅是return的话,只会返回上一次递归的过程,而非退出整个递归函数。

AC 代码

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
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1000010
int a[N];
int num = 0,n;
void quicksort(int left, int right){
num ++;
if(left>=right)
return;
int mid = (right+left+1)/2;
int key = a[mid];
int i = left, j = right;
while(i<=j){
while(a[i]<key) i++;
while(a[j]>key) j--;
if(i<=j){
swap(a[i], a[j]);
i++;j--;
}
}
//这是答案输出部分,我们可以看到,每一次划分是[0,i),[i,n),我们需要输出的是后面的一部分,所以,我们直接输出到right就行,输出后直接退出程序。
if(num == 2){
for (;i<=right;i++)
printf("%d ",a[i]);
exit(0);
}
quicksort(left, i-1);
}
int main(){
scanf("%d",&n);
for (int i = 0;i<n;i++)
scanf("%d",&a[i]);//设数组为arr[n] ,元素从0开始存储
quicksort(0, n-1);
}

B: 女娲加农炮

解题思路

考点: 优先队列

这一题需要我们求出所需的最小能量值。

对于合并的这个过程,我们可以思考一下:每一次的过程为取两个原子聚合成一个原子,显然,对于有n 个原子,我们需要聚和n-1次(每一次聚合总原子数减少一个,我们需要最后只剩下一个原子)

这个过程已经是确定的了,接下来我们想想如何得到最小值:因为过程确定,那么无论采用何种决策方案, 次合并后都将只剩下一个原子。若是想得到最小的答案,那么我们只要每次均取最小的两个合并即可。

正确性显然。其实也不一定显然,然而并不会证
类似于贪心的思想,我们可以得到下列的解题步骤:

  1. 对所有数排序,得到一个有序数组,选择数组最小的两个数合并。ans += a1+a2
  2. 将合并后的原子插入到原有序数组中,保持新数组依旧有序。
  3. 重复1-2过程,直到整个数组中只有一个元素

所以,用到的数据结构即为优先队列,注意STL中优先队列默认是从大到小排列的,需要使用cmp函数,或者greater ,让其从小到大排列

关于优先队列的使用,可以看看这篇blog

时间复杂度:优先队列的插入删除操作时间复杂度为 ,整个过程需要执行 次,所以总的时间复杂度为

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
int main(){
int n;
while(~scanf("%d",&n)){
ll a,b,c,sum=0 ;
priority_queue<ll,vector <ll>,greater<ll>> q;
for (int i =0 ;i<n;i++){
scanf("%lld",&a);
q.push(a);
}
while(q.size()>1){
b = q.top();q.pop();
c = q.top();q.pop();
sum += (b+c);
q.push(b+c);
}
printf("%lld\n",sum);
}
}

C: 第k顺序统计量

解题思路

本题是为了求第k小的数。首先我们可以想到直接排序求解,所有的数排序有可以直接求出第k小的数。这么思考当然是没错的,然而即便是调用sort函数,时间复杂度也为 ,对于这一题而言,时间复杂度过高,会无情的TLE

为什么排序不行呢?因为在这个过程中我们运行了很多不必要的过程,比如我们只需要第k小的数,不对其它数做要求,那么我们花费在排其它数据的时间就属于无用功。

要想快,那么我们首先想到的应该就是分治,事实上绝大多数加快程序运行的方法都是使用分治算法。学习了快速排序,我们可以想到,每一次快速排序都会有一个分隔元素,记为key。每一次快排后,key都在最终排序的正确位置,前半部分都比key小,后半部分都比key大。那么我们只要比较key的位置和k的大小,便可以判断出下一步是在前半部分还是后半部分进行,从而减小了计算量。

时间复杂度为

AC代码

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
#include <cstdio>
int quicksort(int a[],int left,int right,int num){
int key = a[left];
int i = left,j = right;
while(i<j){
while(i<j&&a[j]>=key) j--;
a[i] = a[j];
while(i<j&&a[i]<=key) i++;
a[j] = a[i];
}
a[i] = key;
if(num == i)//找到结果,返回
return a[i];
else if(num<i)
return quicksort(a, left, i-1,num);//递归查找前半部分
else
return quicksort(a, i+1, right,num);//递归查找后半部分
}
int a[3000005];
int main() {
int n;
int A,B,C,k;
while(~scanf("%d %d %d %d %d",&A,&B,&C,&a[1],&k)){
for(int i = 2; i <= 3000000; ++i)
a[i] = ((1LL * a[i - 1] * A ^ B) + C) % 1000000007;
int ans = quicksort(a, 1,3000000 ,k);
printf("%d\n",ans);
}
}

事实上,可以直接调用stl函数,也能解决掉这一题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<algorithm>
const int N = 3000010;
int a[N], A, B, C, k;
int main() {
for(int tc = 0; tc < 7; ++tc) {
scanf("%d%d%d%d%d", &A, &B, &C, &a[1], &k);
for(int i = 2; i <= 3000000; ++i)
a[i] = ((1LL * a[i - 1] * A ^ B) + C) % 1000000007;
std::nth_element(a + 1, a + k, a + 3000001);
printf("%d\n", a[k]);
}
return 0;
}

菜的真实,完全不知道还有这个函数emmm

D: 天秤的烦恼

解题思路

这道题主要就是考排序和去重。

其实题目意思感觉还是有那么一点点歧义的,因为它描述的是在所有晶体管中为第几大,那么要不要去重也不好说。不过WA后也可以试着换换思路,万一对了呢

因为考的是排序+去重,代码的实现方法就可以有很多种,可以选择直接调用库函数,也可以自己写一个判断,也并不需要几行代码~~~

在这里,我们先用sort函数排序,然后用一个临时的数组,如果a[i]!=a[i-1],那么把这个a[i]赋值给b[num++],最后遍历一遍就可以得出结果

注意如果是使用cin 和cout 的话需要取消流同步,不然会造成TLE

时间复杂度为

AC代码

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 <cstdio>
#include <algorithm>
using namespace std;
#define N 1000010
long long a[N],b[N];
int main(){
long long n,k;
while(~scanf("%lld",&n)){
for (int i = 0;i<n;i++){
scanf("%lld",&a[i]);
}
scanf("%lld",&k);
sort(a, a+n);
b[0] = a[0];
int num = 1;
for (int i = 1;i<n;i++){
if(a[i] == a[i-1]) continue;
else b[num++] = a[i];
}
for (int i = num-1;i>=0;i--){
if(b[i] == k){
printf("%d\n",num-i);
break;
}
}
}
}

E: 图书整理

解题思路

主要考点是查找方法,对于这道题,可以有很多不同的做法:

方法1:计数

首先我们可以看看数据的范围:1≤n,t≤100,000 ,number在int范围内。

数据范围不大,只有1e5的大小,所以我们可以对每本书直接计数,使用两个数组a[N],b[N],其中a[i]代表编号为i本的书的数量,b[i]代表第i次查询的编号,对于每次查询,输出一遍即可。时间复杂度为

方法2:二分查找上下界
法1只适合于数据较小的情况,如果数据的范围为int内,计数数组是开不了那么大的,那么法1就不适用了,事实上,助教的本意也不是让我们用计数水过去,而是考察二分查找上下界。

只要把常规的二分改一改即可:
如查找下界:最后得到的lower是最后一个小于p的位置。
上界修改一处即可,具体可看法二代码,得到的是最后一个大于等于p的位置。
注意数组存储位置为1-n;

1
2
3
4
5
6
7
8
9
10
int left = 0, right = n+1;
int mid = (left + right) / 2;
while (right - left > 1){
if (book[mid] < p)
left = mid;
else if (book[mid] >= p)
right = mid;
mid = (left+right)/2;
}
lower = mid;

方法3:map
使用stl中的map,当然,这个的思想和法一其实是一样的,不过使用stl相对而言更易写代码。

方法4:双指针移动
这个方法其实我还没弄懂,暂且放一份AC代码吧

真实菜鸡

AC代码 方法一:计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100010
int a[N],b[N];
int main(){
int n,t;
while(~scanf("%d %d",&n,&t)){
memset(a,0,sizeof(a));
memset(b, 0, sizeof(b));
int num;
for (int i = 0;i<n;i++){
scanf("%d",&num);
a[num]++;
}
for (int i = 0;i<t;i++)
scanf("%d",&b[i]);
for (int i = 0;i<t;i++)
printf("%d ",a[b[i]]);
printf("\n");
}
}

方法二:二分

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int book[N],n,t,p,lower,higher;
int main(){
while(~scanf("%d %d",&n,&t)){
for (int i = 1;i<=n;i++)
scanf("%d",&book[i]);
sort(book,book+n+1);
for (int i = 0; i < t; i++){
scanf("%d", &p);
int left = 0, right = n+1;
int mid = (left + right) / 2;
while (right - left > 1){
if (book[mid] < p)
left = mid;
else if (book[mid] >= p)
right = mid;
mid = (left+right)/2;
}
lower = mid;
left = 0, right = n+1;
mid = (left + right) / 2;
while (right - left > 1){
if (book[mid] <= p)
left = mid;
else if (book[mid] > p)
right = mid;
mid = (left+right)/2;
}
higher = mid;
printf("%d ",higher - lower);
}
printf("\n");
}
}

方法三:map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int n, t, book, p;
map<int, int> mp;
int main(){
while (scanf("%d%d", &n, &t) != EOF){
mp.clear();
for (int i = 0; i < n; i++){
scanf("%d", &book);
mp[book]++;
}
for (int i = 0; i < t; i++){
scanf("%d", &p);
printf("%d ", mp[p]);
}
printf("\n");
}
}

方法四:双指针移动

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
#include<cstdio>
#include<algorithm>

int aa,bb;char ch;int F(){
while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
ch=='-' ? aa=bb=0 : (aa=ch-'0',bb=1);
while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';
return bb ? aa : -aa;
}
const int N = 100010;
struct lr {
int x, i;
bool operator <(const lr &a)const {
return x < a.x;
}
} Q[N];
int n, q, a[N], ans[N];
using std::sort;

int main() {
while(~scanf("%d%d", &n, &q)) {
for(int i = 0; i < n; ++i) a[i] = F();
sort(a, a + n);
for(int i = 0; i < q; ++i) Q[i].i = i, Q[i].x = F();
sort(Q, Q + q);
int j = 0;
for(int i = 0; i < q; ++i) {
if(i && Q[i].x == Q[i - 1].x) {
ans[Q[i].i] = ans[Q[i - 1].i];
continue;
}
int k = j;
while(j < n && a[j] == Q[i].x) ++j;
ans[Q[i].i] = j - k;
}
for(int i = 0; i < q; ++i) printf("%d%c", ans[i], " \n"[i == q-1]);
}
return 0;
}

F: 女娲加农炮||

解题思路

这一题可以说和前面B题相似度90%,我们只需要改一改判断条件,每一push的为取前三个的值即可。

判断条件改为q.size()>2,即剩三个及以上时我们再取。

AC代码

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
#include <cstdio>
#include <queue>
typedef long long ll;
using namespace std;
priority_queue<ll,vector <ll>,greater<ll>> q;
int main(){
int n;
while(~scanf("%d",&n)){
ll a,b,c,d,sum=0 ;
for (int i =0 ;i<n;i++){
scanf("%lld",&a);
q.push(a);
}
while(q.size()>2){
b = q.top();q.pop();
c = q.top();q.pop();
d = q.top();q.pop();
sum+= (b+c+d);
q.push(b+c+d);
}
printf("%lld\n",sum);
while(!q.empty())
q.pop();
}
}

G: 数组优美和值

解题思路

这道题几乎和上一次的上机题序列优美差值一模一样,使用前缀和+归并排序,
助教对于这道题已经有所提示。

要注意的点是数组首位补零,即a[0] = 0;排序的时候记住是0-n,而非1-n。

我们来看一看这道题:

显然,如果令 ;

那么

那么这道题就相当于求 的值
这时候便和上一次上机的题目一模一样了。
时间复杂度为

##AC代码

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
#include <stdio.h>
typedef long long ll;
const int N = 1000010;
ll a[N],k[N];
int n,L,R;
ll ans = 0;
void merge(int left,int right){
if(left>=right)
return;
int mid = (left+right)/2;
merge(left, mid);
merge(mid+1, right);
int s = left,e = left;
for (int i = mid+1;i<=right;i++){
while(a[i]-a[e]>=L&&e<=mid)
e++;
while(a[i]-a[s]>R&&s<=mid)
s++;
ans +=e-s;
}
int i = left,j = mid+1,p=left;
while(i<=mid&&j<=right){
if(a[i]<=a[j])
k[p++] = a[i++];
else
k[p++] = a[j++];
}
while(i<=mid) k[p++] = a[i++];
while(j<=right) k[p++] = a[j++];
for (int i = left;i<=right;i++) a[i] = k[i];
}
int main(){
int T;
scanf("%d",&T);
for (int i = 0;i<T;i++){
ans = 0;
long long num;
a[0] = 0;
scanf("%d%d%d",&n,&L,&R);
for (int j = 1;j<=n;j++){
scanf("%lld",&num);
a[j] = a[j-1]+num;
}
merge(0, n);
printf("%lld\n",ans);
}
return 0;
}

事实上,使用前缀和的时候我们可以发现,初始数组实际上是有序的,所以,我们其实不用分治法,这一题也可以得出答案,并且效率更高:

AC代码2

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
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 1000010;
ll a[N];
int T,n,l,r,num;
int main() {
scanf("%d",&T);
for (int i = 0; i < T; i++) {
ll ans,rp,lp;
memset(a, 0, sizeof(a));
a[0] = 0;
scanf("%d %d %d", &n, &l, &r);
for (int j = 1; j <= n; j++){
scanf("%d", &num);
a[j] = a[j-1] + num;
}
ans = 0; rp = 0; lp = 1;
for (int j = 1; j <= n; j++){
while(lp <= n && a[lp] - a[j-1] < l || lp < j)
lp ++;
while(rp < n && a[rp+1] - a[j-1] <= r)
rp ++;
if(lp <= rp)
ans += rp - lp + 1;
}
printf("%lld\n",ans);
}
}

H: W型串

解题思路

我们可以看看关于w型串的定义,很明显,这是一个递归定义,那么我们便可以对这道题递归求解。

首先,我们来看看非w型串的特点:

  1. 括号不匹配,那么一定不是w型串
  2. 如果记flag为分隔位,那么只能有一个分隔位,即()()形式,如果分隔位大于1,那么一定不是w型串

如果满足上面两条,那么我们应该递归判断里面内容,最后即可得到答案;

我们来看看check函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int check(int left,int right){   //判断从left到right是不是w型串
if(left == right) return 1; //如果为空串,复合条件
int cnt = 0,flag = 0; //cnt判断括号匹配,flag记录分隔位
for (int i = left;i<right;i++){
if(str[i] == '(') cnt++;
else cnt--;
if(cnt<0) return 0 ;//括号不匹配
if(cnt == 0&&i+1!=right){
if(flag == 0 ) flag = i+1;//记下分隔位
else return 0 ;//分隔位多于1,不是w型串
}
}
if(cnt!=0) return 0;//括号不匹配
else if(flag == 0) return check(left+1, right-1);//没有分隔位,递归查找
else return check(left+1,flag - 1)&&check(flag+1, right-1);//有分隔位,递归查找两边
}

时间复杂度为

AC代码

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
#include <cstdio>
#include <cstring>
#define N 1010
char str[N];
int check(int left,int right){
if(left == right) return 1;
int cnt = 0,flag = 0;
for (int i = left;i<right;i++){
if(str[i] == '(') cnt++;
else cnt--;
if(cnt<0) return 0 ;
if(cnt == 0&&i+1!=right){
if(flag == 0 ) flag = i+1;
else return 0 ;
}
}
if(cnt!=0) return 0;
else if(flag == 0) return check(left+1, right-1);
else return check(left+1,flag - 1)&&check(flag+1, right-1);
}
int main(){
int n,len,ans = 0;
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%s",str);
len = strlen(str);
ans = check(0, len);
if (ans == 1) printf("Yes\n");
else printf("No\n");
}
}

I: 堆积糖果

解题思路

这一题理解上可能有一定的困难,暂且放上助教版题解:
考点:二维前缀和、数学、随机化、概率 预计现场完成人数:<3
这道题主要是给大家介绍一种思路,同时作为概率算法的一种介绍,大家有兴趣可以研究,没有兴趣可以不用着急,期末一定不会出这样的题。

题意是对一个矩阵的子矩阵进行染色,每个格子都有自己的接受颜色,问所有染过非自己接受颜色的格子数量。
如果我们对每个颜色编号,每次染色就把对应格子加上这个颜色的编号,那么,一个格子没有被其他颜色染过的必要不充分条件是:这个格子被染色的颜色和是这个颜色的整数倍。
那么,如果对一个颜色随机一个比较大的数,那么上述必要条件存在很大概率不会产生冲突(比如1+3=2+2这种,即把不同颜色累积的认为是该种颜色的累计),因为颜色的值是随机的,而且比较大。那么,如果对所有颜色进行多次随机,进行上述必要性判断,就能认为概率上每个存在非接受颜色染色的格子,都存在一组随机数,能够让这个格子的和不是他接受颜色对应的随机数的倍数。
简单感性理解:假设一组随机数,求和出错概率为p,那么对于n组随机数都出错的概率是p^n,即使p是0.5,n取10的时候出错概率已经小于千分之一了。
但是事实上,大随机数下,几个数的和是另一个数的倍数的概率已经很低,基本上一次就能确定是否由不属于他的颜色,这个概率大家可以尝试探索。
用二维前缀和可以O(1)完成子区间添加一个数,和子区间求和。这个东西在后面会介绍一下过程,具体原理大家可以手动模拟理解一下。

特别地,如果不采用随机,其实对颜色1-n*m编号以后,分别记录i, i*i的前缀和,要求一个格子i的和、i*i的和分别是他接受颜色对应的值的编号x的倍数、x*x的倍数,也可以区分一个格子是否被不被接受的颜色所染色。

对于二维前缀和,如果对[[x1, y1], [x2, y2]]矩形整体加一个数v,可以在某个a数组[x1, y1]、[x2+1,y2+1]处+v, [x1, y2+1]、[x2+1,y1]处-v,然后对a数组求对应的前缀和:

1
2
sum[i][j] = sum[i - 1][j] + sum[i] [j - 1] + a[i][j];
然后,某个格子[x, y]的值可以由sum[x][y] - sum[x][y-1]-sum[x-1][y]+sum[x-1][y-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
#include <cstdio>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 1000010;
ll Map[N];
vector<ll> cnt[N],a[N];

int main(){
int n,m,t;
scanf("%d %d %d",&n,&m,&t);
for (int i = 0; i <= n+1; i++){
a[i].resize(m+2);
cnt[i].resize(m+2);
}
srand(time(0));
for (int i = n * m; i > 0; i--)
Map[i] = (rand() * 1ll<<24ll)^(rand() << 8ll)^(rand()%(1ll<<8));
for (int i = 1, v; i <= n; i++){
for (int j = 1; j <= m; j++){
scanf("%d",&v);
a[i][j] = Map[v];
}
}
while(t--){
int x1,y1,x2,y2,v;
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&v);
++x2;++y2;
ll w = Map[v];
cnt[x1][y1] += w;
cnt[x1][y2] -= w;
cnt[x2][y1] -= w;
cnt[x2][y2] += w;
}
int ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cnt[i][j] += cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1];
ans += (cnt[i][j] % a[i][j])!=0;
}
}
printf("%d\n",ans);
return 0;
}
-------------The End-------------