下一页 »Current position : 首页 >> 树状数组
程序设计实习实验班2017作业（算法 作业19, 20, 21）
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-5994bb7b6ea03795442041/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-5994bb7b6ea11500802634/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-5994bb7b6ea16440161215/]【poj1523】SPF求割点，并且求删去割点后的连通分量个数[cr...
2016程序设计实习实验班免修考试(算法)
02:热血格斗场[crayon-5994bb7b6fdb1208595149/]05:MPIMaelstrom[crayon-5994bb7b6fdbb020961460/]06:Ultra-QuickSort[crayon-5994bb7b6fdc1852939140/]08:DrainageDitches[crayon-5994bb7b6fdc5057796982/] ...
2016 ACM/ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-5994bb7b7051d856290442/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
【NOI考前欢乐赛】[bzoj3648]小奇泛舟
![【NOI考前欢乐赛】[bzoj3648]小奇泛舟](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_12-30-20.jpg)
【题目背景】微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》【问题描述】小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了n处景观（标号从1到n），有些景观通过溪流连接，这样的溪流有m段。小奇想知道，有多少种泛舟的路径，经过的景观数大于等于K呢？（小奇不喜欢一次泛舟重复经过一个景观）【输入格式】第一行包括3个整数，n，m，K。接下来m行，每行2个整...
【NOI考前欢乐赛】小奇遐想
【题目背景】撷来一缕清风飘渺方知今日书信未到窗外三月天霁垂柳新长枝条风中鸟啼犹带欢笑——《清风醉梦》【问题描述】小奇望着青天中的悠悠白云，开始了无限的遐想，在它的视野中，恰好有n朵高度不同的白云排成一排，他想从左到右选出四朵白云a，b，c，d，使得h_a<h_b<h_d<h_c，即看起来像是彩虹的形状！它想知道有多少种方案数。【输入格式】第一行包括1个整数n。第二行包括n个整数，第i个正数表示h_i，保证这n个整数是...
【省选模拟赛】小奇的糖果
原题：EAST!模拟赛RoundXV呓语【题目背景】小奇不小心让糖果散落到了地上，它对着满地的彩色糖果胡思乱想。【问题描述】有N个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。【输入格式】包含多组测试数据,第一行输入一个正整数T表示测试数据组数。接下来T组测试数据,对于每组测试数据,第一行输入两个正整数N、K,分别表...
【cf540X】Codeforces Round #301 (Div. 2)
A.CombinationLock模拟[crayon-5994bb7b71fb3103225429/]B.SchoolMarks塞一堆中位数，特判什么的[crayon-5994bb7b71fc1005567544/]C.IceCave深搜连通性，出点入度特判[crayon-5994bb7b71fcc575053315/]D.BadLuckIsland期望dp+记忆化[crayon-5994bb7b71fd6390057222/]E.InfiniteInversions离散树状数组乱搞[crayon-5994bb7b71fde430501200/] ...
【bzoj3932】[CQOI2015]任务查询系统
![【bzoj3932】[CQOI2015]任务查询系统](http://hzwer.com/wp-content/themes/ly/image/image_post/QQ鎴浘20141204194525.jpg)
好好的一道主席树题我写成了树状数组套主席树TT原因是为了练习模板（一开始根本没想。。。）TTbzoj16s通过，倒数第二是9s。。。多个log萌萌哒[crayon-5994bb7b7275f054454943/] ...
【codechef】January Lunchtime 2015
Pieceofcake 统计每个字母出现次数，取最大值，判断其是否等于l/2[crayon-5994bb7b735bd836040010/]Justmultiply 乘法快速乘即可，但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。发现a^(10b+c)=(a^b)^10*a^c然后就能On算出表达式了^10可以看做常数[crayon-5994bb7b735d0137835328/]Candidatewalk状压一下，转移显然[crayon-5994bb7b735d9190204676/]Manybananas这一题比较有意思将宗族大小分为<=300和>300用数组统...
【fjwc2015】Screen
【题目描述】码农有一块超新星屏幕，它有N个像素点，每个像素点有亮度和灰度两个参数，记为I和H,范围都是0~32000.一天，码农突发奇想，想知道哪个点比较容易亮瞎眼睛。为此，他定义了一个瞎眼指数:瞎眼指数就是灰度和亮度均不大于该像素点的像素个数。现在，码农希望知道，瞎眼指数为0~N-1的像素点分别有多少个 【输入格式】第一行一个数字N，代表有N个像素点。接下来N行，每行两个数字,代表该像素点的亮度和灰度。N个...
【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 矩阵中数...
【bzoj2527】[Poi2011]Meteors
![【bzoj2527】[Poi2011]Meteors](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_12-27-10.jpg)
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
【codechefFNCS】Chef and Churu
题解分块水过将函数分块，每一块大小√n，预处理一块内的函数统计每一个数字的次数，以及这一块的答案这一部分n√n并用树状数组维护a的前缀和，线段树呵呵。。。对于询问将整块的答案加起来，其余部分的每个函数在树状数组中查询对于修改修改树状数组依照每一个数字在每一块的次数，更新每一块的答案这一部分n√nlogn若理论分析似乎分块设小会更优，但若考虑下常数会发现好像并不会。。。注意本题要用unsignedlonglong还有一个很牛...
近期评论