cheese_case

分类

dp题解(2) 题解(25)

/ 注册

全部文章（共26篇）

题解 | #黑白树#

这题容易想到要从下向上贪心，因为从一个点开始只能染色其以及其上方的一些点，而其下方的点需要额外考虑染色，故而从叶子节点开始考虑染色，叶子节点必须染色其范围是k[i],但是并不是最上面一个点才继续染色，而是当前染色点所包含所有点染色后这些点所能达到的最远距离，如果还需要染色，则染可以更新最远距离相对...

2022-03-10

1 476

题解 | #筑巢#

这题有个小坑，很荣幸踩了进去就是ans得初始化必须是-inf ，各位可能会习惯性初始化为0 思路就是只有子点与相连边的和>0就选择它，反之不选，一个假冒伪劣的树形dp 因为建立树时写成了v[b].push_back[b]导致查不出错误，下次直接把头剁了 #include<bits...

2022-03-05

5 452

题解 | 小沙的算数

写一个极简版的，思路：保存每一个有效数区间例如 2+432+53+2 那就有4个区间要保存，分别为2,432,53,2用一个数组保存他们对应的值，考虑到一个区间中所有元素都要能查询到这个值，可以用两种方法运用并查集，将乘法块中的每个数都指向其第一个元素运用一个指针数组，pos[i...

2022-02-07

1 589

题解 | #树#

这题主要就是数中分离连通块的操作相当于切边其次就是逆元打表啦，重要公式: inv[i]=((mod-mod/i)*inv[mod%i])%mod; C与A ll C(ll x,ll y){ return f[x]*inv[x-y]%mod*inv[y]%mod; } ll A(l...

2022-02-05

1 391

题解 | 智乃的数字积木(easy version)

前言: 大家一定要先看清数据范围，分析清楚再写如E题是可以纯暴力模拟的一题且只需要40+行，每次直接暴力找p和q的连接段并进行排序 ">using namespace std; typedef long long ll; const int N = 2e5+8; const int mod...

2022-01-30

0 436

题解 |n的约数

感觉很经典的题目，竟然没有题解质因数分解和约数公式大家都不陌生直接上图又公式不难分析出对于n之内的数尽量让小的因子更多，但并不绝对，比如 2个2 1个3 肯定比 1个2 2个三划算，故选i个2 后面的s一定小于2所选个数，这是对于dfs的一个优化关于这个dfs：对于每个数我们选择多少个...

2022-01-27

3 703

题解 | 选择困难症

感觉这题dp不错，尤其是对于剪枝得思考应该挺常用，先说说我对于dfs得感受:对于每一层得所有可能都要考虑，然后进入下一层即可，对于此题每一层得所有可能即是当前step选哪一个/不选，对于具体细节请看注释 ">using namespace std; typedef long long ll; v...

2022-01-27

1 470

题解 | #九小时九个人九扇门#

整理下当时写A的思路，有点混乱导致花费了大量时间题意 : 从n个数中选出k个(k<=n)使得其和的根=i 问有多少种选取方法第一反应要组合数，然后容易发现gen(a+b)=gen(gen(a)+gen(b)),故先把所有输入全部转换为gen(a[i])； n的大小大概复杂度很适合dp，...

2022-01-25

6 524

题解 | #绝命沙虫#

C.绝命沙虫确实绝了我老命，每次碰到卡精度的东西冲不过去都会直接开摆这次算是涨了记性，仔细看了一下double的精度问题才发现，double类型在计算时会转化为二进制故有损失，例如 double a = 3.0-2.6结果是0.3999999999999999，这就是精度损失故（m-1）是do...

2022-01-22

2 377

题解 | #深渊水妖#

1. 个人总结前言这次小白月赛也算是一个教训，检验出了很多常见问题和不好的习惯，如下喜欢每个测试点memset(a,0,sizeof(a))而导致超时，代码写的比较复杂而不考虑尽可能简略以减少错误读题一掠而过，长一些的题目很经常读错导致代码写错 1，2两个问题集中体现在第一题和第二题...

2022-01-22

2 394