Coloring Tree (牛客多校) (BFS序列妙用+ f(n)-f(n+1)+ 组合数学)

#include<bits/stdc++.h>usingnamespacestd;constdoubleeps=1e-9;//浮点数精度控制#defineVectorpoint#definePointpointconstdoublePI=acos(-1);structPoint{doublex,y;Point(doublex=0,doubley=0):x(x),y(y){}friendVe......

rope:#include<ext/rope>usingnamespace__gnu_cxx; 定义方法：rope<变量类型>变量名称;人话解释：超级string算法解释：块状链表（即讲链表与数组的优势结合，形成分块思想）用途解释：这本来是一个用于快速操作string的工具，却一般被定义成int，然后用作可持久化线段树！insert(intpos,s......

题目大意:给出n个物品,物品有4个空间值,然后有一个权值问在不超过最大的空间值时,最大的权值  思路:一开始想了很多其他思路没有想出来开始广搜算法,发现dp可以解决(注意看数据范围,是满足的)遇到奇怪的题,就试试dp,特别在数据范围很小的时候 ......

Giventherootsoftwobinarytreespandq,writeafunctiontocheckiftheyarethesameornot.Twobinarytreesareconsideredthesameiftheyarestructurallyidentical,andthenodeshavethesamevalue.Solution:classSolution:defisSameTre......

  https://blog.csdn.net/weixin_46156770/article/details/122696483......

题目题目链接：https://codeforces.com/contest/1842/problem/F给定一棵\(n\)个点的树，你可以选择其中\(k\)个点染黑，定义一条边的价值为割去这条边之后，剩下两颗树的黑点数量差；一棵树的价值为所有边的价值之和。对于\(k\in[0,n]\)，求出树的价值的最大值。\(n\leq5000\)。思......

6.27冲刺国赛模拟25T1简单计数不是古典概型所以不能方案数相除。考虑枚举第一个选择的位置\(i\)，这样分成两个独立的区间，只关心\(k\)所在的一个，转移方程：\[f_{n,k}=\dfrac{1}{n-1}\left([k<n]+[k>1]+\sum_{i>k}f_{i-1,k}+\sum_{i<k-1}f_{n-(i+1),k-(i+1)}\right)\]前缀和......

6.17冲刺国赛模拟20T1树染色容易发现每种方案都可以变成没有交边的链剖分，在此基础上的方案数是每个链顶的深度，考虑DP。直接DP大致是维护\(\prod(\proda+\prodb)\timesdep_{top}\)，发现这个东西非常不好转移，转移时需要枚举叶子，复杂度不优秀。改为设\(f_{i,0/1}\)表......

6.21冲刺国赛模拟22T1跳跃不妨看作两只青蛙从相同起点出发且跳跃次数相同，设\(f_{i,j,k}\)为两只青蛙分别在\(i,j\)位置，且相差步数\(k\)。由于需要记录相邻位置对答案贡献，我们在要求必须严格按照升序对处理状态，也就是必须保证当前跳跃的一只青蛙落点在另一只青蛙更前面，且......

6.24冲刺国赛模拟24T2简单图论题原题：Gym-104053CCustomsControls2构造题。这个限制可以进一步加强到对于每个节点\(u\)，\(1\tou\)的路径权值都相等，定义为\(d_u\)。于是对\(u\)连边的两个节点的\(d\)一定相等，进而可以把所有相等的缩到一起，且这些点直接不能连边（点......