wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

容斥法解决错排问题

错排问题简单来说，错排问题就是问有多少个长度为的排列，使得对于所有的都有。递推式错排的一个递推式就是这个递推式复杂度显然是线性的。关于这个递推式的推导请自行百度。这里不再赘述。容斥法解错排问题第一次看到错排问题的时候，并没有推导出上面的递推式。而是用了一种容斥的方法。自认为更加简单易懂...

2020-01-16

2 563

CSP2019游记

Day-1 晚上按照惯例举行了送行仪式，吃了断头餐，然后就互抹吃蛋糕以示祝福。自己蛋糕太少了一口就吃完了，然后就只能静待被抹。。。然后xky送我了一大块奶油，然后，嘿嘿嘿~ 。拿着我新缴获的“弹药”一路往卫生间走，迎面走来个刚洗完脸的。 “洗干净了么？” ”嗯“ ”我看看“，然后趁其不备再抹一把。...

2020-01-16

2 907

笛卡尔树

定义所谓笛卡尔树，就是将给定的个二元组建成一棵树。使得如果只关注，那么这是一个堆。如果只关注,那么这是一棵二叉搜索树。有没有很像。与不同的是，笛卡尔树是可以在时间内构建的。而且如果给定key,那么是可以被卡成一条链的。构造以小根堆为例。借助栈来完成。先按照val从小到大排序。然后用...

2019-07-19

0 709

noip2018游记

Day0 路上紧张到不行。特别担心今年会挂掉。 Day1 一塌糊涂T1似乎是积木大赛的原题。当时只用了个分治的做法在洛谷上水过去了。考场上发现能被卡成T2看了很久只好写了个exgcd，最后10分钟发现是个完全背包。哎。写完过不了大样例啊啊啊。果断删掉，又不小心把iostream库改了，只好用g++手...

2019-07-19

0 462

SDOI2019游记

Rand1 Day0 一大早就起床，结果忙活了整整一上午。12：20从gryz出发，路上发现把耳机和笔忘另一个背包里了(都怪老爸非得让我换背包)，15：30差不多就到山师了。山师也是蛮漂亮的，花开得挺好。到处是牵着手的小情侣。啧啧啧~。恰逢清明，给他们烧柱香吧一时间难以表达内心的欢愉(第一次带着这...

2019-07-19

0 1508

vijos2055 移动金币

题目链接思路首先这是一个阶梯博弈。我们将金币两两组合，如果对方移动前一个，那么我们把后一个移动相同的距离，局面相当于没有变化。如果对方移动后一个，就相当于\(NIM\)游戏中，取走了一些石子。所以这个游戏也就是金币两两组合后，有\(\lceil \frac{m}{2}\rceil\)...

2019-05-15

0 586

POJ2096 Collecting Bugs

题目链接题意有n个bug和s个系统。每天会等概率的在某个系统中找一个某一个bug。问找到全部n个bug并且在每个系统中都找到bug的期望天数。思路 f[i][j]表示在j个系统中找到了i个bug的期望天数。某天有四种可能： 1.在新的系统中找到新的bug，概率为\(\frac{(n...

2019-05-14

0 481

noi.ac89A 电梯

题目思路首先按照\(t\)排序！！！！首先考虑一个暴力\(dp\) 用\(f[i]\)表示前\(i\)个人到达地点所需要的时间。那么就有如下的转移 \[f_i = min_{1 \le j \le i}(max(f_j,t_i) + max\{w_{j + 1} ... w_...

线段树动态规划dp

2019-03-24

0 506

CDQ分治

$cdq$分治主要思想就是将操作离线下来，然后分治之后统计二分之后，左边的修改对于右边查询的贡献。可以顶替很多复杂的数据结构。学会下面这几类问题差不多就会$cdq$了。个人认为看代码比较容易学。二维偏序先考虑这样一类问题给出n个二元组$(a,b)$，求出有多少对$i,j$满...

CDQ分治

2019-02-15

0 444

bzoj3829 POI2014 FAR-FarmCraft

题目链接思路用\(f[i]\)表示完成第\(i\)棵子树所需要得时间。考虑如果有两个子树\(a\)和\(b\),如果先去完成子树\(a\)，那么对于花费得时间就是\(f[b] + siz[a] \times 2 + 1\) 所以如果有先遍历\(a\)更优秀的话。那么一定有\(f[b] + ...

贪心

2019-02-13

0 527