• [HDU3031]To Be Or Not To Be(可并堆,左偏树)

    [HDU3031]To Be Or Not To Be(可并堆,左偏树)

    DescriptionThat'saquestion.NowHappy(XiYangyang)hasbeencaughtbyWolffy(HuiTailang).AsWolffyisbusypreparingthebigmeal,agoodideacomestoHappy.HeproposesagamethatonlyWolffyhadwon,hecaneatHappy.Wolffyalwaysbelievesheisthecleverestone,sotheyreachaconsensus.AndtheybothagreewithWolnie(HongTailang)whenthereferee.AtheaterwillbebeattodiebyWolnie'span.Thegameisdefinedasfollow.Therearemul...

    02018年2月18日5左偏树,HDU,可并堆
  • [HDU5818]Joint Stacks(可并堆,左偏树)

    [HDU5818]Joint Stacks(可并堆,左偏树)

    DescriptionAstackisadatastructureinwhichallinsertionsanddeletionsofentriesaremadeatoneend,calledthe"top"ofthestack.Thelastentrywhichisinsertedisthefirstonethatwillberemoved.Inanotherword,theoperationsperforminaLast-In-First-Out(LIFO)manner.Amergeablestackisastackwith"merge"operation.Therearethreekindsofoperationasfollows:-pushAx:insertxintostackA-popA:removethetopelementofstackA-...

    02018年2月18日4左偏树,HDU,可并堆
  • [HDU5709]Claris Loves Painting(线段树合并,主席树)

    [HDU5709]Claris Loves Painting(线段树合并,主席树)

    DescriptionClarislovespaintingverymuch,sohepaintedatreewithbeautifulcolors.Thetreeisarootedtreewithnnodeswhichareconvenientlylabeledby1,2,...,n.Itsrootisthe1-stnode,andthei-thnodeispaintedwithcolorci.Ifci=cj,thenwethinkthesetwonodeshavethesamecolor.Wedefinedepthiasthedistancebetweenthei-thnodeandtheroot,andsimply,thedistancebetweentwoadjacentnodesisalways1.Standinginfrontofthisbeautifultree...

  • [BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)

    [BZOJ4071/Luogu3644][Apio2015]巴邻旁之桥 (线段树,数论,离散化)

    Description一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域A和区域B。每一块区域沿着河岸都建了恰好1000000001栋的建筑,每条岸边的建筑都从0编号到1000000000。相邻的每对建筑相隔1个单位距离,河的宽度也是1个单位长度。区域A中的i号建筑物恰好与区域B中的i号建筑物隔河相对。城市中有N个居民。第i个居民的房子在区域Pi的Si号建筑上,同时他的办公室坐落在Qi区域的Ti号建筑上。一个居民的房子和办公室可能分布...

    02018年2月17日13线段树,APIO,离散化,BZOJ,Luogu
  • [BZOJ2809/Luogu1552][Apio2012]dispatching(可并堆,左偏树,贪心)

    [BZOJ2809/Luogu1552][Apio2012]dispatching(可并堆,左偏树,贪心)

    Description在一个忍者的帮派里,一些忍者们被选中派遣给顾客,然后依据自己的工作获取报偿。在这个帮派里,有一名忍者被称之为Master。除了Master以外,每名忍者都有且仅有一个上级。为保密,同时增强忍者们的领导力,所有与他们工作相关的指令总是由上级发送给他的直接下属,而不允许通过其他的方式发送。现在你要招募一批忍者,并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水,同时使得支付的薪水总额不超过你...

  • [BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)

    [BZOJ1801/Luogu2051][Ahoi2009]chess 中国象棋(动态规划)

    Description在N行M列的棋盘上,放若干个炮可以是0个,使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法,中国像棋中炮的行走方式大家应该很清楚吧.HttpBZOJLuoguTag动态规划解决思路考虑中国象棋中炮的攻击方式,发现其实就是要求任意一行或任意一列不能摆放超过两个炮。并且我们发现,每一个炮具体摆的位置不影响最后的结果,只贡献组合数。那么我们枚举行,考虑列。设\(F[i][j][k]\)表示当前处理到...

  • [BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)

    [BZOJ1087/Luogu1896][SCOI2005]互不侵犯King(动态规划,状态压缩)

    Description在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。HttpBZOJLuoguTag动态规划,状态压缩解决思路设\(F[i][j][S]\)表示处理到第\(i\)行,当前摆放了\(j\)个国王,当前行状态为\(S\)的方案数,枚举上一行的合法方案累加转移即可。为了方便,可以先预处理出某一行每一...

  • [BZOJ4003/Luogu3261][JLOI2015]城池攻占(可并堆,左偏树)

    [BZOJ4003/Luogu3261][JLOI2015]城池攻占(可并堆,左偏树)

    Description小铭铭最近获得了一副新的桌游,游戏中需要用m个骑士攻占n个城池。这n个城池用1到n的整数表示。除1号城池外,城池i会受到另一座城池fi的管辖,其中fii。也就是说,所有城池构成了一棵有根树。这m个骑士用1到m的整数表示,其中第i个骑士的初始战斗力为si,第一个攻击的城池为ci。每个城池有一个防御值hi,如果一个骑士的战斗力大于等于城池的生命值,那么骑士就可以占领这座城池;否则占领失败,骑士将在这座城池牺牲。...

  • 后缀自动机的一点点理解 by yyb

    后缀自动机的一点点理解 by yyb

    后缀自动机的一点点理解潜在可能格式挂了,yyb博客地址前言最近心血来潮,想学学SAM,于是花了一晚上+一上午勉强打了出来(但是还是不理解)虽说张口就讲我做不到但是一些其他的东西还是有所感触的索性,乱口胡点东西,谢谢关于SAM的一些简单的理解资料丽洁姐WCPPThihocoder上的后缀自动机一些概念这些概念都不读懂,接下来真的是步履维艰本来我们要的是一个能够处理所有后缀的数据结构但是我们发现,如果对于每一个后缀...

  • [BZOJ3140/Luogu3231][Hnoi2013]消毒(二分图)

    [BZOJ3140/Luogu3231][Hnoi2013]消毒(二分图)

    Description最近在生物实验室工作的小T遇到了大麻烦。由于实验室最近升级的缘故,他的分格实验皿是一个长方体,其尺寸为a*b*c,a、b、c均为正整数。为了实验的方便,它被划分为a*b*c个单位立方体区域,每个单位立方体尺寸为1*1*1。用(i,j,k)标识一个单位立方体,1≤i≤a,1≤j≤b,1≤k≤c。这个实验皿已经很久没有人用了,现在,小T被导师要求将其中一些单位立方体区域进行消毒操作(每个区域可以被重复...

    02018年2月11日35二分图,各省省选,BZOJ,Luogu
  • [BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)

    [BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)

    Description申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N天才能完成,其中第i天至少需要Ai个人。布布通过了解得知,一共有M类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天,招募费用是每人Ci元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,...

    02018年2月11日34网络流,NOI,BZOJ,Luogu
  • [SNMOJ280]Atom-wwt by dsl

    [SNMOJ280]Atom-wwt by dsl

    Description题面Solution考虑到一个串是一个子串的情况只可能是他在\(fail\)树上的祖先或者是回文树上的祖先。所以把回文树和\(fail\)树拼在一起,每次二分最大权值,跑最长反链覆盖,判断覆盖数是否大于等于\(k\)即可。[crayon-5a8a835353a50031970004/]...

    02018年2月10日33回文树,网络流,图论,字符串
  • [HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)

    [HDU1512/ZOJ2334/SCU3080/Luogu1456]Monkey King(左偏树,并查集)

    DescriptionOnceinaforest,therelivedNaggressivemonkeys.Atthebeginning,theyeachdoesthingsinitsownwayandnoneofthemknowseachother.Butmonkeyscan'tavoidquarrelling,anditonlyhappensbetweentwomonkeyswhodoesnotknoweachother.Andwhenithappens,boththetwomonkeyswillinvitethestrongestfriendofthem,andduel.Ofcourse,aftertheduel,thetwomonkeysandalloftherefriendsknowseachother,andthequarrelabovewillnolongerh...

  • [BZOJ3993/Luogu3324][SDOI2015]星际战争(网络流,二分)

    [BZOJ3993/Luogu3324][SDOI2015]星际战争(网络流,二分)

    Description3333年,在银河系的某星球上,X军团和Y军团正在激烈地作战。在战斗的某一阶段,Y军团一共派遣了N个巨型机器人进攻X军团的阵地,其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时,这个巨型机器人就被摧毁了。X军团有M个激光武器,其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这种激光武器非常奇怪,一个激光武器只能攻击一些特定的敌人。Y...

  • [BZOJ4554/Luogu2825][Tjoi2016&Heoi2016]游戏(网络流,二分图)

    [BZOJ4554/Luogu2825][Tjoi2016&Heoi2016]游戏(网络流,二分图)

    Description在2016年,佳缘姐姐喜欢上了一款游戏,叫做泡泡堂。简单的说,这个游戏就是在一张地图上放上若干个炸弹,看是否能炸到对手,或者躲开对手的炸弹。在玩游戏的过程中,小H想到了这样一个问题:当给定一张地图,在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列,炸弹的威力可以穿透软石头,但是不能穿透硬石头。给定一张n*m的网格地图:其中*代表...

1 / 6 1 2 3 ...6 下一页 »