头像

paprika




离线:21小时前


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

paprika
6个月前
#include <iostream>
using namespace std;

const int N = 100010,mod = 1e9 + 7;
typedef long long LL;

LL fact[N],infact[N];

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

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

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

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


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

paprika
6个月前
#include <iostream>
using namespace std;

const int N = 2001, MOD = 1e9 + 7;

int c[N][N];

int main()
{
    int n;
    for (int a = 0; a < N; a ++)
        for (int b = 0; b <= a; b ++)
            if (!b) c[a][b] = 1;
            else c[a][b] = (c[a - 1][b] % MOD + c[a - 1][b - 1] % MOD) % MOD;
    cin >> n;
    while (n --)
    {
        int a,b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    return 0;
}


活动打卡代码 AcWing 829. 模拟队列

paprika
6个月前
#include <iostream>
using namespace std;

int q[100010];

int main()
{
    int n;
    cin >> n;
    int tt = -1,hh = 0;
    while (n --)
    {
        string s;
        cin >> s;
        if (s == "push")
        {
            int x;
            cin >> x;
            q[++ tt] = x;
        }
        else if (s == "pop")
        {
            hh ++;
        }
        else if (s == "empty")
        {
            if (hh > tt) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
        else
        {
            cout << q[hh] << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 148. 合并果子

paprika
6个月前
#include <iostream>
#include <vector>
#include <queue>
using namespace std;


int main()
{
    priority_queue<int,vector<int>,greater<int>> heap;
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        heap.push(a);
    }
    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        heap.push(a + b);
        res += a + b;
    }
    cout << res;
    return 0;
}


活动打卡代码 LeetCode 28. 实现 strStr()

paprika
6个月前
class Solution { // 朴素KMP
public:

    int strStr(string s, string p) {
        if (p.empty()) return 0;
        if (s.empty()) return -1;
        int m = s.size(), n = p.size();
        s = ' ' + s; p = ' ' + p; // KMP中起始坐标为1

        vector<int> ne(n + 1); // next数组
        for (int i = 2, j = 0; i <= n; i ++)
        {
            while (j && p[j + 1] != p[i]) j = ne[j];
            if (p[j + 1] == p[i]) j ++;
            ne[i] = j;
        }

        for (int i = 1,j = 0; i <= m; i ++) // 匹配过程
        {
            while (j && p[j + 1] != s[i]) j = ne[j];
            if (p[j + 1] == s[i]) j ++;
            if (j == n) return i - j;
        }
        return -1;
    }
};


活动打卡代码 LeetCode 27. 移除元素

paprika
6个月前
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.size(); i ++)
        {
            if (nums[i] != val)
            {
                nums[k] = nums[i];
                k ++;
            }
        }
        return k;
    }
};



paprika
6个月前
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int cnt = 1;
        for (int i = 0, j = 0;;) // i快指针,j慢指针
        {
            while (nums[i] == nums[j]) // i找到第一个与j不同的
            {
                i ++;
                if (i == nums.size()) return cnt; // i越界则输出答案
            }
            nums[j + 1] = nums[i]; // 放到j的下一位
            j ++;
            cnt ++;           
        }
        return -1;
    }
};



paprika
6个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

 /*三大步骤
 1 判断q走k步后是否超过尾节点
 2 将p后面k个节点翻转
 3 更新p和q节点
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy = new ListNode(-1); // 新建一虚拟节点指向head
        dummy->next = head;
        for (auto q = dummy; ;)
        {
            auto p = q; // q和p都等于虚拟节点dummy,也就是每次循环的头节点的前一个节点
            for (int i = 0; i < k && q; i ++) q = q->next; // 判断走k步后是否超过尾节点过程
            if (!q) return dummy->next;

            auto a = p->next;auto b = a->next; // 指向需要翻转的两个节点

            for (int i = 0; i < k - 1; i ++) // 翻转k个节点过程
            {
                auto c = b->next;
                b->next = a;
                a = b;
                b = c;
            }
            q = p->next; // 更新p和q节点过程
            q->next = b;
            p->next = a;
        }
    }
};


活动打卡代码 AcWing 844. 走迷宫

paprika
6个月前
#include <iostream>
#include <cstring>
using namespace std;

typedef pair<int,int> PII; // 二元组存当前走到的横纵坐标
const int N = 110;

int n,m;
int p[N][N],d[N][N]; // p存迷宫图,d存每个点到{0,0}的最短路,初始化为-1
int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1}; 
PII q[N * N]; // 模拟队列


int bfs()
{
    memset(d,-1,sizeof d); // 初始化距离矩阵
    d[0][0] = 0; // 然后使{0,0}点距离为0
    int hh = 0, tt = -1; // 队头和队尾
    q[++ tt] = {0,0}; // {0,0}点入队
    while (hh <= tt) 
    {
        PII t = q[hh ++]; // 取队头
        for (int i = 0; i < 4; i ++)
        {
            int x = t.first + dx[i], y = t.second + dy[i]; // 往四个方向走
            if (x >= 0 && x < n && y >= 0 && y < m && p[x][y] == 0 && d[x][y] == -1) // 如果能走得通,则下一个点入队,点相应的最小距离加一
            {
                q[++ tt] = {x,y};
                d[x][y]  = d[t.first][t.second] + 1;
            }
        }
    }
    return d[n - 1][m - 1]; // 返回终点的最小距离
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> p[i][j];
    cout << bfs();
    return 0;
}



paprika
6个月前
#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;

int n,m;
int e[N], ne[N], h[N],idx; // 邻接表存有向图
int q[N], d[N]; //d[N]每个点的入度,q[N]为模拟队列

void add(int a,int b)
{
    e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}

bool is_topsort()
{
    int hh = 0, tt = -1; //队头队尾
    for (int i = 1; i <= n; i ++) // 入度为0则入队,说明是起始点
        if (!d[i])
            q[++ tt] = i;
    while (hh <= tt) //q[hh]、hh <= tt都可以
    {
        int t = q[hh ++];
        for (int i = h[t]; i != -1; i = ne[i]) // 取队头,并找它所有的出边
        {
            int j = e[i];
            d[j] --; // 出边的入度减一,如果出边入度为0了,则满足拓扑序列,它也入队
            if (d[j] == 0) q[++ tt] = j;
        }
    }
    return hh == n; // hh == n、tt == n - 1都可以,说明出去了n个点,每个点都出了,能够构成拓扑序列
}                                                                   //且拓扑序列之一就是依次出队的元素

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h); // 邻接表的初始化
    for (int i = 0; i < m; i ++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        d[b] ++; // 出边入度加一
    }
    if (is_topsort())
    {
        for (int i = 0 ;i < n; i ++) // 输出拓扑序列
            cout << q[i] << " ";
    }
    else cout << -1;
}