头像

心里没有一点AC数

兰州大学 - 网易浚源工作室 - 西山居 - $\href{https://www.fogsail.net}{Blog}$




离线:14小时前


活动打卡代码 AcWing 132. 小组队列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1000 + 10;
const int maxm = 1e6 + 10;

// n teams, m people

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0, n;
    while (cin >> n && n) {
        printf("Scenario #%d\n", ++kase);

        queue<int> que[maxn];
        int ID[maxm], m;
        for (int i = 1; i <= n; i++) {
            cin >> m;
            _for(_, 0, m) {
                int num; cin >> num;
                ID[num] = i;
            }
        }

        // then operation
        string op;
        while (cin >> op) {
            if (op[0] == 'S') break;
            if (op[0] == 'E') {
                int x; cin >> x;
                int Y = ID[x];
                if (que[Y].empty()) que[0].push(Y);
                que[Y].push(x);
            }
            if (op[0] == 'D') {
                int Y = que[0].front();
                int x = que[Y].front();
                printf("%d\n", x);
                que[Y].pop();
                if (que[Y].empty()) que[0].pop();
            }
        }

        // end
        printf("\n");
    }
}



#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1000 + 10;
const int maxm = 1e6 + 10;

// n teams, m people

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0, n;
    while (cin >> n && n) {
        printf("Scenario #%d\n", ++kase);

        queue<int> que[maxn];
        int ID[maxm], m;
        for (int i = 1; i <= n; i++) {
            cin >> m;
            _for(_, 0, m) {
                int num; cin >> num;
                ID[num] = i;
            }
        }

        // then operation
        string op;
        while (cin >> op) {
            if (op[0] == 'S') break;
            if (op[0] == 'E') {
                int x; cin >> x;
                int Y = ID[x];
                if (que[Y].empty()) que[0].push(Y);
                que[Y].push(x);
            }
            if (op[0] == 'D') {
                int Y = que[0].front();
                int x = que[Y].front();
                printf("%d\n", x);
                que[Y].pop();
                if (que[Y].empty()) que[0].pop();
            }
        }

        // end
        printf("\n");
    }
}



特殊计数序列——Catalan数

定理 考虑由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的 $2n$ 项序列
$$
a_1, a_2, \cdots , a_{2n}
$$
其部分和总是满足
$$
a_1+a_2+\cdots + a_k \geqslant 0 \quad (\forall k = {1, 2, \cdots, 2n })
$$
这种序列的个数等于第 $n$ 个 Catalan 数
$$
C_n = \frac{1}{n+1} {2n \choose n} (n \geqslant 0)
$$
证明如下
Catlan.001.jpeg

通过以上证明了任意不可接受序列 $U(n, n)$ 与序列 $C(n+1, n-1)$ 存在对应关系
$C(n+1, n-1)$ 的个数实际上就是排列数
$$
\frac{(2n)!}{(n+1)!(n-1)!}
$$
从而
$$
U(n) = \frac{(2n)!}{(n+1)!(n-1)!}
$$
$$
A(n) = {2n \choose n} - U(n) = \frac{1}{n+1}{2n \choose n}
$$

计数类问题编程实现常用函数

阶乘分解

fac.jpg
对于 $N!$ 进行阶乘分解的结果是
$$
\sum_{p^k \leqslant N} \lfloor \frac{N}{p_k} \rfloor
$$

试除法分解质因数

void divide(int x) {
    for (int i = 2; i <= x/i; i++) {
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0) s++, x /= i;
            // i^s
            make_pair(i, s);
        }
    }
    if (x > 1) make_pair(x, 1);
    // x^1
}

朴素筛法求质数

vector<int> primes;
bool st[maxn]; // init st[...] = 0
// st = true 表示这个数是合数

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i]) continue;
        primes.push_back(i);
        for (int j = 2*i; j <= n; j += i) st[j] = true;
    }
}

线性筛法求质数

primes.jpg

vector<int> primes;
bool st[maxn];

void get_primes() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.push_back(i);
        for (int j = 0; primes[j] <= n/i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j]) break;
        }
    }
}

Catalan 数经典应用

这里涉及到一个编程技巧,叫高精度压位
Acwing130

