AtCoder Beginner Contest 333 A-D题解

A.Three Threes

? ? ? ? 模拟。太水了，循环即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5;
int a[N];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cout<<n;
    }
}
signed main(){
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	system("pause");
	return 0;
}

B.Pentagon

? ? ? ? 数学。判断边长是否相等，实际就是比较顶点位置，则可以分类讨论，将顶点分为两类。

? ? ? ? 第一类：相邻顶点，此时顶点的ASCLL码相减那么是1，要么是4。

? ? ? ? 第二类：相对顶点，此时顶点的ASCLL码相减那么是2，要么是3。

? ? ? ? 比较是否为同类顶点即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5;
int a[N];
int check(char a,char b){
    if(a>b) swap(a,b);
    if((b-a==1)||(b-a)==4) return 1;
    else return 0;
}
void solve(){
    char a,b,c,d;cin>>a>>b>>c>>d;
    if(check(a,b)==check(c,d)){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}
signed main(){
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--) solve();
	system("pause");
	return 0;
}

C.Repunit Trio

? ? ? ?暴力枚举。先预处理所有能用的值，依次枚举，排序即可。注意要用unique函数去重，同时求和时数据会很大，记得开longlong。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2e5+5;
int num[20];
vector<int> v;

void solve(){
    int n;cin>>n;
    for(int i=1;i<=19;i++) num[i]=num[i-1]*10+1;
    int res;
    for(int i=1;i<=19;i++){
        for(int j=1;j<=19;j++){
            for(int k=1;k<=19;k++){
                res=num[i]+num[j]+num[k];
                v.push_back(res);
            }
        }
    }
    
    sort(v.begin(),v.end());
    unique(v.begin(),v.end());
    cout<<v[n-1]<<endl;
}

//多组输入
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);//解绑
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}

D.Erase Leaves

? ? ? ? 图论，深度优先搜索（DFS）。这题就是一道基础的图的遍历问题。本人使用链式前向星建图，注意树是特殊的无向无环图，因此建边时需要加两次（用vector模拟会更简洁，我采用相对原始的数组模拟）。DFS过程中，找出与节点1相连的所有子树，用sum数组存下每个子树的节点数量。最后用与节点1相连的子树节点之和减去最大的子树节点即可。注意题目要求把节点1也删掉，故需在最后输出的时候加1.

? ? ? ? Tip：采用数组模拟时，需要将数组开大一个数量级，否则会RE。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=3e6+5;
int sum[N];
int h[N],e[N],ne[N],idx;
int v[N];
int n;

void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void dfs(int x){
    v[x]=1;
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!v[j]){
            dfs(j);
            sum[x]+=sum[j];
        }
    }
    sum[x]++;
}

void solve(){
	memset(h,-1,sizeof h);
    cin>>n;

    for(int i=1;i<n;i++){
        int x,y;cin>>x>>y;
        add(x,y);add(y,x);
    }

    dfs(1);
    int ans=0,mx=0;
    for(int i=h[1];i!=-1;i=ne[i]){
        int j=e[i];
        ans+=sum[j];
        mx=max(mx,sum[j]);
    }
    cout<<ans-mx+1<<endl;
}

//多组输入
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);//解绑
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}