上午/一维数组排序
- 排序：sort，冒泡，选择，插入，计数
复杂度：\(O(nlogn),O(n^2),O(n^2),O(n^2),O(n)\)
点击查看代码
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N], n;
int main(){
// cin>>n;
// for(int i=1; i<=n; i++) cin>>a[i];
// sort(a+1, a+1+n); // 快速排序，默认升序
// 冒泡：每次比较两个相邻元素
// for(int i=n; i>=1; i--){ // 第 n-i+1 轮冒泡
// for(int j=1; j<i; j++) // 需要比较的区间 [1,i-1]
// if(a[j] > a[j+1]) swap(a[j], a[j+1]);
// }
// 选择：每次选择最大值放最后
// for(int i=n; i>=1; i--){
// int k = i; // 最大值所在下标
// for(int j=1; j<i; j++) // [1, i-1]
// if(a[k] < a[j]) k=j;
// swap(a[k], a[i]);
// }
// 插入:将当前元素插入一个有序序列
// for(int i=1; i<=n; i++){
// int k=i;
// for(int j=i-1; j>=1; j--){
// if(a[k] >= a[j]) break;
// else { swap(a[k], a[j]); k=j; }
// }
// }
// for(int i=1; i<=n; i++) cout<<a[i]<<" "; cout<<endl;
// 计数排序，标记思想：a[x] 表示 x 的个数
cin>>n;
for(int i=1; i<=n; i++){
int x; cin>>x;
a[ x ] ++;
}
for(int i=1; i<=10; i++){
for(int j=1; j<=a[i]; j++) // a[i] 个 x
cout<<i<<" ";
}
return 0;
}
/* 给定一个数列：2 4 2 3 1， 请手写其 三种排序的过程
如：冒泡
1. 2 2 3 1 4
2. 2 2 1 3 4
3. 2 1 2 3 4
4. 1 2 2 3 4
*/
-
标记思想练习
-
P1008 [NOIP1998 普及组] 三连击
分析：
方法1:9个for, 枚举所有排列情况
方法2:3个for, 枚举每个三位数
方法3:枚举 \(a=i\)，计算出 \(b=2*i,c=3*i\)，再利用标记思想检查是否 1-9 都出现了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int st[10];
int main(){
for(int i=100; i<=999; i++){
int a=i, b=i*2, c=i*3;
if(c>999) break; // 如果出现四位数，会出现越界，危险
for(int j=0; j<10; j++) st[j]=0;
st[a/100] = st[a/10%10] = st[a%10]=1;
st[b/100] = st[b/10%10] = st[b%10]=1;
st[c/100] = st[c/10%10] = st[c%10]=1;
int s = 0;
for(int j=1;j<=9;j++) s += st[j];
if(s==9) cout<<a<<" "<<b<<" "<<c<<endl;
}
return 0;
}
- P1618 三连击（升级版）
分析：在上题基础上升级，发现死了不变，需要变化的是 a?️c=A:B:C
可以推出当 枚举 \(a=i, b=B*i/A, c=C*i/A\) （先乘后除，思考为什么）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int A,B,C,cnt;
int main(){
cin>>A>>B>>C;
if(A!=0)
for(int i=100; i<=999; i++){
int a=i, b=B/A*i, c=C/A*i;
if(c > 999) break;
int st[10] = {0};
// for(int j=0; j<10; j++) st[j]=0; // 多组数据需要检查，每组都需要初始化
st[a/100] = st[a/10%10] = st[a%10] = 1;
st[b/100] = st[b/10%10] = st[b%10] = 1;
st[c/100] = st[c/10%10] = st[c%10] = 1;
int s=0;
for(int j=1; j<=9; j++) s += st[j];
if(s==9) {
cout<<a<<" "<<b<<" "<<c<<endl;
cnt ++;
}
}
if(cnt==0) cout<<"No!!!";
return 0;
}