Closed Wizmann closed 4 years ago
Code Contest
有N个球，每个球上有一个数字Ai。
从这N个球中取一个球i，问剩下的N-1个球里面，有多少对数字相等的球。
求i = 1...N时的所有结果。
3 <= N <= 2*10^5
如果单纯求某一个结果的时候，这道题就非常简单。我们只需要用一个map统计一下相同的球即可。
但是本题要求1...N的所有结果。这样我们就要尽可能复用之前计算的结果。
可以说，这题是AtCoder ABC160 F题的超级简化版。都是利用f(i)的结果，在较低的复杂度下推出f(i + 1)的结果。
做法就是先求i = 1，然后维护map，并且维护当前的结果。难度较低，这里不展开了。
二进制枚举，Leetcode经典Hard题，略。
给定一个数组A[N]，和一个整数S。 规定F(L, R)的含义是在子数组A[L...R]中，加和为S的子序列的个数。
求在这个数组里所有F(L, R)之和（模998244353）。
1 <= N <= 3000 1 <= S <= 3000
这题的最标准（naive）做法就是开一个三维DP[l][r][sum]，代表在A[l...r]中，加和为sum的子序列的总数。但是在这道题是不行的，会TLE+MLE。所以我们要想办法降低DP纬度。
我们可以只考虑子序列的右边界，DP[r][sum]意为：加和为sum的，并且右边界到r的子序列的种类。这个DP是可以在O(n^2)的复杂度下做的。 这里需要注意一点，如果某一个数A[i]是某一个子序列中的第一个数，它自带i个子序列的种类（数组下标从1开始）。因为对于这一个子序列，其左边界可以有i种。所以要记得加上。
Code Contest
D. Banned K
题意
有N个球，每个球上有一个数字Ai。
从这N个球中取一个球i，问剩下的N-1个球里面，有多少对数字相等的球。
求i = 1...N时的所有结果。
3 <= N <= 2*10^5
解法
如果单纯求某一个结果的时候，这道题就非常简单。我们只需要用一个map统计一下相同的球即可。
但是本题要求1...N的所有结果。这样我们就要尽可能复用之前计算的结果。
做法就是先求i = 1，然后维护map，并且维护当前的结果。难度较低，这里不展开了。
E. Dividing Chocolate
二进制枚举，Leetcode经典Hard题，略。
F. Knapsack for All Segments
题意
给定一个数组A[N]，和一个整数S。 规定F(L, R)的含义是在子数组A[L...R]中，加和为S的子序列的个数。
求在这个数组里所有F(L, R)之和（模998244353）。
1 <= N <= 3000 1 <= S <= 3000
解法
这题的最标准（naive）做法就是开一个三维DP[l][r][sum]，代表在A[l...r]中，加和为sum的子序列的总数。但是在这道题是不行的，会TLE+MLE。所以我们要想办法降低DP纬度。
我们可以只考虑子序列的右边界，DP[r][sum]意为：加和为sum的，并且右边界到r的子序列的种类。这个DP是可以在O(n^2)的复杂度下做的。 这里需要注意一点，如果某一个数A[i]是某一个子序列中的第一个数，它自带i个子序列的种类（数组下标从1开始）。因为对于这一个子序列，其左边界可以有i种。所以要记得加上。