头像

Dr666




离线:1天前


最近来访(69)
用户头像
看到这句话请立刻去搬砖
用户头像
yhz0416
用户头像
X-梧桐
用户头像
2001f
用户头像
星和彦
用户头像
gAg
用户头像
ycq
用户头像
JcWing
用户头像
Sxxxw
用户头像
Eliuak
用户头像
max2021
用户头像
YJHigher
用户头像
testaz
用户头像
一只野生の彩色铅笔
用户头像
Unknown_Error
用户头像
徐菜菜
用户头像
饮水思源
用户头像
理塘的无人机终于回到我手里
用户头像
lumoumou
用户头像
骏马.


Dr666
6天前

1.jpg
2.jpg



活动打卡代码 AcWing 839. 模拟堆

Dr666
24天前
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main()
{
    int n, m = 0;
    scanf("%d", &n);
    while (n -- )
    {
        char op[5];
        int k, x;
        scanf("%s", op);
        if (!strcmp(op, "I"))
        {
            scanf("%d", &x);
            cnt ++ ;
            m ++ ;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if (!strcmp(op, "DM"))
        {
            heap_swap(1, cnt);
            cnt -- ;
            down(1);
        }
        else if (!strcmp(op, "D"))
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt -- ;
            up(k);
            down(k);
        }
        else
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }

    return 0;
}


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

Dr666
25天前
#include<iostream>
using namespace std;
typedef long long ll;
int n,p;
int qui(int a,int b)
{
    long long ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        b >>= 1;
        a = (ll)a * a % p;
    }
    return ans;
}
int C(int a,int b)
{
    if(b > a) return 0;

    ll res = 1;
    for(int i = 1,j = a;i <= b;i++,j--)
    {
        res = (ll) res * j % p;
        res = (ll) res * qui(i,p - 2) % p;
    }
    return res;
}
int lucas(ll a,ll b)
{
    if(a < p && b < p) return C(a,b);
    else return (ll) C(a % p,b % p) * lucas(a / p,b / p) % p;
}
int main()
{
    cin >> n;
    while(n--)
    {
        ll a,b;
        cin >> a >> b >> p;

        cout << lucas(a,b) << endl;
    }
    return 0;
}


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

Dr666
25天前
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10,mod = 1e9 + 7;
int n;
int fact[maxn],infact[maxn];
int qui(int a,int b)
{
    long long ans = 1;

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

    return ans;
}
int main()
{
    cin >> n;

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

    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        printf("%d\n",(LL)fact[a] * infact[b] %mod * infact[a - b] % mod);
    }
    return 0;
}


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

Dr666
26天前
#include<iostream>
using namespace std;
const int maxn = 2010,mod = 1e9 + 7;
int n;
int C[maxn][maxn];
int main()
{
    cin >> n;

    for(int i = 0;i <= maxn;i++) C[i][0] = 1;

    for(int i = 1;i < maxn;i++)
    {
        for(int j = 0;j <= i;j++)
        {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }

    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        printf("%d\n",C[a][b]);
    }
    return 0;
}



Dr666
27天前
class Solution {
public:
    int y1 = 0,y2 = 0,m1 = 0,m2 = 0,d1 = 0,d2 = 0;
    bool leap1 = false,leap2 = false;
    int days[15] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

    bool isleap(int year)
    {
        if(year % 4 == 0 && year % 100 != 0) return true;
        else if(year % 400 == 0) return true;
        else return false;
    }

    int daysBetweenDates(string date1, string date2) {
        for(int i = 1;i <= 12;i++) days[i] += days[i - 1];

        for(int i = 0;i < 4;i++)
        {
            y1 = y1 * 10 + (date1[i] - '0');
            y2 = y2 * 10 + (date2[i] - '0');
        }

        for(int i = 5;i < 7;i++)
        {
            m1 = m1 * 10 + (date1[i] - '0');
            m2 = m2 * 10 + (date2[i] - '0');
        }

        for(int i = 8;i < 10;i++)
        {
            d1 = d1 * 10 + (date1[i] - '0');
            d2 = d2 * 10 + (date2[i] - '0');
        }

        int leap_year1 = (y1 - 1) / 4,leap_year2 = (y2 - 1) / 4;  
        leap1 = isleap(y1),leap2 = isleap(y2); 

        int  day1 = leap_year1 * 366 + (y1 - leap_year1) * 365 + days[m1 - 1] + d1;
        int day2 = leap_year2 * 366 + (y2 - leap_year2) * 365 + days[m2 - 1] + d2;

        if(m1 > 2 && leap1) day1++;
        if(m2 > 2 && leap2) day2++;

        return abs(day1 - day2);
    }
};



Dr666
28天前
class Solution {
public:
    int mod = 1e9 + 7;
    long long cnt(long long x)
    {
        if(x == 4) return 6;
        else return (x * (x - 1) / 2 % mod * cnt(x - 2) % mod); 
    }
    int countOrders(int n) {
        if(n == 1) return n;
        long long ans = cnt(2 * n);
        return ans;
    }
};



Dr666
29天前
class Solution {
public:
    bool success = false;
    bool checkIfExist(vector<int>& a) {
        int n = a.size();
        for(int i = 0;i < n;i++)
        {
            if(success) break;
            for(int j = 0;j < n;j++)
            {
                if(a[j] == a[i] * 2)
                {
                    if(i != j) success = true;
                }
            }
        }

        return  success;

    }
};


活动打卡代码 LeetCode 1345. 跳跃游戏 IV

Dr666
29天前
class Solution {
public:
    int minJumps(vector<int>& arr) {
        queue<int> q;
        const int maxn = arr.size();
        int dist[maxn];
        memset(dist,0,sizeof dist);
        dist[0] = 1;
        q.push(0);

        unordered_map<int,vector<int>> mp;
        for(int i = 0;i < maxn;i++)
           mp[arr[i]].push_back(i);

        while(q.size())
        {
            auto t = q.front();
            q.pop();

            if(t - 1 >= 0 && !dist[t - 1])
            {
                dist[t - 1] = dist[t] + 1;
                q.push(t - 1);
            }

            if(t + 1 < arr.size() && !dist[t + 1])
            {
                dist[t + 1] = dist[t] + 1;
                q.push(t + 1);
            }

            int val = arr[t];
            if(mp.count(val))
            {
                for(auto i : mp[val])
                {
                    if(!dist[i])
                    {
                       dist[i] = dist[t] + 1;
                       q.push(i);
                    }
                }
                mp.erase(val);
            }

            if(dist[maxn - 1]) break;
        }

        return (dist[maxn - 1] - 1);
    }
};



Dr666
1个月前

求佬们帮忙看下,两次的测试用例是一样的,为什么结果不对呢?

question.jpg

这道题是
跳跃游戏

我的源代码

class Solution {
public:
int minJumps(vector[HTML_REMOVED]& arr) {
queue[HTML_REMOVED] q;
const int maxn = 5e4 + 10;
int dist[maxn];
dist[0] = 1;
q.push(0);

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        if(dist[arr.size() - 1]) break;

        if(t - 1 >= 0 && !dist[t - 1])
        {
            dist[t - 1] = dist[t] + 1;
            q.push(t - 1);
        }

        if(t + 1 < arr.size() && !dist[t + 1])
        {
            dist[t + 1] = dist[t] + 1;
            q.push(t + 1);
        }

        for(int i = t;i < arr.size();i++)
        {
            if(arr[i] == arr[t] && !dist[i])
            {
                dist[i] = dist[t] + 1;
                q.push(i);
            }
        }
    }

    return (dist[arr.size() - 1] - 1);
}

};