头像

tea321000

SZU




离线:9小时前


最近来访(3)
用户头像
D.devil
用户头像
无名氏DU
用户头像
明灯


tea321000
10天前
#include <iostream>

using namespace std;

const int N = 1e5 + 1;

int p[N], cnt[N];


int find(int x){
    if(p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n , m;
    scanf("%d %d", &n, &m);
    for (int i = 1 ; i <= n ; i ++){
        p[i] = i;
        cnt[i] = 1;
    }

    while(m --){
        string op;
        int a,b;
        cin >> op;
        if(op == "C"){
            scanf("%d %d", &a, &b);
            a = find(a), b = find(b);

            if (a != b){
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if(op == "Q1"){
            scanf("%d %d", &a, &b);
            if (find(a) == find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else{
            scanf("%d", &a);
            printf("%d\n", cnt[find(a)]);
        }
    }
}


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

tea321000
10天前
#include <iostream>

using namespace std;


const int N = 1e5 + 10;

int p[N];

int find(int x){
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}
int main(){
    int n, m;
    for (int i = 0; i < N ; i ++)
        p[i] = i;
    scanf("%d %d", &n, &m);
    while(m --){
        char op[2];
        int a, b;
        scanf("%s %d %d", op, &a, &b);
        if (*op == 'M')
            p[find(a)] = find(b);
        else{
            if (find(a) == find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
}


活动打卡代码 AcWing 840. 模拟散列表

tea321000
12天前
#include <iostream>
#include <string.h>
using namespace std;

const int N = 1e6;
int a[N];


// 开放寻址法
int find(int x){
    int index = (x % N + N) % N;
    while (a[index] != x && a[index] != NULL){
        index ++;
        if (index > N)
            index = 0;
    }
    //a[index] = x;
    //printf("index = %d, key = %d\n", index , a[index]);
    return index;
}

int main(){
    int n;
    scanf("%d", &n);
    while (n --){
        char s;
        int x;
        cin >> s >> x;
        if (s == 'I')
            a[find(x)] = x;
        else if (s == 'Q')
            printf("%s", a[find(x)] == x ? "Yes":"No"), printf("\n");
    }
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

tea321000
15天前
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++)
        scanf("%d", a + i);
    for (int i = 0; i < m; i ++)
        scanf("%d", b + i);
    bool flag = true;
    for (int i = 0, j = 0; i < n; i ++){
        while (a[i] != b[j] && j < m)
            j ++;
        if(a[i] != b[j]){
            flag = false;
            break;
        }
        j ++;
    }
    if(flag)
        printf("Yes\n");
    else
        printf("No\n");
}



tea321000
20天前
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int res=1;
        for(int i=1, up=1,down=1;i<arr.size();i++)
        {
            if(arr[i]>arr[i-1])
            {
                up = down +1;
                down=1;
            }
            else if(arr[i]<arr[i-1])
            {
                down=up+1;
                up=1;
            }
            else{
                down=up =1;
            }
            res = max(res, max(up, down));
        }
        return res;
    }
};



tea321000
20天前
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n+1);
        for(int i=1; i<=n;i++)
        {
            s[i] = s[i-1]+nums[i-1];
        }
        unordered_map<int, int> cnt;
        cnt[0]++;
        int res =0;
        for(int i=1;i<=n;i++)
        {
            int r =(s[i]%k+k)%k;
            res+= cnt[r];
            cnt[r]++;
        }
        return res;
    }
};



tea321000
20天前
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n+1);
        for(int i=1; i<=n;i++)
        {
            s[i] = s[i-1]+nums[i-1];
        }
        unordered_map<int, int> cnt;
        cnt[0]++;
        int res =0;
        for(int i=1;i<=n;i++)
        {
            int r =(s[i]%k+k)%k;
            res+= cnt[r];
            cnt[r]++;
        }
        return res;
    }
};



tea321000
20天前
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> ans;
    bool dfs(TreeNode* root, vector<int>& voyage, int &k)
    {
        if(!root)   return true;
        if(root->val != voyage[k])  return false;
        k++;
        if(root->left && root->left->val != voyage[k])
        {
            ans.push_back(root->val);
            return dfs(root->right, voyage, k) && dfs(root->left, voyage, k);
        }
        else
        {
            return dfs(root->left, voyage, k) && dfs(root->right, voyage, k);
        }
    }

    vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
        int k = 0;
        if (dfs(root, voyage, k)) return ans;
        return {-1};
    }
};


活动打卡代码 AcWing 3761. 唯一最小数

tea321000
20天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;


int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i ++ )
    {
        map<int, int> mp, idx_mp;
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            int tmp;
            scanf("%d", &tmp);
            mp[tmp]++;
            idx_mp[tmp] = i + 1;
        }
        bool flag=false;
        for(auto it: mp)
        {
            // cout <<"first" << it.first  << "second" << it.second << endl;
            if(it.second == 1)
            {
                cout << idx_mp[it.first] << endl;
                flag = true;
                break;
            }
        }
        if(!flag)
            cout << -1 << endl;
    }


}



tea321000
30天前
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for(auto x:nums)    cnt[x]++;
        int n=nums.size();
        vector<int> s(n+1);
        for(auto [x,c]:cnt)
        {
            s[c]++;
        }
        int i=n, t=0;
        while(t<k)  t+=s[i--];
        vector<int> res;
        for(auto [x,c]:cnt)
            if(c>i)
                res.push_back(x);
        return res;

    }
};