TitanZhang

题解

算法浅谈(1)

/ 注册

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

2020牛客暑期多校训练营（第七场）C A National Pandemic 来自专栏

题目大意给定一棵大小为n的树，有m次操作，分为三种： (1 x w) 位置x上的权值+w，同时所有位置的权值加上w-dis(x,y)；（dis(x,y)为从x到y的边数） (2 x) 如果x位置的权值>0，那么设为0。 (3 x) 输出x位置的权值解题思路这题有很多种做法，我再这里用...

树链剖分

2020-08-06

3 1038

2020牛客暑期多校训练营（第八场）E Enigmatic Partition 来自专栏

题目大意数字n的分区是所有数字之和等于n的集合。如果分区满足以下条件，则称为神秘分区：是整数，对于，。对于任意，设为的神秘分区的个数。现对于给出的每对，求出。解题思路感谢大佬的思路：https://blog.csdn.net/tianyizhicheng/article/de...

二阶隔项差分数学

2020-08-04

2 860

2020牛客暑期多校训练营（第八场）G Game SET 来自专栏

题目大意一张纸牌有4个特征，每种特征有3种不同的情况，所以一套牌中有81张不重复的牌。对于4种特征中的每种，当任意三张卡牌这项特征完全相同，或完全不同时，这三张牌组成一个set。有一些万能卡，万能卡的某些特征可以任意决定，例如[*][diamond][solid][red]可以任意决定第一项特征。...

暴力

2020-08-04

1 749

2020牛客暑期多校训练营（第八场）K Kabaleo Lite 来自专栏

题目大意有n道菜，第i道菜有bi盘，每盘利润为ai（利润可能为负）。遵循以下规则为每个顾客上菜：● 每位顾客至少有一道菜。● 每位顾客都得到从1开始的连续编号的菜，每道菜只吃一盘。问能容纳的最大的顾客数，已经可赚取的最大利润。解题思路出题人：这是一道简单题。可以发现，i因为所有人都必须吃...

贪心

2020-08-03

6 874

2020牛客暑期多校训练营（第八场）I Interesting Computer Game 来自专栏

题目大意一个游戏有N个回合，每回合提供两个整数ai和bi，每回合只能选以下三个操作之一。不做任何操作。如果ai没被选过（指ai的数值），可以选择ai。如果bi没被选过，可以选择bi。先给出所有a1,a2,...,an与b1,b2,...,bn，求出选择的最多整数数量。解题思路 ...

图论并查集

2020-08-03

4 651

2020牛客暑期多校训练营（第七场）J Pointer Analysis 来自专栏

题目大意指针分析旨在确定在执行过程中可以通过程序中的特定指针变量访问哪些对象，这是静态程序分析的基本部分之一。现在，我们希望您对测试数据执行上下文无关的指针分析。一个程序包含26个用小写字母表示的object，每个object也有26个用小写字母表示的成员变量（也称fields，是指向某个ob...

暴力指针

2020-08-03

2 772

2020牛客暑期多校训练营（第七场）G Topo Counting 来自专栏

题目大意原题长的一批的翻译：有一种有向图，被称为排列的DRG图，其包含组节点，第组包含个节点：。 DRG上有2种边：组内边和组间边。第组内的组内边可以表示为：（应该都能看懂）组间边可以表示为：现在我们想知道排列的DRG图的拓扑序列的数量。有向图的拓扑序列可以表示为：。所有节点来自且对于任意...

拓扑排序动态规划组合数学

2020-08-02

1 845

2020牛客暑期多校训练营（第七场）A Social Distancing 来自专栏

题目大意在半径为的圆内放个人，使得相互之间距离尽可能远，即使得尽可能大，表示第i个人与第j个人的欧几里得距离。解题思路这道题我们考虑用dp来做。很容易得出，我们的n个点的距离和为：将其化为加法，可以推出这样的式子：每次直接求出前面一项，而后面用勾股定理求即可。 AC代码 #include&...

平面几何动态规划

2020-08-02

1 817

2020牛客暑期多校训练营（第七场）I Valuable Forests 来自专栏

题目大意我们将无根树T的价值定义为，其中V(T)是T的所有顶点的集合，而d(u)是T的度数。（即内部每个节点度数的平方和）我们将森林的价值定义为森林中所有树木的价值之和。求所有包含N个节点的森林的价值总和，答案对素数M取模。解题思路这题需要用到prufer序列的结论：初识prufe...

prufer序列动态规划组合数学

2020-08-02

5 1140

2020牛客暑期多校训练营（第七场）D Fake News 来自专栏

题目大意（这道题的原版真的有太多槽点了xswl）简单地说，给定n，判断是否为一个平方数。就是判断是不是完全平方数。解题思路这道题队友打了一会表，就猜到了以下第一种操作（大佬带飞tql）最简单的做法，直接特判n是否为1或24即可。证明比较复杂，可以参考： https://www.zhihu...

数学

2020-08-02

1 680