头像

德鲁大叔




离线:22小时前


最近来访(6)
用户头像
BlizzardWasteland
用户头像
sduwhacm03
用户头像
苦苦挣扎
用户头像
alextang
用户头像
Donx


#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N], cnt[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> 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")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }

    return 0;
}



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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int p[N];
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>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(b)]=find(a);
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
}


活动打卡代码 AcWing 143. 最大异或对

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int a[N], son[N * 31][2]; // 在trie树中 二维数组son存的是节点的下标                 
                          // 第一维就是下标的值  第二维代表着儿子 在本题中 只有0或1 两个儿子
int n, idx;

void insert(int x)
{
    int p = 0; // 
    for (int i = 31; i >= 0; i--)
    {
        int u = x >> i & 1; // 取二进制数的某一位的值
        if (!son[p][u]) son[p][u] = ++idx; // 如果下标为p的点的u(0或1)这个儿子不存在,那就创建
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, ret = 0;
    for (int i = 31; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (!son[p][!u])
        {
            p = son[p][u];
            ret = ret * 2 + u; // 这个地方与十进制一样 n = n * 10 + x;
        }                      // 则八进制就是 n = n * 8 + x;
        else
        {
            p = son[p][!u];
            ret = ret * 2 + !u;
        }
    }
    ret = ret ^ x;
    return ret;
}

int main()
{
    cin >> n;
    int maxXorNum = 0; 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        insert(a[i]);
        maxXorNum = max(maxXorNum, query(a[i]));
    }

    cout << maxXorNum << endl;

    return 0;
}




活动打卡代码 AcWing 835. Trie字符串统计

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000100;
int s[N][26],cnt[N],idx;
char str[N];
void insert(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!s[p][u])s[p][u]=++idx;
        p=s[p][u];

    }
    cnt[p]++;


}

int query(char str[])
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int u=str[i]-'a';
        if(!s[p][u]) return 0;
        p=s[p][u];
    }
    return cnt[p];
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        char op[2];
        cin>>op>>str;
        if(op[0]=='I') insert(str);
        else cout<<query(str)<<endl;

    }
    return 0;
}


活动打卡代码 AcWing 831. KMP字符串

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000100;
int n,m;
char s[N],p[N];
int ne[N];
int main()
{
   cin>>n>>p+1>>m>>s+1;

   for(int i=2,j=0;i<=n;i++)
   {
       while(j && p[i]!=p[j+1])j=ne[j];
       if(p[i]==p[j+1])j++;
       ne[i]=j;
   }

   for(int i=1,j=0;i<=m;i++)
   {
       while(j && s[i]!=p[j+1]) j=ne[j];
       if(s[i]==p[j+1])j++;
       if(j==n)
       {
           cout << i-n<<" ";
           j=ne[j];
       }
   }
   return 0;


}


活动打卡代码 Linux 5.9. homework_9

ssh myserver
cd homework
mkdir lesson_5
cd lesson_5

git clone git@git.acwing.com:yxc/homework.git


活动打卡代码 Linux 5.8. homework_8

git merge dev  # 将dev分支合并到当前分支

vim readme.txt

***
111
333
555
444
***

git add .
git commit -m "fix conflicts"


活动打卡代码 Linux 5.7. homework_7

git checkout master  # 切换回master分支

vim readme.txt

***
111
333
555
***

git add .
git commit -m "add 555"


活动打卡代码 Linux 5.6. homework_6

git checkout -b dev
vim readme.txt
***
111
333
444
***

git add .
git commit -m "add 444"


活动打卡代码 Linux 5.5. homework_5

git remote add origin git@git.acwing.com:wykhhh/homework.git
git push -u origin master