yngcy

刷题

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

/ 注册

全部文章 / 刷题（共39篇）

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

codeforces1433G Reducing Delivery Cost（最短路）

题目链接：codeforces 1433G 思路：首先预处理在没有免费边情况下的最短路，再暴力枚举边即可。假设当先线路为 j，对于边 (a, b) ，它有两种情况：免费后不在最短路上，结果是 f[j.first][j.second]。免费后在最短路上，因为这条边的价值改变了，可...

2024-03-16

0 0

codeforces1183H Subsequences (hard version)（线性DP）

题目链接：codeforces1183H Subsequences (hard version) 题目思路：求前 k k k 长的子序列。定义dp[i][j] 为前 i i i 个长度为 j j j 的子序列个数，首先将 dp[i-1][j] 的状态转移到 dp[i][j]，再加上不包含...

2024-03-16

0 0