AtCoder Beginner Contest 284 A-D题解

2023/1/7 C++ 算法竞赛 题解 AtCoder Beginner Contest 284

第一次打AtCoder:D

A. Sequence of Strings

题面

纯签到题

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s[15];
    for(int i=1;i<=n;i++)
        cin>>s[i];
    for(int i=n;i>=1;i--)
        cout<<s[i]<<'\n';
    return 0;
}

B. Multi Test Cases

题面

纯签到题

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int ans=0;
        int a;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a;
            if(a%2==1)
                ans++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

C. Count Connected Components

题面

简单图论题.

但我还不会图论，对我就成了杀题:(

还是有点dfs的概念的，现场造了个算法A了

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
int M[N][N];
bool v[N][N];
bool vis[N];
int n,m;
int ans=0;
int find_node(int a)
{
    for(int i=1;i<=n;i++)
    {
        if(M[a][i]==1&&!v[a][i])
            return i;
    }
    return 0;
}
void dfs(int a)
{
    if(find_node(a)==0)
        return;
    while(find_node(a)!=0)
    {
        vis[a]=true;
        int t=find_node(a);
        v[a][t]=v[t][a]=true;
        if(!vis[t])
        {
            ans--;
            vis[t]=true;
        }
        dfs(t);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    ans=n;
    memset(M,0,sizeof(M));
    memset(vis,false,sizeof(vis));
    memset(v,false,sizeof(v));
    int u,v;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        M[u][v]=M[v][u]=1;
    }
    for(int i=1;i<=n;i++)
        dfs(i);
    cout<<ans<<'\n';
    return 0;
}

D. Happy New Year 2023

题面

一开始先找的p，TLE了，后来改了改也不知道都改了哪，交了一下竟然A了.

回顾一下有可能是因为一开始用二分手写的sqrt()超时严重，也有可能是先找q会好一点.

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,q;
ll find_p(ll n)
{
    if(n%4==0)
    {
        return n/4;
    }
    else if(n%2==0)
    {
        return 2;
    }
    ll temp=n>>2;
    for(ll i=3;i<=temp;i+=2)
    {
        if(n%i==0)
        {
            if(n/i%i!=0)
            {
                return i;
            }
            else
            {
                return n/i/i;
            }
        }
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll n;
        cin>>n;
        q=find_p(n);
        p=sqrt(n/q+0.5);
        cout<<p<<' '<<q<<'\n';
    }
    return 0;
}
img_show