2020-04-18 17:25 宁波市效实中学 C++

关注

牛客挑战赛39 - 牛牛与序列

牛牛与序列

https://ac.nowcoder.com/acm/contest/5157/E

题意

求长度为 $n$ 的序列 $\{a\}$ ，满足 $1 \le a_i \le k$ ，且存在 $i,j$ 满足 $a_{i-1}<a_i,a_{j-1}>a_j$ ，求序列数量。

算法（ $O(T \log n + \sum k)$ ）

赛时没看这题，以为很难。。。

根据容斥原理，答案为全部-单调不升-单调不降+不升不降。

$ans=k^n-2f_{n,k}+k\\ f_{i,j}=\sum_{k \le j} f_{i-1,k}=f_{i-1,j}+f_{i,j-1}=\frac{(i+j)!}{i!j!}$

第二个式子最后一次化简，可以看作 $i \times j$ 的方格，从左上到右下的路径条数，有 $i$ 次向右， $j$ 次向下，即有重复的排列问题。

$f_{n,k}=\frac{\prod_{i=n+1}^{n+k} i}{k!}$

全部评论

推荐最新楼层

今天 17:05

中央财经大学项目助理

在腾讯实习的体验

首先，上下班不打卡真的很人性化，每天只要签个到，10点到工位就能开始吃早饭。食堂的菜品还挺丰富的。早午饭是免费的，午饭得自己出，最常吃的就是小碗菜，晚上还可以免费吃六个菜。同事们都特别温和，刚开始的时候我得慢慢熟悉各种流程，最烦的就是权限申请，要等好几天才能搞定。

腾讯公司福利 453人发布

点赞评论收藏

11-17 18:55

海口经济学院内容运营

23届往届生求帮看简历，想找运营工作

本人23届毕业生，学校背景不好民办本科，专业是旅游管理。由于本专业同学大多去往酒店、旅行社之类的，而我不想找本专业工作然后到现在还没有正式工作，想问问各位前辈我这个简历能找什么方向的运营工作，可以提一些建议吗？一开始了解到的运营岗位是看《从零开始做运营》这本书，但我发现这里面运营岗基本上是从开发出一款互联网产品才衍生出来的，比如内容运营、用户运营、活动运营和产品运营，但现在市面上运营工作名称好多压根不知道都是干什么的要怎么选择，真的不知道怎么下手，那我的问题是看我的背景和经历的话要怎么选择运营岗位呢，是不是旅游行业的运营会好进一些，还有我的简历需要怎么优化呢？职场小白真心求助

我想象的工作vs实际工作

点赞评论收藏

11-09 17:30

门头沟学院 Java

抽象华为

TYUT太摆金星：我也是，好几个华为的社招找我了

点赞评论收藏

11-12 21:11

浙江横店影视职业学院运营

不抱什么希望。

😋😋😋

点赞评论收藏

11-21 10:49

门头沟学院电子工程师

收到offer了！！！！

终于轮到我了，一共收到了4个offer，覆盖了我刚开始秋招最想去的几家，以此贴记录一下我的秋招之旅。1、先说背景和offer（先报喜）我的bg：985硕，电子信息专业，1段oppo实习，意向岗位是电子硬件岗我的offer：oppo，base东莞，硬件部门的软件测试小米，base北京，底软中兴，base深圳，硬件工程师联影，base上海，电子硬件岗2、回顾秋招坎坷之路投递：因为之前实习接触的比较多，所以我会更早的去准备和投递，我的秋招也就比别人都早，大概7月初就开始了，因为有的提前批可能能提前拿到offer或者薪资更高。但是现在看其实都是扯淡，并不是说这个不对，而是这个只属于极少数人，尤其在今年...

俊朗的长颈鹿正在卷：老哥说的好，符合自己期望就行，别人的话都是参考文献！

点赞评论收藏

点赞收藏评论

全站热榜

正在热议

# 25届秋招总结 #

275532次浏览 2361人参与

# 如果实习可以转正，你会不会放弃秋招 #

# 选完offer后，你后悔学本专业吗 #

# 你觉得专业和学校哪个对薪资影响最大 #

牛客挑战赛39 - 牛牛与序列

题意

算法（）

全站热榜

算法（ $O(T \log n + \sum k)$ ）