交互题,给出一个$n\times n$的地图,一个人从$(1,1)$走到$(n,n)$,只能往右或者往下走,现在你可以给每个格子赋值,有q组询问,每组询问给出路程权值和,问走过的路径。
因为$n$很小,可以考虑二进制构造地图,同一行相邻成2,同一列相邻乘4即可。那么对于一个路程权值和,如果二进制是一段连续的1,那么他现在在向右走,如果出现了0就向下走。
给一个单调递增的数组,如果相邻两个元素$a_i<a_{i+1}+1$,那么就令$a_i$加一,令$a_{i+1}$减一。问最后状态如何。
可以确定的是最后的状态一定是相邻相差一,最多有一对相邻是相等的值。于是我们只需要求和然后直接模拟即可。
有$k$个位置,每个位置可以放0或1,有$n$个人,第$i$个人可以把$a_i$位置和$b_i$位置交换一次。给出初始位置的01和最终位置的01,要选一段人使得操作后位置相同个数最大。
考虑这个序列,其实交换$(l,r)$相对于对初始序列的$(1,l-1)$和最终序列的$(1,r)$做反向交换然后互相比较。预处理好然后计算更新答案就行。
给你$n$张数字牌和$m-n$张特殊牌河一个数字集合。进行如下操作:
拿出最上面的那张卡片,如果卡片是数字牌,那么把这个数字放进集合。
其他情况下把所有卡片重新打乱。检验集合是否包含了所有数字,如果包含了结束游戏。
问期望操作次数。
期望操作次数是期望游戏轮数乘以期望每一轮次数。
可以发现如果在游戏中摸到特殊牌那么一轮就会结束,那么我们算出所有排列中第一张特殊牌之前的牌数,然后+1除以排列数目就是每轮游戏操作次数的期望。这个的答案是$\frac{n}{m+1}+1$。
然后另一个部分则是$m\sum_{i=1}^n\frac{1}{i}+1$,最终答案就是这两者相乘。