做题记录

发表于 | 分类于 |

一些记录

Codeforces:

1.https://codeforces.com/gym/104021/problem/K 悬挂法求最大子矩阵

2.https://codeforces.com/gym/104021/problem/F 打表找公式规律,公式求和简化

3.https://codeforces.com/gym/104021/problem/A 题意理解题,加成计算在最后进行,用dp计算每种加成的最多分数即可(注意dp降维后,循环时也要赋值)

4.https://codeforces.com/gym/104021/problem/D 数学题,运用mobius函数化简gcd=1 题解:https://kanata369.github.io/2022/11/18/CF104021D/#more

5.https://codeforces.com/gym/104021/problem/H图论最短路,双向边处理出联通分量,处理出分量内的最短路,通过单向边拓扑得出其他联通分量的最短距离(注意,源点到不了的联通分量的度贡献需要提前去掉)

6.https://codeforces.com/contest/1795/problem/G bitset trick,分块处理优化时间复杂度 题解:https://kanata369.github.io/2023/02/20/CF1795G/#more

7.https://codeforces.com/contest/1681/problem/F 虚树dp,因为考虑的是边权,所以使用pw[i]表示i的父节点到i的边的权值,以此建立边到点的一一映射.将求路径条数转换成求dp[i][0]和dp[i][1],其中dp[i][0]表示i的子树中端点为i的,权值出现0次的路径条数,dp[i][1]表示权值出现1次的路径条数