310

violet_garden

RSqwq

19小时前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], size[N];
string act;

void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}

int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}

void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}

return find(a)==find(b);
}

int main() {
init();
while(m--) {
cin>>act;
if(act=="C") {
} else if(act=="Q1") {
} else {
printf("%d\n",size[find(a)]);
}
}
return 0;
}


1天前
#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}

int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
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))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}


2天前
#include <iostream>
#include <cstdio>
using namespace std;
int n, k, ans = 0;
int fa[150010]; //注意数组开 3 倍。
int find (int x) {
if(fa[x] != x) return fa[x] = find(fa[x]);
return fa[x];
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= 3 * n; i ++ )
fa[i] = i; //基本初始化。
while (k -- ) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if(x > n || y > n) { ans ++; continue; }
if(op == 1) {
if(find(x) == find(y + n)) {
ans ++;
continue;
}
if(find(x) == find(y + 2 * n)) {
ans ++;
continue;
}
fa[find(y)] = find(x);
fa[find(y + n)] = find(x + n);
fa[find(y + 2 * n)] = find(x + 2 * n);
}
if(op == 2) {
if(x == y) { ans ++; continue; }
if(find(x) == find(y)) { ans ++; continue; }
if(find(x) == find(y + 2 * n)) {
ans ++;
continue;
}
fa[find(x)] = find(y + n);
fa[find(y)] = find(x + 2 * n);
fa[find(x + n)] = find(y + 2 * n);
}

}
printf("%d", ans);
return 0;
}


2天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,m,a,b,fa[N], size[N];
string act;

void init() {
for (int i=1; i<=n; i++) {
fa[i] = i;
size[i] = 1;
}
}

int find(int x) {
if(fa[x]==x) return x;
else return fa[x] = find(fa[x]);
}

void merge(int a,int b) {
int x = find(a);
int y = find(b);
fa[x] = y;
size[y] += size[x];
}

return find(a)==find(b);
}

int main() {
init();
while(m--) {
cin>>act;
if(act=="C") {
} else if(act=="Q1") {
} else {
printf("%d\n",size[find(a)]);
}
}
return 0;
}


2天前
#include<iostream>

using namespace std;

const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
/*
经上述可以发现,每个集合中只有祖宗节点的p[x]值等于他自己,即:
p[x]=x;
*/
return p[x];
//找到了便返回祖宗节点的值
}

int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) p[i]=i;
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))
//如果祖宗节点一样,就输出yes
printf("Yes\n");
else
printf("No\n");
}
return 0;
}



2天前
#include<iostream>
#include<algorithm>
using namespace std;
int const N=100010,M=31*N;

int n;
int a[N];
int son[M][2],idx;
//M代表一个数字串二进制可以到多长

void insert(int x)
{
int p=0;  //根节点
for(int i=30;i>=0;i--)
{
int u=x>>i&1;   /////取X的第i位的二进制数是什么  x>>k&1(前面的模板)
if(!son[p][u]) son[p][u]=++idx; ///如果插入中发现没有该子节点,开出这条路
p=son[p][u]; //指针指向下一层
}
}
int search(int x)
{
int p=0;int res=0;
for(int i=30;i>=0;i--)
{                               ///从最大位开始找
int u=x>>i&1;
if(son[p][!u]) ////如果当前层有对应的不相同的数
{   ///p指针就指到不同数的地址

p=son[p][!u];
res=res*2+1;
///*2相当左移一位  然后如果找到对应位上不同的数res+1 例如    001
}                                                       ///       010
else                                            ////          --->011                                                                           //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
{
p=son[p][u];
res=res*2+0;
}
}
return res;
}
int main(void)
{
cin.tie(0);
cin>>n;
idx=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]);
}
int res=0;
for(int i=0;i<n;i++)
{
res=max(res,search(a[i]));  ///search(a[i])查找的是a[i]值的最大与或值
}
cout<<res<<endl;
}


6天前
#include<bits/stdc++.h>
using namespace std;
int n;
char c;
string s;
map<string,int>m;
int main(){
cin>>n;
while(n--){
cin>>c>>s;
if(c=='I')
m[s]++;
if(c=='Q')
cout<<m[s]<<endl;
}
}


7天前
#include <iostream>

using namespace std;

const int N = 1000010;
char p[N], s[N]; // 用 p 来匹配 s
// “next” 数组，若第 i 位存储值为 k
// 说明 p[0...i] 内最长相等前后缀的前缀的最后一位下标为 k
// 即 p[0...k] == p[i-k...i]
int ne[N];
int n, m; // n 是模板串长度 m 是模式串长度

int main()
{
cin >> n >> p >> m >> s;

// p[0...0] 的区间内一定没有相等前后缀
ne[0] = -1;

// 构造模板串的 next 数组
for (int i = 1, j = -1; i < n; i ++)
{
while (j != -1 && p[i] != p[j + 1])
{
// 若前后缀匹配不成功
// 反复令 j 回退，直至到 -1 或是 s[i] == s[j + 1]
j = ne[j];
}
if (p[i] == p[j + 1])
{
j ++; // 匹配成功时，最长相等前后缀变长，最长相等前后缀最后一位变大
}
ne[i] = j; // 令 ne[i] = j，以方便计算 next[i + 1]
}

// kmp start !
for (int i = 0, j = -1; i < m; i ++)
{
while (j != -1 && s[i] != p[j + 1])
{
j = ne[j];
}
if (s[i] == p[j + 1])
{
j ++; // 匹配成功时，模板串指向下一位
}
if (j == n - 1) // 模板串匹配完成，第一个匹配字符下标为 0，故到 n - 1
{
// 匹配成功时，文本串结束位置减去模式串长度即为起始位置
cout << i - j << ' ';

// 模板串在模式串中出现的位置可能是重叠的
// 需要让 j 回退到一定位置，再让 i 加 1 继续进行比较
// 回退到 ne[j] 可以保证 j 最大，即已经成功匹配的部分最长
j = ne[j];
}
}

return 0;
}


8天前
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++ i)
{
scanf("%d", &a[i]);
if (i - k + 1 > q[hh]) ++ hh;                  // 若队首出窗口，hh加1
while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
q[++ tt] = i;                                  // 下标加到队尾
if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
}
cout << endl;
hh = 0; tt = -1;                                   // 重置！
for (int i = 0; i < n; ++ i)
{
if (i - k + 1 > q[hh]) ++ hh;
while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
q[++ tt] = i;
if (i + 1 >= k) printf("%d ", a[q[hh]]);
}
return 0;
}


11天前
# include <iostream>
using namespace std;
const int N = 1000010;
int a[N], q[N], hh, tt = -1;

int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++ i)
{
scanf("%d", &a[i]);
if (i - k + 1 > q[hh]) ++ hh;                  // 若队首出窗口，hh加1
while (hh <= tt && a[i] <= a[q[tt]]) -- tt;    // 若队尾不单调，tt减1
q[++ tt] = i;                                  // 下标加到队尾
if (i + 1 >= k) printf("%d ", a[q[hh]]);       // 输出结果
}
cout << endl;
hh = 0; tt = -1;                                   // 重置！
for (int i = 0; i < n; ++ i)
{
if (i - k + 1 > q[hh]) ++ hh;
while (hh <= tt && a[i] >= a[q[tt]]) -- tt;
q[++ tt] = i;
if (i + 1 >= k) printf("%d ", a[q[hh]]);
}
return 0;
}