第一题【深基7.习8】猴子吃桃

题目描述

一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；接下来的每一天它都会吃剩余的桃子的一半外加一个。第 $n$ 天早上起来一看，只剩下 $1$ 个桃子了。请问小猴买了几个桃子？

输入格式

输入一个正整数 $n$，表示天数。

输出格式

输出小猴买了多少个桃子。

样例 #1

样例输入 #1

4
1

样例输出 #1

22
1

提示

数据保证，$1\le n\le 20$。

解题思路

• 1）直接模拟，题目说什么就做什么。

参考代码

#include
using namespace std;
int main()
{
    int n,ans=1;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		ans+=1;
		ans*=2;
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

第二题【深基9.例4】求第 k 小的数

题目描述

输入 $n$（$1\le n<5000000$ 且 $n$ 为奇数）个数字 $a_i$（$1\le a_i<{10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

输入格式

输出格式

样例 #1

样例输入 #1

5 1
4 3 2 1 5
1
2

样例输出 #1

2
1

解题思路

• 1）在 STL 里有 nth_element 函数，这个函数主要用来将数组元素中第 k 小的整数排出来并在数组中就位。

参考代码

#include
using namespace std;
long long n,k,a[5000010];
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    nth_element(a,a+k,a+n);
    cout<<a[k];
}
1
2
3
4
5
6
7
8
9
10
11

第三题【模板】快速排序

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1
1
2

样例输出 #1

1 2 4 4 5
1

提示

对于 $20\%$ 的数据，有 $N\le 10^3$；

对于 $100\%$ 的数据，有 $N\le 10^5$。

参考代码

#include 
using namespace std;
int n,a[1000001];
void qsort(int l,int r)
{
    int mid=a[(l+r)/2];
    int i=l,j=r;
    do{
        while(a[i]<mid) i++;
        while(a[j]>mid) j--;
        if(i<=j)
        {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }while(i<=j);
    if(l<j) qsort(l,j);
    if(i<r) qsort(i,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}
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

第四题 排序

题目描述

一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 $A,B,C,D$ 表示$A<B,B<C,C<D$。在这道题中，我们将给你一系列形如 $A<B$ 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。

4 6
A