北航软院算法课国庆题目解答

文章目录：

题解
代码
B
题解
代码
C
题解
代码

题解
代码

题解
代码

题解
代码

题解
代码

A

题目描述

AndroidNeko 听说在计算复杂度的重要性刻进主题，想希望你以样写写一个程序来计算满足特定形式递归式的算法复杂度。

具体来说，给定正整数 $a, b, k$，所求递归式为：

T(n) = aT\left(\frac{n}{b}\right) + O\left(n^k\right)

根据主定理，有：

T(n) = \begin{cases} O\left(n^{\log_b a}\right), & \log_b a > k \\ O\left(n^k \log n\right), & \log_b a = k \\ O\left(n^k\right), & \log_b a < k \\ \end{cases}

输入格式

第一行一个正整数 $t$ $(1 \leq t \leq 2 \times 10^5)$，表示数据组数。

对于每组数据，一行三个正整数 $a, b, k$ $(1 \leq a, k \leq 10^9,\, 2 \leq b \leq 10^9)$，含义同题目描述。

输出格式

对于每组数据，输出一行：

若 $T(n)=O(n^{\log_b a})$，输出 n^{\log_ba}
若 $T(n)=O(n^k \log n)$，输出 n^klog n
若 $T(n)=O(n^k)$，输出 n^k
输入样例

6
6 2 2
4 2 2
2 2 2
3 2 2
536870912 2 29
536870911 2 29

输出样例

n^{\log_2 6}
n^2log n
n^2
n^{\log_2 3}
n^29log n
n^29

题解

这道题需要转换为指数函数计算，指数函数计算时容易超过限制，所以在计算b的k次方过程中，要时刻检验判断乘出来的值是否已经大于a了，大于a就直接break并输出就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

unsigned long long a, b, k;
int mode = 0, t;
int main(){
    cin >> t;
    while(t--){
        scanf("%llu%llu%llu",&a,&b,&k);
        if(k>=30) mode = 3;
        unsigned long long t = b;
        k--;
        while(t<=a&&k>0){
            t *= b;
            k--; 
        }
        if(k > 0){
            mode = 3;
        } 
        else{
            if(t > a) mode = 3;
            else if(t == a) mode = 2;
            else mode = 1;
        }
        switch (mode)
        {
        case 1:
            printf("n^{\\log_ba}\n");
            break;
        case 2:
            printf("n^k\\log n\n");
            break;
        default:
            printf("n^k\n");
            break;
        }
    }
    return 0;
}

B

题目描述

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。
已知该序列中一定存在一个元素的出现次数严格大于 $\left\lfloor n/2 \right\rfloor$（即超过一半）。
请你找出这个元素（众数）。

输入

第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^5$），表示序列的元素。

输入保证答案一定存在且唯一。

输出

一行，输出这个序列的众数。

输入样例

7
2 2 1 3 2 3 2

输出样例

题解

这题简单，因为an的大小很小，完全可以开一个数组记录某个数值出现的次数，每次填入一个新的数时把$a[x]++$，然后判断一下是否超过总个数的一半，超过就直接break输出了。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
typedef long long ll;

int n;
int a[100009];

int main(){
    cin >> n;
    int x;
    int cha = n/2;
    for(int i = 1; i <= n; i++){
        cin >> x;
        a[x]++;
        if(a[x]>cha){
            printf("%d",x);
            break;
        }
    }
    return 0;
}

C

题目描述

AndroidNeko 打算做一个基于 Horner 规则的多项式计算器，帮她他进行一类特殊的二元多项式计算。

具体来说，给定如下两个一元多项式:

\sum_{i=0}^{n} a_i x^i = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n

\sum_{i=0}^{m} b_i y^i = b_0 + b_1 y + b_2 y^2 + \cdots + b_m y^m

定义如下的二元多项式:

f(x, y) = \left( \sum_{i=0}^{n} a_i x^i \right) \left( \sum_{i=0}^{m} b_i y^i \right)

你需要处理 $q$ 次计算，第 $i$ 次计算给定两个变量值 $X_i$ 和 $Y_i$，你需要求解 $f(X_i, Y_i) \mod 10007$。

输入格式

第一行一个正整数 $n$ $(1 \leq n \leq 3 \times 10^4)$，表示第一个一元多项式的次数。

第二行 $n + 1$ 个非负整数 $a_0, a_1, \ldots, a_n$ $(0 \leq a_i \leq 10^3)$，表示第一个一元多项式的系数。

