瑜画

题解

/ 注册

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

Beautiful Numbers 题解

吐槽一下，这题内存卡的比较紧我#define int long long + 数组开了15150150*150 就爆内存了，一直以为我递归错误，查了好久。。。用sum表示各个位之和，d表示枚举1到129的一个变量（因为sum要递归完了才能算出来，我们不知道sum究竟是多少，所以要枚举一下），mod...

dp

2020-08-20

4 732

How Many 0's

算一算每一位对应会有多少个0，然后两个数相减即可 #include <iostream> #include <algorithm> #include <string.h> using namespace std; #define int long long int...

dp

2020-08-19

0 680

7的意志题解

dp过程主要是三个参数，第一个是位置pos，第二个是pre（数字取余7），第三个是sum（数位之和取余7）递推的过程pre这一维要乘以10再加上i，sum这一维度加上i即可，注意都要取余7然后注意要开long long，f数组存下能任意填以后的数值，以便加速后面的操作，不然会超时。 #include...

dp

2020-08-19

0 699

诡异数字题解

数位dp，注意当出现次数大于限制次数的时候直接返回0，pos==0还不大于就返回1 f[pos][num][cnt] 表示第pos位，末尾数字为num，连续次数为cnt如果下一位还是num，那么转移到dp(pos-1,num,cnt+1)否则转移到dp(pos-1,i,1)也就是说转移到新的数字这...

dp

2020-08-19

0 793

送分了QAQ 题解

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

dp

2020-08-19

6 697

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 501

Tree 题解

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

dp

2020-08-18

1 751

蓝魔法师题解

用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 598

树学题解

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

dp

2020-08-18

0 520

筛子游戏题解

设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 1095