AcWing 第 97 场周赛 ABC(dfs)

https://www.acwing.com/activity/content/competition/problem_list/3088/

果然绩点成绩和竞赛水平总得寄一个（to me

4944. 热身计算

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL a,b;
        cin>>a>>b;
        cout<<min(a,b)<<" "<<abs(a-b)/2<<endl;
    }
    return 0;
}

4945. 比大小

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        LL n,x;
        cin>>n>>x;
        LL sum1=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=n,j=0;i>=1;i--,j++)
        {
            sum1+=a[i]*pow(x,j);
        }
        LL m,y;
        cin>>m>>y;
        LL sum2=0;
        for(int i=1;i<=m;i++)
        {
            cin>>b[i];
        }
        for(int i=m,j=0;i>=1;i--,j++)
        {
            sum2+=b[i]*pow(y,j);
        }
        //cout<<sum1<<" "<<sum2<<endl;
        if(sum1==sum2) cout<<"="<<endl;
        else if(sum1<sum2) cout<<"<"<<endl;
        else cout<<">"<<endl;
    }
    return 0;
}

4946. 叶子节点

输入样例1：
4 1
1 1 0 0
1 2
1 3
1 4
输出样例1：
2
输入样例2：
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
输出样例2：
2

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e6+10,M=3023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,m,res=0,a[N];
vector<LL> v[N];
void dfs(int idx,int fa,int cnt)
{
    if(cnt<=m)//黑色节点不超过m个，可以继续往下探索
    {
        if(v[idx].size()==1&&idx!=1)//非根节点的叶子节点
        {
            res++;//黑色的数量不超过m个，超过了的进不来
        }
        for(int i:v[idx])//继续往下深搜
        {
            if(i!=fa)
            {
                //黑的就+1，白的就直接是0（从新开始）
                dfs(i,idx,a[i]==1?cnt+1:0);
            }
        }
    }
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<n;i++)
        {
            LL x,y;
            cin>>x>>y;
            v[x].push_back(y);
            v[y].push_back(x);
        }
        //>m个黑色节点连续排列在一起,也就是求不超过m个黑色节点的叶子节点数量
        dfs(1,-1,a[1]);
        cout<<res<<endl;
    }
    return 0;
}