思路  和普通的DP不一样的是 这里求的是满足条件的数的平方的和 而数位DP只跟数每位是什么密切相关  所以要开一个结构 （多加一个 数的和sum 和平方和qsum）存一下各个状态的和的情况   dp[pos][state1][state2].num  满足该状态的数有几个 dp[pos][state1][state2].sum 满足该条件的数的和是多少 dp[pos][state1][state2].qsum 满足该条件的数的平方的和是多少 详见注解 主要是状态转移是 和 和 平方和 的转移公式 ∑(Y + xi)^2 = ∑(Y^2 + 2 * Y * xi + xi^2) = ...

题意: 给出范围 算出 满足  选取一个数中任一一个 树作为支点  两边的数分别乘以到中心的距离和 左和等于右和   的数有多少个 数位DP题 状态转移方程为dp[pos][x][state]=dp[pos-1][x][state-(pos-x)*i]  表示为pos位上的数字为 i    以x为支点  则  以中心点左为负右为正   pos左右的数乘以权值的 和为state pos-1位就是 把pos位的 i乘以权值减去   即 state-(pos-x)*i 如果枚举到最后一位的时候 state==0就说明平衡了 其中 0 00  000  000 ......也是平衡的  出了0其他都...

求次小生成树思路： 先把最小生成树求出来  用一个Max[i][j] 数组把  i点到j 点的道路中 权值最大的那个记录下来 used数组记录该条边有没有被最小生成树使用过   把没有使用过的一条边加入最小生成树必然回形成一条回路   在这条回路中减去 除加入的边的权值最大的一条边  原图必然保持连通  （如果此时 权值最大的边和新加入的边权值相同  则存在 不同的最小生成树） 把每一条边加入再删除后 即可得出次小生成树  参考了： https://blog.csdn.net/qq_33951440/article/details/53084248        https://blog....

题意：给出地铁线  起点和 终点  坐地铁速度为v2  走路为v1 求起点到终点的最短距离  （答案需要四舍五入这里坑了好久）   拿给出的地铁站点 和起点终点建边即可  然后跑个迪杰斯特拉 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const double v1=10000.0/60; 7 const double v2=40000.0/60; 8 int ...