yngcy

刷题

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

/ 注册

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

HDU6957 Maximal submatrix（DP/悬线法）

题目链接：HDU6957 Maximal submatrix 题目描述：给定一个 n ∗ m n*m n∗m 的矩阵，求面积最大的子矩阵，对于该矩阵，满足每列元素是个非递减序列。输入数据格式为，第一行输入测试样例组数 T T T。每组数据首先输入两个整数 n n n...

2024-03-16

0 0

HDU6954 Minimum spanning tree（线性筛/贪心）

题目链接：HDU6954 题目描述：给定 n − 1 n-1 n−1 个点，编号从 2 2 2 到 n n n，边的权值是两个点的最小公倍数。求最小的生成树总权值。输入格式为，第一行输入测试样例组数 T T T。对于每组测试样例，输入一个整数 n n n。其中， 2 ≤ n...

2024-03-16

0 0

HDU6968 I love exam（哈希/线性DP）

比赛时没看出来是背包，还以为是可反悔贪心……补题时看std状态转移方程也看的人麻……原来我还在门外，或者已经入土了…… 题目链接：HDU6968 I love exam 题目描述： Z Z Z 有 n n n 门科目需要考试，而 Z Z Z 所有科目都初始分数为 0 0 0...

2024-03-16

0 0

HDU6976 Game on Plane（思维/贪心)

题目链接：HDU6976 题目描述： Alice 和 Bob 玩一个游戏，有 n n n 条直线在 2D 平面上。Alice 先选择其中的 k k k 条直线，然后 Bob 画一条直线 L L L。Bob 的花费是这条直线 L L L 与 k k k 条直线相交...

2024-03-16

0 0

HDU6979 Photoshop Layers（前缀和）

题目链接：HDU6979 Photoshop Layers 题目描述：给你 n 个图层，自底向上编号从 1 1 1 到 n n n。图层的混合方式有两种，若 m = 1 m=1 m=1，则在之前的图层用当前图层覆盖，即 R n = R i , G n = R i , B n = B...

2024-03-16

0 0

NWERC2020 A Atomic Engery（贪心/背包/鸽巢原理）

题目链接：NEWRC2020 A 题目描述：给你 n n n 个原子，第 i i i 个原子有 i i i 个中子，以及由 a i a_i ai 的能量。接下来由 q q q 次询问，每次输入一个 k k k，表示有 k k k 个中子的原子。若 k ≤ n k \le n k≤...

2024-03-16

0 0

codeforces1260D A Game with Traps（二分/差分）

题目链接：codeforces 1260D 题目思路：求尽可能多的人数，在规定时间内到那目的地，对人数进行二分即可，并且每次带的人敏捷值尽可能高。假设当前人数为 x x x，最低的敏捷值为 y y y。如何求得当前所要花费的最少时间呢？可以用一个差分数组标记，然后通过前缀和计算时间。具体参...

2024-03-16

0 0

codeforces1370D Odd-Even Subsequence（二分/思维）

题目链接：codeforces 1370D 题目思路：二分答案，每次check构造两个序列，枚举答案 x 是从奇数中取得还是偶数中取得。取两个序列长度的最大值 len，即只要有一个序列长度满足条件 len >= k，说明长度还可以再短，答案还可以更小。参考代码： #include ...

2024-03-16

0 0

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