头像

zxwmw




离线:8小时前


活动打卡代码 AcWing 2875. 超级胶水

zxwmw
3天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,x;
int main()
{
    cin>>n;

    ll sum=0,res=0;
    for(int i=0;i<n;i++){
        cin>>x;
        sum+=res*x;
        res+=x;
    }
    cout<<sum<<endl;
    return 0;
}


活动打卡代码 AcWing 2069. 网络分析

zxwmw
3天前
#include<bits/stdc++.h>
using namespace std;
const int N=20010;
const int M=220010;
int h[M],e[M],ne[M],idx;
int p[M+N];
int n,m;
int f[M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int get_boss(int u)
{
    if(p[u]==u)
        return u;
    else if(p[u]!=u)
    {
        p[u]=get_boss(p[u]);
        return p[u];
    }
}
void dfs(int u,int fa)
{
    f[u]+=f[fa];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        dfs(j,u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m;
    int root=n+1;
    for(int i=1;i<M;i++)
    p[i] =  i;
    while(m--)
    {
       int t;
       cin>>t;
       if(t==1)
       {
           int a,b;
           cin>>a>>b;
            a=get_boss(a),b=get_boss(b);
            if(a!=b)
            {
               add(root,a);
               add(root,b);
               p[a]=root;
               p[b]=root;
            }
            root++;
       }
       else
       {
           int a,b;
           cin>>a>>b;
            a=get_boss(a);
           f[a]+=b;
       }
    }
    for(int i=n+1;i<root;i++)
    if(p[i]==i)
    dfs(i,-1);
    for(int i=1;i<=n;i++)
    cout<<f[i]<<' ';
    cout<<endl;
    return 0;
}



活动打卡代码 AcWing 2065. 整除序列

zxwmw
3天前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main()
{
    cin>>n;
    while(n)
    {
        cout<<n<<" ";
        n/=2;
    }
}


问题 dfs造成MLE

zxwmw
3天前

题目链接 acwing 2069

不知道为什么MLE,换成链式前向星也是MLE。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e4+8;
vector<int>G[N];
int parent[N],Size[N];
void init()
{
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        Size[i]=0;
    }
    return ;
}
int get_boss(int u)
{
    if(parent[u]==u)
        return u;
    else if(parent[u]!=u)
    {
        parent[u]=get_boss(parent[u]);
        return parent[u];
    }
}
void Merge(int a,int b)
{
    int v1=get_boss(a);
    int v2=get_boss(b);
        parent[v2]=v1;
    return ;
}
void dfs(int u,int fa,int t)
{
    Size[u]+=t;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            dfs(v,u,t);
        }
    }
}
int main()
{
    cin>>n>>m;
    init();
    int op;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>op>>a>>b;
        if(op==1)
        {
            G[a].push_back(b);
            G[b].push_back(a);
            Merge(a,b);
        }
        else if(op==2)
        {
            dfs(a,-1,b);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<Size[i]<<" ";
    }
    cout<<endl;
    return 0;
}

求大佬帮帮忙



活动打卡代码 AcWing 2066. 解码

zxwmw
6天前
#include<bits/stdc++.h>
using namespace std;
string s;
string ans="";
int times;
int main()
{
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(!isdigit(s[i])&&isdigit(s[i+1]))
        {
            times=s[i+1]-'0';
            //cout<<times<<endl;
            while(times--)
            {
               cout<<s[i];
            }
        }
        if(!isdigit(s[i])&&!isdigit(s[i+1]))
        {
            cout<<s[i];
        }
    }
}



活动打卡代码 AcWing 2067. 走方格

zxwmw
6天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[40][40];
int main()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            dp[i][j]=0;
        }
    }  
    dp[1][1]=1;
    dp[1][1]=1;
    dp[2][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {

            if(i==1&&j==1)
                continue;
            if(i%2==0&&j%2==0)
                continue;
            else
            dp[i][j]=dp[i][j-1]+dp[i-1][j];
           // cout<<i<<" "<<j<<"@@"<<endl;
           // cout<<i<<" "<<j-1<<" "<<i-1<<" "<<j<<"??"<<endl;
          // cout<<dp[i][j-1]<<" "<<dp[i-1][j]<<"!!"<<endl;
        }
    }
    cout<<dp[n][m]<<endl;
}


活动打卡代码 AcWing 1078. 旅游规划

zxwmw
7天前
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
vector<int>G[N];
int d1[N],d2[N],p1[N],up[N];
int maxd;
void dfs1(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            dfs1(v,u);
            int dis=d1[v]+1;
            if(dis>d1[u])
            {
                d2[u]=d1[u],d1[u]=dis;
                p1[u]=v;
            }
            else if(dis>d2[u])
            {
                d2[u]=dis;
            }
        }
    }
}
void dfs2(int u,int fa)
{
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            up[v]=up[u]+1;
            if(p1[u]==v)
            {
                up[v]=max(up[v],d2[u]+1);
            }
            else
            up[v]=max(up[v],d1[u]+1);
            dfs2(v,u);
        }
    }
    maxd=max(maxd,d1[u]+d2[u]);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs1(0,-1);
    dfs2(0,-1);

    for(int i=0;i<n;i++)
    {
        int d[3]={d1[i],d2[i],up[i]};
        sort(d,d+3);
        if(d[1]+d[2]==maxd)
        cout<<i<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 1222. 密码脱落

zxwmw
8天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int dp[N][N];
string s;
int main()
{
    cin>>s;
    for(int len=1;len<=s.size();len++)
    {
        for(int l=0;l+len-1<s.size();l++)
        {
            int r=l+len-1;
            if(len==1)
            {
                dp[l][r]=1;
            }
            else
            {
                if(s[l]==s[r]) 
                    dp[l][r]=dp[l+1][r-1]+2;
                if(dp[l][r-1]>dp[l][r])
                    dp[l][r]=dp[l][r-1];
                if(dp[l+1][r]>dp[l][r]) 
                    dp[l][r]=dp[l+1][r];
            }
        }
    }


    cout<<s.size()-dp[0][s.size()-1]<<endl;
}


活动打卡代码 AcWing 1226. 包子凑数

zxwmw
9天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
bool dp[N];
int a[110];
int main()
{
    int n;
    cin>>n;
    int d=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        d=__gcd(d,a[i]);
    }
    if(d!=1)
    cout<<"INF"<<endl;
    else
    {
        dp[0]=true;
        for(int i=1;i<=n;i++)
        {
            for(int j=a[i];j<=N;j++)
            {
               dp[j]|=dp[j-a[i]]; 
            }
        } 
        int res=0;
    for(int i=1;i<=N;i++)
    {
        if(!dp[i])
        res++;
    }
    cout<<res<<endl;
    }


}


活动打卡代码 AcWing 1220. 生命之树

zxwmw
9天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
typedef long long ll;
ll val[N],fa[N],f[N];
vector<int>G[N];
void dfs(int u,int fa)
{
    f[u]=val[u];
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v!=fa)
        {
            dfs(v,u);
            f[u]+=max(f[v],1ll*0);
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
    }
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1,-1);
   ll res=f[1];
    for(int i=1;i<=n;i++)
    {
        res=max(res,f[i]);
    }
    cout<<res<<endl;





}