• 2016 ACM/ICPC Asia Regional Dalian Online

    2016 ACM/ICPC Asia Regional Dalian Online

    1002DifferentGCDSubarrayQuery问长为n的序列,m个询问,问区间[L,R]所有子段的不同gcd值个数考虑固定左端点,随着右端点的移动,gcd至多衰减log次(每次至少折半)从n开始添加询问的左端点,用树状数组维护每个gcd右端点的最小值[crayon-5881c123bbb76306034916/]1007FriendsandEnemiesn个人,每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...

  • 【NOI考前欢乐赛】[bzoj3648]小奇泛舟

    【NOI考前欢乐赛】[bzoj3648]小奇泛舟

    【题目背景】微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》【问题描述】小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美,名花异石甚多,小奇在地图上标记了n处景观(标号从1到n),有些景观通过溪流连接,这样的溪流有m段。小奇想知道,有多少种泛舟的路径,经过的景观数大于等于K呢?(小奇不喜欢一次泛舟重复经过一个景观)【输入格式】第一行包括3个整数,n,m,K。接下来m行,每行2个整...

    82016年6月26日2,394点分治,树状数组
  • 【NOI考前欢乐赛】小奇遐想

    【NOI考前欢乐赛】小奇遐想

    【题目背景】撷来一缕清风飘渺方知今日书信未到窗外三月天霁垂柳新长枝条风中鸟啼犹带欢笑——《清风醉梦》【问题描述】小奇望着青天中的悠悠白云,开始了无限的遐想,在它的视野中,恰好有n朵高度不同的白云排成一排,他想从左到右选出四朵白云a,b,c,d,使得h_a<h_b<h_d<h_c,即看起来像是彩虹的形状!它想知道有多少种方案数。【输入格式】第一行包括1个整数n。第二行包括n个整数,第i个正数表示h_i,保证这n个整数是...

    12016年6月26日1,322树状数组
  • 【省选模拟赛】小奇的糖果

    【省选模拟赛】小奇的糖果

    原题:EAST!模拟赛RoundXV呓语【题目背景】小奇不小心让糖果散落到了地上,它对着满地的彩色糖果胡思乱想。【问题描述】有N个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。【输入格式】包含多组测试数据,第一行输入一个正整数T表示测试数据组数。接下来T组测试数据,对于每组测试数据,第一行输入两个正整数N、K,分别表...

    02015年11月22日952链表,树状数组
  • 【cf540X】Codeforces Round #301 (Div. 2)

    【cf540X】Codeforces Round #301 (Div. 2)

    A.CombinationLock模拟[crayon-5881c123c2454450492422/]B.SchoolMarks塞一堆中位数,特判什么的[crayon-5881c123c2462322446828/]C.IceCave深搜连通性,出点入度特判[crayon-5881c123c246b237472062/]D.BadLuckIsland期望dp+记忆化[crayon-5881c123c247c971596911/]E.InfiniteInversions离散树状数组乱搞[crayon-5881c123c2485210263246/] ...

  • 【bzoj3932】[CQOI2015]任务查询系统

    【bzoj3932】[CQOI2015]任务查询系统

    好好的一道主席树题我写成了树状数组套主席树TT原因是为了练习模板(一开始根本没想。。。)TTbzoj16s通过,倒数第二是9s。。。多个log萌萌哒[crayon-5881c123c2ae4343531723/]  ...

    52015年4月8日2,474主席树,树状数组
  • 【codechef】January Lunchtime 2015

    【codechef】January Lunchtime 2015

    Pieceofcake 统计每个字母出现次数,取最大值,判断其是否等于l/2[crayon-5881c123c4e5d544053680/]Justmultiply 乘法快速乘即可,但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。发现a^(10b+c)=(a^b)^10*a^c然后就能On算出表达式了^10可以看做常数[crayon-5881c123c4e70484123532/]Candidatewalk状压一下,转移显然[crayon-5881c123c4e7a541871454/]Manybananas这一题比较有意思将宗族大小分为<=300和>300用数组统...

  • 【fjwc2015】Screen

    【fjwc2015】Screen

    【题目描述】码农有一块超新星屏幕,它有N个像素点,每个像素点有亮度和灰度两个参数,记为I和H,范围都是0~32000.一天,码农突发奇想,想知道哪个点比较容易亮瞎眼睛。为此,他定义了一个瞎眼指数:瞎眼指数就是灰度和亮度均不大于该像素点的像素个数。现在,码农希望知道,瞎眼指数为0~N-1的像素点分别有多少个 【输入格式】第一行一个数字N,代表有N个像素点。接下来N行,每行两个数字,代表该像素点的亮度和灰度。N个...

    02015年2月3日710树状数组
  • 【bzoj2738】矩阵乘法

    【bzoj2738】矩阵乘法

    Description  给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。Input  第一行两个数N,Q,表示矩阵大小和询问组数;接下来N行N列一共N*N个数,表示这个矩阵;再接下来Q行每行5个数描述一个询问:x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。Output  对于每组询问输出第K小的数。SampleInput2221341212111223SampleOutput13HINT  矩阵中数...

    12015年1月7日1,700二分法,树状数组
  • 【bzoj2527】[Poi2011]Meteors

    【bzoj2527】[Poi2011]Meteors

    DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...

    32015年1月7日1,701二分法,树状数组
  • 【codechefFNCS】Chef and Churu

    【codechefFNCS】Chef and Churu

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

    02014年12月18日1,134分块,树状数组
  • 【bzoj3790】神奇项链

    【bzoj3790】神奇项链

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

    12014年12月11日1,537树状数组,manacher
  • 【bzoj2819】Nim

    【bzoj2819】Nim

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

    102014年12月9日2,190dfs序,树状数组,博弈论
1 / 4 1 2 3 4 下一页 »