夏驰

分类

题解(3)

/ 注册

全部文章（共3篇）

题解 Matrix and GCD

本题解仅提供F题的另一种求解全一子矩阵个数的方法众所周知，求解全一子矩阵的问题可以用单调栈解决，例如最大子矩阵，子矩阵个数而有另一种工具也可以有效而优雅地解决该类问题，那便是笛卡尔树 (上面的超链接里有介绍笛卡尔树，并且提供了求解最大子矩阵的做法和例题) 如果你熟悉了笛卡尔...

C++

2022-08-16

1 587

Eyjafjalla 2021牛客暑期多校E

该解法时间复杂度为O(nlognlogn)。貌似很多大佬都用优秀的O(nlogn)就把题目解决了，这里提供一种时间复杂度并没那么优秀的解法（离线 + dsu on tree + 树状数组）。题意：n个火山形成一棵树，1号火山为根节点，每一个火山都有权值，t[i]表示第i座火山的温度。对于从...

2021-08-16

2 473

牛客练习赛84 C 牛客推荐系统开发之选飞行棋子

首先这题题型很DP，然后容易想到DP状态f[i][j]为前i个人用前j种棋子的方案数。后来感觉状态转移不太好写(本人太菜)，就把第一维改成了四个人有无使用棋子的状态压缩，状态转移就很显然了。这里我用的是刷表法：f[k][j+1] += f[i][j], 当且仅当：1. 在二进制下，i为k的真子集，且...

2021-06-12

1 626