点分治 听大佬说淀粉质可好吃了然后去做题的我 作用 用来求树上的路径问题 比如求有多少个点之间的路径长度为 k 之类的。 步骤 首先求重心，以保证这棵树的层数较少，防止TLE void getG(int p, int fa) { treeSize[p] = 1;//以当前节点为根的子树大小 sonLargest[p] = 0;//某节点最大的子树大...

震惊，我竟然写出了fhq Treap 先%fhq大佬 然后%zxy大佬 节点定义 struct node { int w,siz,rdm;//权值，大小（包括自己），随机数 int l,r;//左右儿子 } nd[MAXN]; 特有操作 fhq Treap也被叫做无旋Treap，它通过分裂与合并来维持平衡和堆的性质。 按值分裂 将树分成x,...

树上差分 描述 把差分数组（不是前缀和）放到一个树上，使某个节点的权值等于其本身加上所有子节点的差分的那个值的和。（语无伦次） 差分数组的作用是使区间修改的时间复杂度更低，对应到树上，就可以应用到类似于这样的情况： 点的差分 给A—B的简单路径上所有的节点的权值增加1。 可以把这条路径拆成两条链，分别为A到L（A和B的LCA）和B到L。 把A与B的标记增加1，那么A到L和B到L对应...

P3128 [USACO15DEC]最大流Max Flow 题面 题目描述 FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。 FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间...

P2916 [USACO08NOV]安慰奶牛Cheering up the Cow 题目描述 约翰有N个牧场，编号依次为1到N。每个牧场里住着一头奶牛。连接这些牧场的有P条道路，每条道路都是双向的。第j条道路连接的是牧场Sj和Ej，通行需要Lj的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。 约翰知道，在道路被强拆后，奶牛会非常伤心，所以他计划拆除...

义冢OJ P5018 Oulipo 描述 给出两个字符串W和T，求T中有几个W子串 輸入 第一行为数据组数. 每组数据有两行W和T，表示模式串和原始串. 輸出 对每组数据，每行一个数，表示匹配数. 輸入範例 1 3 BAPC BAPC AZA AZAZAZA VERDI AVERDXIVYERDIAN 輸出範例 1 1 3 0 提示 1 ≤ |W| ≤ 10,000 (h...

POJ 2018|Best Cow Fences 都9102年了我做的题怎么题号还是8102 Description Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 &l...

题目描述 Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。 由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加1，FJ把木筏划到对岸就得花更多的时间。 当FJ一个人坐在木筏上，他把木筏划到对岸需要M(1 <= M <= 1000)分钟。当木...

P4147 玉蟾宫 一道难题 题目背景 有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。 题目描述 这片土地被分成N*M个格子，每个格子里写着’R’或者’F’，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。 现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着’F...

一些动规题 也来自义冢OJ 【USACO3.1.2】总分 描述 学生在我们USACO的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。 我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少...