洛谷 P4721 【模板】分治 FFT 解题报告
P4721 【模板】分治 FFT题目背景也可用多项式求逆解决。题目描述给定长度为 \(n−1\) 的数组 \(g[1],g[2],\dots,g[n-1]\)，求 \(f[0],f[1],\dots,f[n-1]\)，其中\(f[i]=\sum_{j=1}^if[i-j]g[j]\)边界为 \(f[...
洛谷P4719 【模板】"动态 DP"&动态树分治
【模板】"动态 DP"&动态树分治 第一道动态\(DP\)的题，只会用树剖来做，全局平衡二叉树什么的就以后再学吧所谓动态\(DP\)，就是在原本的\(DP\)求解的问题上加上修改操作，从而使得问题变成动态的问题这道题的问题就是普通的树形\(DP\)上加上了修改点权的操作题意：给定一棵 \(...
【BZOJ2599】[IOI2011]Race 树的点分治
【BZOJ2599】[IOI2011]RaceDescription给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000Input第一行 两个整数 n, k第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的...
[IOI2011]Race 点分治
[IOI2011]RaceLG传送门点分治板子题。直接点分治统计，统计的时候开个桶维护下就好了。注(tiao)意(le)细(hen)节(jiu)。#include<cstdio>#include<cctype>#include<cstring>#define R ...
模板—点分治B(合并子树)（洛谷P4149 [IOI2011]Race）
洛谷P4149 [IOI2011]Race点分治作用（目前只知道这个）：求一棵树上满足条件的节点二元组(u,v)个数，比较典型的是求dis(u,v)（dis表示距离）满足条件的(u,v)个数。算了自己懒得写了，安利几个blog吧：https://www.cnblogs.com/LadyLex/p/8...
POJ 1741 Tree （点分治）
TreeTime Limit: 1000MS Memory Limit: 30000KTotal Submissions: 20816 Accepted: 6820...
动态规划VS分治策略
•在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。•动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，而我们能够保存已经解决的子问题的答案，在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表...
【BZOJ-1492】货币兑换Cash DP + 斜率优化 + CDQ分治
1492: [NOI2007]货币兑换CashTime Limit: 5 Sec Memory Limit: 64 MBSubmit: 3396 Solved: 1434[Submit][Status][Discuss]Description小Y最近在一家金券交易所工作。该金券交易所只发行交易两...
BZOJ 2599: [IOI2011]Race( 点分治 )
数据范围是N:20w, K100w. 点分治, 我们只需考虑经过当前树根的方案. K最大只有100w, 直接开个数组CNT[x]表示与当前树根距离为x的最少边数, 然后就可以对根的子树依次dfs并更新CNT数组和答案. 复杂度是O(NlogN)----------------------------...
UOJ#7. 【NOI2014】购票 点分治 斜率优化 凸包 二分
原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ7.html题解这题是Unknown的弱化版。如果这个问题出在序列上，那么显然可以CDQ分治 + 斜率优化 + 凸包上二分来做。那么它出在树上？点分治。写挂了好多地方调了好久，自闭了。代码#pragma GC...
【点分治】Osipovsky Cup 2014 Kovrov, Sunday, December 21, 2014 Problem A. Attack and Defence
题意：给你一棵树，每个点有一个左括号或者右括号，问你树上能够完美匹配的路径数量（l->r，r->l 视作不同路径）。点分治可以使用“不扣去重复答案”的写法，只不过，要先将每个点的子树按照从小到大的顺序排序，防止复杂度出错。（此题不需要，因为统计一个子树的贡献的时候，时间复杂度最多只与当前...
P4721 【模板】分治 FFT
其实是分治ntt,因为fft会爆精度,真*裸题分治过程和fft的一模一样,主要就是ntt精度高,用原根来代替fft中的\(w_n^k\)1.定义:设m>1,(a,m)==1,满足\(a^r=1(modm)\)的最小r是\(\phi(r)\),那么a就是m的原根2.性质:如果g是p原根,那么\(...
bzoj4025二分图(线段树分治 并查集)
/*思维难度几乎没有， 就是线段树分治check二分图判断是否为二分图可以通过维护lct看看是否链接出奇环然后发现不用lct， 并查集维护奇偶性即可但是复杂度明明一样哈*/#include<cstdio>#include<algorithm>#include<cstri...
[POJ3233]Matrix Power Series 分治+矩阵
本文为博主原创文章，欢迎转载，请注明出处 www.cnblogs.com/yangyaojia[POJ3233]Matrix Power Series 分治+矩阵题目大意A为n×n(n<=30)的矩阵，让你求\(\sum\limits_{i=1}^{k}A^i\)并将答案对取模p输入格式：有多...
UVA 11990 `Dynamic'' Inversion CDQ分治, 归并排序, 树状数组, 尺取法, 三偏序统计 难度: 2
题目https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3141题意一个1到n的排列，每次随机删除一个，问删除前的逆序数思路综合考虑，对...
『You Are Given a Tree 整体分治 树形dp』
<更新提示><第一次更新><正文>You Are Given a TreeDescriptionA tree is an undirected graph with exactly one simple path between each pair of vert...
【2019北京集训测试赛（七）】 操作 分治+FFT+生成函数
题目大意：你有$n$个操作和一个初始为$0$的变量$x$。第$i$个操作为：以$P_i$的概率给$x$加上$A_i$，剩下$1-P_i$的概率给$x$乘上$B_i$。你袭击生成了一个长度为$n$的排列$C$，并以此执行了第$C_1,C_2....C_n$个操作。求执行完所有操作后，变量$x$的期望膜...
BZOJ1468Tree——点分治
题目描述给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K输入N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k输出一行，有多少对点之间的距离小于等于k样例输入71 6 13 6 3 9 3 5 7 4 1 3 2 4 20 4 7 2...
【BZOJ4237】稻草人（CDQ分治，单调栈）
【BZOJ4237】稻草人（CDQ分治，单调栈）题面BZOJ题解\(CDQ\)分治好题呀假设固定一个左下角的点那么，我们可以找到的右下角长什么样子？？？发现什么？在右侧是一个单调递减的东西那么，对于每一个已经固定好的左下角我们可以通过单调栈来维护答案既然只有左下角对右上角会产生贡献那么，按照\(x\...
洛谷 4115 Qtree4——链分治
题目：https://www.luogu.org/problemnew/show/P4115论文：https://wenku.baidu.com/view/1bc2e4ea172ded630b1cb602.html重链剖分，分别用线段树维护每条重链。线段树叶子的信息是该点轻孩子的信息；线段树区间的信...