sdsxdxl

7029

Andrew1729
Botton
wangyinuo23
wyatt
Angels_of_Death

sdsxdxl
1天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, a, k, p;
int qmi(int a, int k, int p) {
int ans = 1;
while(k) {
if(k & 1)   ans = (LL)ans * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return ans;
}
int main()
{
scanf("%d", &n);
while(n--) {
scanf("%d%d%d", &a, &k, &p);
printf("%d\n", qmi(a, k, p));
}
return 0;
}


sdsxdxl
1个月前

const int N = 1e6 + 50;
class Solution {
public:
int f[N];
int get_idx(vector<int>& v, bool flag) {
int idx = 0, t = 1;
int n = v.size();
if(flag)    n--;
for(int i = 0; i < n; i++) {
idx += v[i] * t;
t *= 10;
}
return idx;
}
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
int n = price.size();
for(int i = 0; i < n; i++) {
vector<int> tmp(n + 1);
tmp[i] = 1;
tmp[n] = price[i];
special.push_back(tmp);
}
int m = special.size();
memset(f, 0x3f, sizeof f);
f[0] = 0;
int end_idx = get_idx(needs, false);
for(int i = 0; i < m; i++) {
int start = get_idx(special[i], true);
for(int j = start; j <= end_idx; j++) {
f[j] = min(f[j], f[j - start] + special[i].back());
}
}
return f[end_idx];
}
};


[4,10,1,5,5,3]
[[1,2,3,3,4,1,8],[3,4,5,5,5,2,14],[2,4,5,1,1,3,22]]
[1,6,5,1,1,4]

sdsxdxl
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N];
void init() {
for(int i = 0; i < N; i++)  p[i] = i, cnt[i] = 1;
}
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if(x == y)  return;
p[x] = y;
cnt[y] += cnt[x];
}
bool check(int x, int y)
{
return find(x) == find(y);
}
int main()
{
init();
int n, m;
cin >> n >> m;
string op;
int a, b;
while(m--)
{
cin >> op;
if(op == "C")
{
cin >> a >> b;
merge(a, b);
}
else if(op == "Q1")
{
cin >> a >> b;
if(check(a, b))     puts("Yes");
else    puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}

return 0;
}


sdsxdxl
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N];
void init() {
for(int i = 0; i < N; i++)  p[i] = i;
}
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if(x == y)  return;
p[x] = y;
}
bool check(int x, int y)
{
return find(x) == find(y);
}
int main()
{
init();
int n, m;
cin >> n >> m;
string op;
int a, b;
while(m--)
{
cin >> op >> a >> b;
if(op == "M")   merge(a, b);
else
{
if(check(a, b))     puts("Yes");
else    puts("No");
}
}
return 0;
}


sdsxdxl
2个月前
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<stack>
#include<unordered_map>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
typedef long long LL;
int main()
{
int n, r, y, g;
scanf("%d%d%d%d", &r, &y, &g, &n);
int k, t;
LL sum = 0;
for(int i = 0; i < n; i++)
{
scanf("%d%d", &k, &t);
if(k == 0)  sum += t;
else
{
LL tmp = sum - t;
if(tmp > 0)
{
LL cur = tmp % (LL)(r + y + g);
if(k == 1)      //red
{
if(cur >= g)     sum += (g + y + r - sum);
}
else if(k == 2)     //yellow
{
if(cur < r)    sum += r - cur;
else if(cur < r + g)   sum += 0;
else    sum += (r + g + y - cur + r);
}
else    //green
{
if(cur < r + y)    sum += (r + y - cur);
}
}
else
{
if(k == 1)  sum -= tmp;
else if(k == 2)     sum += (-tmp + r);
}
}
}
printf("%lld", sum);
return 0;
}



sdsxdxl
3个月前

### 写法一

#include<bits/stdc++.h>
using namespace std;
const int N = 32;
int postorder[N], inorder[N];

struct node{
node(int v){
val = v;
left = right = nullptr;
}
int val;
node* left;
node* right;
};

