2759 一个动态树好题（数论转化图论）

Day 1 早上起床时真的好困。。。第一天的题难度是真的大，每一题都只打了部分分，其他的分全不会打，最后只拿到了90分。感觉自己还是太菜了，T3的manacher做过都忘了怎么打，还是要加油啊。。。【注：由于这一天的游记是在Day 2才写的，所以当时的题目都忘了好多了（还是有点儿健忘，好好休息吧）】(2021.1.29)（写于：2021.1.30） Day 2 昨天晚上11点才睡，今天早上精神不是很好。题目下发下来，我粗略地看了一下所有题后直接就去开T1了，没想到，这一开就是2.5h...T1"做出来后"，剩下三题也没有什么时间做了，就都打了暴力。（T2调了蛮久，T4在最后...

比赛时间：2020.5.24 做题情况  T1（洛谷难度：普及-）（得分：100）  水题，直接在输入时维护各连续区间的和就行 中间调试代码时间过长 （虽然才做了6分钟） 做这种水题时要注意审题，尽量一遍过关  T2（洛谷难度：提高+/省选-）（得分：40）  考场做法：  矩阵乘法A×B=C，将"×"重载一下，将中的加号改为异或，仍然满足结合律 将题目所给的设为矩阵A 将图以邻接矩阵的形式存储下来，设为矩阵B 则C为，使用矩阵快速幂求解 时间复杂度为   未完待续。。。

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

树形dp 一般的转移方式：dfs  状态的设置一般为：f[当前节点][当前节点（或以节点为根的子树）的状态（特殊点有多少个、该节点染什么色等）] 表示的一般是 以当前节点为根的子树对答案的贡献（或最值等）。 给出的是无根树，一般有以下情况： a.枚举根的时间复杂度能过的 b.随便一个点为根都行的 c.先随便一个点来dp，然后再进行换根操作的（二次扫描换根法）（例子：POJ3585） 与背包问题的结合（例题：二叉苹果树）   期望dp  倒序（递归）进行dp   区间dp  枚举区间长度，再枚举左端点   背包问题  一维1到n 01背包：二维m到v_i 完全背包：二维v_i到m 多重背包：二进...

https://mp.weixin.qq.com/s?__biz=MzI4MzQ4NzAwMw==&mid=2247484153&idx=1&sn=cba74ff1df395b1235fd2c27e74f1b51&chksm=eb88bc8ddcff359bfd6638d464e0379b07cc2bb2cf4f5b092ed5612d3bfa636114a36af57772&scene=21#wechat_redirect

这题要求的是符合一些条件的数，明显是数位dp的套路，所以我们就向数位dp方面想。   先来看条件：   1.整数中不能有7。处理方式非常简单，就是当枚举到7时直接continue掉就行了   2.整数的每一位加起来的和不是7的整数。这个也很简单，在dp数组和dfs中加入一个记录当前每一位的和的维度就行了。   3.这个整数不是7的整数倍。在转移过程中，假设我们的原数是a，要新增的数字是b，那么我们的新数就是a*10+b，继续增加一个维度来记录。       对于这一题来说，处理条件并不大难，有难度的地方在数字的平方和的维护。维护平方和需要我们在转移的过程中记录三个值：   1.与7无关的数字个...

这一题的题面，告诉我们是要求逆序对数为k的数列。   但是， 恐怖的数据范围说明了一切   n<=1000 k<=1000   这么大的数据，对于求逆序对的任何方法都是会TLE的       既然按照题面的说法不行，我们就在我们的知识范围内搜索：   图论？数论？dp？   (实际上并不是这么简单，要多做题才能理解这其中的套路)   没错！就是dp！   在dp中，有一种类型是专门用来计算符合每种规则的dp——计数dp   接下来，就是       设置状态      按照一贯的套路，求什么设什么   我们设f[i][j]为在长度为i的所有排列（全排列）中，逆序对数为j的个数   ...

    因为这道题目要求的是方案数，所以我们设一个两维数组f[i][x]作为从s(i==0)/t(i==1)到点x的最短路的条数。于是条件1就被转化为了：       求两个点A和B，使得f[0][A]*f[1][A]+f[0][B]*f[1][B]=f[0][T](或者f[1][S])       为了求出f数组，我们需要正反各跑一遍dijkstra，然后建出一个从S到T的最短路的图（显然这个图是一个DAG）。于是我们就满足了条件1。       对于条...

思路：dp   设两个二维数组f1与f2，它们的定义如下：   f1[i][j]：前i个数，最后一个数为j，使这i个数为升序的最小改变数   f2[i][j]：前i个数，最后一个数为j，使这i个数为降序的最小改变数   首先，f1与f2的边界条件为：   f1[1][j]=[d[i]=j]   f2[1][j]=[d[i]=j]   然后，经过简单的推理，容易得出dp方程：   f1[i][j]=min{f1[i-1][k]+[j=d[i]]} (1<=k<=j)   f1[i][j]=min{f1[i-1][k]+[j=d[i]]} (j<=k<=3)    最后，把...

数位dp   题意相信大家都懂（不懂就继续读吧学好文化课吧），接下来看数据范围      1<=a,b<=231     显然，枚举是会T掉的，所以我们考虑数位dp（注意：我是用前缀和来处理出答案的，也就是最终答案为ansb-ansa-1）。       1.状态的设置       首先，因为是数位dp，所以状态的第一位肯定是数位。接着，我们再来分析题目，看有什么东西是必须记录的。然而，因为这一题的状态十分明显，就是各个数字之和，所以我们就直接拿这个和当作第二维的状态。最终的状态就是f[i][j]，代表有i位，数字和为j且满足题目所求（数字和...

应该都不难看出这是个树形dp吧，那接下来就讲过程了。   状态设置       我们设置一个dp数组f[i][j]，表示以i为根的树，当前状态为j时设置看守的最小花费。       a.i表示当前结点的编号。        b.j表示当前结点的状态，根据题意，只要在某一个结点设置看守，那么它的父亲与儿子也会受到影响。所以对于一个结点,可能会有以下三种情况：1.被它的父亲影响；2.被它自身设置的看守影响；3，被它的某一个儿子影响。        这样，我们就设好了状态。    状态转移方程    ...

 准备SCP，然后翻车。。。