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;
}