node* dfs(int l1, int r1, int l2, int r2)
{
if(l1 > r1 || l2 > r2)     return nullptr;
node* root = new node(postorder[r1]);
int spilt = -1;
for(int i = l2; i <= r2; i++)
{
if(inorder[i] == postorder[r1])
{
spilt = i;
break;
}
}
int cnt = spilt - l2;
root -> left = dfs(l1, l1 + cnt - 1, l2, spilt - 1);
root -> right = dfs(l1 + cnt, r1 - 1, spilt + 1, r2);
return root;
}

int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)  cin >> postorder[i];
for(int i = 0; i < n; i++)  cin >> inorder[i];
node* root = dfs(0, n - 1, 0, n - 1);
queue<node*> q;
q.push(root);
while(q.size())
{
node* t = q.front();
q.pop();
cout << t -> val << ' ';
if(t -> left)   q.push(t -> left);
if(t -> right)  q.push(t -> right);
}
return 0;
}


### 写法二

#include<bits/stdc++.h>
using namespace std;
const int N = 32;
int postorder[N], inorder[N];
int l[N], r[N];

int dfs(int l1, int r1, int l2, int r2)
{
if(l1 > r1 || l2 > r2)     return -1;
int root = postorder[r1], split = -1;
for(int i = l2; i <= r2; i++)
{
if(inorder[i] == root)
{
split = i;
break;
}
}
int cnt = split - l2;
l[root] = dfs(l1, l1 + cnt - 1, l2, split - 1);
r[root] = dfs(l1 + cnt, r1 - 1, split + 1, r2);
return root;
}

int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i++)  cin >> postorder[i];
for(int i = 0; i < n; i++)  cin >> inorder[i];
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
int root = dfs(0, n - 1, 0, n - 1);
queue<int> q;
q.push(root);
while(q.size())
{
int t = q.front();
cout << t << ' ';
q.pop();
if(l[t] != -1)    q.push(l[t]);
if(r[t] != -1)    q.push(r[t]);
}
return 0;
}


sdsxdxl
3个月前
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
*   public:
*     // Return true if this NestedInteger holds a single integer, rather than a nested list.
*     bool isInteger() const;
*
*     // Return the single integer that this NestedInteger holds, if it holds a single integer
*     // The result is undefined if this NestedInteger holds a nested list
*     int getInteger() const;
*
*     // Return the nested list that this NestedInteger holds, if it holds a nested list
*     // The result is undefined if this NestedInteger holds a single integer
*     const vector<NestedInteger> &getList() const;
* };
*/

class NestedIterator {
public:
vector<int> nums;
int idx = 0;
public:
void dfs(vector<NestedInteger> &nestedList) {
for(NestedInteger& i : nestedList)
{
if(i.isInteger())    nums.push_back(i.getInteger());
else    dfs(i.getList());
}
}
NestedIterator(vector<NestedInteger> &nestedList) {
dfs(nestedList);
}

int next() {
return nums[idx++];
}

bool hasNext() {
return idx < nums.size();
}
};

/**
* Your NestedIterator object will be instantiated and called as such:
* NestedIterator i(nestedList);
* while (i.hasNext()) cout << i.next();
*/


sdsxdxl
3个月前
class Solution {
public:
if(num1 == 0)   return num2;
else if(num2 == 0)  return num1;
return add(num1 ^ num2, (num1 & num2) << 1);
}
};


sdsxdxl
3个月前
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while(n)
{
n -= n & (-n);
ans++;
}
return ans;
/*
ans = __builtin_popcount(n);
return ans;
*/
/*
for(int i = 0; i < 32; i++)
{
if(n >> i & 1)  ans++;
}
return ans;
*/
}
};


sdsxdxl
3个月前
/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* h = new ListNode(-999, head);
ListNode* cur = h, *pre = nullptr;
ListNode* first = nullptr, *last = nullptr;
ListNode* first_pre = nullptr;
int k = 0;
while(cur && k <= right)
{
if(k == left - 1)   first_pre = cur;
if(k == left)       first = cur;
if(k == right)      last = cur;
if(k > left)
{
ListNode* t = cur -> next;
cur -> next = pre;
pre = cur;
cur = t;
}
else
{
pre = cur;
cur = cur -> next;
}
k++;
}
first_pre -> next = last;
first -> next = cur;
return h -> next;
}
};