ThinkofBlank

题解

未归档(4) 论文(10) 题单(1)

/ 注册

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

Steps to One 题解

挺简单的一道概率dp+简单数论+简单容斥题目。由于是编译器小白，枚举了n次编译器qwq。。。 c++的同学建议用clang++17那个编译器qwq 一.概率dp+简单数论部分比较容易想到的，我们设表示当前gcd为i，期望步后到达1 初始化然后，我们来推下转移方程: 明显的有，那么，我们只要...

数论题解动态规划研究

2020-06-08

4 947

比赛题解

一开始以为求第0-12个问题的解决概率懵逼了很久一道简单的概率dp/dfs问题我们先求出每个问题的解决概率。我们运用正难则反的思想，先求出我们不能解决第i个问题的概率，即：然后，用1减去这个概率就是第i个题可以解决的概率了，设为那么，现在就可以随便乱搞了。注意到，n很小，可以直接dfs...

优化题解动态规划

2020-05-18

4 893

加分二叉树题解

一道比较经典的区间dp题目首先我们设dp[i][j]表示我们用i-j这些点构造树的最大收益是多少首先dp[i][i]=a[i]（只有一个点，最大价值即点本身价值）现在，我们考虑转移：因为一颗子树的价值=左子树价值*右子树价值+根价值那么，如果我们知道了根，左子树，右子树后，就可以进行转移了...

题解动态规划

2020-05-12

1 726

Moovie Mooving 题解

一.闲话英文题真难受，盯google盯了好久qwq，输入部分还是看样例解释看出来的qwq,英语菜鸡没人权qwq 二.题解这道题，题意是：有n场电影，每场电影都有若干场。给你每个电影的播放时间以及每场的开始时间，问你，要连续不断的看电影直到看到l为止，最少需要看几部电影（每部电影最多看一场） ...

题解动态规划

2020-05-09

0 705

「火」皇家烈焰题解

明显动规求解。因为每个点的情况之和其左右两边那个点有关，所以，我们只需知道一个点左右两个点的状态就可以算出这个点的情况了，那么我们考虑将一个点左右两个点的状态储存下来。但是，仔细分析下，我们i这个点是由i-1这个状态转移过来的，那么，我们转移过来的时候，其实并不需要知道i-1这个点前面那个点的状态...

题解动态规划

2020-05-06

2 1267

[SCOI2009]粉刷匠题解

一.闲话五一收假了，qwq好气哦二.题解终于做到原题了（雾）这次就是一个比较简单的dp，只是状态的复杂度。。。（请参考传纸条）我们设dp[i][j][k][0/1]表示已刷完i-1个木块，第i个木块我们刷了前j个格子，第j个格子是否刷成符合我们需求的颜色,我们一共刷了k次所能获得的不难发...

题解动态规划

2020-05-02

0 698

美味菜肴题解

一.闲谈好吧，又是个套路题。。。我对题面已无力吐槽。。。“第3-n+2行”明明应该是“第3-m+2行”，害我debug好久qwq 二.题解首先，明显这是一个01背包问题（一开始看到食材无限时，以为是完全背包，结果被样例2卡了，样例出的不错。。。）当然，我们直接打01背包是会错的，为什么？因为...

排序题解动态规划

2020-04-27

1 799

Removal 题解

update:添加了个优化又是一道简单dp,qwq 我们读题，发现k和m的范围都很小，所以我们考虑从这里入手我们设dp[i][j]表示选了i个数，最后一个是j的方案数，那么就有：那么，我们想下转移。首先，我们枚举新增了一个数a[i] 那么，分为两种情况: 一.a[i]被剔除了这个情况下，...

题解动态规划

2020-04-24

4 928

子序列题解

update:新方法，树状数组优化dp，复杂度一道很简单的dp+数论题。。。我们设dp[i]表示以i结尾的子序列中成立的方案数那么，就有转移：答案就很显然了: 于是这题就基本做完了，不过，麻烦的是，你需要做这个式子如果我们直接算，最大的情况就可能搞出个,然后爆炸(当然，你要打个高精也没...

数论题解动态规划

2020-04-23

5 1154

[CQOI2013]二进制A+B 题解

一道数位dp题，状态有点复杂但是不难补个范围：题目大意：给你三个数:a,b,c你可以对这三个数的二进制进行任意排列使得最终满足：c=a+b求最小的满足条件的c，如果没有输出-1这道题，我们考虑先计算出a,b,c各种的二进制中有多少个"1",分别设为：A,B,C在算出三个数中二进制长度最长的，设...

题解动态规划

2020-04-17

0 1123