//对于每一个结点，是孩子+1的乘积 //因为自己一定会取，所以孩子的集合方案就多了一个空集 //换根dp过程，把原来的父节点旋转下去 //首先将父亲结点的方案数除以这个转上去的孩子+1 //也就是说消除原来这个孩子结点的贡献 //然后把新父亲结点乘以这个新孩子结点，也就是说贡献上去 //第二次dfs的过程中输出每个值 就完事了换根dp的时候涉及到除法去除掉子树的贡献，要注意到考虑inv==0的情况，因为有可能某个孩子的dp值刚好是mod-1（贼坑！），这时候就得用其他孩子重新计算一遍dp值，每次深搜的时候直接计算ans数组就好了，不要去改变各个点的dp值，否则会引起错误。 //对于每一个结点...

用dp[j][k]表示j结点的连通块 大小为k的方案数然后从叶子结点一路递推回来，分类讨论。如果不切掉连着的边，两个连通块合并，方案数就是直接相乘dp[u][j+k]= dp[u][j]*dp[to][k]如果切掉连着的边，方案数就是独立的那么就是加上孩子的dp和，dp[u][j]=dp[u][j] * dp[v][k] #include <bits/stdc++.h> using namespace std; #define ll long long const ll mod=998244353; ll n,k; ll dp[2020][2020];//第一维度表示谁的连通块 第...

换根dp，维护dp数组：以某结点为根的时候的答案维护_size数组：某结点为根的子树大小第二次dfs的时候换根进行旋转就可以了，类似于AVL树和Splay Tree的旋转 #include <bits/stdc++.h> using namespace std; const int N=1000100; #define ll long long ll _size[N]; ll dp[N]; ll ans=1e17; struct node { int v,next; }e[N<<1]; int cnt=0; int head[N]; void add(int u,int...

设f[i]表示达到i分时到达目标状态的期望，pk为投掷k分的概率，p0为回到0的概率，这个先预处理出来请在这里输入引用内容则f[i]=∑(pkf[i+k])+f[0]p0+1请在这里输入引用内容• f[i]=∑(pkf[i+k])+f[0]p0+1• 每个状态都和f[0]有关系，而且f[0]就是我们所求，为一个常数• 设f[i]=A[i]f[0]+B[i];• 代入上述方程右边得到：• f[i]=∑(pkA[i+k]f[0]+pkB[i+k])+f[0]p0+1=• (∑(pkA[i+k])+p0)f[0]+∑(pkB[i+k])+1;• 所以 A[i]=(∑(pkA[i+k])+p0) B[...

根据上课听的雨巨的思路，移项运算一下然后写代码  #include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 1010; double dp[N][N]; int main() { int n, s; while (~scanf("%d%d", &n, &s)) { memset(dp, 0, sizeof(dp)); for (int i = n; i >= 0; --i) { for (int j = ...

倒着dp，计算分母（能往几个地方转移分母就是几）用dp[i]表示i点到终点需要步数的数学期望能走到至多六个位置，直接转移就好了，要记得加上自己这个位置得分 #include <bits/stdc++.h> using namespace std; int a[105]; double dp[105]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[n]=a[n]; for(int i=n-1;i>=1;i--) { int num=min(6...

用二维数组dp，第一维表示状态，第二维表示当前行。最后输出的是最后一行全部都横着放的状态。用1表示竖着放，0表示横着放，注释详细。。。 #include <bits/stdc++.h> using namespace std; #define ll long long ll dp[1<<12][12]; int h,w; bool judge(int x)//判断连续的0是不是偶数个 { int ww=w; int cnt=0; while(ww--) { if(x&1) { if(cnt&1) return false; cnt=0; } else c...

这题比较简单，不过有需要注意的点：1.选取的被碰气体得是对应二进制表示为0的2.选取的一个碰他的气体也得是对应二进制为0的（还没消失的气体）具体看代码，有详细注释： //1表示哪个气体被碰掉消失了 0表示气体还没被碰掉 #include <bits/stdc++.h> using namespace std; const int N=12; int mp[N][N]; int dp[1<<N];//表示某个状态 //dp[i|jj]=max(dp[i]+mp[j][i]) int main() { int n; while(~scanf("%d",&n)){ i...

前面部分跟“郊区春游”差不多，属于TSP问题，不懂的可以看一下我郊区春游的那篇题解。也是枚举起点、终点（终点这里得比起点大，避免重复统计），进行状态转移，不同的是这里的dp数组记录的是方案数量，然后每次转移以后要判终点和起点是否可以相连，相连就进行统计。最后答案要除以2，原因是大于等于3的回路可能会顺时针走一遍、逆时针走一遍（本题只统计大于等于3的就是这个原因）。除以2用逆元来解决在模意义下的除法。 #include <bits/stdc++.h> using namespace std; #define ll long long #define lowbit(x) x&(...

题意：一开始就在旅游的几个点选一个作为起点，然后这个点就算游过了，游完别的景点在最后一个景点停下即可。用dp[i][j]，i表示状态（哪些点游过，哪些点没有），j表示最后停留在哪个点。具体看代码详细注释： #include <bits/stdc++.h> using namespace std; int n,m,r; const int N=205; const int INF=0x3f3f3f3f; int rs[18];//表示必须要旅游的点 int mp[N][N]; int dp[34000][20]; void floyed() { for(int k=1;k<=n...

先看同一行哪一些方案可以放置，以减小时间复杂度（老套路）查看的方法是看左边第一、二，右边第一、二 不能跟自己这个位置同时有1 然后统计这个方法包含的炮兵数，统计方法是线性dp，通过lowbit（树状数组的东西），转移计数。（每个方案的炮兵数量是这个方案的二进制串去除最低位的1的炮兵数量+1）最后一行一行向前dp，记住原则，一直统计新的一行的平原，并用二进制串表示，再相邻行不断的判断筛选掉不可行的方案，用dp数组向前推进可行方案，每推进一次更新一次ans的最大值，最终输出ans的最大值即可。。 #include <iostream> using namespace std; char...

比赛时候弄错了一行代码，一直没AC，吐血。。。直接贪心，从后往前翻，只要出现连续两个1就进行翻转，这样就能确保收益大于直接修改的，具体细节看代码（不过好像dp的方法比较无脑，贪心的细节容易错，好吧，还是太菜了） 记录修改的位置，通过二分查找判断每个点在翻转完毕以后是1还是0，如果是1就需要修改。 #include <bits/stdc++.h> using namespace std; int a[100100],pre[100100]; int loc[100100]; int lian0[100100],lian1[100100]; int main() { int n; sc...

题面意思，问围着一个x的跑道跑顺时针跑，打卡完毕的时候跑k米及以上的概率。 思路：因为这个人跑步只能先打第一张卡，在打第二张卡，所以有可能第二张卡在第一张卡前面，那么这个人就得跑第二圈才能打第二张卡，否则是直接就可以在第一圈打掉第一张卡和第二张卡。而且，无论如何都是可以在两圈以内完成打卡的 根据这个规律，将情况分为三种：（正难则反，求能够在k米之前能够完成打卡的概率，最后再减）1.k≥2x，那么这个人将永远不可能跑到k米2.k>=x&&k<x，那么要想跑k米，就一定会倒腾到第二圈，即第二张卡在第一张卡前面，直接减去第一张卡在第二张卡前面的概率0.5。第一张卡只需要放...