AtCoder Beginner Contest 284
A - Sequence of Strings
Problem Statement
题意:给你n个字符串,让你倒序输出
Solve
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
string s[N];
int main()
{
int n;
cin>>n;
for(int i = 1;i<=n;i++)
cin>>s[i];
for(int i = n;i>=1;i--)
cout<<s[i]<<endl;
return 0;
}
B - Multi Test Casescenter
Problem Statement
题意:给你一个长度为n的序列,统计奇数出现次数
Solve
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int ans = 0;
for(int i = 1;i<=n;i++)
{
int x;
cin>>x;
if(x&1)ans++;
}
cout<<ans<<endl;
}
return 0;
}
C - Count Connected Components
Problem Statement
题意:给你一个简单无向图,\(N\)个点,\(M\)条边,找有多少个连通块
Solve
题解:并查集裸题,找有多少个连通块
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m,fa[N];
set<int>s;
int find(int x)
{
if(x==fa[x])return x;
return fa[x] = find(fa[x]);
}
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i<=n;i++)fa[i] = i;
for(int i = 1;i<=m;i++)
{
int x,y;
cin>>x>>y;
int fx = find(x),fy = find(y);
if(fx!=fy)
fa[fx] = fy;
}
for(int i = 1;i<=n;i++)
fa[i] = find(fa[i]);
for(int i = 1;i<=n;i++)
s.insert(fa[i]);
cout<<s.size()<<endl;
return 0;
}
D - Happy New Year 2023
Problem Statement
题意:给你一个正整数\(N\),\(N=p^2 \times q\) ,其中\(p,q\)为两个不同的素数,现在需要找出这个\(p\)和\(q\)。
Solve
题解:
因为发现\(N\)的范围是\(10^{18}\),直接写肯定\(TLE\)。
我们发现\(min(p,q)<\sqrt[3]{N}\),因为当\(p=q\)时,\(min(p,q)\)有最大值等于\(\sqrt[3]{N}\)
又因为题目给的\(N\)一定保证了\(p\)和\(q\)的存在性,且都为质数,所以\(N\)不存在其他因子。
我们只需要找到其中一个去求另一个就行了。时间复杂度O(\(\sqrt[3]{N}\))。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i = 2;i<sqrt(n)+1;i++)
{
if(n%(i*i)==0)
{
cout<<i<<" "<<n/(i*i)<<endl;
break;
}
else if(n%i==0)
{
cout<<(int)sqrt(n/i)<<" "<<i<<endl;
break;
}
}
}
return 0;
}
E - Count Simple Paths
Problem Statement
题意:给你一个简单无向图,\(N\)个点\(M\)条边,求从\(1\)出发简单路径的数量\(K\)。
简单路:路径中不出现重复的点。
题目保证\(ans = min(K,10^6)\)
- \(1<=N<=2\times10^5\)
- \(0 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2}\right)\)
Solve
题解:求路径条数?一眼\(dfs\),但是会不会\(TLE\)嘞,不会,因为当\(K>10^6\)时候输出\(10^6\),那就是一个裸的\(dfs\).
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
vector<int>edge[N];
int ans = 0;
bool vis[N];
void dfs(int x)
{
if(ans>=1e6)
return;
ans++;
for(auto y:edge[x])
{
if(!vis[y])
{
vis[y] = true;
dfs(y);
vis[y] = false;
if(ans>=1e6)
return;
}
}
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i<=m;i++)
{
int x,y;
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
vis[1] = true;
dfs(1);
cout<<ans<<endl;
return 0;
}
- Beginner AtCoder Contest ABCDE 284beginner atcoder contest abcde contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 328 beginner atcoder contest 332 beginner atcoder contest 315 beginner atcoder contest 327