UhhhQQQU

分类

dp中的一些操作(1) 学习笔记(2) 游记(2) 题解(6)

/ 注册

全部文章（共11篇）

有用的链接

线性筛：https://blog.csdn.net/calculate23/article/details/89513721 球&盒子：https://blog.csdn.net/qwb492859377/article/details/50654627 https://www.cnblog...

2022-10-11

0 257

游记|GDKOI2021

Day 1 早上起床时真的好困。。。第一天的题难度是真的大，每一题都只打了部分分，其他的分全不会打，最后只拿到了90分。感觉自己还是太菜了，T3的manacher做过都忘了怎么打，还是要加油啊。。。【注：由于这一天的游记是在Day 2才写的，所以当时的题目都忘了好多了（还是有点儿健忘，好好休息吧）】...

失败经验

2021-01-30

1 445

游记|NOI Online #3 提高组

比赛时间：2020.5.24 做题情况 T1（洛谷难度：普及-）（得分：100）水题，直接在输入时维护各连续区间的和就行中间调试代码时间过长（虽然才做了6分钟）做这种水题时要注意审题，尽量一遍过关 T2（洛谷难度：提高+/省选-）（得分：40）考场做法：矩阵乘法A×B=...

2020-05-29

0 521

矩阵乘法学习笔记

1. 矩阵乘法的运算前提条件：A的列数等于B的行数（否则没有意义）运算过程要计算A×B=C，设A为n*m的矩阵，B为m*p的矩阵，C为积则可以表示为可得C为n*p的矩阵一个例子：相关性质矩阵乘法结合律：A×B×C=A×(B×C) 矩阵乘法不满***换律。...

2020-05-15

0 709

动态规划tips

树形dp 一般的转移方式：dfs 状态的设置一般为：f[当前节点][当前节点（或以节点为根的子树）的状态（特殊点有多少个、该节点染什么色等）] 表示的一般是以当前节点为根的子树对答案的贡献（或最值等）。给出的是无根树，一般有以下情况： a.枚举根的时间复杂度能过的 b.随便一个点为根都行的...

2020-02-18

1 575

题解|恨7不成妻

这题要求的是符合一些条件的数，明显是数位dp的套路，所以我们就向数位dp方面想。先来看条件： 1.整数中不能有7。处理方式非常简单，就是当枚举到7时直接continue掉就行了 2.整数的每一位加起来的和不是7的整数。这个也很简单，在dp数组和dfs中加入...

2020-01-14

0 744

题解|[HAOI2009]逆序对数列

这一题的题面，告诉我们是要求逆序对数为k的数列。但是，恐怖的数据范围说明了一切 n<=1000 k<=1000 这么大的数据，对于求逆序对的任何方法都是会TLE的既然按照题面的说法不行，我们就在我们的知识范围...

2020-01-11

1 840

题解|大吉大利，晚上吃鸡！

因为这道题目要求的是方案数，所以我们设一个两维数组f[i][x]作为从s(i==0)/t(i==1)到点x的最短路的条数。于是条件1就被转化为了：求两个点A和B，使得f[0][A]*f[1...

2020-01-11

9 1106

题解|Eating Together

思路：dp 设两个二维数组f1与f2，它们的定义如下： f1[i][j]：前i个数，最后一个数为j，使这i个数为升序的最小改变数 f2[i][j]：前i个数，最后一个数为j，使这i个数为降序的最小改变数首先，f1与f2的边界条件为： ...

2020-01-11

0 660

题解|数字游戏2

数位dp 题意相信大家都懂（不懂就继续读吧学好文化课吧），接下来看数据范围 1<=a,b<=231 显然，枚举是会T掉的，所以我们考虑数位dp（注意：我是用前缀和来处理出答案的，也就是最终答案为ansb-ansa-1）。 ...

2020-01-11

0 526