第三行一个正整数 $m$ $(1 \leq m \leq 3 \times 10^4)$，表示第二个一元多项式的次数。

第四行 $m + 1$ 个非负整数 $b_0, b_1, \ldots, b_m$ $(0 \leq b_i \leq 10^3)$，表示第二个一元多项式的系数。

第五行一个正整数 $q$ $(1 \leq q \leq 2.5 \times 10^3)$，表示计算的次数。

接下来 $q$ 行, 第 $i$ 行有两个非负整数 $X_i, Y_i$ $(0 \leq X_i, Y_i \leq 10^4)$，表示第 $i$ 次计算给定的两个变量值。

输出格式

输出 $q$ 行，第 $i$ 行一个非负整数，表示 $f(X_i, Y_i) \mod 10007$。

输入样例1

输出样例1

输入样例2

5
100 200 300 400 900 1000
4
100 200 400 900 1000
5
1000 2000
2000 3000
4000 5000
6000 7000
8000 9000

输出样例2

Hint

ab \mod c = (a \mod c)(b \mod c) \mod c

题解

这道题很坑，硬算会有一个数据点过不去（TLE）。

题目中隐晦地告诉了要用Hornor算法：

Horner 算法是一种高效计算多项式值的方法。对于一个 $n$ 次多项式：

P(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n

Horner 算法将其重写为嵌套形式，并用递推的方式计算：

P(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + x a_n)\cdots))

这样只需 $n$ 次乘法和 $n$ 次加法即可完成计算，显著提高多项式计算效率。

还有第二个更坑的点，我改成Hornor规则之后那个数据点还是过不去。然后把原来的unsigned long long改成int之后就不超时了。助教nb，这时间卡的太准了！

代码

#include <iostream>
// #include <cstdio>
// #include <cctype>
// #include <cmath>
// #include <cstring>
// #include <string>
// #include <vector>
// #include <algorithm>
// #include <queue>
// #include <stack>



using namespace std;

int n, m, q, x, y;
int a[30009], b[30009];
int aixi, biyi;

int main(){
    cin >> n;
    for(int i = 0; i <= n; i++){
        scanf("%d",&a[i]);
    }
    cin >> m;
    for(int i = 0; i <= m; i++){
        scanf("%d",&b[i]);
    }
    cin >> q;
    while(q--){
        aixi = a[n]; biyi = b[m];
        scanf("%d%d",&x,&y);
        for(int i = n - 1; i >=0; i--){
            aixi = (aixi*x + a[i])%10007;
        }
        for(int i = m - 1; i >=0; i--){
            biyi = (biyi*y + b[i])%10007;
        }
        printf("%d\n",(aixi*biyi)%10007);
    }
    return 0;
}

D

题目描述

2jogger1当上了军训的教官！他的连队里共有 $n$ 名学生，他们的身高为 $a_i(1 \le i \le n)$，为了参加文艺汇演，他决定找出身高差最大的两名同学参加，他想知道身高差最大是多少以及保证身高差最大时最多能有多少种选法？两种选法不同当且仅当所选的两名学生至少有一个不同。

输入

第一行一个正整数 $n$，表示学生的总数，保证 $2 \le n \le 2 \times 10^5$。

第二行 $n$ 个空格隔开的正整数 $a_i$，保证 $1 \le a_i \le 10^9$。

输出

一行两个空格隔开的整数，分别表示最大身高差和选法数。

输入样例

3
1 4 5

输出样例

4 1

输入样例

4
1 5 5 1

输出样例

4 4

题解

找到最大值和最小值以及各自出现的次数就行，要注意的是最大值与最小值相等时最终总数计算。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;
int n, maxx = -1, minx = 1000000009, maxnum = 0, minnum = 0, a;

int main(){
    cin >> n;
    while(n--){
        scanf("%d",&a);
        if(a < minx){
            minnum = 1;
            minx = a;
        }else if(a == minx){
            minnum ++;
        }
        if(a > maxx){
            maxnum = 1;
            maxx = a;
        }else if(a == maxx){
            maxnum ++;
        }
    }
    if(maxx!=minx) printf("%d %lld",maxx-minx,(long long)maxnum*(long long)minnum);
    else{
        long long num = maxnum;
        num = (num*(num - 1))/2;
        printf("%d %lld",maxx-minx, num);
    }
    return 0;
}

E

题目描述

