AtCoder Beginners Contest 274 Editoral
Task A – Batting Average
Problem Statement
There are integers \(A\) and \(B\), which satisfy \(1≤A≤10\) and \(0≤B≤A\).
Let S be the string obtained as follows.
Round off \(\dfrac AB\) to three decimal digits, then write the integer part (1 digit), . (the decimal point), and the decimal part (3 digits) in this order, with trailing zeros.
For example, if A=7 and B=4, then \(\dfrac AB=\dfrac74\) =0.571428… rounded off to three decimal digits is 0.571. Thus, S is 0.571.
You are given A and B as the input and asked to print S.
Sample Data
Sample Input 1
7 4
Sample Output 1
0.571
题面翻译
对\(\dfrac AB\)四舍五入到保留四个有效数字
Source Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
float a, b;
cin >> a >> b;
while (b / a > 1)
{
b -= a;
}
cout << fixed << setprecision(3) << b / a << endl;
}
解析
如果需要解析那你不适合学编程
Task B – Line Sensor
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters \(C_{i, j}\) . If \(C_{i, j}\) is ., $ (i, j)$ is empty; if it is #, \((i, j)\) contains a box. For integers \(j\) satisfying \(1 \leq j \leq W\) , let the integer $ X_{j} $ defined as follows.
- \(X_{j}\) is the number of boxes in the \(j\) -th column. In other words, \(X_{j}\) is the number of integers \(i\) such that \(C_{i, j}\) is
#. Find all of $X_{1}, X_{2}, \ldots, X_{W} $
Sample Input 1
3 4
#..#
.#.#
.#.#
Sample Output 1
1 2 0 3
题面翻译
对于一个H行W列的表格，.表示空，#表示有内容，求每一列有多少个有内容的格子。
Source Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int h, w;
// system("pause");
bool square[1005][1005];
int ans[1005] = {0};
cin >> h >> w;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < w; j++)
{
char ch = getchar();
if (ch == '\n')
ch = getchar();
if (ch == '#')
{
square[i][j] = 1;
ans[j]++;
}
else
square[i][j] = 0;
}
}
for (int i = 0; i < w; i++)
{
cout << ans[i] << " ";
}
}
解析
在每次读入的时候直接存储到对应的列去，但是注意在换行的时候要额外读入一个'\n'。
Task C – Ameba （变形虫）
我不理解为什么会有这么恶心的题面
Problem Statement
You observed amoebae and kept some records.
Initially, there was one amoeba, numbered 1.
You made N records. According to the i-th record, the amoeba numbered \(A_i\) disappeared by dividing itself into two new amoebae, which were then numbered \(2i\) and \(2i+1\).
Here, amoeba \(A_i\)is said to be the parent of amoebae of \(2i\) and \(2i+1\).
For each \(k=1,…,2N+1\), how many generations away is amoeba k from amoeba \(1\)?
Sample Input 1
2
1 2
Sample Output 1
0
1
1
2
2
题面翻译
每一只虫子的孩子是这只虫子编号的两倍和两倍加一，标准的二叉树。
Source Code
// /*
// 编号i的变形虫，其两个孩子为2i,2i+1
// 对于i输出dist(i,1)+1两次
// dist(i,1)=dist(i-1,1)+1;
// */
// #include <bits/stdc++.h>
// using namespace std;
// int parent[2 * 10 ^ 5 + 1] = {0};
// int dist(int i, int org)
// {
// cout << '\t' << parent[i] << " " << org << endl;
// if (i == org)
// return 0;
// return (parent[i], org) + 1;
// }
// int main()
// {
// parent[2] = 1;
// parent[1] = 1;
// parent[4] = 2;
// cout << dist(1, 1) << endl;
// cout << dist(2, 1);
// int n;
// cin >> n;
// for (int i = 1; i <= n; i++)
// {
// int t;
// cin >> t;
// parent[2 * t] = parent[2 * t + 1] = dist(t, 1);
// cout << i << " " << parent[2 * t] << " " << parent[2 * t + 1] << endl;
// }
// for (int i = 1; i <= 2 * n + 1; i++)
// {
// cout << dist(i, 1) << endl;
// }
// }
#include <iostream>
using namespace std;
int n, g[400010];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int v;
cin >> v;
g[2 * i | 1] = g[2 * i] = g[v] + 1;
}
for (int i = 1; i <= 2 * n + 1; i++)
cout << g[i] << endl;
}
解析
求每个节点的深度
原文地址：http://www.cnblogs.com/sweepy/p/abc-274.html
