夏驰

题解

/ 注册

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

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