头像

sdsxdxl




离线:1天前


最近来访(5)
用户头像
Andrew1729
用户头像
Botton
用户头像
wangyinuo23
用户头像
wyatt
用户头像
Angels_of_Death

活动打卡代码 AcWing 875. 快速幂

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个月前

思路是,把price合并到special里,完全背包统一处理。第二位是把6维数组压缩成一维,但是不知道为啥错了。

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]

正确输出:91
我的输出:71




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


活动打卡代码 AcWing 836. 合并集合

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




活动打卡代码 AcWing 1497. 树的遍历

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:
    int add(int num1, int num2){
        if(num1 == 0)   return num2;
        else if(num2 == 0)  return num1;
        return add(num1 ^ num2, (num1 & num2) << 1);
    }
};


活动打卡代码 LeetCode 191. 位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;
        */
    }
};


活动打卡代码 LeetCode 92. 反转链表 II

sdsxdxl
3个月前
/**
 * Definition for singly-linked list.
 * 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) {
        if(!head || left == right)  return head;
        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;
    }
};