Z_L_G

题解

总结(20) 训练赛(13)

/ 注册

全部文章 / 题解（共34篇）

算法入门-[NOIP2003]加分二叉树

题意一个1-base二叉树，n个结点，中序遍历为(1,2,3,...,n),每个点有一个val，选择一个子树的加分规则如下：如果某个子树为空，就视为val=1，叶子节点分数为本身的分数求符合中序遍历的加分最高的二叉树，输出加分和前序遍历思路对于一段中序遍历序号，总需要选择一个根，切分...

区间dp dp

2025-07-09

0 29

算法入门-树学

题意一个树，n个结点，每个结点的深度是到根的距离，整棵树的价值是所有点的深度和求选择哪个点为根时可以使深度和最小思路让每一个点为根跑一遍dfs就可以维护出每个点的深度和整个树的深度和但是让每一个点跑一遍复杂度会爆炸能不能只跑一遍？如果只跑一遍，根变换怎么办对于一个选定根的树，如果...

深度优先搜索 dp

2025-07-09

0 16

算法入门-[NOIP2018]货币系统

#动态规划 #完全背包题意给定一个n种面值组成的货币系统，如果其中某一个面值可以由系统中的其它货币表示就认为这个面值是冗余的求出这个货币系统去除冗余后最少有几种面值思路按照题意完全背包即可注意判断一个货币是否冗余，是在使用它之前判断是否已经被表示代码 #include<b...

dp 完全背包

2025-07-08

0 28

算法入门-[SCOI2009]粉刷匠

#动态规划 #多次dp 题意有n块木板，每块木板有m格，你可以粉刷t次，每次可以粉刷连续的若干格，不能覆盖给定正确的粉刷方案，请问最多可以刷对多少格 0<=n,m<=50,t<=2500 思路如果只有一块木板，可以线性dp解决表示刷i次，刷到j 对于若干块板子，如果...

dp 多次dp

2025-07-08

0 26

脑洞大开-打砖块(brike)

#妙妙题 #动态规划题意倒置金字塔形的砖块墙，共有n行，第i行有n-i+1块砖每块砖有价值，敲掉一块砖需要敲掉它左上和右上的两块砖敲掉m块砖能获得的最大价值总和是多少 n<=50,m<=500 思路原数据读入形式如下 1 2 3 4 5 1 2 3 4 1 2 3...

妙妙题 dp

2025-07-08

0 25

算法入门-小A买彩票

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

dp 概率

2025-06-28

0 28

算法入门-数学考试

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

dp

2025-06-28

0 28

算法入门「木」迷雾森林

题意类似于过河卒思路正常实现即可，注意取模代码 #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 29

算法入门-[NOIP2002]过河卒

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

dp

2025-06-27

0 26

算法入门-钉子和小球

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

dp 概率

2025-06-27

0 32