Codeforces Education Round7
A:Infinite Sequence
A题比较简单,主要就利用公式$ \sum_{k=1}^n k=\frac {(1+n)* n}{2} $来确定距离所要求的数字最近的一个1所在的位置。然后就可得到该数值了。
代码如下：
代码
1 | public class Round7_A{ |
B. The Time
B题也比较简单，主要就注意几个边界条件即可以及格式化输出即可。
1 | //num只有个位时，会自动在十位补0 |
C. Not Equal on a Segment
题目
题意为查询一个数组的某一区间是否存在指定的$$$x$$$不相同的数，若不存在输出-1，否则输出任意一个不相同的树的秩。
解法介绍
1.暴力解法就是遍历整个区间，但时间肯定不够。
2.线段树法：线段树广泛用于区间查询，但是该题仅需输出任意一个不相同的树的位置即可，所以可以不用该法。(其实我还没有特别熟线段树)
3.解法：设输入数据的数组为1
2
3
4创建一个数组```diff[]=new int[arrayLength]```使其任意秩```diff[i]```值为满足$$$ a_j \ne a_i (j>i) $$$的第一个j的值。这也是官方答案所给的解法。代码如下：<br>
### 边界条件
该代码需要考虑到的边界条件有：<br>
1.数组内容全部相同
2.数组内容出现连续相同的项
3.数组内容全部不相同
4.diff数组的最后一项是否有值(统一将diff数组的最后一项设为数组长度)
1 |
|
查询时使用的代码:
1 | try{ |
IO问题
这一题以及下面的e题还有一个问题就是如果使用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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
我使用了[ java_acm快速输入和输出 ][1]中提供的一个输入输出方法，代码如下
#### 解决代码
```java
public class Main {
private static Reader reader = null;
private static Writer writer = null;
public static void main(String[] args) {
reader = new InputStreamReader(System.in);
writer = new OutputStreamWriter(System.out);
try {
m = getInt();
writer.write("something");
writer.flush();
}
} catch (Exception e) {
e.printStackTrace();
}
}
/**
* 获取键盘输入的整数
*
* @return 输入的整数
*/
public static int getInt() {
int read;
int res = 0;
boolean isNegative = false;// 是不是负数
try {
while ((read = reader.read()) != -1) {
if ((char) read == '-') {
res = 0;
isNegative = true;
break;
} else if (isNumber((char) read)) {
res = read - '0';
break;
}
}
while ((read = reader.read()) != -1) {
char ch = (char) read;
if (isNumber(ch)) {
res = res * 10 + (read - '0');
} else {
break;
}
}
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
if (isNegative == true) {
res = -1 * res;
}
return res;
}
/**
* 判断字符是否空白
*
* @param ch
* 字符
* @return 判断结果
*/
public static boolean isBlank(char ch) {
if (ch == '\r' || ch == '\n' || ch == ' ') {
return true;
}
return false;
}
/**
* 判断字符是不是数字
*
* @param ch
* 字符
* @return 判断结果
*/
public static boolean isNumber(char ch) {
if (ch <= '9' && ch >= '0') {
return true;
}
return false;
}
}
E. Ants in Leaves
题目
You are given a tree with n vertices and a root in the vertex 1. There is an ant in each leaf of the tree. In one second some ants can simultaneously go to the parent vertex from the vertex they were in. No two ants can be in the same vertex simultaneously except for the root of the tree.
Find the minimal time required for all ants to be in the root of the tree.
题意：n只蚂蚁从树的叶节点向根节点爬，每秒只能爬到它的父节点处，但是除了根节点，其它所有节点都只能同时存在一只蚂蚁。
解法
This problem was suggested by Aleksa Plavsic allllekssssa.
Let z be the array of the depths of all leaves in the subtree of the vertex v. Let’s sort z.
Statement 1: it’s profitable to lift the leaves in order of their appearing in z.
Statement 2: denote ax — the time of appearing the x-th leaf in the vertex v, let’s consider the leaves $$$z_i$$$ and $$$z_{i+1}$$$ then $$$a_{z_i+1} \geq a_{z_i}+1$$$.
Statement 3: $$$a_{z_i+1}=max(d_{z_i}+1,a_{z_i}+1)$$$, where $$$d_x$$$ is the depth of the x-th leaf in the subtree of the vertex v. The last statement gives us the solution for the problem: we should simply iterate over z from left to right and recalculate the array a by formula from the third statement. All statements can be easily proved and it’s recommended to do by yourself to understand better the idea of the solution.
代码实现
建图
1 | int V=getInt(); |
dfs()详细代码
1 |
|
solve()代码
1 |
|
