「入门组」11月9日洛谷模拟题!

「入门组」题解

T1

这个题有两种做法,第一种是二进制加减,第二种就是纯模拟

这里讲第一种方法

以栈顶为二进制数的最低位,另 R 为 0, B 为 1

每次操作就对这个二进制数减一,直到这个数变为0

然后就可以得到我们的答案了

1
2
3
4
5
for (int i = 0; i < n; i++) {
if (Stack[i] == 'B') {
ans += (1ll << i);
}
}

T2

这个题其实是个送分题 但是很多人不写我觉得应该是题面劝退

为了让你们理解方便 我甚至将原题的题面放到了最后

有两个正整数序列,A 序列满足单调递增性,B 序列随机排列,你的任务是在A中找到一个最小的数,使它大于B序列中的所有数,如找不到输出 -1。

1
2
3
4
5
5 4
1 2 3 4 5
2 1 3 4

output:5

对于这两个数列,我们需要满足的只有 让第二组的最大的小于第一组里面的某个数 因为第一组是递增的 所以 for遍历一遍就 OK 了

T3

这个题其实是个送分 规律如下

从0开始

1

0 -> 1

2

0 -> 2 0 -> 1 -> 2

3

0 -> 3 0 -> 2 -> 3 0 -> 1 -> 3 0 -> 1 -> 2 -> 3

于是我们可以得到一种 for 循环的写法 和 一种公式的写法

1
2
3
4
5
6
7
8
9
for (int i = 1; i <= n; i++) {
dp[i] = 1;
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] += dp[j];
}
}

和 通式 ->$ n^{n - 1} $也可以过

T4

搜索dfs 可以拿90分 裸题

但是有10分的点需要判断是否为矩形,该如何判断呢?

将一个矩形内的所有点数加起来,然后除最短的一边,如果最短的一边为1的话需要暴力判断

然后100分 QAQ

0%