下一页 »Current position : 首页 >> 线段树
PKU2019数据结构与算法实习期末考试
http://dapractise.openjudge.cn/2019finalexam2/排队[crayon-696a4eba731b4718159454/]树状数组过线段树不过[crayon-696a4eba731c0093856496/]线段树求最大数[crayon-696a4eba731c7772050954/]关键词搜索[crayon-696a4eba731d1562289815/]旅行最短路[crayon-696a4eba731de320513999/]强连通分量[crayon-696a4eba731ea206611699/]统计不同子串[crayon-696a4eba731f6972374564/]匹配网络流模板[crayon-696a4eba7320b439733744/]线性...
PKU2019数据结构与算法实习模板
本文包括：并查集最短路强连通分量线段树AC自动机(Trie)网络流后缀数组POJ1182食物链如果并查集中X向Y连边长为1的边，代表X吃Y这题如果用按秩合并并查集比较好想，带路径压缩的话，需要考虑重新连边的时候，边权的设置[crayon-696a4eba74947809469869/]POJ1860CurrencyExchange最短路模板[crayon-696a4eba74957827488911/]POJ2186PopularCows如果X喜欢Y，Y向X连边。缩点以后，计算每个强连通块的入度，唯一...
PKU2019数据结构与算法实习作业 1~10
题目来源：http://dapractise.openjudge.cn/2019hwall/冰阔落I[crayon-696a4eba7524d713329902/]POJ1182食物链[crayon-696a4eba75257940565075/]POJ2492ABug'sLife[crayon-696a4eba7525c401700128/]POJ3321AppleTree树状数组维护dfs序[crayon-696a4eba75261409034855/]POJ1195Mobilephones[crayon-696a4eba75267748317764/]不好做的最长上升子序列[crayon-696a4eba7526b219004790/]POJ2182DifficultLostC...
「CF1237X」Codeforces Global Round 5
A.BalancedRatingChanges先把所有奇数除二下取整，再任选一些加一[crayon-696a4eba75eb0094653757/]B.BalancedTunnel按进入顺序排序，依次考虑，维护出站顺序的最大值直观理解就是，比一辆车先进站的，如果在它之后出站，它肯定插队了[crayon-696a4eba75ebb168235986/]C2.BalancedRemovals(Harder)先考虑二维情况，按x，y排序，可以把所有点看成一列一列的点，先再每一列上两两配对。这样每一列最多剩下一个，再把相邻列...
2015程序设计实习实验班免修考试(校内)
「poj1037」decorativefence用f(i,j)表示长度为i，开头为j，开头为上升的序列用g(i,j)表示长度为i，开头为j，开头为下降的序列考虑在序列的第二位放一个数字，改变上升/下降预处理完之后，一位位枚举贪心[crayon-696a4eba7653e012950119/]「poj1011」Sticks经典的搜索剪枝1.长度取值范围是木棍的最长长度到长度总和之间。2.长度总和一定可以整除原来的长度。3.从大到小排序搜索。4.某次组合时，如果不能加入某根木棍，同种长度的木...
「CF718X」Codeforces Round #373 (Div. 1)
A.EfimandStrangeGrade给一个长为n的小数，有t次操作，每次可以让小数点后的某一位向前四舍五入问能最终能得到的最大的数题解考虑找到最前的一个大等于5的数字，从其开始考虑四舍五入如果四舍五入到小数点，将小数点去掉最后再处理一下整数位的进位问题[crayon-696a4eba76f24905267207/]C.SashaandArray给定一个长度为n的数列an，有两种操作1、将L到R的加上X2、询问\(\sum_{L\leqi\leqR}F(a_i)\)题解考虑在线段树的每...
「小奇模拟赛」小奇的自动机
「题目背景」小奇在研究后缀自动机时遇到了一个难题。「问题描述」定义：如果字符串A是字符串B的后缀，那么称B是A的XQ串。小奇有n个只包含小写字母的字符串，编号为1-n，表示为Si。接下来对于每个串Si，小奇想知道：对于小奇拥有的n个字符串，所有是Si的XQ串的编号集合(包括i）中第Ki小的编号。「输入格式」第1行1个整数n。接下来n行，第i+1行包括1个字符串Si。再接下来n行，第n+1+i行的整数表示Ki。「输出格式」输出...
「省选模拟赛」小奇的花园
原题：「泉七培训-刘定峰」花园「题目背景」小奇在家中的花园漫步时，总是会思考一些奇怪的问题。「问题描述」小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。「输入格式」第一行为两个整数n，q，表示温室的数目和操作的数目。第二行有n个整数T1...
「BZOJ3600」没有人的算术
http://pan.baidu.com/s/1B0JNovfk大大的题好厉害QAQWJMZBMR在论文中也有提到平衡树的这种用法《重量平衡树和后缀平衡树在信息学奥赛中的应用》大概就是用平衡树维护这些数，给每个数一个实数值表示其大小生成一个数(a,b)的时候，由于a,b都是之前出现过的数，所以我们可以直接在平衡树上插入，返回代表它的实数值用线段树求区间最大值[crayon-696a4eba78467166076521/] ...
「CF339X」Codeforces Round #197 (Div. 2)
A.HelpfulMaths排序[crayon-696a4eba78d30111293249/]B.XeniaandRingroad题意即题解[crayon-696a4eba78d39447014306/]C.XeniaandWeights搜索可过[crayon-696a4eba78d3e884508968/]D.XeniaandBitOperations线段树模拟每次询问可以自底向上修改[crayon-696a4eba78d42324201583/]E.ThreeSwaps由于只有三次交换，所以数列最多被分成七段找到所有断点爆搜[crayon-696a4eba78d47694490223/] ...
「CF260X」Codeforces Round #158 (Div. 2)
A.AddingDigits模拟，每次可以根据当前模的结果，得出下一个添加的数字[crayon-696a4eba9610e855446023/]B.AncientProphesy在串中枚举一段，用map统计出现次数[crayon-696a4eba96118308462076/]C.BallsandBoxes可以发现，拿来分的那个盒子现在的数量一定是最少的，于是模拟大法[crayon-696a4eba9611e739218426/]D.BlackandWhiteTree将两色的结点排序后，依次贪心构造构造方法很简单[crayon-696a4eba96123408762762/]E...
PKUSC 2014 #2
A:QuadTiling对于某一层来说，状态只有6种，所以手推下转移方程，矩阵乘法加速即可[crayon-696a4eba967c0390336215/]B:Garden傻逼线段树[crayon-696a4eba967ca754940959/]D:One-movecheckmate枚举一下皇后能一步到达的位置，然后判一下是否将死注意细节较多具体见discuss[crayon-696a4eba967d2000743460/]E:ATP二分答案后，从比赛最后阶段往前考虑当然是每场给每个人分配一个可以打败的最NB的人。。。贪心判解的可行性...
近期评论