活泼泼

题解

zngg数据结构专题班(6)

/ 注册

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

题解 | #Palindrome#

简要题意：给出一个字符串，求增加多少字符能使之回文方法：串长减去最长回文子序列长度，即增加非最长回文串的内容传统方法dp[i] [j]表示i到j最长回文串长度若s[i]==s[j]，dp[i] [j]=dp[i+1] [j-1]+2否则dp[i] [j] = max(dp[i+1] [j],dp[i...

dp

2021-07-15

1 521

题解 | #Maximum sum#

简要题意：给一串数，找连续两串使其和最大传统求最大子串的方法不能保证两段不相交，因此考虑多开个b数组记录以它开头的最大子串令a[i]为以i结尾的子串最大和，b[j]为以j开头的子串最大和，这样ans=max(a[i]+b[j])，这样需要O(n^2) 下面考虑将其优化成O(n): 法一：(官方题...

dp

2021-07-15

0 556

题解 | #Brackets#

一开始我去考虑每个空格接受的球，后来发现想复杂了。如果最上面定义为第0行，最下面是第n-1行，那么我们可以手动补充第n行，也就是把最下面的每个格子都看成一个钉子。这样就不用考虑空格了，只需考虑钉子的事情。令dp[i][j]为走到第i行第j列的球数，sum为最后一行的总和，那么所求的答案就是dp[n...

dp

2021-07-13

3 637

题解 | #[NOIP2010]关押罪犯#

目标：影响力最大的冲突事件最小常见思路：①贪心；②二分；③搜索、动态规划贪心：先按照冲突从大到小排序，冲突大的先分开：对每个罪犯建两个点，表示他在A或B监狱。若两人分开，则罪犯1在A监狱与罪犯2在B监狱合并、1在B与2在A合并。如果后面想分开两人时，发现他们已经在同一集合中，则这个事件就是...

2021-06-05

0 862

题解 | #Defeat the Enemy#

2014上海区域赛真题uva一直连不上，下面的代码是我在vjudge上提交的首先，敌人按照防御从大到小排序，先解决防御强的敌人，这里用结构体数组保存就可以了。我方按照攻击力从大到小排序。每次解决防御最强的敌人：先把我方攻击力高于对方防御的人加入集合s，则集合s中的人都是这次行动的可能人选。由于对方防...

multiset

2021-05-17

2 698

题解 | #Efficient Solutions#

源自雨巨的课程ppt首先考虑一下静态的情况：如果给定了n个点，如何求其中优势点的个数？要找一个优势点A，就是以A和原点O为对角点的各边平行于坐标轴的矩形中，没有其他的点。也就是说，如果不存在一个点的x和y都比A小，那么A就是优势点。所以要想找优势点，就是要同时比较x和y的大小。考虑x用于枚举，y用于...

2021-05-16

3 698

题解 | #[JSOI2007]建筑抢修#

可反悔的贪心。从小到大对倒塌时长排序，先修快倒塌的（从小到大枚举修理时长）。如果时间不够修当前的楼，就先判断这个楼是否有必要修（修它的用时<修之前楼用时的最大值，就有必要修）。如果没必要就不修，如果有必要就把前面修的时间最长的楼去掉，不去修它。 #include <bits/stdc++...

2021-05-16

0 536

题解 | #tokitsukaze and Soldier#

按照s从大到小排序。先选s大、宽容的人，他能接受的人最多，然后再不断选s小的人。如果人数超了，就把战斗力最低的人踢掉（贪心完的后悔）。这样其实是决定枚举最大人数的人，先找s大的人，就不会对后面有影响，不会出现：我的s满足了，但上一个选进来的人s不满足。这样保证后面来的人能容忍的人少，前面人的s大，不...

堆贪心

2021-04-17

0 492

题解 | #Running Median#

利用对顶堆求中位数我们可以构造两个堆，堆1放小的数，堆2放大的数。堆1为大顶堆，记录这些小的数中的最大者；堆2为小顶堆，记录这些大的数中的最小者。每次输入一个数，只需要把它和小顶堆的最大数比较，若这个数小于堆顶，表明这个数小，就放进小顶堆；若这个数大于堆顶，表明这个数大，放进大顶堆。当输入的元...

对顶堆

2021-04-17

0 473

题解 | #合并果子#

典型哈夫曼树问题方法一：使用小根堆解决 #include <bits/stdc++.h> using namespace std; typedef long long ll; int n; priority_queue<int,vector<int>,greater&l...

最小堆哈夫曼树

2021-04-17

0 693