• 【bzoj2819】Nim

    【bzoj2819】Nim

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

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

    NOI2011阿狸的打字机

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

    32014年12月6日3,713dfs序,AC自动机,树状数组
  • 【bzoj3289】Mato的文件管理

    【bzoj3289】Mato的文件管理

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

    32014年12月3日2,554树状数组,莫队算法
  • 【bzoj1145】[CTSC2008]图腾totem

    【bzoj1145】[CTSC2008]图腾totem

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

    12014年12月2日1,895树状数组
  • 【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日1,373树状数组
  • 【NOIP模拟赛】弱点

    【NOIP模拟赛】弱点

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

    02014年11月4日946树状数组
  • 【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日870树状数组
  • 【bzoj1106】[POI2007]立方体大作战tet

    【bzoj1106】[POI2007]立方体大作战tet

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

    02014年10月11日1,107树状数组
  • 【bzoj3192】[JLOI2013]删除物品

    【bzoj3192】[JLOI2013]删除物品

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

    02014年8月13日1,108树状数组
  • 【bzoj1935】[Shoi2007]Tree 园丁的烦恼

    【bzoj1935】[Shoi2007]Tree 园丁的烦恼

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

    12014年8月6日1,883树状数组,离线处理
  • 【czy系列赛】czy的后宫3

    【czy系列赛】czy的后宫3

    czy的后宫3【题目描述】上次czy在机房妥善安排了他的后宫之后,他发现可以将他的妹子分为c种,他经常会考虑这样一个问题:在[l,r]的妹子中间,能挑选出多少不同类型的妹子呢?注意:由于czy非常丧尸,所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数,你懂得。问题简述:n个数,m次询问,每次问[l,r]区间有多少个数恰好出现正偶数次【输入格式】第一行3个整数,表示n,c,m第二行n个数,每个数Ai在[1,c]之间,表示一个Ai类型...

    42014年7月19日2,394树状数组,离线处理,莫队算法
  • 【bzoj3688】【FJ2014集训】折线统计

    【bzoj3688】【FJ2014集训】折线统计

    【题目描述】二维平面上有n个点(xi,yi),现在这些点中取若干点构成一个集合S,对它们按照x坐标排序,顺次连接,将会构成一些连续上升、下降的折线,设其数量为f(S)。如下图中,1->2,2->3,3->5,5->6(数字为下图中从左到右的点编号),将折线分为了4部分,每部分连续上升、下降。现给定k,求满足f(S)=k的S集合个数。【输入格式】第一行两个整数n和k,以下n行每行两个数(xi,yi)表示第i个点的坐标。所有点的坐标值都在...

    02014年7月13日1,226递推与动规,树状数组
  • 【bzoj3262】陌上花开

    【bzoj3262】陌上花开

    Description有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input第一行为N,K(1<=N<=100,000,1<=K<=200,000),分别表示花的数量和最大属性值。以下N行,每行三个整数...

    02014年6月19日3,478treap,树套树,树状数组