paprika

4604

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;
}


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;
}


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;
}


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;
}


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;
}
};


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个月前
/**
* 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
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;
}
}
};


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]为模拟队列

{
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;