头像

舒克不开飞机

古大




在线 


最近来访(0)

活动打卡代码 AcWing 785. 快速排序

分治:不断把数据分成两部分,一半小于另一半

不稳定:q[i]、q[j]和分界点相同时仍交换

  1. 确定分界(4种方法):取q[l], q[(l + r) / 2], q[r], 随机点

  2. 调整区间:小于分界点的在左区间,其余在右区间

    使用两个数组作为左右区间
    
    使用两个指针(i = l - 1,j = r + 1),如果a[i]>x, a[j]<x 就交换a[i] a[j],否则一直移动指针
    
  3. 递归:给左右排序

#include <iostream>

using namespace std;

const int N = 1e6+10;

int q[N];
int n;

void quick_sort(int q[], int l, int r) {
    if (l >= r) return; // 如果只有一个数不用排序

    int x = q[l+r >> 1], i = l-1, j = r+1; 
    // l+r >> 1 相当于 (l+r)/2
    // 确定分界x 后面用do...while这里需要将指针先向两边移动
    while (i < j) {
        do i++; while (q[i] < x); // q[i]的位置正确,指针后移
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

int main() {
    ios::sync_with_stdio(false); // 关闭io缓冲
    cin>>n;
    for (int i = 0; i < n; i ++ ) {
        cin>>q[i];
    }
    quick_sort(q, 0, n-1);
    for (int i = 0; i < n; i ++ ) {
        cout<<q[i]<<' ';
    }
}


活动打卡代码 AcWing 1960. 闪烁

【位运算 状态压缩 找环】

环:状态数远小于要转换的次数,说明状态会重复
状态压缩:用string或者二进制表示状态
位运算:用异或和移位来进行状态转换

用 1<<n 计算 2^n

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/42197/



活动打卡代码 AcWing 1969. 品种邻近

【枚举】
记录该ID上次出现的下标

#include <iostream>
#include <cstring>

using namespace std;
int N, K;
const int MAX = 1000010;
int dist[MAX];
int main() {
    cin>>N>>K;
    int ans = -1, x;
    memset(dist,-1,sizeof(dist));
    for (int i = 0 ; i < N ; ++i) {
        cin>>x;
        if (dist[x] != -1) {
            int det = i - dist[x];
            if (det <= K) {
                ans = max(ans,x);
            }
        }
        dist[x] = i;
    }
    cout<<ans;
}

也可以用队列或者双指针的滑动窗口法



活动打卡代码 AcWing 1978. 奶牛过马路

IMG_B1E4D502B475-1.jpeg
【排序、前缀最值】

用从1开始的数组(在0和MAX+1放-INF和INF),方便计算
注意在外面定义数组,否则INF和—INF可能赋不上

#include <iostream>
#include <cstring>
#include <algorithm>

#define a first 
#define b second
using namespace std;
const int MAX = 1e5+10, INF = 1e8;
int N;
pair<int,int> node[MAX];
int sum_max[MAX], sum_min[MAX];
int main(){
    cin>>N;
    // 从1开始 可以用i-1计算前缀最大值
    // 计算后缀最小值
    for (int i = 1 ; i <= N ; ++i) { 
        cin>>node[i].a>>node[i].b;
    }
    sort(node+1,node+N+1);

    sum_min[N+1] = INF;
    sum_max[0] = -INF; 
    for (int i = 1 ; i <= N ; ++i) {
        sum_max[i] = max(sum_max[i-1], node[i].b);
    }
    for (int i = N ; i > 0 ; --i) {
        sum_min[i] = min(sum_min[i+1], node[i].b);
    }
    int ans = 0;
    for (int i = 1 ; i <= N ; ++i) {
        if (node[i].b<sum_min[i+1]&&node[i].b>sum_max[i-1]) ans++;
    }
    cout<<ans;
}



AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/42197/