363045841 的博客

Appearance

抽签 ​

二分优化

cpp
void solve(int cycle){
    int n,m;
    cin >> n >> m;
    int num[n+1];
    rep(i,1,n) cin >> num[i];
    int preSum[n*n+5];
    rep(i,1,n){
        rep(j,1,n){
            preSum[i*n+j] = num[i] + num[j];
        }
    }
    sort(preSum+1, preSum+n*n);
    rep(i,1,n){
        rep(j,i + 1,n){
            dbg(num[i], num[j]);
            auto pos = lower_bound(preSum+1, preSum+n*n, m - num[i] - num[j]);
            if(*pos == m - num[i] - num[j]){
                cout << num[i] << " " << num[j] << " " << *pos << endl;
                exit(0);
            }
        }
    }
    cout << "NO\n";
}

深度优先搜索 ​

cpp
int n,k;
int a[10];
int his[10];
bool dfs(int i,int sum){
    //if(i == 4)
    dbg(i,sum);
    if(i == n){
        return (sum == k);
    }
    
    if(dfs(i+1,sum)){
        return true;
    }
    if(dfs(i+1,sum+a[i])){
        his[i] = a[i];
        return true;
    }
    return false;
}
void solve(int cycle){
    cin >> n;
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    cin >> k;
    if(dfs(0,0)){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    for(int i = 0;i<n;i++){
        cout << his[i] << " ";
    }
}

哈夫曼树贪心 ​

cpp
#include <iostream>
#include <queue>
using namespace std;

using ll = long long;

priority_queue<ll, vector<ll>, greater<ll>> pq;//创建一个小根堆

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        pq.push(x);
    }//将结果放入优先队列中（小根堆），反向构建哈夫曼树

    ll ret = 0;
    while (pq.size() > 1)
    {
        ll x = pq.top();
        pq.pop();
        ll y = pq.top();
        pq.pop();
        ret += x + y;//有几层就会加几层
        pq.push(x + y);
        cout << x + y << " ";
    }
    cout << ret << endl;
    return 0;
}

对顶堆 ​

cpp
void solve(int cycle){
    int n;
    cin >> n;
    int k = 1;
    rep(i,1,n){
        int x;
        cin >> x;
        if(b.empty() || x >= b.top()){
            b.push(x);
        }else{
            a.push(x);
        }
        k = (i + 1) / 2;
        while(b.size() > k){
            a.push(b.top());
            b.pop();
        }
        while(b.size() < k){
            b.push(a.top());
            a.pop();
        }
        if(i % 2 != 0){
            cout << b.top() << endl;
            dbg(k);
        }
        
    }
}

单调队列 ​

P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这里 ≥ 是单调增队列，≤ 是单调减队列

cpp
int main(){
    int n,k;
    cin >> n >> k;
    vector<int> num(n + 1);
    rep(i,1,n) cin >> num[i];
    vector<int> ans_min;
    vector<int> ans_max;
    deque<int> dq;//warning : the deque save i-th number
    for(int i = 1;i<=n;i++){
        // deque in
        while(!dq.empty() && num[dq.back()] <= num[i]){
            dq.pop_back();//let small number get out
        }
        dq.push_back(i);
        if(i - dq.front() >= k){
            //eg. let i_th = [1,2,3,4] and k = 3
            //the length of a region is 4 - 1 = 3
            //so we need to pop the first number
            dq.pop_front();
        }
        if(i >= k){
            ans_max.push_back(num[dq.front()]);
        }
    }

    deque<int> dq2;
    for(int i = 1;i<=n;i++){
        while(!dq2.empty() && num[dq2.back()] >= num[i]){
            dq2.pop_back();
        }
        dq2.push_back(i);
        if(i - dq2.front() >= k){
            dq2.pop_front();
        }
        if(i >= k){
            ans_min.push_back(num[dq2.front()]);
        }
    }
    for(auto &x : ans_min) cout << x << ' ';
    cout << endl;
    for(auto &x : ans_max) cout << x << ' ';
    cout << endl;
}

单调栈 ​

笔记：单调栈【基础算法精讲 26】_哔哩哔哩_bilibili 标程：739. 每日温度 - 力扣（LeetCode）