yngcy

分类

刷题(39) 编程工具(1) 题解(4)

/ 注册

全部文章（共49篇）

codeforces1041D Glider（二分/前缀和/贪心）

题目链接：codeforces 1041D 题目思路：显然，为了尽可能覆盖多的区间，起点一定是某段区间的左端点，故枚举左端点，二分查找终点，下降的高度用前缀和记录即可。具体参见代码。参考代码： #include <bits/stdc++.h> using namespace ...

2024-03-16

0 0

codeforce1519D Maximum Sum of Products（区间DP）

题目链接：codeforces 1519D 题目思路：区间 dp /记忆化深搜，定义dp[i][j]为翻转区间 [ l , r ] [l,r] [l,r] 的前后差值。状态转移方程为dp[l][r] = dfs(l+1, r-1) + a[r] * b[l] + a[l] * b[r] - ...

2024-03-16

0 0

codeforces1199C MP3（离散化/前缀和/二分）

题目链接：codeforces 1199C 题目思路：将 a [ 1 … n ] a[1…n] a[1…n] 离散化，前缀和维护区间个数。枚举区间起点，二分查找终点，取最大值。参考代码： #include <iostream> #include <map> #in...

2024-03-16

0 0

codeforces1188C Array Beauty（DP/前缀和）

雀食是DP好题，DP玄学优化呜呜。题目链接：codeforces 1188C 题目思路：美丽值与顺序无关，故对数组排序，子序列的美丽值就是所有相邻数的差值的最小值。设美丽值为 x x x 的子序列个数为 cnt[x]，那么美丽值为1的子序列个数为 cnt[1]，它对答案的贡献为 cn...

2024-03-16

0 0

codeforces1119D Frets On Fire（差分/前缀和/二分）

题目链接：codeforces 1119D 题目思路：数据这么大一定是找规律……求区间里数的个数，与顺序无关，不妨先排个序。不难发现当 a [ i ] + r > = a [ i + 1 ] − l a[i]+r >= a[i+1]-l a[i]+r>=a[i+

2024-03-16

0 0

codeforces837D Round Subset（数学/背包DP）

题目链接：codeforces 837D 题目思路：要求结果的 0 0 0 最多，不难想到这个数的因子 2 2 2 和 5 5 5 的个数尽可能多。故将每个数分解，然后就是一个比较简单的背包问题。参考代码： #include <iostream> #include &l...

2024-03-16

0 0

codeforces1486D Max Median（二分/思维）

题目链接：codeforces 1486D 题目思路：二分中位数，每次将大于等于 mid 的数标记为 1 1 1，否则标记为 − 1 -1 −1。我们要找到一个长度为 k 的区间，枚举右端点，每次只要找到一个左端点，使区间 [ l , r ] [l, r] [l,r] 的和大于 0 0...

2024-03-16

0 0

codeforces1228C Primes and Multiplication（快速幂/唯一分解定理）

题目链接：codeforces 1228C 题目思路： f ( x , y ) f(x, y) f(x,y) 是所有 x x x 的质因子在 y y y 中出现次数的乘积，题目要求 1 1 1~ n n n 的乘积，故对于每个质因子，统计其出现次数，再求乘积即可。参考代码： #in...

2024-03-16

0 0

codeforces1603A Di-visible Confusion（思维）

题目链接：codeforces1603A 题目思路：从头开始删数字，对于每个数字 a i a_i ai，如果它不能被 2 2 2 ~ i + 1 i+1 i+1 的数整除，说明它可以被删除。参考代码： #include <iostream> using namespa...

2024-03-16

0 0

codeforces1581C Portal（线性DP/前缀和）

题目链接：codeforces 1581C 思路：定义 dp[i] 为前 i − 1 i-1 i−1 列最小的花费。枚举时先枚举上下边，在对列 DP。因为第 k k k 列可能是边界，也可能在后面的过程中变成中间的部分，所以每次单独计算，而不算在 dp[i] 里面。参考代码： #in...

2024-03-16

0 0