Atcoder Beginner Contest 274 ( C - E )

C - Ameba

题目大意: 刚开始有一个生物序号为$1$，有$n$次记录，在第$i$次记录中第$a_i$个生物消失会生成第$2i$和$2i+1$个生物，问对于生物从$1$到$2N+1$他们距离$1$有多少代

解题思路: 按照题意模拟即可

c++ language-none

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i];
	for(int i = 1;i <= n;++i)
	{
		int to1 = i * 2;
		int to2 = i * 2 + 1;
		dis[to1] = dis[to2] = dis[a[i]] + 1;
	}
	for(int i = 1;i <= 2 * n + 1;++i)
	{
		cout << dis[i] << "\n";
	}
	return 0;
}

D - Robot Arms 2

题目大意: 给定一个长度为$n$的序列以及$x,y$,问是否存在$n + 1$个点$p_1,p_2,…,p_n,p_{n + 1}$在二维坐标系中满足$p_1 = (0,0),p_2 = (a_1,0),p_{n + 1} = (x,y)$相邻两个点距离是$a_i$并且是$90$度

解题思路: 分析后发现实际上$x$和$y$是相互不干扰的，那么我们可以分开来处理，注意到$a$的范围很小那么我们可以枚举遍历到的数值是多少

c++ language-none

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
// typedef long long ll;
const int maxn = 4e5 + 10;
int n,x,y;
int a[maxn],dis[maxn];
int dp[2][maxn],pre[2][maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> x >> y;
	for(int i = 1;i <= n;++i) cin >> a[i];
	int midp = 10000;
	pre[1][midp + a[1]] = 1;
	pre[0][midp] = 1;
	for(int i = 2;i <= n;++i)
	{
		int now = i & 1;
		for(int j = 0;j <= 20000;++j)
		{
			if(pre[now][j])
			{
				dp[now][j + a[i]] = 1;
				if(j - a[i] >= 0) dp[now][j - a[i]] = 1;
				// cout << "?? now-> " << now << " " << j << "\n";
			}
		}
		for(int j = 0;j <= 20000;++j) pre[now][j] = dp[now][j],dp[now][j] = 0;
	}
	if(pre[1][midp + x] && pre[0][midp + y]) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

E - Booster

题目大意: 给定一个二维平面其中有$n$个城镇和$m$个加速点$(1 \leq n + m \leq 17)$，初始点在$(0,0)$，问必须经理过所有城镇点需要的时间最短是多少，没必要经过所有加速点但是我们每经过一次加速点我们当前的速度就会翻倍

解题思路: 看到题目数据的时候我们就会自然而然的考虑到状态压缩，如何存在当前的状态呢？我们可以用$dp[i][j]$来表示$i$的二进制位状态表示经过了哪些点，然后末尾点是$j$

那么我们思考转移的过程，假设我们当前位置$j$存在$1$,并且当前$k$也是$1$

那么我们可以从$k$点转移到$j$点，那么相对应的方程就是$dp[i][j] = min(dp[i][j],dp[i - (1 << j)][k] + d / v)$

然后我们可以在最后枚举从哪个点最后来以及最后的状态获得答案

c++ language-none

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
double dp[1 << 18][20];
pair<double,double> p[20];
double getdis(int i,int j)
{
	return sqrt((p[i].first - p[j].first) * (p[i].first - p[j].first) + (p[i].second - p[j].second) * (p[i].second - p[j].second));
}
int n,m;
int countx(int x)
{
	int now = 0;
	for(int i = n;i < n + m;++i)
	{
		if(x >> i & 1) now++;
	}
	return now;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	p[0] = {0,0};
	n++;
	for(int i = 1;i < n + m;++i)
	{
		cin >> p[i].first >> p[i].second;
	}
	for(int i = 0;i < (1 << (n + m));++i)
	{
		for(int j = 0;j < n + m;++j) dp[i][j] = 1e18;
	}
	dp[1][0] = 0;
	cout << fixed << setprecision(10);
	for(int i = 0;i < (1 << (n + m));++i)
	{
		for(int j = 0;j < (n + m);++j)
		{
			if(i >> j & 1)
			{
				for(int k = 0;k < (n + m);++k)
				{
					if((i - (1 << j)) >> k & 1)
					{
						double d = getdis(j,k);
						int nowcnt = countx(i - (1 << j));
						int v = (1 << nowcnt);
						dp[i][j] = min(dp[i][j],dp[i - (1 << j)][k] + d / (1.0 * v));
					}
				}
			}
		}
	}
	double ans = 1e18;
	for(int i = (1 << n) - 1;i < (1 << (n + m));i += (1 << n))
	{
		for(int j = 0;j < n + m;++j)
		{
			double d = getdis(0,j);
			int v = 1 << countx(i);
			ans = min(ans,dp[i][j] + d / (1.0 * v));
		}
	}
	cout << fixed << setprecision(10) << ans << "\n";
	return 0;
}