题意有点绕，大概意思就是，现在你要将2个完全一样的区域都分成n份，且这n份的面积也都相同，我们将每一份区域定一个id(理解为1-n的排列)，问怎么分使得这俩个区域，相同id的子区域相交之后的共有的面积，n个共有面积的最小值能取到多少。 题解：我们将题意转化一下，把这俩次划分看成一张二分图，在所有可能的排列中，那么第一次划分的第iii号点和第二次划分的所有可能出现iii的nnn个位置的面积并之和就是1/n,即它自己面积本身。即这是一个满二分图，其中每一个节点，其所连边的权值和为1/n1/n1/n 那么现在我们就将题意转化成了要求寻找⼀个尽可能⼤的ansansans，使得在任何满⾜上述条件的⼆分图...

题意:问有多少种长度为n的01串，其中1的总个数为m，最长的连续1的长度为k   解法:看到要精准计算k，考虑转化一下，计算最长的连续1的长度小于等于k的方案数-计算最长的连续1的长度小于k的方案数，那么就是我们想要的答案。  我们记最长的连续1的长度小于等于k的方案数为anskans_kansk​  anskans_kansk​的计算方式可以考虑容斥，容斥长度大于k的有多少段。那么anskans_kansk​=0段连续1的长度大于k - 1段连续1的长度大于k + 2段连续1的长度大于k .... i段连续1的长度大于k 对于i段连续1的长度大于k的方案计算方式，可以直接相当于这些段的1的数...

题意：从一个含有2*n个点的完全图中删去一棵树，问在剩下点中选取n条边，使得这n条边为独立集的选法有多少种。    想法：一般这种让你求选某个特定的值的题目的时候，如果没有好的切入点，就要想到容斥。那么这题我们怎么用容斥来思考呢。既然不让我们选树边，那我们就反其道而行之，强行选树边,那么：   ans=(选取0条树边的方案)（剩下2n个点的完全图任选n条边的方案）-(选取1条树边的方案)（剩下2n-2个点的完全图任选n-1条边的方案）+(选取2条树边的方案)（剩下2n-4个点的完全图任选n-2条边的方案）....(选取k条树边的方案)（剩下2n-2*k个点的完全图任选n-k条边的方案）   那...

题意：有n-1条边(保证为偶数)，分成n-1/2组，每组俩条边，且这俩条边之间要有一个公共点，求方案数 解析：我们想到用f[i]代表以i为根的方案数，那么f[i]首先要先乘以v:g[i],f[i]=f[i]*f[v],考虑子方案数的求法 假设当前我们有n条可以自由组合的边，若n为偶数 那么答案要再乘以一个C(n,2)C(n-2,2)....*C(2,2) / A(n/2,n/2) 化简这个式子，得到原式=n!/n!! = 1 *3 *5 *...(n-1) 若n为奇数，那么其中一定有一条边是要贡献给其父亲结点的，因为题目保证了边数是偶数，不可能会有奇数的边剩下。 所以我们需要统计对于每个根，其...

题意：有一个n个点m条边的无向连通图，每个点有一个权值，每条边之间也有一条边权。对于一个点，假如要走过这个点相连的某一条边，那么要保证我当前手里的权值和大于等于这条边的边权。 现在有q次询问，每次询问给出一个起始点和起始权值，每第一次经过一个点就可以获取其点权，求最多能达到的权值和。 解析：首先对于点和点之间，假如有好多种走法，我们一定是选择最短的走法，那么我们就可以先构建出这个图的最小生成树，这样能省去很多不必要的边。对于题目询问的这种问题，我们很容易猜想到要使用重构的方法去构造一棵新的树(因为一般题目里出现俩点之间最大边权等等类似的字眼，要想到kruscal重构树)。 对样例一进行krus...

题意：给出n个物品的体积和价值，可以选择最多k个的物品体积翻倍，问能否分出俩个子集，使这俩个子集的体积和相同且价值和最大 考虑从01背包入手，01背包的状态转移方程f[i][j]表示前i个物品放入容量为j的背包里的最大价值，那么f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i] 考虑此题怎么从01背包转换过来，先不考虑子集这个概念，只考虑翻倍，那么我们可以多开一维，f[i][j][k]表示前i个物品，翻了j个，放入容量为k的背包里的最大价值，那么f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k-w[i]],f[i-1][j-1]...

