头像

天_1




离线:19小时前


最近来访(3)
用户头像
violet_garden
用户头像
旁若无人
用户头像
RSqwq


天_1
19小时前
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
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];
}

bool ask(int a,int b) {
    return find(a)==find(b);
}

int main() {
    read(n),read(m);
    init();
    while(m--) {
        cin>>act;
        if(act=="C") {
            read(a),read(b);
            if(!ask(a,b)) merge(a,b);
        } else if(act=="Q1") {
            read(a),read(b);
            ask(a,b) ? printf("Yes\n") : printf("No\n");
        } else {
            read(a);
            printf("%d\n",size[find(a)]);
        }
    }   
    return 0;
}



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



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



天_1
2天前
#include<bits/stdc++.h>
#define read(x) scanf("%d",&x)
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];
}

bool ask(int a,int b) {
    return find(a)==find(b);
}

int main() {
    read(n),read(m);
    init();
    while(m--) {
        cin>>act;
        if(act=="C") {
            read(a),read(b);
            if(!ask(a,b)) merge(a,b);
        } else if(act=="Q1") {
            read(a),read(b);
            ask(a,b) ? printf("Yes\n") : printf("No\n");
        } else {
            read(a);
            printf("%d\n",size[find(a)]);
        }
    }   
    return 0;
}



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





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



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



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



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



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