跳至主要內容
Codeforces Round 1044 (Div. 2 A-E)

A. Redstone?

题目大意：n个齿轮从左到右耦合在一起，数组a表示每个齿轮的齿数。最左边的齿轮依次带动其他齿轮旋转，相邻齿轮旋转速度与齿数成反比。问是否存在一种排列，使得最右边的齿轮旋转速率和最左边的相等。

思路：最右侧齿轮转速为：

Xanadu132025年8月29日大约 6 分钟C++codeforcesdp
卡特兰数

以下例子都属于卡特兰数问题：

  1. 有 2n2n 个人排成一行进入剧场。入场费 5 元。其中只有 nn 个人有一张 5 元钞票，另外 nn 个人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？

  2. 有一个大小为 n×nn\times n 的方格图左下角为 (0,0)(0,0) 右上角为 (n,n)(n,n)，从左下角开始每次都只能向右或者向上走一单位，不走到对角线 y=xy=x 上方（但可以触碰）的情况下到达右上角有多少可能的路径？

  3. 在圆上选择 2n2n 个点，将这些点成对连接起来使得所得的 nn 条线段不相交的方法数？

  4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？

  5. 一个栈（无穷大）的进栈序列为 1,2,3,…,n1,2,3,\ldots,n 有多少个不同的出栈序列？

  6. nn 个结点可构造多少个不同的二叉树？

  7. 由 nn 个 +1+1 和 nn 个 −1-1 组成的 2n2n 个数 a1,a2,…,a2na_1,a_2,\dots,a_{2n}，其部分和满足 a1+a2+⋯+ak≥0 (k=1,2,3,…,2n)a_1+a_2+\cdots+a_k\ge 0\ (k=1,2,3,\dots,2n)，有多少个满足条件的数列？

Xanadu132025年8月23日大约 3 分钟C++algorithmluogu卡特兰数
HDOJ-1058 丑数

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1058

序数词太ex了...

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
mt19937_64 rng(random_device{}());
string get_suf(int x) {
    if (x / 10 % 10 == 1) return "th";
    if (x % 10 == 1) return "st";
    if (x % 10 == 2) return "nd";
    if (x % 10 == 3) return "rd";
    return "th";
}
void solve() {
    vector<int> dp(N, INT_MAX);
    dp[1] = 1;
    int cur[4] = {1, 1, 1, 1};
    int base[4] = {2, 3, 5, 7};
    for (int i = 2; i <= 5842; ++i) {
        vector<int> vec(4);
        for (int j = 0; j < 4; ++j) {
            vec[j] = dp[cur[j]] * base[j];
        }
        dp[i] = *min_element(vec.begin(), vec.end());
        for (int j = 0; j < 4; ++j) {
            if (dp[i] == dp[cur[j]] * base[j]) ++cur[j];
        }
    }
    int n;
    while (cin >> n && n) {
        cout << "The " << n << get_suf(n) << " humble number is " << dp[n] << ".\n";
    }
}
int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) 
        solve();
    return 0;
}
Xanadu132025年8月20日小于 1 分钟hdojC++algorithm
洛谷P1106 删数问题

题目传送门：https://www.luogu.com.cn/problem/P1106

解法一：循环k次，每次找逆序对并删除左边的数，如果找不到则说明数列已经是非递减的，直接删最右边的。注意前导零的处理即可。

时间复杂度：O(kn)O(kn)

Xanadu132025年8月20日大约 2 分钟C++algorithm贪心
最长递增子序列

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 分钟C++C++
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++C++KMP
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++C++
洛谷P3916 图的遍历

题目传送门：https://www.luogu.com.cn/problem/P3916

解法一：DFS

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
constexpr int N = 1e5 + 5, M = 1e5 + 5;
int ver[M], nxt[M], head[N], tot, vis[N], d[N];
void add(int x, int y) {
    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
}
void dfs(int x, int val) {
    if (vis[x]) return;
    vis[x] = 1;
    d[x] = val;
    for (int i = head[x]; i ; i = nxt[i]) {
        int y = ver[i];
        dfs(y, val);
    }
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        add(y, x);
    }
    for (int i = n; i >= 1; --i) {
        dfs(i, i);
    }
    for (int i = 1; i <= n; ++i) {
        cout << d[i] << ' ';
    }
}

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月5日大约 1 分钟C++algorithmBFSDFS
Made with ❤️
Copyright © 2025 Xanadu13