P3156 【深基15.例1】询问学号 题目链接 题目理解 我们可以把这个题目想象成一个 “学生学号登记与查询” 的场景： 有 n 名同学按顺序进入教室，我们需要把他们的学号 “登记” 下来。 之后老师会问 m 次：“第 i 个进教室的同学学号是多少？” 我们要快速给出答案。 #include<bits/stdc++.h> using namespace std; int a[2000001];//注意不要把数组开在主函数里 int main() { int n,m,x; cin >> n >> m; for(int i=1;i<=n;i++) cin...

简单：C,A 中等：E 难：B,D,F C - Remove the Ends 首先要明白，在任何时候，我们都应该要么移除最左边的正数元素，要么移除最右边的负数元素。因为如果我们选取的不是最左边的正数元素，那么我们本可以先选取最左边的那个正数元素，这样能得到更高的分数；对于选取最右边的负数元素，也有类似的道理。 现在，如果你进行上述操作若干次，最终总会先取到一些正数构成的前缀，然后再取到剩余的由负数构成的后缀。所以，为了计算结果，我们只需要检查将数组分成前缀和后缀的所有 (n + 1) 种方式，然后从所有情况中取最大值，而这在 (O(n)) 的时间复杂度内很容易实现。 #include<...