其实就是计算 Catalan 数
$$
\frac{1}{n+1} {2n \choose n}
$$

  • 打表 $[2, 2n]$ 所有的素数
  • 阶乘分解,$\textbf{for} \ \forall p \in \textbf{primes}[\cdots]$
    求出 $\textbf{pw}[p]= \textbf{get}(2n, p) - 2\cdot \textbf{get}(n, p)$
    即素数 $p$ 在$2n \choose n$ 这项中的幂指
  • 对 $n+1$ 进行素因子分解,$n+1 = \cdots p^s \cdots$,然后 $\textbf{pw}[p] -= s$
  • $\textbf{for} \ \forall p \in \textbf{primes}[\cdots]:$ 执行 $\textbf{pw}[p]$ 次 $\textbf{muti}(ans, p)$
const int maxn = 120000 + 10;
int n;

vector<int> primes;
bool st[maxn];

void get_primes() {
    memset(st, 0, sizeof st);
    for (int i = 2; i <= 2*n; i++) {
        if (st[i]) continue;
        primes.push_back(i);
        for (int j = 2*i; j <= 2*n; j += i) st[j] = true;
    }
}

int pw[maxn];

inline int get(int n, int p) {
    int s = 0;
    while (n) s += n/p, n /= p;
    return s;
}

void multi(vector<ll>& res, int b) {
    ll t = 0;
    for (int i = 0; i < res.size(); i++) {
        t += res[i] * b;
        res[i] = t % 100000000, t /= 100000000;
    }
    while (t) res.push_back(t % 100000000), t /= 100000000;
}

void out(const vector<ll>& res) {
    printf("%lld", res.back());
    for (int i = res.size()-2; i >= 0; i--) {
        printf("%08lld", res[i]);
    }
    printf("\n");
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n;

    // get primes
    get_primes();

    // divide factorial
    for (auto p : primes) pw[p] = get(2*n, p) - 2 * get(n, p);

    // divide
    int x = n+1;
    for (auto p : primes) if (p <= x) {
        int s = 0;
        while (x % p == 0) s++, x /= p;
        pw[p] -= s;
    }

    // multi
    vector<ll> ans;
    ans.push_back(1);
    for (auto p : primes) {
        for (int j = 0; j < pw[p]; j++) multi(ans, p);
    }

    // output
    out(ans);
}



特殊计数序列——Catalan数

定理 考虑由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的 $2n$ 项序列
$$
a_1, a_2, \cdots , a_{2n}
$$
其部分和总是满足
$$
a_1+a_2+\cdots + a_k \geqslant 0 \quad (\forall k = {1, 2, \cdots, 2n })
$$
这种序列的个数等于第 $n$ 个 Catalan 数
$$
C_n = \frac{1}{n+1} {2n \choose n} (n \geqslant 0)
$$
证明如下
Catlan.001.jpeg

通过以上证明了任意不可接受序列 $U(n, n)$ 与序列 $C(n+1, n-1)$ 存在对应关系
$C(n+1, n-1)$ 的个数实际上就是排列数
$$
\frac{(2n)!}{(n+1)!(n-1)!}
$$
从而
$$
U(n) = \frac{(2n)!}{(n+1)!(n-1)!}
$$
$$
A(n) = {2n \choose n} - U(n) = \frac{1}{n+1}{2n \choose n}
$$

计数类问题编程实现常用函数

阶乘分解

fac.jpg
对于 $N!$ 进行阶乘分解的结果是
$$
\sum_{p^k \leqslant N} \lfloor \frac{N}{p_k} \rfloor
$$

试除法分解质因数

void divide(int x) {
    for (int i = 2; i <= x/i; i++) {
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0) s++, x /= i;
            // i^s
            make_pair(i, s);
        }
    }
    if (x > 1) make_pair(x, 1);
    // x^1
}

朴素筛法求质数

vector<int> primes;
bool st[maxn]; // init st[...] = 0
// st = true 表示这个数是合数

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (st[i]) continue;
        primes.push_back(i);
        for (int j = 2*i; j <= n; j += i) st[j] = true;
    }
}

线性筛法求质数

primes.jpg

vector<int> primes;
bool st[maxn];