给定一个长度为 $n$ 的非升序数组 $a_1, a_2, \ldots, a_n$ ，以及 $q$ 个查询。
对于每个查询给出整数 $x$，请你输出：

lower\_bound(x)： 数列中第一个大于等于 $x$ 的位置（下标从 1 开始计数），若不存在则输出 $n+1$；
upper\_bound(x)： 数列中第一个大于 $x$ 的位置（下标从 1 开始计数），若不存在则输出 $n+1$。

输入

第一行包含两个整数 $n, q$（$1 \leq n, q \leq 2 \times 10^{5}$），表示数组长度和查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示数组元素（保证数列非升序排列）。

接下来 $q$ 行，每行包含一个整数 $x$（$-10^9 \leq x \leq 10^9$），表示一个查询。

输出

对于每个查询，输出一行两个整数，分别表示 lower\_bound(x) 和 upper\_bound(x)。

输入样例

输出样例

2 4
4 4
5 6

题解

直接使用二分查找即可。

代码

#include <stdio.h>

int n, q;
int an[200009];
int sch;

int bsearch(int a[], int l, int r){
    while(l < r){
        int mid = l + r >> 1;
        if (an[mid] >= sch) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int a[], int l, int r){
    while(l < r){
        int mid = l + r + 1 >> 1;
        if (an[mid] <= sch) l = mid;
        else r = mid - 1;
    }
    return l;
}

int main(){
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++){
        scanf("%d",&an[i]);
    }
    while(q--){
        scanf("%d",&sch);
        int ans1 = bsearch(an,1,n);
        int ans2 = bsearch2(an,1,n);
        if(an[ans1] < sch) ans1++;
        if(an[ans2] <= sch) ans2++;
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

F

题目描述

在今天上完算法课之后，2ogger认为他已经完全掌握二分了，他忙满满地准备开始各分支拉，但他完全没注意到所给的数列是无序的！但我们发现所给的数列 $p_1, p_2, \dots, p_n$ 是一个排列。

对于一次询问，会给出一个区间 $[l, r]$ 和一个整数 $k$，函数 $f(l, r, k)$ 表示从 $[l, r]$ 区间不断向内取整分半、取最大值的过程，其定义如下：如果 $l > r$，则 $f(l, r, k) = 0$；否则，令 $m = \left\lfloor \frac{l + r}{2} \right\rfloor$，其中 $\left\lfloor x \right\rfloor$ 表示向下取整。

如果 $p_m = k$，则 $f(l, r, k) = 1$。
如果 $p_m < k$，则 $f(l, r, k) = f(m+1, r, k)$。
如果 $p_m > k$，则 $f(l, r, k) = f(l, m-1, k)$。

再给出一个整数 $d$，你需要重新排列 $[l, r]$ 区间，使得对于任意 $k$（$1 \leq j \leq d$），$f(l, r, k_j) = 1$，即可以对 $p_{h_1}, p_{h_2}, \ldots, p_{h_{r-l+1}}$ 在 $[l, r]$ 内任意重新排序。

输入

第一行有两个空格隔开的正整数 $n, q$，表示数列的长度和询问个数，保证 $1 \leq n, q \leq 2 \times 10^5$。

第二行为 $n$ 个空格隔开的整数 $p_1, p_2, \dots, p_n$，保证所给的是一个排列。

接下来 $q$ 行包含 $q$ 组询问，每组 $k, l, r, k_1, ..., k_k$，含义与题目描述一致。保证 $1 \leq l \leq r \leq n, 1 \leq k \leq n$。

输出

对于每个查询输出一行，表示最小的 $d$ 使得 $f(l, r, k_j) = 1$，如果无论如何都不能成功输出 $-1$。注意每次询问之间是相互独立的，也即实际上不会重新排序。

输入样例

7 4
7 5 4 2 7 6 4
2 2 5 2 4
3 1 3 1 2 3
4 1 7 1 7 3 5
2 1 5 1 7

输出样例

题解

首先要理解题意，这题太长了，还写的不太清楚。

这道题给的数列是一个排列，这道题里面的意思是，n个数的排列指只有数字1-n、且每个数字出现且仅出现一次，排列是乱序。

然后题目背景是二分查找，对于一个数组，如果任何元素都能被二分查找，则这个数组必须是有序的。现在的数组没序，且每次查询只用保证其中某个元素被二分查找出来，其他的无所谓，所以可以通过替换部分元素达到。

对于从l到r的数组，查找k，我们可以先用一个数组/哈希表（这个题数据数组就够了）记录数值为k的元素的原始位置，所以可以知道k的位置kpos。现在就相当于在l到r的位置找到第kpos位置的某次二分查找，这样的二分查找的查找路径是一定的。

那我们可以先通过一个正常排好序的数组模拟一下l到r数组查找位置kpos的二分查找，确定中间查找到的位置，然后再会原数组去看原数组中是否满足（是否向左走或者向右走，即与k的大小关系）。最后算出来路径上需要有几个比k大的数、几个比k小的数，以及每种有几个数不对需要修改。

最后先算一下查找的数k在1-n里面能否有这么多比k大的数、比k小的数，不能就返回-1，能就拿错误的数量算一下就行。

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;
int n, q, l, r, k;
int map[200009];
int a[200009];
int moni[200009];

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        map[a[i]] = i;
        moni[i] = i;
    }
    while(q--){
        scanf("%d%d%d",&l,&r,&k);
        int kpos = map[k];
        if(kpos > r || kpos < l){
            printf("-1\n");
            continue;
        }
        int da = 0, dawrong = 0, xiao = 0, xiaowrong = 0;
        while(l < r){
            int mid = l + r >> 1;
            if(moni[mid] == kpos){
                //printf("t");
                break;
            }else if(moni[mid] < kpos){
                l = mid + 1;
                xiao++;
                if(a[mid] > k) xiaowrong++;
            }else{
                r = mid - 1;
                da ++;
                if(a[mid] < k) dawrong++;
            }
        }
        //printf("%d %d %d %d %d\n",kpos,da,dawrong,xiao,xiaowrong);
        if(((k-1)<xiao)||((n-k)<da)){
            printf("-1\n");
            continue;
        }else{
            int zong = min(dawrong,xiaowrong)*2;
            zong += (max(dawrong,xiaowrong) - min(dawrong,xiaowrong))*2;
            printf("%d\n",zong);
        }
    }
    return 0;
}

