2017年9月

BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节

题目描述输入Line 1: 牛的数量 N。Lines 2..N+1: 第 i+1 是一个整数,表示第i头牛的高度。输出Line 1: 一个整数表示c[1] 至 c[N]的和。样例输入6 10 3 7 4 12 2样例输出5代码#include <cstdio> #include <algorithm> using namespace std; const int N = 90001; int a[N], s[N], tp; int sum[N]; int main() { //freopen("input", "- 阅读剩余部分 -

BZOJ 1677: [Usaco2005 Jan]Sumsets 求和

题目描述给出一个N(1≤N≤10^6),使用一些2的若干次幂的数相加来求之.问有多少种方法输入一个整数N.输出方法数.这个数可能很大,请输出其在十进制下的最后9位.样例输入7样例输出6题解当一个数 n 是奇数,可以拆分成前一个偶数 n-1 加上个 1,所以 f[n] = f[n-1]当一个数 n 是偶数,如果它拆分含有 1,拆分方案应该是 f[n-1]如果没有 1,拆分方案应该是 f[n/2]代码#include <cstdio> #include <algorithm> using namespace std; const int N = 1000- 阅读剩余部分 -

BZOJ 1657: [Usaco2006 Mar]Mooo 奶牛的歌声

题目描述Farmer John的N(1<=N<=50,000)头奶牛整齐地站成一列“嚎叫”。每头奶牛有一个确定的高度h(1<=h<=2000000000),叫的音量为v (1<=v<=10000)。每头奶牛的叫声向两端传播,但在每个方向都只会被身高严格大于它的最近的一头奶牛听到,所以每个叫声都只会 被0,1,2头奶牛听到(这取决于它的两边有没有比它高的奶牛)。 一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后,Farmer John打算买一个耳罩给被残害得最厉 害的奶牛,请你帮他计算最大的总音量。输入第1行:一个- 阅读剩余部分 -

BZOJ 1611: [Usaco2008 Feb]Meteor Shower流星雨

题目描述去年偶们湖南遭受N年不遇到冰冻灾害,现在芙蓉哥哥则听说另一个骇人听闻的消息: 一场流星雨即将袭击整个霸中,由于流星体积过大,它们无法在撞击到地面前燃烧殆尽, 届时将会对它撞到的一切东西造成毁灭性的打击。很自然地,芙蓉哥哥开始担心自己的 安全问题。以霸中至In型男名誉起誓,他一定要在被流星砸到前,到达一个安全的地方 (也就是说,一块不会被任何流星砸到的土地)。如果将霸中放入一个直角坐标系中, 芙蓉哥哥现在的位置是原点,并且,芙蓉哥哥不能踏上一块被流星砸过的土地。根据预 报,一共有M颗流星(1 <= M <= 50,000)会坠落在霸中上,其中第i颗流星会在- 阅读剩余部分 -

BZOJ 2834: 回家的路

题目描述输入输出样例输入2 1 1 2 1 1 2 2样例输出5提示N<=20000, M<=100000题解这是一道分层图最短路的题,把横向路线和纵向路线分别建两层图,然后两层图对应的中转站连一条权值为 1 的边,两个可以横竖相互到达的中转站连一条权值为距离的边,把起点和终点也连上可以到达的中转站,然后跑一边最短路就行了。代码#include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std;- 阅读剩余部分 -

BZOJ 1068: [SCOI2007]压缩

题目描述给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没有M,则从串的开始算起)开始的解压结果(称为缓冲串)。 bcdcdcdcd可以压缩为bMcdRR,下面是解压缩的过程另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。输入输入仅一行,包含待压缩字符串,仅包含小写字母,长度为n。输出输出仅一行,即压缩后字符串的最短长度。样例输入bcdcdcdcdxcdcdcdcd样例输出12提示在第一个- 阅读剩余部分 -

洛谷 P1040 加分二叉树

题目描述设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;(1)tree的最高加分(2)tree的前序遍历输入- 阅读剩余部分 -

BZOJ 4419: [Shoi2013]发微博

题目描述刚开通的SH微博共有n个用户(1..n标号),在短短一个月的时间内,用户们活动频繁,共有m条按时间顺序的记录:! x 表示用户x发了一条微博; + x y 表示用户x和用户y成为了好友 - x y 表示用户x和用户y解除了好友关系当一个用户发微博的时候,所有他的好友(直接关系)都会看到他的消息。假设最开始所有人之间都不是好友关系,记录也都是合法的(即+ x y时x和y一定不是好友,而- x y时x和y一定是好友)。问这m条记录发生之后,每个用户分别看到了多少条消息。输入第1行2个整数n,m。接下来m行,按时间顺序读入m条记录,每条记录的格式如题目所述,用空格隔开- 阅读剩余部分 -

BZOJ 3401: [Usaco2009 Mar]Look Up 仰望

题目描述约翰的N(1≤N≤105)头奶牛站成一排,奶牛i的身高是Hi(l≤Hi≤1,000,000).现在,每只奶牛都在向后看齐.对于奶牛i,如果奶牛j满足i<j且Hi<Hj,我们可以说奶牛i可以仰望奶牛j. 求出每只奶牛离她最近的仰望对象.输入第1行输入N,之后每行输入一个身高.N <= 10^5输出共N行,按顺序每行输出一只奶牛的最近仰望对象.如果没有仰望对象,输出0.样例输入6326112样例输出330660题解裸的单调栈,维护一个不下降的单调栈,遇到比当前高度小的弹栈就行了。代码#include <cstdio> #include- 阅读剩余部分 -

【NOIP模拟赛】Nim 游戏·改、聚会、历史

前言又是一个模拟赛,再一次爆炸。T1 Nim 游戏·改(nim.c/cpp/pas)题目描述众所周知的 Nim 游戏是这样的:有 n 堆石子,小 A 和小 B 轮流取石子,小 A 先操作,每次选择一堆石子,在这堆中取走任意多个石子,最后没有石子可取的人输。现在为了加强Nim 游戏难度,每堆非空石子有一次额外的特殊机会,即耗掉这个机会,然后什么也不拿走,而其他条件都不变。当然,如果你将一堆本来有额外机会的石子拿空,那么这次额外机会也就没有了。现在假设小 A 和小 B 都绝顶聪明,他们将进行 T 轮游戏。每轮游戏若小 A 必胜,输出“A”,否则输出“B”。输入格式第一行为一个整- 阅读剩余部分 -

BZOJ 1015: [JSOI2008]星球大战starwar

题目描述很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。 但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反抗军首领交给你一个任务:给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。(如果两个星球可以通过现存的以太- 阅读剩余部分 -

BZOJ 3083: 遥远的国度

题目描述zcwwzdjn在追杀十分sb的zhx,而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时,守护神RapiD阻拦了zcwwzdjn的去路,他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。问题是这样的:遥远的国度有n个城市,这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都,我们可以把这个首都看做整棵树的根,但遥远的国度比较奇怪,首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值,有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候,如果把首都看- 阅读剩余部分 -

BZOJ 3626: [LNOI2014]LCA

题目描述给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)输入第一行2个整数n q。接下来n-1行,分别表示点1到点n-1的父节点编号。接下来q行,每行3个整数l r z。输出输出q行,每行表示一个询问的答案。每个答案对201314取模输出样例输入5 200111 4 31 4 2- 阅读剩余部分 -