活泼泼

分类

zngg数据结构专题班(6) 题解(21)

/ 注册

全部文章（共27篇）

题解|#智乃酱的子集与超集#

链接：https://ac.nowcoder.com/acm/contest/19483/B简要题意：给出一个数组a，定义一个集合的价值为里头所有物品价值的异或。现给出若干集合，求每个集合所有子集、所有超集的价值之和分析：采用二进制来表示每个集合。二进制的每一位可以看成dp的一个维度。如集合1011...

高维前缀和

2021-08-21

4 1317

题解|#智乃酱的静态数组维护问题多项式 #

题目链接：https://ac.nowcoder.com/acm/contest/19483/D简要题意：给出一个不超过5阶的多项式，再给出一个数组a。m次修改，每次找一段区间[L,R]，给区间里的每个数分别加上f(1),f(2),...,f(r-l+1)利用数学定理：最高次项为n次的n阶多项式差分...

多次前缀和

2021-08-21

1 858

题解|#牛牛的Link Power I#

题目链接：https://ac.nowcoder.com/acm/contest/19483/G 模型总结：模型1：等差数列原数组： 0 1 0 0 0 0前缀和： 0 1 1 1 1 1再前缀和：0 1 2 3 4 5 模型2：平方数列原本数组： 1 1 0 0 0 0 01...

二次前缀和

2021-08-17

0 570

题解 | #积木大赛# && 道路铺设

链接：https://ac.nowcoder.com/acm/contest/19483/I简要题意：对于一个全0数组，每次可以选一段[l,r]，将里头元素全部+1.问要想生成给定数组a，至少需要几次操作分析：差分数组的应用考虑差分数组。每次选择长度[l,r]进行+1时，差分数组中d[r+1]-1，...

2021-08-17

0 621

题解 | #智乃的双塔问题#

题目链接：https://ac.nowcoder.com/acm/contest/19483/E题目一上手，很容易想到动态规划。用dp[i][0]表示从第1层到达第i层左边的方案数，dp[i][1]表示从第1层到达第i层右边的方案数：当梯子为'/'时， dp[i][1]=dp[i-1][0]...

广义前缀和

2021-08-17

2 1040

题解 | #牛牛的猜球游戏#

题目链接：https://ac.nowcoder.com/acm/contest/19483/F简要题意：给出一个长为10的数组，其中仅含0-9且每个数恰好出现一次。给出一个操作集，每次操作可以调换两个数。现在仅针对集合中[l,r]的一小段进行操作，求操作结果这里采用的是广义前缀和的思想，当连续的操...

广义前缀和

2021-08-16

1 1217

题解 | #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 523

题解 | #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 559

题解 | #Brackets#

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

dp

2021-07-13

3 638

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

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

2021-06-05

0 865