tea321000

SZU

1766

D.devil

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

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

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

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

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;

}
};