瑜画

题解

/ 注册

全部文章 / 题解（共42篇）

送分了QAQ 题解

数位dp，如果有4直接标记状态2，如果有3标记状态1，如果有8并且状态为1，标记状态2。依次枚举数位，如果发现数字一定合法（该位小于x，后面的位上的数可以任意填），并且f数组已经算过，可以直接返回。 //注意记忆化如果后面可以任意填了并且已经算过就直接返回 if(flag&&f[p...

dp

2020-08-19

6 719

Accumulation Degree 题解

换根dp 注意多组数据对于第一次dfs，每一个点的水流等于容量和流量的最小值。对于第二次dfs，消除贡献即可。 #include <bits/stdc++.h> using namespace std; const int N=200005; #define ll long long c...

dp

2020-08-19

0 509

Tree 题解

//对于每一个结点，是孩子+1的乘积 //因为自己一定会取，所以孩子的集合方案就多了一个空集 //换根dp过程，把原来的父节点旋转下去 //首先将父亲结点的方案数除以这个转上去的孩子+1 //也就是说消除原来这个孩子结点的贡献 //然后把新父亲结点乘以这个新孩子结点，也就是说贡献上去 //第二次df...

dp

2020-08-18

1 761

蓝魔法师题解

用dp[j][k]表示j结点的连通块大小为k的方案数然后从叶子结点一路递推回来，分类讨论。如果不切掉连着的边，两个连通块合并，方案数就是直接相乘dp[u][j+k]= dp[u][j]*dp[to][k]如果切掉连着的边，方案数就是独立的那么就是加上孩子的dp和，dp[u][j]=dp[u][j]...

dp

2020-08-18

1 611

树学题解

换根dp，维护dp数组：以某结点为根的时候的答案维护_size数组：某结点为根的子树大小第二次dfs的时候换根进行旋转就可以了，类似于AVL树和Splay Tree的旋转 #include <bits/stdc++.h> using namespace std; const int N=...

dp

2020-08-18

0 522

筛子游戏题解

设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]就是我们...

dp

2020-08-18

3 1105

Collecting Bugs 题解

根据上课听的雨巨的思路，移项运算一下然后写代码 #include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 1010; doubl...

dp

2020-08-17

0 638

带富翁题解

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

dp

2020-08-17

1 572

Mondriaan's Dream 题解

用二维数组dp，第一维表示状态，第二维表示当前行。最后输出的是最后一行全部都横着放的状态。用1表示竖着放，0表示横着放，注释详细。。。 #include <bits/stdc++.h> using namespace std; #define ll long long ll dp[1&l...

dp

2020-08-17

1 704

Most Powerful 题解

这题比较简单，不过有需要注意的点：1.选取的被碰气体得是对应二进制表示为0的2.选取的一个碰他的气体也得是对应二进制为0的（还没消失的气体）具体看代码，有详细注释： //1表示哪个气体被碰掉消失了 0表示气体还没被碰掉 #include <bits/stdc++.h> using nam...

dp

2020-08-17

0 593