Z_L_G

题解

总结(19) 训练赛(13)

/ 注册

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

算法入门-Mondriaan's Dream

题意 n行m列矩形，用1*2的矩形块填充，有多少种填充方案思路依然是棋盘放置一类的问题，考虑一行一行放对于每一行，上一行竖着放的地方一定放不了，上一行横着放的地方可以竖着放也可以横着放，行内不可能的是把一个横着的拆开，两行间不可能的是，上一行竖着，这一行还放东西设计状态：横着放记为0，...

状压dp 妙妙题

2025-07-05

0 22

算法入门-[NOIP2008]传纸条

#双线dp 双线表示同时有两种状态，且会相互影响题意给定M*N的地图，每个点有val，每个点只能走一次从左上走到右下再走回左上，且向下的过程只能向下向右，向上的过程只能向上向左走完最多获得的val是多少思路思路一：严格按照一圈走无法完成，走下去的过程走过的格子会影响走上去的过程...

双线dp

2025-07-05

0 22

算法入门-Most Powerful

题意 n个原子，两个原子i，j碰撞会释放能量，并且j会消失，求n个原子能产生的最大能量思路状压dp 每个原子去碰撞的时候，要还剩下哪些原子也就是每次从还存在的原子中挑出两个原子碰撞，并选择一个消失最终剩下一个原子结束状态压缩是你过程，从全满，到只剩一个特别的，在st=0的时候要人为...

状压dp

2025-07-03

0 26

算法入门-炮兵阵地

题意给定N*M的地图，包含山地和平地，山地不能布置炮兵炮兵会攻击自己上下两格，左右两格的位置，请问在炮兵相互不打架的情况下，地图上最多放置多少炮兵思路仍旧按行考虑，预处理行内可行状态枚举每行可能性，和前两行状态有关，所以是一个三维的dp 表示第i行状态j，i-1行状态为k 代码 ...

状压dp

2025-07-02

0 17

算法入门-[SCOI2005]互不侵犯KING

题意有一个N*N(N<10)的棋盘，其中需要放置K个国王，国王会攻击以他为中心的九宫格范围内的棋子，要是所有国王互不攻击，总共有多少种方案思路如果按顺序从上到下，从左到右，每次放置新的国王的时候都需要考虑它左边和上侧的国王，状态过于复杂难以描述由于N不大可以考虑一行一行放置，这样...

状压dp

2025-07-02

0 29

算法入门-小A买彩票

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

dp 概率

2025-06-28

0 27

算法入门-数学考试

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

dp

2025-06-28

0 27

算法入门「木」迷雾森林

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

算法入门-[NOIP2002]过河卒

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

dp

2025-06-27

0 22

算法入门-钉子和小球

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

dp 概率

2025-06-27

0 29