吐槽：这比赛名字为啥没有英文版。。。
题目大意
给定整数$A,B$，输出$\frac BA$，保留三位小数。
$1\le A\le 10$
$0\le B\le A$
分析
签到题，使用printf或cout格式化输出即可。
代码
1
2
3
4
5
6
7
8
9
10
|
#include <cstdio>
using namespace std;
int main()
{
int a, b;
scanf("%d%d", &a, &b);
printf("%.3Lf\n", (long double)b / a);
return 0;
}
|
题目大意
给定一个$H\times W$的网格，每个方格内都是.或#。
求每一列的#的个数，分别输出。
$1\le H,W\le 1000$
分析
开一个数组ans[W]，存储每一列的#的个数。输入时统计一下即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#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;
}
|
题目大意
有一棵由$2N+1$个结点组成的树，根结点是$1$。
整棵树用一个序列$A=(A_1,A_2,\dots,A_N)$表示：
求每个结点的深度。
$1\le N\le 2\times 10^5$
$1\le A_i\le 2i-1$
解法1
根据题意构造树的邻接表，从根结点$1$开始向下搜索，从而推出每个结点的深度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#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即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#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;
}
|
题目大意
给定整数$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)$进行转移即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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$。
只要两个子问题的条件都满足，那么一定存在一种可行的操作序列来满足原题的要求。
至此，问题得到解决。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#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;
}
|
题目大意
在平面直角坐标系中，有$N$个城市和$M$个箱子。城市$i$位于坐标$(X_i,Y_i)$，箱子$i$则在坐标$(P_i,Q_i)$。
Takahashi现在要从原点$(0,0)$开始访问$N$个城市，中途箱子可去可不去。他初始的速度为$1$，每碰到一个箱子都可以将速度提升至原先的两倍（每个箱子只能加速一次）。
至少要用多少时间，才能将$N$个城市都访问至少一次？
分析
参考AtCoder 官方题解的做法，这里不详细解释。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#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;
}
|