学习生成函数网课小记(防止忘记) 生成函数这个东西经常会和容斥结合在一起来做题，用暴力的思想来解决难以入手的题目 在生成函数中的G(x),千万不要把x想成有什么含义，它只是作为一种符号，一种标志出现，计算x的n次项的方案数时，我们只取前面的系数 这里通过几道题来入门生成函数 第一题:背包 这题就是考察对生成函数以及其求逆之后的化简 关于生成函数求逆，常用的如图，B(x)为A(x)的逆  考虑每一个要求的生成函数。（只选条件中的物品） 条件一：(肥宅快乐水)1+x 逆元: 1−x21−x\frac{1-x^2}{1-x} 1−x1−x2​ 条件二：(大盘鸡)1+x+x^2 逆元: 1−x31−x...

【浮点数三分】洛谷：P3382 三分模板  www.luogu.com.cn/problem/P3382  前置知识：三分-->用来计算凸/凹函数，即单峰/谷函数的极值点 分为整数三分和浮点数三分俩种，其中整数三分的题目更加变化多端 对于浮点数三分，我们只需要设置mid左右俩边相等距离的俩个值midl和midr分别计算答案比较即可。如果cal(midl)>cal(midr)) ，那么舍弃右区间，r=midr，否则舍弃左区间，l=midl，具体实现可以参考如下代码，记住可以使用秦九韶算法加速计算多项式过程 #pragma GCC optimize(2) #include<bit...

https://ac.nowcoder.com/acm/contest/7605/B  题解：https://ac.nowcoder.com/discuss/542124?type=101&order=0&pos=2&page=1&source_id=discuss_tag_nctrack&channel=-1) 个人实现： #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define INF 0x3f3f3f3f #define rep(i, a, ...

牛牛与交换排序题意是给你一个1-n的排列，问能否存在一个k，使得每次翻转一个长度为k的区间，且每次翻转的区间要比上一次更靠右，问能否找到这样一个k。手写几组样例便会很清晰地发现，最小的k一定是第一个数字与位置不一样的那个数与自己位置的距离的差值。我们可以令k=abs(pos[i]-i)+1;接下来就是模拟区间翻转的过程了，我们可以利用stl里面的deque或者写一个平衡树，达到O(n)的复杂度来实现这一过程这里的deque模拟更多是一种思维的发散，写过类似的题就会写，没写过的话是真的很难想到。具体实现的话，便是在长度为k的队列里，找到翻转后变成位置与数字统一的那个数字，然后把它弹出，插入下一个...

01字典树听名字便知是用字典树来维护一个01串即一个二进制数的数据结构。字典树又称前缀树，他和hash在查询映射这方面各有优劣。现在介绍的01字典树在处理区间异或这方面上往往非常常用，现在我们来一一展开。 对于一个十进制的数字而言，我们可以将它的二进制从前往后的每一位都取下来，然后模仿字典树的方式进行插入，最终会形成一个只含01的一棵树，形似二叉树，因为每一个结点最多只有俩个左右子结点。 现在我们拿一道例题出来进行分析 hdu 4825：题意，给出n个数和m次查询，每次查询给一个数字s，问在n个数中哪个数字与s的异或值最大。 首先是初始化与插入 int ch[32*maxn][2],val[3...

几个知识点：  直线的斜率可以通过 c++函数atan2(Δy,Δx) 求出，其返回的是弧度，即当斜率为90°时atan2(90°)=1.57   c++的sin(x),cos(x)这些函数都是使用弧度制的  3.点 顺时针旋转θ角度后的新坐标 //没有凸包 /*------------------ 二维几何 ------------------------------------------------------------------ */ const double eps=1e-8; const double inf=1e20; const double pi=acos(-1.0); ...

题意：给出n个数和k，m次查询，每次输出区间可以最小分割成多少和<=k的段 这题是ST表的应用，我们利用倍增的思想，对于每个位置，我们用dp[i][j]表示从i开始之后每一段割2^j个数字，最右端点可以到哪，查询的时候从大端点查到小端点，一定可以把整个区间拼接完成，要是有非法的数字，右端点则是他自己，判断一下即可 #include<bits/stdc++.h> #define ll long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; inline int read(){ ll f...