Translation Notice
This article was machine-translated using DeepSeek-R1.
- Original Version: Authored in Chinese by myself
- Accuracy Advisory: Potential discrepancies may exist between translations
- Precedence: The Chinese text shall prevail in case of ambiguity
- Feedback: Technical suggestions regarding translation quality are welcomed
Note: Why doesn’t this contest have an English name…
Problem Summary
Given integers $A$ and $B$, output $\frac BA$ rounded to three decimal places.
$1\le A\le 10$
$0\le B\le A$
Analysis
A warm-up problem. Use formatted output with printf or cout.
Code
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;
}
|
Problem Summary
Given an $H\times W$ grid where each cell is . or #, count the number of # in each column and output the results.
$1\le H,W\le 1000$
Analysis
Maintain an array ans[W] to track counts per column. Accumulate during input.
Code
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;
}
|
Problem Summary
A tree with $2N+1$ nodes has root node 1. The tree is defined by sequence $A=(A_1,A_2,\dots,A_N)$:
- Node $A_i$ is the parent of $2i$ and $2i+1$.
Compute the depth of each node.
$1\le N\le 2\times 10^5$
$1\le A_i\le 2i-1$
Solution 1
Construct the tree’s adjacency list from the sequence and compute depths via DFS from the root.
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;
}
|
Solution 2 (Optimal)
Since $A_i$ is always processed before $2i$ and $2i+1$, compute depths directly during input:
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;
}
|
Problem Summary
Given $N$ and sequence $A=(A_1,A_2,\dots,A_N)$, determine if we can reach $(x,y)$ from $(0,0)$ in $N$ steps:
- Step 1: Move $A_1$ units right to $(A_1,0)$
- Step $i$ ($i>1$): Turn 90° left/right, then move $A_i$ units.
$2\le N\le 10^3$
$1\le A_i\le 10$
$-10^4\le x,y\le 10^4$
Analysis
Split the problem into independent x and y axes:
- For the x-axis: Start at $A_1$, target $x$, moves $A_3,A_5,\dots$
- For the y-axis: Start at $0$, target $y$, moves $A_2,A_4,\dots$
Use set-based DP to track reachable positions for each axis. Both axes must satisfy their targets.
Code
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;
}
|
Problem Summary
In a 2D plane, visit all $N$ cities starting from $(0,0)$. Optional $M$ boosters double speed when collected. Compute the minimum time required.
Each city has coordinates $(X_i,Y_i)$, boosters $(P_i,Q_i)$. Initial speed is 1.
Analysis
Refer to Official Editorial for detailed approach.
Code
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;
}
|