第一题【深基7.习8】猴子吃桃
题目描述
一只小猴买了若干个桃子。第一天他刚好吃了这些桃子的一半，又贪嘴多吃了一个；接下来的每一天它都会吃剩余的桃子的一半外加一个。第 n天早上起来一看，只剩下 1个桃子了。请问小猴买了几个桃子？
输入格式
输入一个正整数 n ，表示天数。
输出格式
输出小猴买了多少个桃子。
样例 #1
样例输入 #1
4
样例输出 #1
22
提示
数据保证，1 ≤ n ≤ 20 。
解题思路
1）直接模拟，题目说什么就做什么。
参考代码
#include<iostream> 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; }
第二题【深基9.例4】求第 k 小的数
题目描述
输入 n（1 ≤ n < 5000000 且 n 为奇数）个数字 a i （1 ≤ a i <
），输出这些数字的第 k 小的数。最小的数是第 0小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
输入格式
输出格式
样例 #1
样例输入 #1
5 1 4 3 2 1 5
样例输出 #1
2
解题思路
1）在 STL 里有 nth_element 函数，这个函数主要用来将数组元素中第 k 小的整数排出来并在数组中就位。
参考代码
#include<bits/stdc++.h> 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]; }
第三题【模板】快速排序
题目描述
利用快速排序算法将读入的 N个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）
输入格式
第 1 行为一个正整数 N，第 2 行包含 N 个空格隔开的正整数 a i ，为你需要进行排序的数，数据保证了 A i 不超过
。
输出格式
将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。
样例 #1
样例输入 #1
5 4 2 4 5 1
样例输出 #1
1 2 4 4 5
提示
对于 20 % 的数据，有 N ≤ 
；
对于 100 % 的数据，有 N ≤ 
。
参考代码
#include <bits/stdc++.h> 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]<<" "; }
第四题 排序
题目描述
一个不同的值的升序排序数列指的是一个从左到右元素依次增大的序列，例如，一个有序的数列 A , B , C , D 表示A < B , B < C , C < D。在这道题中，我们将给你一系列形如 A < B 的关系，并要求你判断是否能够根据这些关系确定这个数列的顺序。
输入格式
第一行有两个正整数 n , m，n表示需要排序的元素数量，2 ≤ n ≤ 26 ，第 1 到 n 个元素将用大写的 A , B , C , D … 表示。m表示将给出的形如 A < B 的关系的数量。
接下来有 m 行，每行有 3 个字符，分别为一个大写字母，一个 < 符号，一个大写字母，表示两个元素之间的关系。
输出格式
若根据前 x个关系即可确定这 n个元素的顺序 yyy..y（如 ABC），输出
Sorted sequence determined after xxx relations: yyy...y.
若根据前 x个关系即发现存在矛盾（如 A < B , B < C , C < A ），输出
Inconsistency found after x relations.
若根据这 m个关系无法确定这 n个元素的顺序，输出
Sorted sequence cannot be determined.
（提示：确定 n个元素的顺序后即可结束程序，可以不用考虑确定顺序之后出现矛盾的情况）
样例 #1
样例输入 #1
4 6 A<B A<C B<C C<D B<D A<B
样例输出 #1
Sorted sequence determined after 4 relations: ABCD.
样例 #2
样例输入 #2
3 2 A<B B<A
样例输出 #2
Inconsistency found after 2 relations.
样例 #3
样例输入 #3
26 1 A<Z
样例输出 #3
Sorted sequence cannot be determined.
提示
2 ≤ n ≤ 26 , 1 ≤ m ≤ 600 。
解题思路
1）拓扑排序
2）我们将每个字母转化为一个点，只需要考虑整个图拓扑排序的情况。
3）建立栈，将入度为 0 的点入栈。
4）将栈首能到达的点的入度减一。
5）当栈不为空时，进行退栈，并将入度为 0 的点入栈。
参考代码
#include <bits/stdc++.h> using namespace std; int n, m; vector<int> e[30]; int degree[30]; int a[30]; stack<int> s; bool vis[30]; int mrk; bool topo(int r) { int sz = 0; bool finished = true; int t[30]; for(int i = 0; i < n; i++) { t[i] = degree[i]; if(!degree[i]) s.push(i), vis[i] = true; } while(!s.empty()) { if(s.size() > 1) finished = false; int k = s.top(); a[sz++] = k; s.pop(); for(int i = 0; i < e[k].size(); i++) t[e[k][i]]--; for(int i = 0; i < n; i++) if(!t[i] && !vis[i]) s.push(i), vis[i] = true;; } if(sz < n) return false; if(finished && !mrk) mrk = r; return true; } int main() { cin>>n>>m; for(int i = 1; i <= m; i++) { char c[3]; scanf("%s", c); int x = c[0] - 'A', y = c[2] - 'A'; e[x].push_back(y); degree[y]++; if(!topo(i)) { cout<<"Inconsistency found after "<<i<<" relations."; return 0; } memset(vis, false, sizeof(vis)); } if(mrk) { cout<<"Sorted sequence determined after "<<mrk<<" relations: "; for(int i = 0; i < n; i++) cout<<char(a[i] + 'A'); cout<<"."; } else cout<<"Sorted sequence cannot be determined."; return 0; }
