Acwing算法笔记
第一章
快排
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int main() {
int a[N];
int n;
cin>>n;
for (int i = 0; i < n; i ++ ){
cin>>a[i];
}
sort(a,a+n);
for (int i = 0; i < n; i ++ ){
cout<<a[i]<<" ";
}
}
归并排序
模版：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r) // 归并排序
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int solve(){
int n;
cin>>n;
int a[N];
for (int i = 0; i < n; i ++ )
cin>>a[i];
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++ )
cout<<a[i]<<" ";
}
signed main(){
int t = 1;
//cin>>t;
while(t--){
solve();
}
}
AcWing 788. 逆序对的数量
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define int long long
int n;
int a[N],tmp[N];
int merge_sort(int l,int r){
if(l >= r) return 0;
int mid = l+r>>1;
int res = merge_sort(l,mid) + merge_sort(mid+1,r); //递归左右两部分
//归并部分
int k = 0,i = l,j = mid+1;
while(i <= mid && j <= r)
if(a[i] <= a[j]) tmp[k++] = a[i++]; //注意是小于等于
else {
tmp[k++] = a[j++];
res+=mid-i+1;
}
while(i <= mid){
tmp[k++] = a[i++];
}
while(j <= r){
tmp[k++] = a[j++];
}
//物归原主
for(int i = l,j = 0;i<=r;i++,j++){
a[i] = tmp[j];
}
return res;
}
signed main(){
cin>>n;
for (int i = 0; i < n; i ++ ) cin>>a[i];
cout<<merge_sort(0,n-1);
}
整数二分
#include<bits/stdc++.h>
const int N = 1e5+10 ;
using namespace std;
int n,q;
int a[N];
int k;
void check(int x,int n){
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] < x) l = mid + 1;
else r = mid;
}
if ( a[l]!= x){
cout << "-1 -1" << endl;
return;
}
int l1 = l,r1 = n;
while (l1+1 <r1){
int mid = l1+r1>>1;
if(a[mid] <= x) l1 = mid;
else r1 = mid;
}
::printf("%d %d\n",l,l1);
}
int main()
{
cin>>n>>q;
for (int i = 0; i < n; i++) {
cin>>a[i];
}
for (int i = 0; i < q; i++) {
cin>>k;
check(k,n);
}
return 0;
}
第四章
质因数分解
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
void divide(){
int a;
cin>>a;
for (int i = 2; i <= a/i; i ++ ){
if(a%i == 0){
int s = 0;
while(a%i == 0){
a/=i;
s++;
}
cout << i << " "<< s<<endl; //每个质因数和个数（s为个数）
}
}
if(a > 1) cout << a<<" "<<1<<endl; //唯一的大于sqrt（n）的数
cout << endl;
}
int main(){
int n;
cin>>n;
while(n--){
divide();
}
}
快速幂和快速幂求逆元
//快速幂
/**
* 快速的求出a^k mod p 的结果
*/
#define int long long
int qmi(int a,int b,int p){
int res = 1;
while(b){
if(b&1) res= res*a%p;
b >>=1;
a = a*a%p;
}
return res;
}
//快速幂求逆元
int inv(int a,int b){
return qmi(a,b-2,b);//费马小定理
}
第五章 STL
map
-
map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。
-
常见用法： begin() 返回指向map头部的迭代器 clear() 删除所有元素 empty() 判断map是否为空 end() 返回指向map末尾的迭代器 erase() 删除一个元素 find() 查找一个元素 insert() 插入元素 size() 返回map中元素的个数
使用map模拟链表
题目(https://ac.nowcoder.com/acm/contest/74362/D)
#include<bits/stdc++.h> #define int long long typedef long long ll; using namespace std; const int N = 1e5 + 10; const int mod = 1e9 + 7; void solve(){; int q; cin>>q; map<int,int> l,r; int op = -1e9-1,ed = 1e9+1;//使用map模拟的初始化 r[op] = ed;//头结点的右边为尾节点，尾节点的左边为头结点 l[ed] = op; int sz = 0; while (q--){ int chk; cin>>chk; if(chk == 1){ //使用map模拟链表，l[i]代表元素i左节点，r代表元素i右节点 int x,y; cin>>x>>y; int ll,rr; //插入位置的左节点和右节点 if(y == 0){ ll = op; rr = r[op]; }else{ ll = y; rr = r[y]; } r[x] = rr; //先更新插入元素的右节点 l[x] = ll; //更新插入元素的左节点 l[rr] = x; //更新插入元素右边元素的左节点 r[ll] = x; //更新插入元素左边元素的右节点 sz++; } else{ int x; //模拟链表的删除 cin>>x; int ll = l[x],rr = r[x]; r[ll] = rr; l[rr] = ll; sz--; } } cout<<sz<<endl;//输出 for(int i = r[op];i != end;i = r[i]){ cout<<i<<" "; } } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); int t = 1; //cin>>t; while(t--){ solve(); } return 0 ; }
unordered_map：
- unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)。
- 优点： 因为内部实现了哈希表，因此其查找速度非常的快。
- 用法与map基本相同。
第六章 dp
非常典的一个背包问题https://ac.nowcoder.com/acm/contest/74362/E
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
void solve(){
int n;
cin>>n;
//背包dp问题
int dp[205][80010]; //由于j可能为负数，需要偏移，40000代表0,0代表-40000
//dp[i][j]代表i个元素使得求和结果为j的最小选择个数
/**
*对于i,j，第i个元素为x，那么当前元素x可以选择保持初始符号，
*直接加进来，那么dp[i,j]从dp[i-1,j-x]转移过来，
*也可以选择取反再加，那么dp[i,j]从dp[i-1,j+x]+1转移过来，
*由于进行了取反操作，操作次数加一。
*/
memset(dp,0x3f,sizeof(dp));
dp[0][40000] = 0;
for(int i = 1;i<=n;i++){
int x = 0;
cin>>x;
for(int j = 0;j<=80000;j++){
if(j-x >= 0 && j-x <= 80000) dp[i][j] = min(dp[i][j],dp[i-1][j-x]+1);
if(j+x >= 0 && j+x <= 80000) dp[i][j] = min(dp[i][j],dp[i-1][j+x]);
}
}
if(dp[n][40000] <= n){
cout<<dp[n][40000];
}else{
cout<<"-1";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int t = 1;
//cin>>t;
while(t--){
solve();
}
return 0 ;
}
京公网安备 11010502036488号