G

题目描述

给定一个序列 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$，如果 $1 \leq i < j \leq n$ 且 $a_i > k \cdot a_j$，我们就将 $(i, j)$ 称作一个逆序 $k$ 倍对。请你计算序列中逆序 $k$ 倍对的个数。

输入格式

第一行两个正整数 $n, k$（$1 \leq n \leq 10^5, 1 \leq k < 10$），含义同题目描述。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 2^{31}$），含义同题目描述。

为了提高区分度，对于得分占比 $10\%$ 的测试点，我们保证 $1 \leq n \leq 100$。

输出格式

一行一个非负整数，表示序列中逆序 $k$ 倍对的个数。

输入样例

5 2
5 4 3 2 1

输出样例

题解

实在没思路，先查了一下网上有没有类似的题，发现逆序数是个挺常见的题（但跟这个不完全一样），故学习了一下。算法：逆序对问题及其求解 - 知乎

树状数组实在没学过，归并排序我倒是看懂了，迁移了一下。

原本是在归并的时候添加$mid - i + 1$，现在改成在归并操作之前再循环一下，把判断条件改成a[i] > t*a[j]，思路完全一样，如下：

while(i<=mid&&j<=r){
    if(a[i] > t*a[j]){
        ans += mid -i +1;
        j++;
    }else{
        i++;
    }
}

代码

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_map>

using namespace std;
int n, t;
int a[100009], b[100009];
long long ans = 0;

void merge_sort(int l,int r)
{
    if(l==r)
        return;
    int mid=(l+r)>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(a[i] > t*a[j]){
            ans += mid -i +1;
            j++;
        }else{
            i++;
        }
    }
    i=l,j=mid+1;
    while(i<=mid && j<=r)
    {
        if(a[i]<=a[j]) 
            b[k++]=a[i++];
        else
        {
            b[k++]=a[j++];
        }
    }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=r)
        b[k++]=a[j++];
    for(int p=l;p<=r;p++)
        a[p]=b[p],b[p]=0;
}

int main(){
    cin >> n >> t;
    for(int i = 1; i <= n;i++){
        scanf("%d",&a[i]);
    }
    merge_sort(1,n);
    printf("%lld",ans);
    return 0;
}

Alex Li的学习笔记

不想学习…

北航软院算法课国庆题目解答

A

题解

代码

B

题解

代码

C

题解

代码

D

题解

代码

E

题解

代码

F

题解

代码

G

题解

代码

添加新评论