标签: C++

n^2 dp

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
mt19937_64 rng(random_device{}());
void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (auto &e : arr)
        cin >> e;
    vector<int> dp(n, 1);
    int ans = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] >= arr[i]) {
                dp[j] = max(dp[j], dp[i] + 1);
                ans = max(ans, dp[j]);
            }
        }
    }
    cout << ans << '\n';
}
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Xanadu132025年8月14日大约 1 分钟

KMP算法

https://oi-wiki.org/string/kmp/

vector<int> pre(string &s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; ++i) {
        int j = pi[i-1];
        while (j && s[i] != s[j]) j = pi[j-1];
        if (s[i] == s[j]) ++j;
        pi[i] = j;
    }
    return pi;
}
int kmp(string &str1, string &str2) {
    string str = str2 + '#' + str1;
    vector<int> pi = pre(str);
    int n = str2.size();
    for (size_t i = str2.size() + 1; i < str.size(); ++i) {
        if (pi[i] == n) return i - 2 * n;
    }
    return -1;
}
void solve() {
    string str1 = "banana";
    string str2 = "na";
    assert(kmp(str1, str2) == 2);
}

Xanadu132025年8月13日小于 1 分钟

C++手撕智能指针

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
mt19937_64 rng(random_device{}());
template <class T>
class Arc {
private:
    int* cnt;
    T* ptr;
    mutex* lock;
    void inc() {
        lock->lock();
        ++*cnt;
        lock->unlock();
    }
    void release() {
        bool del = false;
        lock->lock();
        if (--*cnt == 0) {
            delete ptr;
            delete cnt;
            del = true;
        }
        lock->unlock();
        if (del) delete lock;
    }
public:
    Arc(T* ptr = nullptr):cnt(new int(1)), ptr(ptr), lock(new mutex) {}
    Arc(const Arc<T> &lhs):cnt(lhs.cnt), ptr(lhs.ptr), lock(lhs.lock) {
        inc();
    }
    Arc<T>& operator =(const Arc<T>& rhs) {
        if (ptr != rhs.ptr) {
            release();
            cnt = rhs.cnt;
            ptr = rhs.ptr;
            lock = rhs.lock;
            inc();
        }
        return *this;
    }
    T& operator*() {
        return *ptr;
    }
    T* operator->() {
        return ptr;
    }
    T* get() {
        return ptr;
    }
    ~Arc() {
        release();
    }
};
void solve() {
    auto ptr = Arc<vector<int>>(new vector<int>);
    ptr->push_back(1);
    ptr->push_back(2);
    ptr->push_back(3);
    for (auto &e : *ptr) {
        cout << e << ' ';
    }
}
int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int tt; cin >> tt;
    // while (tt--)
        solve();
    return 0;
}

Xanadu132025年8月12日小于 1 分钟

C++编码基础

使用cout时保留几位小数

cout << fixed << setprecision(2) << (double) ans / n;

Xanadu132025年4月18日小于 1 分钟

priority_queue重载运算符

typedef pair<int, int> pii;
struct cmp {
    bool operator () (const pii& lhs, const pii& rhs) {
        return lhs.second > rhs.second;
    }
};

priority_queue<pii, vector<pii>, cmp> q;

Xanadu132025年4月12日小于 1 分钟

C++中原生编译时字符串混淆实现

C++中具有强大的模板元编程，可以不依赖任何外部库，仅使用C++ std实现编译时的字符串混淆。

原始版本

在我的另一篇文章中提到过一个C++中字符串混淆的简易版本：

但其中0x55是硬编码的，我们需要引入编译时随机数来消除这一硬编码。

Xanadu132024年12月17日大约 3 分钟