Z_L_G

分类

总结(20) 训练赛(18) 题解(129)

/ 注册

全部文章（共40篇）

最大全0子矩形问题

题意对于一个由0,1构成的矩形，求解其中面积最大的全0子矩形，和全0子正方形思路法一：枚举上下左右四个边界，利用二维前缀和，如果前缀和为0就成立复杂度：法二：枚举左右边界，对边界内的1按y排序，每两个相邻点+边界构成矩形复杂度：,(m为1的个数，最多到) 法三：悬线法，...

dp

2025-07-06

0 31

算法入门-小A买彩票

题意买彩票，3元一张，中1,2,3,4元的概率相等买n张，求不亏的概率输出要求：最简分数，如果概率为0就输出"0/1"，概率为1就输出"1/1" 思路类似昨天弹球的问题状态转移可以靠钱勾连表示买了i张彩票赚j元的可能最后求一个GCD就行，注意只要买了就会亏，所以概率为1只有可能...

dp 概率

2025-06-28

0 37

算法入门-数学考试

题意给定n个数，求两个长度为k的不连续区间和最大是多少思路选择两个不重叠区间，必然一个在左，一个在右可以维护一个前缀和，用表示0~i中最大的长度为k的区间的值然后从后往前遍历，取每一个长为k的区间，为右区间，同时通过在O(1)的时间内获得左区间的最大值，两者相加即可也可以直接维护一...

dp

2025-06-28

0 34

算法入门「木」迷雾森林

题意类似于过河卒思路正常实现即可，注意取模代码 #include<bits/stdc++.h> #define N 3030 #define mod 2333 using namespace std; int a[N][N]; long long dp[N][N]; ...

dp

2025-06-27

0 44

算法入门-[NOIP2002]过河卒

题意 n*m的棋盘，卒在(0,0)，可以向右或者向下走，最终要走到(n,m)，同时，棋盘上还有一匹马，它会控制他能走到的8个点，以及它自己所在的位置,卒不能走这几个位置请问最终有多少条路径能让卒走到(n,m) 思路实现方法一：提前把不能走的点标一个极小值，转移方程为实现方法二：走到每一个...

dp

2025-06-27

0 51

算法入门-钉子和小球

题意一个竖直放置的三角形模板，钉着n(n+1)/2颗钉子，最底下有(n+1)个格子从最顶上落下一个小球，小球碰到钉子落向两边的概率相等求去除m个钉子后，落到最底下第m+1格的概率是多少，以a/b的形式输出思路概率不好处理，不妨认为小球每下落一层就分裂成两个，在有钉子的地方，一个去左边...

dp 概率

2025-06-27

0 44

算法入门-花店橱窗

题意花店有f朵花，v个盆，每个花放每个盆有不同的美观度，求如何摆放能使美观度最大特别的，给花编上号，花必须按照顺序摆放，编号小的的花不能放在编号大的花的后面思路由于必须按照顺序摆放，所以新的一盆花可放的盆一定是上一盆花放的盆的后面初始化:对于最开始，每朵花放在自己编号的盆里，其它...

dp

2025-06-27

0 29

算法入门-免费馅饼

题意在一个W*H的长方形平面内，有若干块饼下坠，每块饼会有{下坠时间，下坠位置，下坠速度，价值}四个信息人最初站在中间，可以移动(-2,-1,0,1,2)，请输出最多获得的价值以及开始后每一秒的操作思路这题有很多坑点显然是一个动态规划，状态转移方程坑点1:由于起点强制锁定在中间，但...

dp

2025-06-27

0 36

算法入门-舔狗舔到最后一无所有

题意每天可以从三家店中选一家，不能连续三天选同一家，t次询问，每次询问连续选n天有多少种不同的选择方案思路简单动态规划，显然第i天的可选择方案数取决于第i-1和第i-2天对于任意一个店，第i天可以选它的情况是第i-1天选另外两家，不用考虑第i-2天第i-1天选它，第i-2天只能...

dp

2025-06-24

0 39

算法入门-方块与收纳盒

题意走楼梯，斐波那契换了个描述思路水题，代码 #include<bits/stdc++.h> using namespace std; /** * dp[i]=dp[i-1]+dp[i-2] */ vector<long long> dp(100); in...

dp

2025-06-23

0 44