这是洛谷的第一次初赛膜你赛，我在这订正一下我的错题
1.十进制数114的相反数的8位二进制补码是：
A.
10001110
10001110
10001110 B.
10001101
10001101
10001101 C.
01110010
01110010
01110010 D.
01110011
01110011
01110011
这题选 A
二进制数的相反数 二进制数的最高位是它的符号位，一个二进制数的相反数就是把它的符号位取反
(
114
)
10
=
(
01110010
)
2
(114)_{10}=(01110010)_{2}
(114)10=(01110010)2
(
−
114
)
10
=
(
11110010
)
2
(-114)_{10}=(11110010)_{2}
(−114)10=(11110010)2
二进制数的补码 正二进制数的补码是它本身 负二进制数的补码是把它各位取反后加一
[
11110010
]
补
=
10001110
[11110010]_{补}=10001110
[11110010]补=10001110
在一个长度为 n 的数组中找到第 k 大的数字，平均的算法时间复杂度最低的是：
A.
O
(
n
)
O(n)
O(n) B.
O
(
n
k
)
O(nk)
O(nk) C.
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn) D.
O
(
n
2
)
O(n^2)
O(n2)
这题选 A 洛谷原题 根据快排思想来寻找第
k
k
k 小的数。
快排的核心思想是二分。
在原二分的基础上可以进行修改：因为每次递归都会将数组划分为三部分，而答案只会在这三部分中的一个。在快排的交换完成后，只需在其中一个继续搜索，从而达到优化时间复杂度的效果。
在平均的条件下，每次只需在剩下数字的一半中继续搜索，
∑
i
=
0
∞
n
2
i
=
2
×
n
\sum_{i=0}^{\infty}{\frac{n}{2^{i}}}=2\times n
∑i=0∞2in=2×n
所以复杂度是
O
(
n
)
O(n)
O(n)
14.一个7个顶点的完全图需要删掉多少边才能变为森林？
A.
16
16
16 B.
21
21
21 C.
15
15
15 D.
6
6
6
这题选 C
森林
由一棵或一棵以上棵树组成的数据结构 一棵树也能作为森林
所以删边后剩下
6
6
6 条边，要删掉
15
15
15 条边。
这道并没有错，但是觉得很有趣
（封禁xxs）现有
n
n
n 个xxs （编号为
1
1
1 到
n
n
n ），每个xxs都有一个关注者，第
i
i
i 个xxs的关注者是
a
i
a_i
ai 。现在管理员要将其中一些xxs的账号封禁，但需要注意的是如果封禁了第
i
i
i 个人，那么为了不打草惊蛇，就不能封禁他的关注者
a
i
a_i
ai 。现在想要知道最多可以封禁多少个xxs。
#include <cstdio>
using namespace std
;
#define MAXN 300005
int n
, ans
= 0, a
[MAXN
], in
[MAXN
] = {0};
bool vis
[MAXN
] ={0};
void dfs(int cur
, int w
) {
if(vis
[cur
])
return;
vis
[cur
] = true;
if(w
== 1) ans
++;
in
[a
[cur
]]--;
if(in
[a
[cur
]] == 0 || w
== 1)
dfs(a
[cur
], 1 - w
);
}
int main(){
scanf("%d", &n
);
for(int i
= 1; i
<= n
; i
++){
scanf("%d", &a
[i
]);
in
[a
[i
]]++;
}
for(int i
= 1; i
<= n
; i
++)
if(!in
[i
]) dfs(i
, 1);
for(int i
= 1; i
<= n
; i
++)
if(!vis
[i
]) dfs(i
, 0);
printf("%d\n", ans
);
return 0;
}
