• 「codechefFNCS」Chef and Churu

    「codechefFNCS」Chef and Churu

    题解分块水过将函数分块,每一块大小√n,预处理一块内的函数统计每一个数字的次数,以及这一块的答案这一部分n√n并用树状数组维护a的前缀和,线段树呵呵。。。对于询问将整块的答案加起来,其余部分的每个函数在树状数组中查询对于修改修改树状数组依照每一个数字在每一块的次数,更新每一块的答案这一部分n√nlogn若理论分析似乎分块设小会更优,但若考虑下常数会发现好像并不会。。。注意本题要用unsignedlonglong还有一个很牛...

    02014年12月18日2,176分块,树状数组
  • 「BZOJ3790」神奇项链

    「BZOJ3790」神奇项链

    Description母亲节就要到了,小H准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串,每个小写字母表示一种颜色。为了制作这个项链,小H购买了两个机器。第一个机器可以生成所有形式的回文串,第二个机器可以把两个回文串连接起来,而且第二个机器还有一个特殊的性质:假如一个字符串的后缀和一个字符串的前缀是完全相同的,那么可以将这个重复部分重叠。例如:aba和aca连接起来,可以生成串abaaca或abaca。...

    02014年12月11日3,143树状数组,manacher
  • 「BZOJ2819」Nim

    「BZOJ2819」Nim

    Description著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。为了设计漂亮一点的初始局面,vfleaking用以下方式来找灵感:拿出很多石子,把它们聚成一堆一堆的,对每一堆编号1,2,3,4,...n,在堆与堆间连边,没有自环与重边,从任意堆...

    82014年12月9日4,631dfs序,树状数组,博弈论
  • NOI2011阿狸的打字机

    NOI2011阿狸的打字机

    Description 阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现,这个打字机是这样工作的:l输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。l按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消...

    32014年12月6日7,302dfs序,AC自动机,树状数组
  • 「BZOJ3289」Mato的文件管理

    「BZOJ3289」Mato的文件管理

    DescriptionMato同学从各路神犇以各种方式(你们懂的)收集了许多资料,这些资料一共有n份,每份有一个大小和一个编号。为了防止他人偷拷,这些资料都是加密过的,只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r],他今天就看编号在此区间内的这些资料。Mato有一个习惯,他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来,再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内...

    42014年12月3日4,429树状数组,莫队算法
  • 「BZOJ1145」[CTSC2008] 图腾totem

    「BZOJ1145」[CTSC2008] 图腾totem

    Description在完成了古越州圆盘密码的研究之后,考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落,一个部落崇拜闪电,另一个部落崇拜高山,他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画,壁画上被标记出了N个点,经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关,因此不妨设坐标分别为(1,y...

    12014年12月2日2,886树状数组
  • 「BZOJ2789」letters

    「BZOJ2789」letters

    Description给出两个长度相同且由大写英文字母组成的字符串A、B,保证A和B中每种字母出现的次数相同。现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B。Input第一行一个正整数n(2<=n<=1,000,000),表示字符串的长度。第二行和第三行各一个长度为n的字符串,并且只包含大写英文字母。Output一个非负整数,表示最少的交换次数。SampleInput3ABCBCASampleOutput2HINTABC->...

    02014年11月11日2,166树状数组
  • 「NOIP模拟赛」弱点

    「NOIP模拟赛」弱点

    「题目描述」一队勇士正在向你进攻,每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点,如果存在i<j<k使得ai>aj>ak,则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。「输入」输入文件:weakness.in输入的第一行是一个整数n,表示勇士的数目。接下来一行包括n个整数,表示每个勇士的战斗值ai。「输出」输入文件:weakness.out输出为一行,包含一个整数。...

    12014年11月4日1,582树状数组
  • 「codecomb2097」rect

    「codecomb2097」rect

    Description在一个n*m的格子棋盘上,有n*m堆石子,现在有两种操作:1、给(x1,y1)->(x2,y2)这个矩形内所有的石子堆加入k个石子。1<=x1<=x2<=n,1<=y1<=y2<=m。2、询问某格(x,y)上面有多少石子。Input第一行两个整数n和m,分别表示棋盘的长宽,n对应上述的x轴,m对应y轴。第二行一个整数p,表示操作数量。以下p行,首先一个是整数t,t=1或2,表示是哪种操作。 如果t=1,则后面跟5个整数x1,y1,x2,y2,k,如上所...

    02014年10月16日1,295树状数组
  • 「BZOJ1106」[POI2007] 立方体大作战tet

    「BZOJ1106」[POI2007] 立方体大作战tet

    Description一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有2n个元素的栈,元素一个叠一个地放置。这些元素拥有n个不同的编号,每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同,则将他们都从栈中移除,所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除...

    02014年10月11日1,644树状数组
  • 「BZOJ3192」[JLOI2013] 删除物品

    「BZOJ3192」[JLOI2013] 删除物品

    Description箱子再分配问题需要解决如下问题: (1)一共有N个物品,堆成M堆。 (2)所有物品都是一样的,但是它们有不同的优先级。 (3)你只能够移动某堆中位于顶端的物品。 (4)你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的,可以直接将之删除而不用移动。(5)求出将所有物品删除所需的最小步数。删除操作不计入步数之中。 (6)只是一个比较难解决的问题,这里你只...

    02014年8月13日1,553树状数组
  • 「BZOJ1935」[SHOI2007] Tree 园丁的烦恼

    「BZOJ1935」[SHOI2007] Tree 园丁的烦恼

    Description很久很久以前,在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者,在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里,若有所思,他问一个园丁道:“最近我在思索一个问题,如果我们把花坛摆成六个六角形,那么……”“那么本质上它是一个深度优先搜索,陛下”,园丁深深地向国王鞠了一躬。“嗯……我听说有一种怪物叫九头蛇,它非常贪吃苹果树……”“是的,显然这是一道经典的...

    12014年8月6日3,069树状数组,离线处理