头像

发光二极管

KickStart 退役选手 :)




离线:2个月前


活动打卡代码 AcWing 888. 求组合数 IV

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 5010;
int primes[N], sum[N], cnt;
bool st[N];
int a, b;

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

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

vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i ++ )
    {
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main()
{
    cin >> a >> b;
    get_primes(a);

    for (int i = 0; i < cnt; ++i)
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(a - b, p) - get(b, p);
    }

    vector<int> res{1};
    for (int i = 0; i < cnt; ++i)
        for (int j = 0; j < sum[i]; ++j)
        {
            res = mul(res, primes[i]);
        }

    for (int i = res.size() - 1; i >= 0; --i)
    {
        cout << res[i];
    }
    cout << endl;
    return 0;
}



活动打卡代码 AcWing 887. 求组合数 III

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
int p;

LL qmi(LL a, LL b)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

LL C(LL a, LL b)
{
    if (b > a) return 0;

    LL res = 1;
    for (int i = 1, j = a; i <= b; ++ i, -- j)
    {
        res = res * j % p;
        res = res * qmi((LL)i, (LL)p - 2) % p;
    }
    return res;
}

LL lucas(LL a, LL b)
{
    if (a < p && b < p) return C(a, b);
    else return C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main()
{
    int n;
    cin >> n;
    while ( n -- )
    {
        LL a, b;
        cin >> a >> b >> p;
        cout << lucas(a, b) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 886. 求组合数 II

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;
LL fact[N], infact[N];

LL qmi(LL a, LL b, LL mod)
{
    LL res = 1;
    while (b)
    {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

int main()
{
    int n;

    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }

    cin >> n;
    while ( n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << fact[a] * infact[b] % mod * infact[a - b] % mod << endl;
    }

    return 0;
}




活动打卡代码 AcWing 885. 求组合数 I

#include <iostream>
using namespace std;

const int N = 2010, mod = 1e9 + 7;
int n, c[N][N];

void init()
{
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

int main()
{
    cin >> n;
    init();

    while ( n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 827. 双链表

#include <iostream>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int l[N], r[N], e[N], idx;

void init()
{
    r[0] = 1, l[1] = 0, idx = 2;
}

void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k], l[idx] = k;
    l[r[k]] = idx, r[k] = idx ++ ;
}

void remove(int k)
{
    r[l[k]] = r[k], l[r[k]] = l[k];
}

int main()
{
    int n, x, k;
    string op;
    cin >> n;
    init();
    while (n -- )
    {
        cin >> op;
        if (op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else if (op == "IR")
        {
            cin >> k >> x;
            add(k + 1, x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if (op == "L")
        {
            cin >> x;
            add(0, x);
        }
        else 
        {
            cin >> x;
            add(l[1], x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i])
    {
        cout << e[i] << " ";
    }
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 826. 单链表

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

const int N = 1e5 + 10;
int e[N], ne[N], head, idx;

void init()
{
    head = -1, idx = 0;
}

void add(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

void add(int x, int k)
{
    e[idx] = x, ne[idx] = ne[k - 1], ne[k - 1] = idx ++ ;
}

void remove(int k)
{
    if (k == 0)
    {
        head = ne[head];
        return ;
    }
    ne[k - 1] = ne[ne[k - 1]];
}

int main()
{
    string op;
    int k, x, n;

    init();
    cin >> n;

    while ( n -- )
    {
        cin >> op;
        if (op == "H")
        {
            cin >> x;
            add(x);
        }
        else if (op == "I")
        {
            cin >> k >> x;
            add(x, k);
        }
        else
        {
            cin >> k;
            remove(k);
        }
    }

    for (int i = head; ~i; i = ne[i])
    {
        cout << e[i] << " ";
    }
    cout << endl;
    return 0;
}



活动打卡代码 AcWing 125. 耍杂技的牛

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

#define w first
#define s second
typedef pair<int, int> PII;
const int N = 1e5 + 10;

PII cows[N];

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> cows[i].w >> cows[i].s;
    }

    sort(cows, cows + n, [](PII &a, PII &b) {
        return a.w + a.s < b.w + b.s;
    });

    int sum = 0, res = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        res = max(res, sum - cows[i].s);
        sum += cows[i].w;
    }

    cout << res << endl;
    return 0;
}



活动打卡代码 AcWing 1100. 抓住那头牛

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int dst[2 * N], n, k;
int q[2 * N];

int bfs()
{
    memset(dst, -1, sizeof dst);
    int hh = 0, tt = 0;
    q[0] = n;
    dst[n] = 0;

    while (hh <= tt)
    {
        int t = q[ hh ++ ];

        if (t == k) return dst[t];

        if (t + 1 < N && dst[t + 1] == -1)
        {
            q[ ++ tt] = t + 1;
            dst[t + 1] = dst[t] + 1;
        }

        if (t - 1 >= 0 && dst[t - 1] == -1)
        {
            q[ ++ tt] = t - 1;
            dst[t - 1] = dst[t] + 1;
        }

        if (2 * t < N && dst[2 * t] == -1)
        {
            q[ ++ tt] = 2 * t;
            dst[2 * t] = dst[t] + 1;
        }
    }
    return -1;
}

int main()
{
    cin >> n >> k;
    cout << bfs() << endl;
    return 0;
}



活动打卡代码 AcWing 188. 武士风度的牛

#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 155;
char g[N][N];
int n, m;
PII q[N * N];
int dst[N][N];

int bfs()
{
    int sx, sy;
    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (g[i][j] == 'K') 
                sx = i, sy = j;

    memset(dst, -1, sizeof dst);
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    dst[sx][sy] = 0;

    while (hh <= tt)
    {
        PII t = q[ hh ++ ];
        for (int i = 0; i < 8; ++i)
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (g[x][y] == '*') continue;
            if (dst[x][y] != -1) continue;
            if (g[x][y] == 'H') return dst[t.x][t.y] + 1;
            q[ ++ tt] = {x, y};
            dst[x][y] = dst[t.x][t.y] + 1;
        }
    }
    return -1;
}

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; ++i)
        cin >> g[i];

    cout << bfs() << endl;
    return 0;
}


活动打卡代码 AcWing 1076. 迷宫问题

#include <iostream>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010;
int g[N][N], n;
PII q[N * N];
bool st[N][N];
PII pre[N][N];

void bfs()
{
    st[n - 1][n - 1] = true;
    q[0] = {n - 1, n - 1};
    int hh = 0, tt = 0;
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (hh <= tt)
    {
        PII t = q[hh ++ ];
        for (int i = 0; i < 4; ++i)
        {
            int x = t.x + dirs[i][0], y = t.y + dirs[i][1];
            if (x < 0 || x >= n || y < 0 || y >= n || st[x][y]) continue;
            if (g[x][y] == 1) continue;
            pre[x][y] = t;
            st[x][y] = true;
            q[ ++ tt] = {x, y};
        }
    }

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> g[i][j];

    bfs();

    PII start(0, 0);
    while (true)
    {
        cout << start.x << " " << start.y << endl;
        if (start.x == n - 1 && start.y == n - 1) break;
        start = pre[start.x][start.y];
    }
    return 0;
}