9.9 360笔试（探险+黑白翻转）
技术类笔试A卷，编程题总体不算太难，难在前面的选择题
第一题：探险
小X在一片大陆上探险，有一天他发现了一个洞穴，洞穴里面有n道门，打开每道门都需要对应的钥匙，编号为i的钥匙能用于打开第i道门，而且只有在打开了第i (i≥1)道门之后，才能打开第i+1道门，一开始只能打开第1道门。幸运的是，小X在外面探索的途中，每天都能发现一把能打开这n道门中其中一道门的钥匙，每天找完钥匙后他都会去打开所有能打开的门。现在给出他每天找到的钥匙编号，请问每道门分别在哪一天被打开。
输入：
第一行包含一个正整数n ，表示门的数量。
接下来一行包含n个正整数a1，a2，...，an，其中ai表示第i天他找到的钥匙的编号，能够打开第ai道门，数据保证a1-an为1-n的一个排列。
输出：
输出一行n个数s1，s2，...，sn，其中si表示第i道门在第si天被打开。
解法：按照题意模拟即可：先在数组内记下已经获得过钥匙的门，利用指针p记录目前所在的位置，每天不断开门（每开一个门，输出一个数）直到不能开为止。
注意天数和门序号均是从1开始，而不是0开始。
n = int(input())
nums = [int(x) for x in input().split()]
doors = [0] * n
p = 0
ans = [-1] * n
for i in range(n):
doors[nums[i] - 1] = 1
while p < n and doors[p] == 1:
ans[p] = i + 1
p += 1
print(str(ans)[1:-1].replace(',','')) 第二题：黑白翻转
有n个黑白棋子，它们的一面是黑色，一面是白色。它们被排成一行，位置可以用标号1~n来表示。一开始，所有的棋子都是黑色向上，有q次操作，每次操作将位置标号在区间[L, R]内的所有棋子翻转（原来黑色变白色，原来白色变黑色）。请在每次操作后，求这n个棋子中，黑色向上的棋子个数。
输入:
第一行两个整数 n, q，1 <= n <= 10^18, q <= 300;
后面q行，每行两个整数 L,R，1 <= L <= R <= n。
输出:
q行，每行一个整数，表示每次操作后黑色向上的棋子个数。
这是区间查询问题的变种。对于每次修改一个区间的操作，用差分数组往往较快。本题只有“黑、白”两种棋子，因此可以做适当地简化。
现在有n个棋子排成一行。不难想象到，每进行一次操作（输入L,R），相当于在第L和L-1个棋子之间、第R和R+1个棋子之间，各插入一个"翻转点"。
这里“翻转点”两侧的棋颜色是相反的，两个“翻转点”之间的棋颜色都是相同的。用数组 flips 记下所有的翻转点，同时为了将边缘情况一般化，加入 0 和 n 两个翻转点。
进行q次操作以后，共有 2q+2 个“翻转点”。我们将它们排序，此时具有如下规律：
- 第1~2个翻转点之前的棋均为黑色
- 第2~3个翻转点之间的棋均为白色
- ……
- 第2q-1 ~ 2q个翻转点之后的棋均为黑色
（翻转点重合是不需要特殊考虑的）
n, q = [int(x) for x in input().split()] flips = [0, n] for _ in range(q): L, R = [int(x) for x in input().split()] flips = sorted(flips + [L - 1, R]) ans = 0 for i in range(0, len(flips), 2): ans += flips[i+1] - flips[i] print(ans)
查看6道真题和解析