算法竞赛上册笔记
0. 加速
- 关闭std同步输出，加快读取输出速度。
在代码中加入ios::sync_with_stdio(false);即可关闭同步输出。
1. 基础数据结构
1.1 链表
luogo P1996 链接
#include <iostream>
#include <vector>
using namespace std;
struct Node{
int val;
Node *next;
Node(int x): val(x),next(nullptr){}
};
int main(){
int n,m;
cin >> n>> m;
Node* header,*p,*now,*prev;
header = new Node(1);
now = header;
for(int i=2;i<=n;i++){
p = new Node(i);
now->next = p;
now = p;
}
now->next = header;
prev = now;
now = header;
while((n--)>1){
for(int i=1;i<m;i++){
prev = now;
now = now->next;
}
cout << now->val << " ";
prev->next = now->next;
delete now;
now = prev->next;
}
cout << now->val << "";
delete now;
return 0;
}
通过使用动态链表，进行链表的修改，在遍历链表时，通过修改链表的next指针，可以实现删除节点的操作,通过prev指针可以找到要删除的节点的前一个节点，然后将prev->next指向now->next即可,这样便可以完成本题的要求。
1.2 队列
luogo P1540 链接
#include <bits/stdc++.h>
using namespace std;
queue<int> mem;
int Hash[1003] ={};
int main(){
int m,n;
cin >> m >> n;
int cnt=0;
while(n--){
int en;
cin >> en;
if(!Hash[en]){
++cnt;
mem.push(en);
Hash[en] = 1;
while(mem.size()>m){
Hash[mem.front()]=0;
mem.pop();
}
}
}
cout << cnt << endl;
return 0;
}
通过使用队列，可以实现一个固定大小的队列，当队列满时，新来的元素会自动删除最早进入队列的元素，这样可以实现一个固定大小的队列，并记录每个元素是否已经进入队列。
luogo P1886 链接
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int main(){
int a[N]={};
deque<int > q;
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++){
while(!q.empty() && a[q.back()]>a[i]) q.pop_back();
q.push_back(i);
if(i>=m){
while(!q.empty() && q.front()<=i-m) q.pop_front();
cout << a[q.front()] << " ";
}
}
cout << endl;
while(!q.empty()) q.pop_front();
for(int i=1;i<=n;i++){
while(!q.empty() && a[q.back()]<a[i]) q.pop_back();
q.push_back(i);
if(i>=m){
while(!q.empty() && q.front()<=i-m) q.pop_front();
cout << a[q.front()] << " ";
}
}
return 0;
}
本题核心思路是将最小值始终放在队列的左侧，只要大于特定长度的时候，就输出最小值，直到有新的最小值进入队列，将前面的元素删除，成为新的最小值，或者队列满后，删除最早进入队列的元素。
或将最大值始终放在队列的左侧，只要大于特定长度的时候，就输出最小值，直到有新的最大值进入队列，将前面的元素删除，成为新的最大值，或者队列满后，删除最早进入队列的元素。
其中!q.empty() && a[q.back()]>a[i]表示当前元素小于队列左侧元素，!q.empty() && a[q.back()]<a[i]表示当前元素大于队列左侧元素。然后使用q.pop_back();删除队列元素，以保持队列左侧为最小值或最大值。
if(i>=m)表示当前元素距离队列左侧的距离大于等于m，则输出队列左侧元素。
while(!q.empty() && q.front()<=i-m) q.pop_front(); 当队列满时，删除最早进入队列的元素，同时保持队列左侧为最小值或最大值。
DP+单调队列求解限定长度的最大子序和
#include <bits/stdc++.h>
using namespace std;
deque<int> dq;
int s[100005];
int main(){
int n,m;
cin >> n>>m;
for(int i=1;i<=n;i++)
cin >> s[i];
for(int i=1;i<=n;i++)
s[i] = s[i]+s[i-1];
int ans = -1e8;
dq.push_back(0);
for(int i=1;i<=n;i++){
while(!dq.empty() && dq.front()<i-m) dq.pop_front();
if(dq.empty()) ans = max(ans,s[i]);
else ans = max(ans,s[i]-s[dq.front()]);
while(!dq.empty() && s[dq.back()]>=s[i]) dq.pop_back();
dq.push_back(i);
}
cout << ans << endl;
return 0;
}
在本体中使用前缀和的方式，将数组s中的元素变成前缀和数组s，这样就可以使用单调队列来求解。
使用while(!dq.empty() && dq.front()<i-m) dq.pop_front();来删除队列中距离当前元素大于m的元素，因为这些元素的前缀和已经不再需要，可以舍弃。
使用if(dq.empty()) ans = max(ans,s[i]);来初始化答案，因为队列为空时，ans为s[i]，所以初始化为ans为s[i]。
使用else ans = max(ans,s[i]-s[dq.front()]);来更新答案，因为队列中元素的前缀和大于等于s[i]，所以ans为s[i]减去队列左侧元素的前缀和。
毕竟使用了
前缀和,所以s[i]-s[dq.front()]就可以求出区间i-dp.front()的最大子序和值了。
i-dp.front()表示区间的区间由while(!dq.empty() && dq.front()<i-m) dq.pop_front();进行维护。同时，使用
while(!dq.empty() && s[dq.back()]>=s[i]) dq.pop_back();来删除队列中s[i]之前的元素,因为dp中存储的那些元素，都有可能会成为dp.front(),所以为了保证值最大，要使s[dp.front()]尽可能小，因为这些元素的前缀和已经不再需要，可以舍弃。
注意事项
在使用双端队列的时候，一定要先使用
while(!q.empty() && a[q.back()]>a[i]) q.pop_back();来维护队列的状态，然后使用q.push_back(i);来添加元素，这样可以保证队列左侧为最小值或最大值。否则，就会导致队列无法正常保持为最小值或最大值，导致输出错误。
因为你先将
i压入队列后，q.back就成了i，这个时候再使用while(!q.empty() && a[q.back()]>a[i]) q.pop_back();就不能删除i之前的元素，导致q.front()的值错误。
1.3 单调栈
luogo P2947 链接
#include <bits/stdc++.h>
using namespace std;
int h[1000005],ans[100005];
int main(){
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> h[i];
}
stack<int> st;
for(int i=n;i>=1;i--){
while(!st.empty() && h[st.top()]<=h[i]) st.pop();
if(st.empty()) ans[i]=0;
else ans[i] = st.top();
st.push(i);
}
for(int i=1;i<=n;i++) cout << ans[i] << endl;
return 0;
}
本题使用单调栈，维护一个栈，通过倒序放入栈，维护仰望对象(也就是向右看齐的最大值)，栈顶元素维护为比栈底小，
while(!st.empty() && h[st.top()]<=h[i]) st.pop();维护栈底元素为比栈顶元素大，这样栈底元素就是栈底元素的仰望对象。
else ans[i] = st.top();使用ans数组记录栈顶元素的仰望对象，这样就可以求解出每个元素的仰望对象。
1.4 哈夫曼树和哈夫曼编码
#include <bits/stdc++.h>
using namespace std;
int main(){
priority_queue<int,vector<int>,greater<int>> q;
string s;
while(getline(cin,s) && s!="END"){
sort(s.begin(),s.end());
int num =1;
for(int i=1;i<=s.length();i++){
if(s[i]!=s[i-1]){q.push(num);num=1;}
else num++;
}
int ans=0;
if(q.size()==1) ans = s.length();
while(q.size()>1){
int a=q.top();q.pop();
int b= q.top();q.pop();
q.push(a+b);
ans +=a+b;
}
q.pop();
cout << s.length()*8<<" " << ans << " "<<(double) s.length()*8/(double ) ans << "";
}
return 0;
}
代码实现了哈夫曼编码的核心思想，以下是对代码中各部分如何进行压缩的详细解释：
1. 原始编码长度：s.length() * 8
原始的编码方式假设每个字符都用固定的 **8 位（1 字节）**来表示。这是基于计算机常用的 ASCII 编码方式，其中每个字符占用 8 位存储空间。
计算逻辑：
- 如果输入字符串的长度为
s.length()：- 原始的总编码长度为：
s.length() * 8。 - 因为每个字符占 8 位，所以整个字符串的总长度是字符串长度乘以 8。
- 原始的总编码长度为：
示例：
- 输入字符串
aaaabcc：- 字符串长度
s.length() = 7。 - 原始编码长度：
7 * 8 = 56（假设每个字符都用 8 位表示）。
- 字符串长度
2. 哈夫曼编码如何实现压缩？
哈夫曼编码通过为频率较高的字符分配更短的编码，而频率较低的字符分配更长的编码，从而实现压缩。
核心思想：
- 频率决定编码长度：
- 高频字符占用更短的比特数。
- 低频字符占用较长的比特数。
- 哈夫曼树生成过程：
- 每次合并两个频率最小的节点，构建一棵最优二叉树。
- 每个叶子节点（字符）到根节点的路径长度即为该字符的编码长度。
示例：
对于 aaaabcc，字符频率如下：
a: 4b: 1c: 2
生成的哈夫曼树可能如下：
(*,7)
/ \
(*,3) a(4)
/ \
b(1) c(2)
对应编码：
a: 0（1 位）b: 10（2 位）c: 11（2 位）
总长度计算：
a: 4 次 * 1 位 = 4 位b: 1 次 * 2 位 = 2 位c: 2 次 * 2 位 = 4 位- 总长度：
4 + 2 + 4 = 10 位
相比原始的 56 位，哈夫曼编码压缩到 10 位。
关于为什么压缩后的长度为
10位(ans)，可以这样计算,a为1位，b为2位，c为2位，所以按照频率计算和就是10位。关于代码中为什么可以从下面一步一步加上去，可以这么理解，他的父节点计算的是到两边的频率，但同时长度为一，所以根节点在计算总长度的时候，需要把两边子结点的长度加上，所以才有了
ans的计算。
1.4.1 二叉树的遍历
1.4.1.1 前序遍历
void preorder(Node* root){
if(root==NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
1.4.1.2 中序遍历
void inorder(Node* root){
if(root==NULL) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
1.4.1.3 后序遍历
void postorder(Node* root){
if(root==NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
，前序，中序和后序遍历的关系
- 前序遍历：根节点->左子树->右子树
- 中序遍历：左子树->根节点->右子树
- 后序遍历：左子树->右子树->根节点
从中序，后序遍历可以推出前序遍历。
例：luogu P1030 链接
思路：因为后序遍历的最后一个元素为根节点或父节点，可以通过使用这个元素(后序的最后一个元素)，来截开左右子树，因为在中序遍历中的根节点，左侧为左子树遍历出的结果，右侧为右子树遍历出的结果(相应的可以根据中序遍历的结果，在后序遍历的结果中分离出左右子树(根据在中序遍历截取的字符串大小))，之后在左右子树中重复前面的过程即可，最后弹出结果。
2. 基本算法
2.2.3 多指针
luogu P1102 链接
#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int a[N];
int main(){
//int a[20]={};
int n,c;
cin >> n >> c;
for(int i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+1+n);
long long ans =0;
for(int i=1,j=1,k=1;i<=n;i++){
while(j<=n && a[j]-a[i]<c) j++; //j指针向右移动，找到距离a[i]小于c的第一个数
while(k<=n && a[k]-a[i]<=c) k++; //k指针向右移动，找到距离a[i]不大于c的第一个数
if(a[j]-a[i]==c && a[k-1]-a[i]==c && k-1>=1 ) ans +=k-j;
}
cout << ans << endl;
return 0;
}
假如说我们输入的实例为(我们输入的为排完序的数组)：
6 3
4 4 5 7 7 8
当i为1时，
那么,j,k寻找的区间就是：[4,6)
这样就可以直接算出前面i配对的个数，即ans+=k-j
关于为什么要这么弄？是因为双指针的算法并不能正常处理
4与7的配对情况，因为第一次匹配后，指针往前走就不能再匹配了，会导致少匹配2次
2.3.2 整数二分
luogu P1824 链接
#include <bits/stdc++.h>
using namespace std;
bool check(int dis,int n,int c,int x[]){
int cnt =1,place= 0;
for(int i=1;i<n;++i)
if(x[i]-x[place]>=dis){
cnt++;
place = i;
}
if(cnt >=c) return true;
else return false;
}
int main(){
ios::sync_with_stdio(false);
int n,c,x[20]={};
cin >> n >>c ;
for(int i=0;i<n;i++) cin >> x[i];
sort(x,x+n);
int left=0,right = x[n-1]-x[0];
int ans=0;
while(left<right){
int mid = left +(right-left)/2;
if(check(mid,n,c,x)){
ans = mid;
left = mid+1;
}else{
right = mid;
}
}
cout << ans << endl;
return 0;
}
这个题首先要理解题意，这个问题是找最大的最近距离，简单举个例子，就是，你有N个在不同位置的房子，你要找C个房子(C<=N),假设这N个房子在同一条直线上，那么你找的那C个房子的距离要尽可能的大。
所以，解这道题，就是要找一个最大的dis，使得C个房子的距离都大于等于dis。(要记得先排序，因为要找最大的距离，所以要从小到大排序)
那么，我们可以用二分法来解决这个问题，我们先初始化left=0，right=x[n-1]-x[0]，因为我们的房子在同一条直线上，所以x[n-1]-x[0]就是最远处的距离。
然后，我们用while循环来进行二分，每次二分，我们计算mid的值，然后判断mid是否满足条件，如果满足条件，我们更新ans=mid，然后left=mid+1，如果不满足条件，我们更新right=mid，然后再次进行二分。
使用check函数进行的判断，
2.6 前缀和与差分
一维差分
#include <bits/stdc++.h>
using namespace std;
const int N= 100010;
int main(){
int a[20]={},d[20]={};
int n;
while(cin>>n){
for(int i=1;i<=n;i++){
int l,r;
cin >> l >> r;
d[l]++;
d[r+1]--;
}
for(int i=1;i<=n;i++){
a[i] = a[i-1]+d[i];
if(i!=n) cout << a[i] ;
else cout << a[i];
}
}
return 0;
}
本题使用前缀和和差分的方式，将数组a中的元素变成前缀和数组a，并将数组d中的元素变成差分数组d。
d[k] = a[k] - a[k-1] ----> a[k] = d[1]+d[2]+...+d[k-1]+d[k]使用差分的方法可以只改变数组的
前缀和数组d，而不改变原数组a。然后通过计算
d数组的前缀和，将前缀和加到数组a中，就可以避免复杂度为O(mn)的方法，改变数组a中区间的元素值。
- 感谢你赐予我前进的力量
-
微信 
支付宝