void get_primes() {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes.push_back(i);
        for (int j = 0; primes[j] <= n/i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j]) break;
        }
    }
}

Catalan 数经典应用

这里涉及到一个编程技巧,叫高精度压位
Acwing130

其实就是计算 Catalan 数
$$
\frac{1}{n+1} {2n \choose n}
$$

  • 打表 $[2, 2n]$ 所有的素数
  • 阶乘分解,$\textbf{for} \ \forall p \in \textbf{primes}[\cdots]$
    求出 $\textbf{pw}[p]= \textbf{get}(2n, p) - 2\cdot \textbf{get}(n, p)$
    即素数 $p$ 在$2n \choose n$ 这项中的幂指
  • 对 $n+1$ 进行素因子分解,$n+1 = \cdots p^s \cdots$,然后 $\textbf{pw}[p] -= s$
  • $\textbf{for} \ \forall p \in \textbf{primes}[\cdots]:$ 执行 $\textbf{pw}[p]$ 次 $\textbf{muti}(ans, p)$
const int maxn = 120000 + 10;
int n;

vector<int> primes;
bool st[maxn];

void get_primes() {
    memset(st, 0, sizeof st);
    for (int i = 2; i <= 2*n; i++) {
        if (st[i]) continue;
        primes.push_back(i);
        for (int j = 2*i; j <= 2*n; j += i) st[j] = true;
    }
}

int pw[maxn];

inline int get(int n, int p) {
    int s = 0;
    while (n) s += n/p, n /= p;
    return s;
}

void multi(vector<ll>& res, int b) {
    ll t = 0;
    for (int i = 0; i < res.size(); i++) {
        t += res[i] * b;
        res[i] = t % 100000000, t /= 100000000;
    }
    while (t) res.push_back(t % 100000000), t /= 100000000;
}

void out(const vector<ll>& res) {
    printf("%lld", res.back());
    for (int i = res.size()-2; i >= 0; i--) {
        printf("%08lld", res[i]);
    }
    printf("\n");
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> n;

    // get primes
    get_primes();

    // divide factorial
    for (auto p : primes) pw[p] = get(2*n, p) - 2 * get(n, p);

    // divide
    int x = n+1;
    for (auto p : primes) if (p <= x) {
        int s = 0;
        while (x % p == 0) s++, x /= p;
        pw[p] -= s;
    }

    // multi
    vector<ll> ans;
    ans.push_back(1);
    for (auto p : primes) {
        for (int j = 0; j < pw[p]; j++) multi(ans, p);
    }

    // output
    out(ans);
}


活动打卡代码 AcWing 129. 火车进栈

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

int tot = 20, n;
vector<int> ans;
stack<int> stk;

void dfs(int u) {
    if (tot == 0) return;
    if (ans.size() == n) {
        for (auto c : ans) printf("%d", c);
        printf("\n");
        tot--;
        return;
    }

    if (stk.size()) {
        int x = stk.top();
        stk.pop();
        ans.push_back(x);
        dfs(u);
        stk.push(x);
        ans.pop_back();
    }
    if (u <= n) {
        stk.push(u);
        dfs(u+1);
        stk.pop();
    }
}

void init() {
    ans.clear();
}

int main() {
    //freopen("input.txt", "r", stdin);
    init();
    scanf("%d", &n);
    dfs(1);
}



#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

int tot = 20, n;
vector<int> ans;
stack<int> stk;

void dfs(int u) {
    if (tot == 0) return;
    if (ans.size() == n) {
        for (auto c : ans) printf("%d", c);
        printf("\n");
        tot--;
        return;
    }

    if (stk.size()) {
        int x = stk.top();
        stk.pop();
        ans.push_back(x);
        dfs(u);
        stk.push(x);
        ans.pop_back();
    }
    if (u <= n) {
        stk.push(u);
        dfs(u+1);
        stk.pop();
    }
}

void init() {
    ans.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    scanf("%d", &n);
    dfs(1);
}


活动打卡代码 AcWing 128. 编辑器

Acwing128.001.jpeg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
int sum[maxn], f[maxn];
stack<int> A, B;

