TitanZhang

题解

算法浅谈(1)

/ 注册

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

2020牛客暑期多校训练营（第十场）C-Decrement on the Tree 来自专栏

题目大意有一棵包含n个顶点（n-1条边）的带边权的树，每次都可以选择两个不同的顶点，将这条链上每个边权值减去1。要使所有边权值为零，最小操作数是多少？还需要支持边权的修改：将第p个边的权重更改为w，每次修改后都要输出答案。解题思路没有图示，我很抱歉！我会尽量清楚地叙述一下这个做法的原理。（刚才...

图论

2020-08-11

5 774

2020牛客暑期多校训练营（第十场）I-Tournament 来自专栏

题目大意有n个球队，每个球队都和其它所有球队比一场，所以一共有场比赛，每天一场比赛。每个球队会在第一场比赛开始时到，最后一场比赛后走。安排一个日程表，使所有球队停留的天数之和最小。解题思路最开始拿到题，由于样例的关系，还以为就是暴力输出全排列即可（发出了WA的声音）。输入：4输出：1 21...

构造

2020-08-10

5 1030

2020牛客暑期多校训练营（第十场）D-Hearthstone Battlegrounds 来自专栏

题目大意没玩过炉石的小白翻译：现在有四种随从，这里的每种随从，如果对面没有免疫都是秒杀：带圣盾、亡语；带圣盾；带亡语；普通随从。每种buff的效果：圣盾效果：免疫任何攻击，免疫一次后消失；亡语效果：随从死亡时召唤一个藤蔓；藤蔓：只有1攻击1血量的小怪。每回合都要发动一次攻...

模拟贪心

2020-08-10

10 1255

2020牛客暑期多校训练营（第九场）C-Groundhog and Gaming Time 来自专栏

题目大意给定n个区间[L_i, R_i]，每个区间有 1/2 的概率被选择，表示第i个被选择的线段，求的期望，答案对998244353取模。解题思路不同于官方题解通过树形dp的思路，我们的方法是通过累加每种情况对期望的贡献来求解。线段的交取决于最大的左端点以及最小的右端点，同时维护两个东西比...

期望线段树

2020-08-09

2 804

2020牛客暑期多校训练营（第九场） B Groundhog and Apple Tree 来自专栏

题目大意有一个n个点的树，走过每一条边时会减少一定的hp，每条边只能最多经过2次（即每个子树只能进出一次）。吃了第i个点的苹果会回复a[i]的hp。可以在原地休息，每个单位时间回复1hp。hp不能为负。从根节点1开始出发，初始hp为0，要求经过所有点后返回1号点，求最少休息时间。解题思路这道题...

贪心树形dp

2020-08-09

2 776

2020牛客暑期多校训练营（第九场）J-The Escape Plan of Groundhog 来自专栏

题目大意一堆桌子被排列成n×m（范围为[1,500]）的矩形，a[i][j]=1表示位置(i,j)处有桌子，0表示没有。我们要寻找满足这些条件的子矩形：该子矩形的四条边上没有空位；子矩形中的空位与桌子的数量之差不超过1（不包括侧面的桌子）；子矩形的长度和宽度必须大于1。有多少个子矩形可...

前缀和

2020-08-09

2 746

2020牛客暑期多校训练营（第九场）E-Groundhog Chasing Death 来自专栏

题目大意给出，求出解题思路看到这样的数据范围和数的大小，显然是不可能用类似两重循环的暴力方法搞过的。所以，我们要开始尝试用分解的方式来解决。看到求gcd，就应该尝试对给出的数分解质因数，然后对每个质因数分别讨论其幂次。那么，这个问题就转化为了个子问题。这样，每个子问题都形如给出，要求出 ...

费马小定理质因数分解

2020-08-09

2 693

2020牛客暑期多校训练营（第九场）F-Groundhog Looking Dowdy 来自专栏

题目大意有n天，每天穿一件衣服，第天有件衣服可以穿，穿第件衣服的的权值为。求其中任意m天中，所穿衣服的权值最大值与最小值的最小差。解题思路我们要做的是最小化最大最小值之差，所以必要的肯定是把所有衣服按照权值从小到大排个序。我们可以把每件衣服打一个标记，记录一下是从哪一天来的。然后在里面维护一个...

滑动窗口尺取

2020-08-08

2 786

2020牛客暑期多校训练营（第九场）K-The Flee Plan of Groundhog 来自专栏

题目大意给定一棵有n个节点，n-1条边的树，每条边长度为1，开始土拨鼠在1号节点，沿着最短路走向n号。土拨鼠出发t秒钟后，Orange以2m/s的速度跑向土拨鼠，而土拨鼠以1m/s的速度向任意方向逃跑。设每秒钟土拨鼠先移动Orange再移动。土拨鼠可以选择留在原地。求Orange最晚几秒钟能...

树形dp

2020-08-08

5 794

2020牛客暑期多校训练营（第九场）A-Groundhog and 2-Power Representation 来自专栏

题目大意输入计算式，求解。其中2(x)表示2的x次方，式中每一项都对应着答案在二进制表示下的数位为1的位。解题思路高精度快速幂，冲冲冲！但是要注意的是具体实现时的细节（队友的高精度写的一堆Bug），还有读入时一层层递归下去。 AC代码 #include<bits/stdc++.h>...

高精度

2020-08-08

1 635