头像

小王子




离线:3天前


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

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1e5+10,M=31*N;
int son[M][2],num[M];
int idx=0;

void ins(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(!son[p][u])
            son[p][u]=++idx;
        p=son[p][u];
    }
}

int ser(int x)
{
    int p=0;
    int an=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(son[p][!u])
        {
            an=an*2+1;
            p=son[p][!u];
        }
        else
        {
            an=an*2+0;
            p=son[p][u];
        }
    }
    return an;
}

int main()
{
    int n;  cin>>n;
    for(int i=0;i<n;i++) cin>>num[i];
    for(int i=0;i<n;i++) ins(num[i]);
    int ma=0;
    for(int i=0;i<n;i++)
    {
        int  s=ser(num[i]);
        if(ma<s)  ma=s;
    }
    cout<<ma<<endl;
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 841. 字符串哈希

//这里填你的代码^^
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int N=1e5+10;
char wo[N];
ULL su[N],p=131,P[N];

ULL get(int l,int r)
{
    return su[r]-su[l-1]*P[r+1-l];
}

int main()
{
    int n,m;    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>wo[i];
    P[0]=1;
    for(int i=1;i<=n;i++)   
    {
        su[i]=su[i-1]*p+wo[i];
        P[i]=P[i-1]*p;
    }
    while(m--)
    {
        int l1,r1,l2,r2;    cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1e5+3;
int num[N];
bool ex[N];

void ins()
{
    int x;  cin>>x;
    int h=(x%N+N)%N;
    while(ex[h]) h=(h+1)%N;
    num[h]=x;
    ex[h]=1;
}

void que()
{
    int x;  cin>>x;
    int h=(x%N+N)%N;
    while(ex[h]&&num[h]!=x) h=(h+1)%N;
    if(ex[h])   cout<<"Yes"<<endl;
    else    cout<<"No"<<endl;
}

int main()
{
    int m;    cin>>m;
    while(m--)
    {
        char c; cin>>c;
        if(c=='I')  ins();
        else        que();
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



题目链接 AcWing 240

我发现在避开错误判断后,对于记录正确信息,省略关于x,y是否已经在同一食物链的判断,程序无法通过。
假如x,y已经处于同一食物链,那么相当于只更新了该食物链顶点到自己的距离,距离的变化无非是增加或减少3的倍数,并不会影响后续的判断。但是为啥程序不能ac,不是很懂orz

错误的代码:

#include <iostream>

using namespace std;

const int N = 50010;

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

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

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0;
    while (m -- )
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);

        if (x > n || y > n) res ++ ;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)
            {
                if (px == py && (d[x] - d[y]) % 3) res ++ ;
                else //if (px != py)  省略了判断x,y是否处于同一食物链
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else //if (px != py)  省略了判断x,y是否处于同一食物链
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}



活动打卡代码 AcWing 240. 食物链

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1e5+10;
int se[N],d[N];
int fake=0;

int find(int a)
{
    if(se[a]!=a)
    {
        int f=find(se[a]);
        d[a]+=d[se[a]];
        se[a]=f;
    }
    return se[a];
}

void to(int n)
{
    int a,b; cin>>a>>b;
    int fa=find(a),fb=find(b);
    if(a>n||b>n)
        fake++;
    else if(fa==fb&&(d[a]-d[b])%3)
        fake++;
    else if(fa!=fb)
    {
        se[fa]=fb;
        d[fa]=d[b]-d[a];
    }
}

void ch(int n)
{
    int a,b;    cin>>a>>b;
    int fa=find(a),fb=find(b);
    if(a>n||b>n)
        fake++;
    else if(fa==fb&&(d[a]-d[b]+1)%3)
        fake++;
    else if(fa!=fb)
    {
        se[fa]=fb;
        d[fa]=d[b]-1-d[a];
    }

}

int main()
{
    int n,m;    cin>>n>>m;
    for(int i=1;i<=n;i++)   se[i]=i;
    for(int i=0;i<m;i++)
    {
        char c; cin>>c;
        if(c=='1')  to(n);
        else        ch(n);
    }
    cout<<fake<<endl;
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



//这里填你的代码^^
#include<iostream>
#include<string>
using namespace std;
const int N=1e5+10;
int se[N],sum[N];

int find(int a)
{
    if(a!=se[a])
        se[a]=find(se[a]);
    return se[a];
}

void mer()
{
    int a,b;    cin>>a>>b;
    a=find(a);  b=find(b);
    if(a!=b)
    {
        se[a]=b;
        sum[b]+=sum[a];
    }
}

void que()
{
    int a,b;    cin>>a>>b;
    if(find(a)==find(b))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

void show()
{
    int a;  cin>>a;
    cout<<sum[find(a)]<<endl;
}

int main()
{
    int n,m;    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        se[i]=i;    sum[i]=1;
    }
    for(int i=0;i<m;i++)
    {
        string s;   cin>>s;
        if(s=="C")  mer();
        else if(s=="Q1")    que();
        else                show();
    }
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1e5+10;
int se[N];

int find(int a)
{
    if(a!=se[a])
        se[a]=find(se[a]);
    return se[a];
}

void mer(int a,int b)
{
    int fa=find(a),fb=find(b);
    if(fa!=fb)  se[fa]=fb;
}

void que(int a,int b)
{
    if(find(a)==find(b))
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}

int main()
{
    int n,m;    cin>>n>>m;
    for(int i=1;i<=n;i++)    se[i]=i;
    for(int i=0;i<m;i++)
    {
        char c; cin>>c;
        int a,b;    cin>>a>>b;
        if(c=='M')  mer(a,b);
        else        que(a,b);
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 839. 模拟堆

//这里填你的代码^^
#include<iostream>
#include<string>
using namespace std;
const int N=1e5+10;
int hea[N][2],num[N];
int si=0,sum=0;

void ss(int a,int b)
{
    swap(hea[a][0],hea[b][0]);
    swap(hea[a][1],hea[b][1]);
    swap(num[hea[a][0]],num[hea[b][0]]);    
}

void up(int p)
{
    while(p>1)
    {
        if(hea[p][1]<hea[p/2][1])
        {
            ss(p,p/2);
            p/=2;
        }
        else    break;
    }
}

void down(int p)
{
    while(2*p<=si)
    {
        int minp;
        if(2*p+1<=si)
            if(hea[2*p][1]<hea[2*p+1][1])
                minp=2*p;
            else
                minp=2*p+1;
        else    minp=2*p;
        if(hea[p][1]>hea[minp][1])
        {
            ss(p,minp);
            p=minp;
        }
        else    break;
    }
}

void ins()
{
    int x;  cin>>x;
    si++;sum++;
    hea[si][0]=sum; hea[si][1]=x;
    num[sum]=si;
    up(si);
//    cout<<"ins"<<endl;
}

void del()
{
    int k;    cin>>k;
    int p=num[k];
    ss(p,si);
    si--;
    up(p);
    down(p);
//    cout<<"del"<<endl;
}

void pop()
{
    ss(1,si);
    si--;
    down(1);
//    cout<<"pop"<<endl;
}

void show()
{
    cout<<hea[1][1]<<endl;
//    cout<<"show"<<endl;
}

void chan()
{
    int k,x;    cin>>k>>x;
    int p=num[k];
    hea[p][1]=x;
    up(p);
    down(p);
//    cout<<"chan"<<endl;
}

int main()
{
    int n;  cin>>n;
    for(int i=0;i<n;i++)
    {
        string c; cin>>c;
        if(c=="I")  ins();
        else if(c=="DM") pop();
        else if(c=="PM") show();
        else if(c=="D") del();
        else chan();
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 838. 堆排序

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1e5+10;
int hea[N];
int si=0;

void up(int p)
{
    while(p>1&&hea[p]<hea[p/2])
    {
        swap(hea[p],hea[p/2]);
        p/=2;
    }
}

void down(int p)
{
    while(2*p<=si)
    {
        int minp;
        if(2*p+1<=si)
            if(hea[2*p]<hea[2*p+1])
                minp=2*p;
            else
                minp=2*p+1;
        else    minp=2*p;
        if(hea[p]>hea[minp])
        {
            swap(hea[p],hea[minp]);
            p=minp;
        }
        else    break;
    }
}

void ins(int x)
{
    hea[++si]=x;
    up(si);
}

void pop()
{
    swap(hea[1],hea[si]);
    cout<<hea[si--]<<' ';
    down(1);
}

int main()
{
    int n,m;  cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x;  cin>>x;
        ins(x);
    }
    for(int i=0;i<m;i++)
        pop();
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


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

//这里填你的代码^^
#include<iostream>
using namespace std;
const int N=1e5+10;
int son[N][26],cnt[N];
char str[N];
int pos=0;

void ins()
{
    int p=0;
    for(int i=0;str[i]!='\n';i++)
    {
        int x=str[i]-'a';
        if(son[p][x]==0)    son[p][x]=++pos;
        p=son[p][x];
    }
    cnt[p]++;
}

int que()
{
    int p=0;
    for(int i=0;str[i]!='\n';i++)
    {
        int x=str[i]-'a';
        if(son[p][x]==0)    return 0;
        p=son[p][x];
    }
    return cnt[p];
}

int main()
{
    int n;  scanf("%d",&n);getchar();
    for(int i=0;i<n;i++)
    {
        char c; scanf("%c",&c);getchar();
        char b=90;
        for(int j=0;b!='\n';j++)
        {
            scanf("%c",&b); str[j]=b;
        }

     //   for(int j=0;str[j]!='\n';j++) cout<<str[j];cout<<endl;
        if(c=='I')  ins();
        else        cout<<que()<<endl;
    }
    return 0;
}
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~