吐槽：这比赛名字为啥没有英文版。。。
A - Batting Average
题目大意
给定整数\(A,B\)，输出\(\frac BA\)，保留三位小数。
\(1\le A\le 10\)
\(0\le B\le A\)
分析
签到题，使用printf或cout格式化输出即可。
代码
#include <cstdio>
using namespace std;
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%.3Lf\n", (long double)b / a);
return 0;
}
B - Line Sensor
题目大意
给定一个\(H\times W\)的网格，每个方格内都是.或#。
求每一列的#的个数，分别输出。
\(1\le H,W\le 1000\)
分析
开一个数组ans[W]，存储每一列的#的个数。输入时统计一下即可。
代码
#include <cstdio>
#define maxn 1005
using namespace std;
char s[maxn];
int ans[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
while(n--)
{
scanf("%s", s);
for(int i=0; i<m; i++)
if(s[i] == '#')
ans[i] ++;
}
for(int i=0; i<m; i++)
printf("%d ", ans[i]);
return 0;
}
C - Ameba
题目大意
有一棵由\(2N+1\)个结点组成的树，根结点是\(1\)。
整棵树用一个序列\(A=(A_1,A_2,\dots,A_N)\)表示：
- 结点\(A_i\)是\(2i\)和\(2i+1\)的父亲。
求每个结点的深度。
\(1\le N\le 2\times 10^5\)
\(1\le A_i\le 2i-1\)
解法1
根据题意构造树的邻接表，从根结点\(1\)开始向下搜索，从而推出每个结点的深度。
#include <cstdio>
#include <vector>
#define maxn 200005
using namespace std;
vector<int> G[maxn << 1];
int dep[maxn << 1];
void dfs(int v, int par)
{
for(int u: G[v])
if(u != par)
{
dep[u] = dep[v] + 1;
dfs(u, v);
}
}
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
int x;
scanf("%d", &x);
G[x].push_back(i << 1);
G[x].push_back(i << 1 | 1);
}
dep[1] = 0;
dfs(1, -1);
for(int i=1; i<=(n<<1)+1; i++)
printf("%d\n", dep[i]);
return 0;
}
解法2（最优解）
我们从解法\(1\)进一步考虑：由于\(1\le A_i\le 2i-1\)，所以\(A_i\)一定在\(2i\)和\(2i+1\)前被处理，那么直接在输入时计算depth[2*i] = depth[2*i+1] = depth[A[i]] + 1即可。
#include <cstdio>
#include <vector>
#define maxn 200005
using namespace std;
int dep[maxn << 1];
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
int x;
scanf("%d", &x);
dep[i << 1] = dep[i << 1 | 1] = dep[x] + 1;
}
for(int i=1; i<=(n<<1)+1; i++)
printf("%d\n", dep[i]);
return 0;
}
D - Robot Arms 2
题目大意
给定整数\(N\)和序列\(A=(A_1,A_2,\dots,A_N)\)，能否在平面直角坐标系中通过\(N\)步从\((0,0)\)走到\((x,y)\)？每一步如下：
- 第\(1\)步：从\((0,0)\)走到\((A_1,0)\)（向右前进\(A_1\)格）。
- 第\(i\)步（\(i>1\)）先左转或右转\(90\degree\)，再前进\(A_i\)格。
\(2\le N\le 10^3\)
\(1\le A_i\le 10\)
\(-10^4\le x,y\le 10^4\)
分析
先考虑另一个问题：
在一维坐标系中，从\(s\)开始进行\(N\)次位移，第\(i\)次的操作如下：
\(\to~\)选择左移或者右移\(A_i\)个长度单位，即坐标加上\(A_i\)或者减去\(A_i\)。
\(N\)次操作后是否能到达终点\(t\)？注意：必须为最终到达，中途经过不算数！
很容易想到使用一个简单的\(\text{DP}\)，令\(f(i,j)\)表示前\(i\)次操作后是否能达到\(j\)（\(0\)或\(1\)），转移显而易见：\(f(i,j)=f(i-1,j-A_i)\vee f(i-1,j+A_i)\)。
但是这样的时间复杂度很高，高达\(\mathcal O(Nk)\)，其中\(k\)为坐标系大小。
稍加思考会发现，只有小部分坐标能真正达到，其余都没有必要参与转移，所以使用set进行存储，\(S_i\)表示前\(i\)次操作后能到达的坐标集合，利用\(S_i=(S_{i-1}+A_i)\cup(S_{i-1}-A_i)\)进行转移即可。
代码：
inline bool check(vector<int>& v, int start, int target)
{
set<int> s;
s.insert(start);
for(int d: v)
{
set<int> ls = s;
s.clear();
for(int x: ls)
s.insert(x + d), s.insert(x - d);
}
return s.count(target);
}
然后回到原来的问题，发现由于\(x\)和\(y\)两个坐标互不影响，所以把两个坐标轴分别独立出来是没有问题的，可以转换为刚才的子问题：
- 对于\(x\)坐标，起始位置为\(A_1\)，终点为\(x\)，移动序列为\(A_3,A_5,\dots\)。
- 对于\(y\)坐标，起始位置为\(0\)，终点为\(y\)，移动序列为\(A_2,A_4,\dots\)。
只要两个子问题的条件都满足，那么一定存在一种可行的操作序列来满足原题的要求。
至此，问题得到解决。
代码
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
inline bool check(vector<int>& v, int start, int target)
{
set<int> s;
s.insert(start);
for(int d: v)
{
set<int> ls = s;
s.clear();
for(int x: ls)
s.insert(x + d), s.insert(x - d);
}
return s.count(target);
}
int main()
{
int n, x, y;
scanf("%d%d%d", &n, &x, &y);
vector<int> a(n);
for(int& t: a) scanf("%d", &t);
vector<int> dx;
for(int i=2; i<n; i+=2)
dx.push_back(a[i]);
if(!check(dx, a[0], x)) { puts("No"); return 0; }
vector<int> dy;
for(int i=1; i<n; i+=2)
dy.push_back(a[i]);
puts(check(dy, 0, y)? "Yes": "No");
return 0;
}
E - Booster
题目大意
在平面直角坐标系中，有\(N\)个城市和\(M\)个箱子。城市\(i\)位于坐标\((X_i,Y_i)\)，箱子\(i\)则在坐标\((P_i,Q_i)\)。
Takahashi现在要从原点\((0,0)\)开始访问\(N\)个城市，中途箱子可去可不去。他初始的速度为\(1\)，每碰到一个箱子都可以将速度提升至原先的两倍（每个箱子只能加速一次）。
至少要用多少时间，才能将\(N\)个城市都访问至少一次？
分析
参考AtCoder 官方题解的做法，这里不详细解释。
代码
#include <cstdio>
#include <cmath>
#define maxn 17
using namespace std;
inline double ppow(int x) { return 1.0 / (1 << __builtin_popcount(x)); }
inline void setmin(double& x, double y)
{
if(y < x) x = y;
}
double x[maxn], y[maxn], dp[maxn][1 << maxn];
int main()
{
// Input
int n, m;
scanf("%d%d", &n, &m);
m += n;
for(int i=0; i<m; i++)
scanf("%lf%lf", x + i, y + i);
int mx = 1 << m;
for(int i=0; i<m; i++)
for(int s=0; s<mx; s++)
dp[i][s] = 1e18;
// DP: Initial state
for(int i=0; i<m; i++)
dp[i][1 << i] = hypot(x[i], y[i]);
// DP: Transfer
for(int s=1; s<mx; s++)
{
double coef = ppow(s >> n);
for(int i=0; i<m; i++)
{
if(!(s >> i & 1)) continue;
for(int j=0; j<m; j++)
{
if(s >> j & 1) continue;
setmin(dp[j][s | (1 << j)],
dp[i][s] + hypot(x[i] - x[j], y[i] - y[j])*coef);
}
}
}
// Output
double ans = 1e18;
for(int i=0, t=1<<n; i<m; i++)
for(int s=t-1; s<mx; s+=t)
setmin(ans, dp[i][s] + dp[i][1 << i] * ppow(s >> n));
printf("%.10f\n", ans);
return 0;
}