头像

天郁闷




离线:13小时前


最近来访(271)
用户头像
ISaac_7
用户头像
Weather
用户头像
yxc
用户头像
sz_jinzikai
用户头像
InstellarMa
用户头像
_wyp_
用户头像
acwing_4300
用户头像
pluto-
用户头像
大草包
用户头像
MyloXyloto
用户头像
旧手机换菜刀了啊
用户头像
童心
用户头像
夜一喵QAQ
用户头像
谁把可乐的名字拿走了
用户头像
人间小甜瓜
用户头像
库尔勒香梨
用户头像
牧濑红莉栖
用户头像
海天色
用户头像
村山良树
用户头像
爱吃干煸鱼的大布丁

活动打卡代码 AcWing 891. Nim游戏

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e5 + 10;

int n;

int main()
{
    cin >> n;

    int res = 0;
    while(n --)
    {
        int x;
        cin >> x;
        res ^= x;
    }

    if(res) puts("Yes");
    else puts("No");


    return 0;
}


活动打卡代码 AcWing 890. 能被整除的数

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 20;

int n, m;
int p[N];

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

    for(int i = 0; i < m; i ++) cin >> p[i];

    int res = 0;
    for(int i = 1; i < 1 << m; i ++)
    {
        int s = 0;
        int t = 1;
        for(int j = 0; j < m; j ++)
        {
            if(i >> j & 1)
            {
                if((LL)t * p[j] > n)
                {
                    t = -1;
                    break;
                }
                t = t * p[j];
                s ++;
            }

        }

            if(t == -1) continue;

            if(s & 1) res += n / t;
            else res -= n / t;
    }

    cout << res << endl;



    return 0;
}


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

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 22;

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

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

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

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

    while(t --)
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }



    return 0;
}



#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL; 

const int N = 1e5, P = 1e9 + 7;

int n;

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

int main()
{
    cin >> n;

    int a = 2 * n, b = n;

    int  res = 1;
    for(int i = a; i >= a - b + 1; i --) res = res * (LL)i % P;
    for(int i = b; i >= 1; i --) res = res * (LL)qmi(i, P - 2, P) % P;

    res = (LL)res * qmi(n + 1, P - 2, P) % P;

    cout << res << endl;

    return 0;
}




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

#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

const int N = 5010;

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

void get_primes(int x)
{
    for(int i = 2; i <= x; i ++)
    {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= x / i; j ++)
        {
            st[i * primes[j]] = 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;

    for(int i = 0, t = 0; i < a.size() || t; i ++)
    {
        if(i < a.size()) t += a[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    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(b, p) - get(a - b, p);
    }

    vector<int> res;
    res.push_back(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];
    puts("");



    return 0;
}


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

#include<iostream>
#include<cstring>

using namespace std;

const int N = 2010, P = 1e9 + 7;

int n;
int 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 - 1] + c[i - 1][j]) % P;
        }
    }
}

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

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


    return 0;
}


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

#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, P = 1e9 + 7;

int n;
int fact[N], infact[N];

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

int main()
{
    cin >> n;

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

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

    return 0;
}


活动打卡代码 AcWing 907. 区间覆盖

天郁闷
11天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range& W) const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    cin >> st >> ed;
    cin >> n;

    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    } 

    sort(range, range + n);

    bool is_flag = false;
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        int j = i, r = -2e9;
        while(j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++;
        }
        if(r < st)
        {
            res = -1;
            break;
        }
        res ++;
        if(r >= ed)
        {
            is_flag = true;
            break;
        }
        st = r;
        i = j - 1;
    }

    if(!is_flag) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}





活动打卡代码 AcWing 906. 区间分组

天郁闷
11天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 1e5 + 10;

int n;
struct Edge
{
    int l, r;
    bool operator< (const Edge& W)const
    {
        return l < W.l;
    }
}edge[N];

int main()
{
    cin >> n;

    for(int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        edge[i] = {l, r};
    }

    sort(edge, edge + n);

    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i = 0; i < n; i ++)
    {
        auto r = edge[i];
        if(heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else
        {
            heap.pop();
            heap.push(r.r);
        }
    }

    cout << heap.size() << endl;

    return 0;
}


活动打卡代码 AcWing 1275. 最大数

天郁闷
11天前

线段树的基本应用

#include<iostream>
#include<cstring>

using namespace std;

const int N = 2e5 + 10;

int m, p;
struct Tree
{
    int l, r;
    int v;
}t[N * 4];

void build(int u, int l, int r)
{
    t[u].l = l, t[u].r = r;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void push_up(int u)
{
    t[u].v = max(t[u << 1].v, t[u << 1 | 1].v);
}

int query(int u, int l, int r)
{
      if(t[u].l >= l && t[u].r <= r) return t[u].v;
      int v = 0;
      int mid = t[u].l + t[u].r >> 1;
      if(l <= mid) v = query(u << 1, l , r);
      if(r > mid) v = max(query(u << 1 | 1, l , r), v);
      return v;
}

void modify(int u, int k, int x)
{
    if(t[u].l == k && t[u].r == k) 
    {
        t[u].v = x;
        return ;
    }
    int mid = t[u].l + t[u].r >> 1;
    if(k <= mid) modify(u << 1, k ,x);
    if(k > mid) modify(u << 1 | 1, k, x);
    push_up(u);
}


int main()
{
    cin >> m >> p;
    build(1, 1, m);
    int n = 0;

    string op;
    int x, last = 0;
    while(m --)
    {
        cin >> op >> x;
        if(op == "Q")
        {
            last = query(1, n - x + 1, n);
            cout << last  << endl;
        }
        else
        {
            modify(1, n + 1, ((long long)x + last) % p);
            n ++;
        }

    }



    return 0;
}