void solve() {
    char cmd[2];
    scanf("%s", cmd);

    if (cmd[0] == 'I') {
        int x; scanf("%d", &x);
        A.push(x);
        sum[A.size()] = sum[A.size()-1] + A.top();
        f[A.size()] = max(f[A.size()-1], sum[A.size()]);
    }
    if (cmd[0] == 'L') {
        if (A.size()) {
            B.push(A.top()), A.pop();
        }
    }
    if (cmd[0] == 'D') {
        if (A.size()) A.pop();
    }
    if (cmd[0] == 'R') {
        if (B.size()) {
            A.push(B.top()), B.pop();
            sum[A.size()] = sum[A.size()-1] + A.top();
            f[A.size()] = max(f[A.size()-1], sum[A.size()]);
        }
    }
    if (cmd[0] == 'Q') {
        int x; scanf("%d", &x);
        //debug(x);
        printf("%d\n", f[x]);
    }
}

void init() {
    memset(sum, 0, sizeof sum);
    memset(f, -inf, sizeof f);
    while (A.size()) A.pop();
    while (B.size()) B.pop();
}

int main() {
    freopen("input.txt", "r", stdin);
    init();
    int n;
    scanf("%d", &n);
    _for(_, 0, n) {
        solve();
    }
}



Acwing128.001.jpeg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 1000010;
const int inf = 0x3f3f3f3f;
int sum[maxn], f[maxn];
stack<int> A, B;

void solve() {
    char cmd[2];
    scanf("%s", cmd);

    if (cmd[0] == 'I') {
        int x; scanf("%d", &x);
        A.push(x);
        sum[A.size()] = sum[A.size()-1] + A.top();
        f[A.size()] = max(f[A.size()-1], sum[A.size()]);
    }
    if (cmd[0] == 'L') {
        if (A.size()) {
            B.push(A.top()), A.pop();
        }
    }
    if (cmd[0] == 'D') {
        if (A.size()) A.pop();
    }
    if (cmd[0] == 'R') {
        if (B.size()) {
            A.push(B.top()), B.pop();
            sum[A.size()] = sum[A.size()-1] + A.top();
            f[A.size()] = max(f[A.size()-1], sum[A.size()]);
        }
    }
    if (cmd[0] == 'Q') {
        int x; scanf("%d", &x);
        //debug(x);
        printf("%d\n", f[x]);
    }
}

void init() {
    memset(sum, 0, sizeof sum);
    memset(f, -inf, sizeof f);
    while (A.size()) A.pop();
    while (B.size()) B.pop();
}

int main() {
    //freopen("input.txt", "r", stdin);
    init();
    int n;
    scanf("%d", &n);
    _for(_, 0, n) {
        solve();
    }
}



class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk;
    stack<int> monostk;
    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        if (monostk.empty() || monostk.top() >= x) monostk.push(x);
    }

    void pop() {
        if (monostk.size() && monostk.top() == stk.top()) monostk.pop();
        stk.pop();
    }

    int top() {
        return stk.top();
    }

    int getMin() {
        return monostk.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */


活动打卡代码 AcWing 127. 任务

Acwing127.001.jpeg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 100000 + 10;
int n, m;
// m tasks  n machine

class A {
public:
    int x, y;
    bool operator< (const A &rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
} T[maxn], M[maxn];

void solve() {
    sort(T, T+m);
    sort(M, M+n);
    multiset<int> st;

    ll ans = 0;
    ll cnt = 0;
    for (int i = m-1, j = n-1; i >= 0; i--) {
        while (j >= 0 && M[j].x >= T[i].x) st.insert(M[j--].y);
        auto it = lower_bound(st.begin(), st.end(), T[i].y);
        if (it != st.end()) {
            cnt++;
            ans += T[i].x * 500 + T[i].y * 2;
            st.erase(it);
        }
    }
    printf("%lld %lld\n", cnt, ans);
}

void init() {
    //
}

int main() {
    //freopen("input.txt", "r", stdin);
    init();

    scanf("%d%d", &n, &m);
    _for(i, 0, n) scanf("%d%d", &M[i].x, &M[i].y);
    _for(i, 0, m) scanf("%d%d", &T[i].x, &T[i].y);

    // then solve
    solve();
}