bzoj千题计划129：bzoj2007: [Noi2010]海拔
http://www.lydsy.com/JudgeOnline/problem.php?id=20071、所有点的高度一定在0~1之间，如果有一个点的高度超过了1，那么必定会有人先上坡，再下坡，一定不如一直上坡优2、所有点高度一定可以转化为非0即1比如：0->0.3->0.5->...
BZOJ1565: [NOI2009]植物大战僵尸
DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。Sample Input3 210 020 0-10 0-5 1 0 0100 1 2 1100 0Sample Output25HINT在样例中, 植物P1,...
Beta Round ＃9 (酱油杯noi考后欢乐赛)PLQ和他的小伙伴们
题目：http://www.contesthunter.org/contest/Beta%20Round%20%EF%BC%839%20%28%E9%85%B1%E6%B2%B9%E6%9D%AFnoi%E8%80%83%E5%90%8E%E6%AC%A2%E4%B9%90%E8%B5%9B%29/...
loj#2305. 「NOI2017」游戏 2-sat
链接https://loj.ac/problem/2305https://www.luogu.org/problemnew/show/P3825思路3-sat神马的就不要想了，NP问题除去x每个点只有两种可能，2-satx只有8个，\(3^n\)暴力枚举哪个不选2-sat是对称性的当起点x的战车不存...
【BZOJ2434-[Noi2011]】阿狸的打字机（AC自动机（fail树）+离线+树状数组）
Description阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l 按一下印有'B'的按...
BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)
BZOJ洛谷如果某天能够赚钱，那么一定会在这天把手上的金券全卖掉。同样如果某天要买，一定会把所有钱花光。那么令\(f_i\)表示到第\(i\)天所拥有的最多钱数（此时手上没有任何金券），可以选择什么都不干，\(f_i=f_{i-1}\)；也可以从之前的某一天\(j\)花\(f_j\)的钱买金券，在第...
【数论】【莫比乌斯反演】【线性筛】bzoj2005 [Noi2010]能量采集
http://blog.csdn.net/Clove_unique/article/details/51089272Key：1、连接平面上某个整点（a,b）到原点的线段上有gcd（a,b）个整点。2、欧拉函数的性质之一：若(N%a==0 && (N/a)%a==0) 则有:phi(N...
[BZOJ]4199 品酒大会(Noi2015)
讲道理是后缀数组裸题吧，虽然知道后缀数组的原理但是小C不会写是什么鬼。。小C趁着做这题的当儿，学习了一下后缀数组。网络上的后缀数组模板完全看不懂怎么破，全程照着黄学长的代码抄，感觉黄学长写得还是很优雅的。求LCP的部分已经崩坏了，小C自己脑补的做法是。。倍增？？看到正确的写法之后小C内心是绝望的，大...
【BZOJ】【2005】【NOI2010】能量采集
欧拉函数玛雅，我应该先看看JZP的论文的……贾志鹏《线性筛法与积性函数》例题一这题的做法……仔细想下可以得到：$ans=2*\sum_{a=1}^n\sum_{b=1}^m gcd(a,b)-n*m$那么重点就在于算$\sum_{a=1}^n\sum_{b=1}^m gcd(a,b)$这个东西cop...
BZOJ5418 NOI2018屠龙勇士（excrt）
显然multiset求出每次用哪把剑。注意到除了p=1的情况，其他数据都保证了ai<pi，于是先特判一下p=1。比较坑的是还可能存在ai=pi，稍微考虑一下。剩下的部分即解bix≡ai(mod pi)方程组。没有保证模数互质，于是excrt一发。excrt实际上就是不停exgcd合并两个方程。...
[BZOJ4200][Noi2015]小园丁与老司机
4200: [Noi2015]小园丁与老司机Time Limit: 20 Sec Memory Limit: 512 MBSec Special JudgeSubmit: 106 Solved: 58[Submit][Status][Discuss]Description小园丁 Mr. S 负...
BZOJ1565 [NOI2009]植物大战僵尸（拓扑排序 + 最大权闭合子图）
题目Sourcehttp://www.lydsy.com/JudgeOnline/problem.php?id=1565DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。Sample Input3 210 02...
【NOI2018】
总之国赛已经过了1个月了。感谢北大当初给我的一本约救我狗命，不然国赛就要没学上了。铜牌倒数十多名，我觉得我也是混到了一种境界。虽然对于集训队已经失去梦想，但是，Day1全场堪称最低的21分，也是有点过分了吧？多组数据，万万没想到啊……我简直石乐志，雅礼考了10天的捆绑，让我以为全世界都是捆绑？还是我...
NOI2005维修数列 splay
好题，错了不知道多少遍。这题其他几个操作都是比较经典的，多了一个最大子序列的。这时候对于当前的区间，最大子序列，可能使左区间的最值，可能是右区间的最值，也可能是整个区间的。所以维护lx[],rx[],mx[]。lx[rt] = max(lx[l],sum[l]+key[rt]+max(0,lx[r]...
解题：NOI 2010 航空管制
题面常见的套路与不常见的套路第一问是常见的套路，建反边用优先队列跑拓扑排序第二问是不常见的套路，如何判断一个点最早什么时候起飞？先不加它来拓扑排序，直到拓扑排序不能进行下去了，这个时刻就是它必须加入的时刻。因为我们是反着做的，所以这样求出来的就是最早时刻。 // luogu-judger-enabl...
【BZOJ 1503】[NOI2004]郁闷的出纳员
【链接】 我是链接,点我呀:) 【题意】在这里输入题意【题解】因为所有人工资同时递减。所以可以设置一个变化值delta.然后每个人的初始值为k则把k-delta加入伸展树中。会发现delta变化之后。伸展树中每个人的工资就仍然是原先的值+delta比如I 2000delta = 100则会插入一...
bzoj 1503[NOI 2004] 郁闷的出纳员
题目大意：给4种操作I：添加一个员工工资信息A：增加所有员工的工资S：减少所有员工的工资F：询问工资第k高的员工的工资情况自己做的第一道splay树的题目，初学找找感觉 #include <cstdio> #include <cstring> #include <ios...
【BZOJ】【1503】 【NOI2004】郁闷的出纳员
SplaySplay的模板题吧……妥妥的序列操作= =（好像有段时间没写过这种纯数据结构题了……） /************************************************************** Problem: 1503 User: Tunix ...
NOI 2004 郁闷的出纳员
DescriptionOIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们...
数据结构（跳跃表）：NOI 2004 郁闷的出纳员
郁闷的出纳员【问题描述】OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他...