头像

Quavo




离线:12小时前


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

Quavo
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#define IO std::ios::sync_with_stdio(false);cin.tie(0);
typedef long long LL;
using namespace std;
const int N=50010;
int n,m;
LL p[N],d[N];////p[]父节点,d[]表示到父结点的距离//状态压缩后成为至祖宗结点的距离;
int find(int x)
{
    if(p[x]!=x){
        int tmp=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=tmp;

    }
    return p[x];

}

int main()
{
    IO;
    cin>>n>>m;//n个动物,m句话;
    //scanf("%d%d",&n,&m);
    int  fake=0;
    for(int i=1;i<=n;i++){
        p[i]=i;

    }
    while(m--)
    {
        int op;
        int a,b;
        cin>>op>>a>>b;
        if(a>n||b>n)  fake++;

        else
        {
            int pa=find(a);
            int pb=find(b);
            if(op==1)///同类
            {///同一棵树上
                if(pa==pb&&(d[a]-d[b])%3!=0)
                {
                    fake++;
                }
                else  if(pa!=pb)//不在一棵数上;
                {
                    p[pa]=pb;
                    d[pa]=d[b]-d[a];///(d[a]+d[pa])%3=d[b]%3;

                }

            }
            else
            {
                if(pa==pb&&(d[a]-d[b]-1)%3!=0)  
                {
                    fake++;
                }
                else if(pa!=pb)
                {
                    p[pa]=pb;
                    //d[a]+?-1=d[b];
                    d[pa]=d[b]+1-d[a];
                }

            }
        }
    }
    cout<<fake<<endl;
    return  0;

}



Quavo
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
#include<cstring>
#define IO std::ios::ios_stdio(false);cin.tie(0);
using  namespace std;
const int N=1e5+10;
int n,m,p[N],cnt[N];
void  init(int n)
{
    for(int i=1;i<=n;i++){
        p[i]=i;
        cnt[i]=1;
    }
}
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return  p[x];



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



int main()
{
    cin>>n>>m;
    init(n);


    while(m--){
        string op;
        int a,b;
        cin>>op;
        if(op=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
            merge(a,b);

        }
        if(op=="Q1"){
            cin>>a>>b;
            if(find(a)==find(b))  cout<<"Yes"<<" "<<endl;
            else{
                cout<<"No"<<" "<<endl;
            }
        }
        if(op=="Q2"){
            cin>>a;
            cout<<cnt[find(a)]<<endl;


        }
    }
    return  0;
}


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

Quavo
4天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

```

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N=1e5+10;
int h[N],mysize;
int n,m;
void down(int u){
int t=u;
if(u2<=mysize&&h[u2]<h[t]) t=2u;
if(u
2+1<=mysize&&h[u2+1]<h[t]) t=2u+1;
while(u!=t){
swap(h[t],h[u]);
down(t);
}
}

int main()
{
cin>>n>>m;
mysize=n;
for(int i=1;i<=n;i++){
cin>>h[i];
}
for(int i=n/2;i;i–){
down(i);
}
while(m–){
cout<<h[1]<<” “;
h[1]=h[size–];
down(1);
}

}



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

Quavo
12天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
const int M=131;
typedef unsigned long long ULL;
int  n,m;
char str[N];
ULL h[N],p[N];
ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    cin>>n>>m;
    cin>>str+1;
    p[0]=1;
    for(int i=1;i<=n;i++)
    {////哈希前缀
    h[i]=h[i-1]*M+str[i];
    p[i]=p[i-1]*M;


    }
    while(m--)///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. 模拟散列表

Quavo
13天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstring>///含有 memset(name,初始化值,sizeof  name)
using namespace std;
const int N=1e5+3;
int m,x;
int e[N],ne[N],idx,h[N];
void insert(int x)
{
    int  k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;

}
int  find(int x){
int k=(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])
    {
        if(e[i]==x)  return true;
        return false;
    }
}



int main()
{
    cin>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        char op[2];
        cin>>op>>x;
        if(op[0]=='I')  insert(x);
        else{
            if(find(x)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }

    return 0;



}


活动打卡代码 AcWing 3. 完全背包问题

Quavo
16天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int f[N],v[N],w[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=v[i];j<=m;j++){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
}


活动打卡代码 AcWing 2. 01背包问题

Quavo
18天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int  n,m;
int f[N],v[N],w[N];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);

        }

    }
    cout<<f[m]<<endl;
    return 0;
}


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

Quavo
22天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,p[N];
int find(int x)
{
    if(p[x]!=x)  p[x]=find(p[x]);////如果结点的父节点不是祖宗结点,则让他变成祖宗结点;
    else  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;
        cin>>op>>a>>b;
        if(op[0]=='M')  p[find(a)]=find(b);///让a的祖宗结点的父节点等于b的祖宗结点or //a的祖宗结点指向b的祖宗结点
        else{
        if(find(a)==find(b))  puts("Yes");
        else  puts("No");
        }
    }
    return  0;
}


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

Quavo
1个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

```

include[HTML_REMOVED]

using namespace std;
const int N=100010;
int son[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(!son[p][u])   son[p][u]=++idx;
    p=son[p][u];

}

cnt[p]++;

}

int query(char * str)
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-‘a’;

    if(!son[p][u])  return  0;

    p=son[p][u];


}

return  cnt[p];

}

int main()
{
int n;
cin>>n;
while (n–)
{

string op;
cin>>op>>str;

if(op=="I")  insert(str);
if(op=="Q")  cout<<query(str)<<' '<<endl;

}
return 0;

}
```



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

Quavo
1个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

```

include[HTML_REMOVED]

using namespace std;
const int N=100010,M=1000010;
int n,m,ne[M];
char p[N],s[M];
int main()
{
cin>>n>>p+1>>m>>s+1;
//构建ne[];
for(int i=2,j=0;i<=n;i )///因为ne[1]的无前缀和后缀,故是0,直接ne[2]开始;
{
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(n==j){
        cout<<i-n;
        j=ne[j];
    }
}

}