1572.涂色（paint）

Question

1572.涂色（paint）
(Input: paint.in, Output: paint.out)
时间限制: 2 s 空间限制: 256 MB 具体限制

题目描述
Introl获得了一个N行的杨辉三角，他将每行中值为奇数的位置涂为了黑色。

Chihiro将提出M次询问，在第L行第R个位置是否被涂成黑色，请你回答 Yes 或 No。

输入
从文件 paint.in 中读入数据。

第一行两个整数N和M。

接下来M行，每行给出L,R表示一组询问。

输出
输出到文件 paint.out 中。

共M行，每行输出 Yes 或 No。

样例数据
输入 #1 复制
3 2
2 2
3 2
输出 #1 复制
Yes
No

数据范围限制
对于30% 的数据，1≤N,M≤50。

对于100% 的数据，1≤N≤4000，1≤M≤10
6
。

提示
构成的杨辉三角为：

1

1 1

1 2 1

除第三行第二个位置外，其余位置均被涂为黑色。

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

题目分析： 本题可以先预处理出所有行的奇数组成的序列，然后每一次查询判断所在行的奇数组成的序列是否包含查询的位置即可。 假设第n行有m个奇数，那么问题变成了给定两个正整数m和k，询问第m个奇数是否为k。显然，第m个奇数即为第m个从小到大的奇数，可以用一个O(k)的算法预处理出前k个奇数，然后二分查找即可，这样查询的时间复杂度为O(mlogk)。 预处理出每一行奇数组成的序列时，可以用前缀和预处理出每一行的奇数总数和奇数组成的序列，也可以用暴力法逐个判断第i行的每个位置是否为奇数并记录奇偶性。时间复杂度为O(n^2)。 算法流程： 1.读入n、m和每组询问的l、r。 2.预处理出每一行的奇数组成的序列。 3.对于每组询问，判断所在行的奇数组成的序列是否包含r这个奇数。如果包含，输出Yes，否则输出No。 代码实现：