瑜画

题解

/ 注册

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

德玛西亚万岁题解

二进制状压dp，只要相邻行列没有同时有两个战士，并且满足只有1的位置有战士，即可。注意多组数据要重置f数组 #include <bits/stdc++.h> using namespace std; #define int long long const int mod=10000000...

dp

2020-08-22

0 641

[ZJOI2008]骑士题解

本题考察基环外向树上的树形dp首先需要找到环上的任意一条边，然后删去这条边，再对这条边的两个点进行树形dp，最后选择根节点都不选的最大值，就是最后的答案。根节点都不选的理由是：如果选上根结点，由于环上找出来的这条边切断了，所以在进行树形dp的时候，没有考虑切断的这条边上的另一个点，有可能把那个点选上...

dp

2020-08-21

0 855

[SCOI2009]WINDY数题解

记录一下当前数和前导0即可，相邻两数位之差绝对值小于2的方案直接忽略不计。五分钟AC解决战斗。 #include <bits/stdc++.h> using namespace std; #define int long long int a[20]; int f[20][12][2];...

dp

2020-08-21

0 707

[CQOI2016]手机号码题解

记录位置、这一位的数、上一位的数，然后比较三个数是否相同，相同则符合，还要两个参数记录是否出现4和8，要注意处理前导0 //记录最后出现的数字是几上一位是几是否已经有三连号有没有出现8 有没有出现4 #include <bits/stdc++.h> using namespace...

dp

2020-08-21

0 794

好朋友题解

统计0的个数，再判断有没有前导0，如果出现了007就记录，然后用相应的四位数组进行记忆化，比较常规的数位dp #include <bits/stdc++.h> using namespace std; #define int long long int a[20]; int f[20][...

dp

2020-08-21

1 989

Beacutiful numbers 题解

题意：求出l到r中，能整除自己各非0位的和的数有多少个。转换一下，就相当于求整除自己各非0位的最小公倍数，然后1到9公倍数范围是1到2520，会爆内存，考虑离散化。转移过程有两种，一种是非0的，一种是数位是0的，是0的话最小公倍数不变，否则最小公倍数跟新的数求一下最小公倍数。然后mod要一直取余...

dp

2020-08-20

0 722

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