AtCoder Beginner Contest 204 补题记录

寄了,vp一场只写出了两道题,我是彩笔

C - Tour

题目大意:给定n个点m条单向边,求总共有多少个点对能够满足(i,j)从i到j

解题思路:在写题目的时候想到用环去写,只要找到环的数量就可以计算,但是苦于找不到所有环,由于给的数据范围非常小(只有2000),那么在n ^ 2的时间复杂度的算法都能够被接受,那么我们遍历一遍全图是O(n)的时间,n个点都遍历一遍就是n ^ 2,那么我们就可以通过暴力直接去写

反思:考虑到时间复杂度,没考虑到暴力做法,想法太过局限

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
vector<vector<int> > G;
int vis[maxn];
int T,n,m;
int u,v;
ll ans = 0;
void BFS(int s)
{
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		for(int h:G[x])
		{
			if(vis[h] == 0)
			{
				vis[h] = 1;
				q.push(h);
			}
		}
	}
}
void DFS(int s)
{
	if(vis[s]) return;
	vis[s] = 1;
	for(auto h:G[s])
	{
		if(vis[h] == 0)
		{
			DFS(h);
		}
	}
	return;
}
void solve()
{
	scanf("%d %d",&n,&m);
	G.resize(maxn);
	for(int i = 1;i <= m;++i)
	{
		scanf("%d %d",&u,&v);
		G[u].emplace_back(v);
	}
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j) vis[j] = 0;
		DFS(i);
		for(int j = 1;j <= n;++j)
		{
			if(vis[j]) ans++;
		}
	}
	printf("%lld\n",ans);
}
int main()
{
	T = 1;
	while(T--)
	{
		solve();
	}
	return 0;
}
AtCoder Beginner Contest 204 补题记录

D - Cooking 

解题思路:给定n个物品需要烹饪,我们有2个锅,求我们需要烹饪最短时间

解题思路:在做题过程中,想到其实物品如何摆放是对最终结果没有影响的,无论最终如何都只有A锅和B锅加起来是全部的时间,那么我们假设A锅时间比较大,那么对于A锅来说,我们要尽可能找到A的大于所有烹饪时间一半的最小值。但是如何去找呢?

想法一:二分,我们可以通过二分去枚举时间,但是如何去线性的表示并且修改相对应的递增递减呢?

因此二分的想法被我们给否决了,但是对于任意一个时刻对于任意一个物品,我们如果需要把物品放入,这个时间是取决于之前的时间的,分析时间复杂度我们可以发现ai的值并不是很大,因此我们可以想到如果有一个东西是储存之前i - 1个物品所需要的时间,那么对于第i 个时间来说,我们我们就可以进行计算了

那么对于A锅来说,设出动态规划转移方程式dp[i][j],i表示第i个物品,j表示可能需要的时间,那么对于这一时刻如果我们这里有东西的,我们可以选择把物品放在b锅,则dp[i + 1][j] = 1;我们也可以选择把东西放回A锅,那么可以得出dp[i + 1][j + a[i]] = 1

需要注意的是我们的边界点是dp[0][0] = 1,边界循环是从0 - > n - 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
bool dp[110][maxn];
int T,n,m;
int a[110];
int sum = 0;
void solve()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)
	{
		scanf("%d",&a[i]);
		sum += a[i];
	}
	dp[0][0] = 1;
	for(int i = 0;i < n;++i)
	{
		for(int j = 0;j <= sum;++j)
		{
			if(dp[i][j])
			{
				dp[i + 1][j] = 1;
				dp[i + 1][j + a[i + 1]] = 1;
			}
		}
	}
	for(int i = (sum + 1) / 2;i <= sum;++i)
	{
		if(dp[n][i])
		{
			printf("%d\n",i);
			break;
		}
	}
}
int main()
{
	solve();
	return 0;
}
AtCoder Beginner Contest 204 补题记录

 

上一篇:AtCoder abc231_d(或者说……UnionFind?)


下一篇:atcoder abc 226 F - Score of Permutations