23行代码，秒杀【9.20-哔哩哔哩-算法方向编程题】
90分钟的卷子，只有三道编程，一共写了23行代码
下面主要说一下思路，以及分享一下我的代码（python）。求大佬们点赞！欢迎讨论
第一题：有效缩减
现在有一个长度为 n 的序列，其中第 i 个数字为非负整数 ai。牛牛觉得这个序列里面的元素太大了，想要将它们变得尽可能地小，于是发明了一个数字缩减器，使用方法如下：
1. 缩减器中有一个计数器 k ，初始时 k = 0，缩减器可以多次使用
2. 每次可以选择任意个数字，使得这些数字减少 2k
3. 无论选择数字的数量是否是0，计数器 k 都会增加 1
4. 假设某一次操作选择数字的数量不是0，那么我们认为这是一次有效的缩减
牛牛想要让这个序列中的数字之和尽可能地小，但是又不希望有任何一个数被缩减器减成负数。于是他邀请了牛妹来解决这个问题，牛妹使用了若干次缩减器之后，使得这个序列的每个数字都尽可能地减了，且都为非负整数。现在牛牛想知道，牛妹最少使用了几次有效的缩减？
输入:
第一行为正整数 M 表示使用的测试组数， M <10。接下来有M组测试数据：
每组测则试数据的第一行输入一个正整数 N 表示序列的长度 1 < N ≤ 100000；接下来一行为N个非负整数表示序列中的每一个元素 0 < ai ≤ 2147483647(int 的最大值)
输出描述:
对于每组则i试数据输出一行一个正整数表示答案
解题思路：位或运算
阅读题意，缩减类似于二进制。因为“这个序列的每个数字都尽可能地减了”，所以牛妹一定是将所有数字都缩减到0了。这样一来，可以根据数字的二进制表示，找出它在哪几次次被缩减过。
同时，如何判断计数器为 k 的时候，是否进行了有效的缩减呢？很简单，只要这些数字中，只要至少一个数字二进制的右边第 k 位是1，这次就是有效缩减。因此很自然地想到位或运算操作。
这样一来，这题代码实现就很容易了：把所有数字都进行位或运算。看得到的数字二进制表示中，有多少位是 1 即可。
for _ in range(int(input())):
n = int(input())
nums = [int(x) for x in input().split()]
a = 0
for x in nums:
a |= x
print(bin(a).count('1')) 第二题：最近报价
牛妹安排牛牛出去采购,一共需要购买 n 件产品,编号为1,2,..., n。
已知每件物品的价格，为了上报便捷，牛牛贪图了个方便，每购买完一件产品（原价购买），记录的是下述值：
在之前购买的产品中（不包括当前购买的这件产品）筛选出所有价格高于当前产品价格的产品编号，挑选其中编号最大的那个，记录其价格。
而这个记录的工作显然交到了你手上，希望你在牛牛购买完所有产品之后，把记录下的价格立即交给他。
已知每件物品的价格，为了上报便捷，牛牛贪图了个方便，每购买完一件产品（原价购买），记录的是下述值：
在之前购买的产品中（不包括当前购买的这件产品）筛选出所有价格高于当前产品价格的产品编号，挑选其中编号最大的那个，记录其价格。
而这个记录的工作显然交到了你手上，希望你在牛牛购买完所有产品之后，把记录下的价格立即交给他。
输入描述:
本题为多组测试数据，第一行输出一个正整数 T(1 ≤ T ≤ 1000)，代表测i试数据组数。
对于每组测j试数据，第一行输入一个正整数n(1 ≤ n ≤ 1000)，代表产品数量。
第二行输入 n 个正整数 w1, w2, ..., wn (1 ≤ wt ≤ 1000)，按照购买顺序，依次代表每件产品的价格。
输出描述:
对于每组测试数据，一行输出 n 个正整数，依次代表每件物品购买完之后所记录的价格。如果不存在满足题意的用于记录价格的产品，则用 INF 代替。
本题为多组测试数据，第一行输出一个正整数 T(1 ≤ T ≤ 1000)，代表测i试数据组数。
对于每组测j试数据，第一行输入一个正整数n(1 ≤ n ≤ 1000)，代表产品数量。
第二行输入 n 个正整数 w1, w2, ..., wn (1 ≤ wt ≤ 1000)，按照购买顺序，依次代表每件产品的价格。
输出描述:
对于每组测试数据，一行输出 n 个正整数，依次代表每件物品购买完之后所记录的价格。如果不存在满足题意的用于记录价格的产品，则用 INF 代替。
【样例输入】
1
3
9 6 3
【样例输出】
INF 9 6
解题思路：单调栈
首先将答案数组 ans 的所有元素初始化为 INF。建立一个堆栈 s，之后会用到。
逆向遍历数组，记录下每个物品的价格和下标（wi, i）。同时使用单调栈 s，记录暂时未匹配到更高价格的物品的价格和下标。
遍历过程中，进行如下步骤：
1. 匹配所有栈顶的便宜商品：即将栈顶所有价格低于 wi 的商品信息弹出，并将 ans 对应位置的 INF 修改为 wi
2. 将当前的物品信息（wi, i）入栈
遍历完成后，数组 ans 中所有前面存在更高价格的商品，均为所求的价格；其余未匹配到更高的价格的商品，均为 INF。 for _ in range(int(input())):
n = int(input())
nums = [int(x) for x in input().split()]
s, ans = [], ['INF'] * n
for i in range(n - 1, -1, -1):
while s and s[-1][0] < nums[i]:
ans[s.pop()[1]] = str(nums[i])
s.append((nums[i], i))
print(' '.join(ans)) 第三题：多项式的一次项系数
牛牛给出了一个长度为 n 有关于未知量 x 的式子，他想知道 x 的一次项系数是多少?
牛牛以字符串的形式给出这个式子，这个式子会由若干个 (x-d) 和 (x+d) 的括号式组成，括号式之间是乘积关系。其中 d ('1' < d < '9') 是具有数字意义的字符。
牛牛以字符串的形式给出这个式子，这个式子会由若干个 (x-d) 和 (x+d) 的括号式组成，括号式之间是乘积关系。其中 d ('1' < d < '9') 是具有数字意义的字符。
具体格式可见样例。
输入描述:
一行一个字符串，长度为 n (5 < n < 100000)。
输出描述:
一行整数,表示未知里 x 的一次项系数,对10007取模。
一行一个字符串，长度为 n (5 < n < 100000)。
输出描述:
一行整数,表示未知里 x 的一次项系数,对10007取模。
【样例输入】
(x-1)(x+2)(x+3)
【样例输出】
1
解题思路：乘积数组
首先，需要一点点的数学知识：对于这种
形式的多项式，x 的一次项系数等于
，
其中 P 是 a1, a2, ..., an的乘积。
因此，我们可以参考【某扣238： 除自身以外数组的乘积】（下称“参考题”）。给定一个数组，对于每个数，算出除自身外其余各数的乘积，求和即可。
到了这里，剩下的已经比参考题简单了。先将输入中每一项的常数提取到数组里，然后直接将参考题的思路套进来即可。既没有参考题中不能使用除法的限制，也不需要考虑数组中有 0 的情况。
代码实现：
首先将输入的多项式转化为一个数组。下方代码中第一行直接实现了这一步，这里以示例输入(x-1)(x+2)(x+3)具体说一下：
- 输入的 input() 为"(x-1)(x+2)(x+3)"
- [1: -1]去掉了首尾的括号，变为 "x-1)(x+2)(x+3"
- split(')(') 是根据字符串中的一对背对背的括号 ")("，将字符串分割为列表。因此变为 ["x-1", "x+2", "x+3"]
- s[1:] 去掉了每个表达式开头的 x， 变为 ["-1", "+2", "+3"]
- 使用 eval() 转化为整数，即 [-1, 2, 3]
（不得不吹一波python啊，太方便了555555）
之后，先算出所有数字的乘积 prod，然后再遍历将每个数 ai，将 prod / ai 求和即可，注意要对 10007 取余。
nums = [eval(s[1:]) for s in input()[1:-1].split(')(')]
ans, prod = 0, 1
for x in nums:
prod *= x
for x in nums:
ans += prod // x
print(int(ans % 10007))
类似资料：