DearFrozencodechenback

分类

题解(8)

/ 注册

全部文章（共8篇）

题解 CF1165E

这题一眼排序不等式，第个位置会贡献次(乘法原理),于是写了个排之后再逆序排，两个乘起来再乘以贡献的次数，结果。然后就发现哪里不对了，事实上位置是固定的，所以排序不等式中的应该是，这里需要特别注意的是，因为排序不等式中是要最大的配上最小的，所以在算排序不等式中的是不能取模的！！！（取模后最大的就不一...

2019-08-16

0 570

题解 CF1187C

看到这个问题，我们先分析下什么时候不可行。为了方便我们称的区间为区间，称的区间为区间经过漫长的讨论，我们发现只有当一个区间是一个区间的子区间时答案是不存在，其他情况都可以通过构造得到。那么问题就转化为判断每一个区间是否是某个区间的子区间。不难想到把区间要求离线下来，同时对于每个点用并查集维护...

2019-08-16

0 543

题解 P3313

做法前面的大佬都说的很清楚了，这题的关键主要在于对宗教建线段树和动态开点。既然是动态开点就要记录下每个节点的左右儿子，这里用引用调用来更新每个点的左右儿子。事实上能对答案产生贡献的只有有值的节点，所以对于没有值的节点我们不需要把它建出来，这样可以省不少空间。这里仿照了Owen_codeisking...

2019-08-16

0 581

题解 CF1190D

扫描线板子题？首先离散化是理所当然的，因为这个矩形无上界，我们考虑按排序，从上往下枚举。（其实也算是出题人的暗示）接下来的问题是如何统计下界为的矩形数量，事实上我们只关心矩形的和,自然而然想到枚举,枚举什么？？枚举和会让复杂度爆炸。考虑如何优化，（当然是换个东西枚举）我们选择枚举相同的点，对于...

2019-08-16

0 487

题解 CF1200E 【Compress Words】

这题事实上要我们求的是: 当前拼接好的串的后缀和待拼接串的前缀的最大匹配长度。可能有点绕，我们结合样例2来理解下。当前拼接好的串待拼接串后缀和前缀的最大匹配最大匹配长度所以我们只要把加入到当前拼接好的串。此时当前拼接好的串这下应该理解了吧那么怎么求最大匹配长度...

2019-08-16

0 768

题解 NOIP2017 pjT4 【跳房子】

蒟蒻不会单调队列，怎么办？另类方法，一样AC 题目要我们求最小的，这看上去就不太好直接求。怎么办？一个常见的想法，将原问题转换成判定性问题:给定弹跳距离的范围，能否获得至少分。(注意:玩家可以在任意时刻结束游戏，所以只要出现一个时刻的分数满足即可）一个朴素的想法:可以DP! 每次找前面合法状态(...

2019-08-16

0 796

题解|算法竞赛进阶指南选课

树形dp模板题首先建一个虚拟节点0，让原本的森林变成一颗树。然后我们设dp[i][j]表示以i为根的子树中,选j门课的最大价值。转移时我们枚举当前以x为根的子树选课的数量(t)，以及分配给x的子节点y多少节课(j)。不难写出方程：dp[x][t]=max(dp[x][t],dp[x][t-j]+dp...

2019-08-16

1 568

题解|算法竞赛进阶指南巡逻

k=1时，如果我们新修建一个道路，那么就会有一段路程少走一遍。此时选择连接树的直径的两个端点显然是最优的。难就难在k=2的时候，还是上面的思路，先连接两个直径的端点。假设我们接下来连接的是x,y两个叶子结点，它们到直径的距离分别为dis[x],dis[y]，并设直径上两点的距离为d[u,v]，这里...

2019-08-16

1 848