被表弟的高中竞赛题难住了

Rorshach 发表于 2021-2-17 02:35
做leetcode不会做oi题不是很正常，明显是后者要难

确实是这样，如果是像我说的那样做的话，基本上是一道lc medium（而且必须用最优解） + 一道lc hard + 一些衔接段的代码和推导。基本上是两道lc hard的综合了， 或者是一道hard和一道比较难的medium。

不知道小帅 发表于 2021-2-17 02:56
确实是这样，如果是像我说的那样做的话，基本上是一道lc medium（而且必须用最优解） + 一道lc hard + 一 ...

你解法可以的而且std应该也是你这个解法，先二分答案然后再在类似前缀和的数组上做逆序对，很自然每一步放在OI里也非常套路，一般这种题目会放在联赛的D1T2或者D2T1

Rorshach 发表于 2021-2-17 03:07
你解法可以的而且std应该也是你这个解法，先二分答案然后再在类似前缀和的数组上做逆序对，很自然每一步 ...

省选还是NOI的D1T2难度啊？那也就算是中档题难度吧？那NOIP中档题就已经是lc上面hard偏上的难度了啊。确实是太难了，像我这种只刷lc的，基本上也接近能做出来的难度极限了。

不知道小帅 发表于 2021-2-16 05:29
这个题目我的想法是二分。二分的思路可以参考leetcode的378题，也就是我们猜一个数， ...

暂时改成了大括号，之后会修改这个bug，论坛编辑中也有插入代码的功能

不知道小帅 发表于 2021-2-17 03:18
省选还是NOI的D1T2难度啊？那也就算是中档题难度吧？那NOIP中档题就已经是lc上面hard偏上的难度了啊。确 ...

NOIP(省联赛)中档题，省选和NOI比这个难度高太多了。。。。尤其是省选，一个题目全省能在考场上做对的两个手一般能数得过来

不过竞赛本来就不expect你全做出来的，如果你NOIP这种中档题做对，简单题不做错，难题打对暴力分，就算在浙江也有1=了

你至少这个题目做出来了也算挺强的了，觉得难是因为你没怎么碰过更难的题目。我感觉如果觉得leetcode会做的话不要自我设限，就，不要产生那种“我只刷lc最多也能做做这种题了”的想法，把自己当OI或者ACM选手，看看竞赛书打打codeforces比赛，一般能稳在1800分以上基本会觉得这种题目不算那么“极限”了，回头看面经题简直就像是降维打击

instant_dev 发表于 2021-2-17 03:27
暂时改成了大括号，之后会修改这个bug，论坛编辑中也有插入代码的功能

谢谢。这个确实有时候想写公式或者推导啥的就比较麻烦。也不太方便开代码编辑器。

wangshangsam 发表于 2021-2-17 01:26
啊对。。。我把subarry理解成subset了（i.e.，1+3）这种也算

那这样的话好像还可以通过heap解决：先往hea ...

这个k最大可能是n方级别的数。所以这种做法应该还是会超时，而且需要额外的变量记录当前的平均值对应的左右起点便于去重和扩展。应该还是像我说的二分+归并排序。

不知道小帅 发表于 2021-02-16 04:29:48
这个题目我的想法是二分。二分的思路可以参考leetcode的378题，也就是我们猜一个数，然后看有没有多少个subarray的平均值大于等于这个数，如果有多于k个，说明当前数是小于实际的要求的值的，需

很合理！太厉害了！我的等级还远远不够竞赛题😭😭

不知道小帅 发表于 2021-2-16 20:29
这个题目我的想法是二分。二分的思路可以参考leetcode的378题，也就是我们猜一个数，然后看有没有多少个sub ...

我还真按照你提供的思路编了一个。但是到最后一步卡住了。我想请教一下，如果第k个mean是个分数（不能变成整数那种），那是要继续二分下去吗？还是说在确定了第k个mean在两个整数之间之后，能有一种比较efficient的方法求出确切的那个分数。我真的挺着迷编程序的，如果能给个完全的程序解那就太感谢了！

在此也喊话楼主，要不你再问问你小表弟儿，看他们老师放习题答案了没有（捂脸）。

pphuangyi 发表于 2021-2-17 22:47
我还真按照你提供的思路编了一个。但是到最后一步卡住了。我想请教一下，如果第k个mean是个分数（不能变 ...

可以继续的。就是double类型也无所谓，可以把精度控制的，就是你二分的边界可以是double，然后写成这样，

1. 
   
2. double tol = 1e-6;
   
3. while (r - l < tol) {
   
4.     dobule mid = (l + r) / 2;
   
5. }

复制代码