活泼泼

zngg数据结...

题解(21)

/ 注册

全部文章 / zngg数据结构专题班（共6篇）

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

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

高维前缀和

2021-08-21

3 1092

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

题目链接：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 603

题解|#牛牛的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 413

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

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

2021-08-17

0 468

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

题目链接：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 803

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

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

广义前缀和

2021-08-16

1 952