【题解】NOIP2016愤怒的小鸟
一眼n<=18状压dp……方程什么的都很显然，枚举两只小鸟，再将这条抛物线上的小鸟抓出来就好啦。只是这样O(n^3)的dp必然是要TLE的，我一开始这样交上去显然跑得巨慢无比，后来转念一想：面对一个崭新的情况的时候，只有搭配的优劣之分，没有先后的区别，所以最外面的一层可以直接去掉，变成O(n^...
[Jzoj 4709]. 【NOIP2016提高A组模拟8.17】Matrix
Description InputSample Input 4 3 5 4 1 7 3 4 7 4 8 Output Sample Output 59716The Solution这是雅礼中学和我们学校的联考题呀。。上面给的那个dp可以理解成在一个网络上，只能向右，向下走，向下走的话，加上的贡献就要...
【NOIP2016】愤怒的小鸟
题目描述Kiana最近沉迷于一款神奇的游戏无法自拔。简单来说，这款游戏是在一个平面上进行的。有一架弹弓位于(0,0)处，每次Kiana可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如的曲线，其中a,b是Kiana指定的参数，且必须满足a<0。当小鸟落回地面(即x轴）时，它就会瞬间...
【NOIP2016提高A组模拟9.9】爬山
//真想把这道题@#@#@##$#@%#*啊！！！！！！！ Description国家一级爬山运动员h10今天获得了一张有着密密麻麻标记的地图，在好奇心的驱使下，他又踏上了去爬山的路。 对于爬山，h10有一个原则，那就是不走回头路，于是他把地图上的所有边都标记成了有向边。他决定从点S出发，每到达一个...
【NOIP2016提高A组模拟8.15】Garden
Input N个花园的形态 Output 对于每个花园，输出形态 Sample Input 2 3 2 X. .. .X 2 2 X. .. Sample Output 60 6 Solution 可以发现最多只能有8个X，所以就状压这8个X就行了 f[i][s]表示当前涂...
【noip2016】【洛谷P2827】蚯蚓
这个题只知道可以用优先队列去做，但是不知道正解想法，看到题解后恍然大悟，详情请看代码中间 #include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<...
【JZOJ4710】【NOIP2016提高A组模拟8.17】Value
题目描述 输入 输出 样例输入 5 8 2 10 7 5 1 11 8 13 3 样例输出 27 数据范围 解法 选定一些物品a[1],a[2],a[3]…a[num]，尝试交换a[i],a[j]，那么对答案的贡献是： -(v[i]-xsum)-(v...
[jzoj 4807]. 【NOIP2016提高A组五校联考3】破解
Input 第一行，一个整数T表示一共T组数据。 每组数据第一行，两个整数N，M，分别表示密码串长度和区间个数。 接下来M行，第i行两个整数Li,Ri表示一个区间[Li,Ri]。 Output 每组数据一行，一个整数表示所有的可能，答案对(10^9+7)取模。 Sample Inpu...
NOIP2016 “西湖边超萌小松鼠” 模拟赛
总的来说，这套题的难度比较接近近些年来Day1的真实难度，认为非常值得一打 GotoAndPlay 题目大意 询问这个图上是否存在一种跳法，能跳到这个图上的每一个点 题目解析 犯了个低级错误，双向边忘记*2，最后两个点RE了 因为题目告知是“跳两次”，所以很容易想到将这个图分成“奇数点”和“偶...
【NOIP2016模拟7.12】游戏
Description Input 这个地图 Output 对应的答案 Data Constraint n,m<=50 Solution 记得之前做过一道题：小行星带 这题也差不多，被#分开行当做不同的行，例如 * #**当做两行。列也同样处理。行和列相交的地方连边，求...
【JZOJ4819】【NOIP2016提高A组模拟10.15】算循环
题目描述 输入 输出 样例输入 167 198 样例输出 906462341 数据范围 解法 令 f(n)=∑ni=1i ， g(n)=∑ni=1i2 易得 ans=∑ni=1∑mj=1f(n−i+1)∗f(m−j+1) 等价...
16.10.7 A:4815. 【NOIP2016提高A组五校联考4】ksum
这道题目仔细想想就可以发现是一个堆，我们先做1~n的前缀和，然后我们把（1，n）放入堆，[a+1,b]和[a,b-1]才有可能成为下次取出的对 象，那么我就将[a+1,b]和[a,b-1]加进堆，这样重复 k 次即可,另外，如果每次都[a+1,b]和[a,b-1]加入堆，会得到重复的答案，...
【NOIP2016提高A组模拟9.15】Osu
题目Input Sample Input4 2 1 2 2 2 0 2 3 0 0 4 2 0 Output Sample Output1 2 1 样例解释： 圆圈只在出现的时刻有效。即：时刻t_i时鼠标位置恰好在(x_i,y_i)才能得分。 Kaguya所做的工作就是在这些时刻间移动鼠标。 对于样...
【JZOJ4815】【NOIP2016提高A组五校联考4】ksum
题目描述 输入 输出 样例输入 3 4 1 3 4 样例输出 8 7 4 4 数据范围 样例解释 解法 二分做法 考虑到可以二分第k大的值mid，如果比mid大的区间和数小于或等于mid，那么mid就合法。 找一个合法的最小mid就是我们要找的mid。 询问有多少个区间大于或等于mid...
JZOJ 4815 【NOIP2016提高A组五校联考4】ksum
ksum 题目大意 给出一个长度为 n 的数组，现在 求前 k 大的数。 数据范围 题解 我们将所有的数按照其对应区间的左端点来分类，那么一共会分成n类。 维护一个大小为 n 的堆，一个位置维护一个类别。 一开始将区间[ 1 ...
[JZOJ 4815]【NOIP2016提高A组五校联考4】ksum
Sample Input 样例输入1： 3 4 1 3 4 样例输入2： 3 3 10 2 7 Sample Output 样例输出1： 8 7 4 4 样例输出2： 19 12 10 The Solution 我们可以发现，如果当前最大的是[l,r]字段，那么易得[l,r+1]子段 和[l...
BZOJ4719 [Noip2016]天天爱跑步
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。 本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！ Description小c同学认为跑步非常有趣,于是决...
【NOIP2016提高A组五校联考4】ksum
题目 分析 发现，当子段[l,r]被取了出来，那么[l-1,r]、[l,r+1]一定也被取了出来。 那么，首先将[1,n]放入大顶堆，每次将堆顶的子段[l,r]取出来，因为它是堆顶，所以一定是最大的子段，输出它，并将[l+1,r]和[l,r-1]放进堆中。 一共就只用做k次就可以了。 ...
【NOIP2016提高A组五校联考4】ksum
Description Solution 这题不是明显的堆来模拟吗，然后在hash判个重就好了。 但是，这题要值得反思的是，我以前的人工堆有一个很致命的错误，就是堆顶退堆的时候，应该把堆底和堆顶交换，然后num–之后再down一下，这然才对，错误的就不说了。 还有一个问题就是：我不会用S...
ksum 【NOIP2016提高A组五校联考4】
题目 样例输入： 3 4 1 3 4 样例输出： 8 7 4 4 剖解题目 。。。。。。。。 思路 看到ai每个都是正整数，就立刻想到最大的肯定是全部，下一个肯定就是删掉头尾任意一个数后得到的子序列。 很明显是堆嘛。。。然而我几乎没有打过堆。QwQ。 我是正直的人，才不会用c++中的...