树状数组 - hzwer.com

程序设计实习实验班2017作业(算法作业19, 20, 21)
一些以前做过的就不再贴了AFunnyStoneGame发现每一堆的每个石子之间都是相互独立的[crayon-5c425151db429547682254/]nnimn阶nim和，在二进制下，每一位求和后对(n+1)取模[crayon-5c425151db439420869426/]一个水水的序列在建操作树的过程中就能顺便维护信息每次新加入节点的时候维护一下这个点的倍增数组，询问的时候直接向上倍增[crayon-5c425151db43e666700141/]「poj1523」SPF求割点，并且求删去割点后的连通分量个数[cr...
02017年6月24日2,891状压动规,树状数组,博弈论,树上倍增,矩阵乘法

2016程序设计实习实验班免修考试(算法)
02:热血格斗场[crayon-5c425151dc502758660648/]05:MPIMaelstrom[crayon-5c425151dc50e380694312/]06:Ultra-QuickSort[crayon-5c425151dc517180347672/]08:DrainageDitches[crayon-5c425151dc520557283745/] ...
02017年2月10日2,385STL,floyd,最大流,树状数组
2016 ACM / ICPC Asia Regional Dalian Online
1002DifferentGCDSubarrayQuery问长为n的序列，m个询问，问区间[L,R]所有子段的不同gcd值个数考虑固定左端点，随着右端点的移动，gcd至多衰减log次（每次至少折半）从n开始添加询问的左端点，用树状数组维护每个gcd右端点的最小值[crayon-5c425151dcabb664589030/]1007FriendsandEnemiesn个人，每个人可以用m种颜色中的一部分染色自己的项链两个人是朋友当且仅当他们拥有相同的颜色敌人不拥有任何相同的颜色问对于任意一...
02016年9月14日2,445ST表,构造,二分法,最短路,树状数组
「NOI考前欢乐赛」[BZOJ3648] 小奇泛舟
「题目背景」微露点滴沾衿落袖丽日绰约轻解莲舟蒹葭荣茂燕雀啁啾白石溪畔斜阳逐流——《白石溪》「问题描述」小奇喜欢在斜阳下的白石溪上泛舟。白石溪风光奇美，名花异石甚多，小奇在地图上标记了n处景观（标号从1到n），有些景观通过溪流连接，这样的溪流有m段。小奇想知道，有多少种泛舟的路径，经过的景观数大于等于K呢？（小奇不喜欢一次泛舟重复经过一个景观）「输入格式」第一行包括3个整数，n，m，K。接下来m行，每行2个整...
72016年6月26日4,956点分治,树状数组
「NOI考前欢乐赛」小奇遐想
「题目背景」撷来一缕清风飘渺方知今日书信未到窗外三月天霁垂柳新长枝条风中鸟啼犹带欢笑——《清风醉梦》「问题描述」小奇望着青天中的悠悠白云，开始了无限的遐想，在它的视野中，恰好有n朵高度不同的白云排成一排，他想从左到右选出四朵白云a，b，c，d，使得h_a<h_b<h_d<h_c，即看起来像是彩虹的形状！它想知道有多少种方案数。「输入格式」第一行包括1个整数n。第二行包括n个整数，第i个正数表示h_i，保证这n个整数是...
12016年6月26日2,991树状数组
「省选模拟赛」小奇的糖果
原题：EAST!模拟赛RoundXV呓语「题目背景」小奇不小心让糖果散落到了地上，它对着满地的彩色糖果胡思乱想。「问题描述」有N个彩色糖果在平面上。小奇想在平面上取一条水平的线段,并拾起它上方或下方的所有糖果。求出最多能够拾起多少糖果,使得获得的糖果并不包含所有的颜色。「输入格式」包含多组测试数据,第一行输入一个正整数T表示测试数据组数。接下来T组测试数据,对于每组测试数据,第一行输入两个正整数N、K,分别表...
02015年11月22日2,461链表,树状数组
「CF540X」Codeforces Round #301 (Div. 2)
A.CombinationLock模拟[crayon-5c425151de516811910979/]B.SchoolMarks塞一堆中位数，特判什么的[crayon-5c425151de524657227690/]C.IceCave深搜连通性，出点入度特判[crayon-5c425151de52f888354465/]D.BadLuckIsland期望dp+记忆化[crayon-5c425151de538913541021/]E.InfiniteInversions离散树状数组乱搞[crayon-5c425151de540778252056/] ...
02015年5月13日1,868模拟,深度搜索,树状数组,记忆化搜索,概率与期望
「BZOJ3932」[CQOI2015] 任务查询系统
好好的一道主席树题我写成了树状数组套主席树TT原因是为了练习模板（一开始根本没想。。。）TTbzoj16s通过，倒数第二是9s。。。多个log萌萌哒[crayon-5c425151dea7c030225482/] ...
72015年4月8日5,861主席树,树状数组
「codechef」January Lunchtime 2015
Pieceofcake 统计每个字母出现次数，取最大值，判断其是否等于l/2[crayon-5c425151df3f9162988227/]Justmultiply 乘法快速乘即可，但乘方由于M过大。。使用欧拉函数降幂比较麻烦。。发现a^(10b+c)=(a^b)^10*a^c然后就能On算出表达式了^10可以看做常数[crayon-5c425151df401683506080/]Candidatewalk状压一下，转移显然[crayon-5c425151df407976547680/]Manybananas这一题比较有意思将宗族大小分为<=300和>300用数组统...
02015年3月1日1,915模拟,状压动规,快速幂,树状数组
「fjWC2015」Screen
「题目描述」码农有一块超新星屏幕，它有N个像素点，每个像素点有亮度和灰度两个参数，记为I和H,范围都是0~32000.一天，码农突发奇想，想知道哪个点比较容易亮瞎眼睛。为此，他定义了一个瞎眼指数:瞎眼指数就是灰度和亮度均不大于该像素点的像素个数。现在，码农希望知道，瞎眼指数为0~N-1的像素点分别有多少个「输入格式」第一行一个数字N，代表有N个像素点。接下来N行，每行两个数字,代表该像素点的亮度和灰度。N个...
02015年2月3日1,366树状数组
「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　　矩阵中数...
02015年1月7日4,386二分法,树状数组
「BZOJ2527」[POI2011] Meteors
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
42015年1月7日4,960二分法,树状数组