解题报告：这道题是个状态机模型的简单题吧，主要题目的细节是买入卖出加起来算是一笔交易，状态转移也不说了，注意一下j-1和j的区别，f[i][j][k]代表前i天的股票已经进行了j次交易，k为0代表当前手里没有股票，k=1时代表手中有股票，初始化把交易次数为0并且手中没有股票的方案都变为0，别的都是非法状态。 AC代码： #include<iostream> #include<cstring> using namespace std; const int N=100010,M=110; int f[N][M][2]; int w[N]; int main() { ...

这题看了大佬的博客，才明白是用差分做，差分的前缀和的下标代表a[i]+a[n-i+1]的值，我们只要预处理出来每个范围内的操作次数，最后利用差分思想前缀和就能做出这道题了，不过预处理区间的时候别忘了两数之和要特判一下。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #inc...

解题报告：这道题还是要在草稿本上面好好演算一下的，把式子做一下等价变化，A[i+1]=2A[i]+2C[i]-A[i-1] 假设A[1]=0的情况下带进去，然后把最后真正的A[n+1]和假设出来的A[n+1]相减然后除以（n+1）就是答案。这里的n+1是通过规律看出来的。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector>...

解题报告：其实这题我以前做过，但是我给忘记了怎么剪枝，刚好蓝桥杯训练到了这题，那就补一补吧，主要是要把行、列、3x3小矩阵这三个信息的状态压缩，然后某点x,y可选的值在他们状态相与的情况下才满足，然后每次搜索，搜索分支最小的搜索，还有个小优化就是lowbit运算，返回二进制最近的1的数值，然后还要预处理出来1<<i的值就可以了。 #include<iostream> using namespace std; string str; const int N=9; int one[1<<N],map[1<<N]; int row[N],col[...

解题报告：这道题其实就是树形dp的板子题，还掺杂着一点数论的气息，如果朴素去枚举每个数的最大公约数用试除法，o（n根号n）,如果n大点就不行了，可以用线性筛的思想，去枚举每个公约数，把他的>=2倍都加上它，这样做法线性On的。然后dfs任意一个节点，找最大距离就可以了。 #include<iostream> #include<cstring> using namespace std; const int N=50010; int h[N],e[N*2],idx,ne[N*2]; int sum[N]; int ans; void add(int a,int ...

解题报告：这道题也是树形dp题，f[i][j]代表根节点是i的情况下留j条边的最大值的方案，最后要求的是以1为根最大值为q的方案，状态转移方程就是类似于分组背包问题，先从大到小枚举体积，再枚举给子树的体积. #include<iostream> #include<cstring> using namespace std; const int N=110; int h[N],e[N*2],ne[N*2],idx,w[N*2]; int n , q; void add(int a,int b,int c) { e[idx]=b , w[idx]...

解题报告：其实这题就是没有上司的舞会和战略游戏的翻版，，类似于状态机f[u][j] 以u为根节点，j有0,1，2,分别表示被父节点侦察到，被子节点侦察到，自己身上放守卫。 #include<iostream> #include<cstring> using namespace std; const int N=1510; int f[N][3]; int n; int h[N],e[N*2],idx,ne[N*2],w[N*2]; bool st[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]...

解题报告： 这题看了y总的解说是区间dp类型的题目，f[l][r]代表把l到r之间的多边形划分成三角形的最大方案。 其中状态转移就是f[l][r]=min(f[l][r],f[l][k]+f[k][r]+w[l]*w[r]*w[k])(k<r&&k>l)，然后再套一点大数模板就行啦。。 #include<iostream> #include<cstring> using namespace std; const int N=55 ,M=35; typedef long long ll; ...

解题报告：这道题目是真的。。。一言难尽，以为很难，结果他这个p[i]指的是数i在排列中的位置，那就跟着它模拟就行了，然后判断是否有一个数比他大并且没用过，如果有就break输出no，如果没有就把当前的数***去。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #includ...

解题报告：这种水题。我竟然想不到了，，直接dfs有炸弹的点，++cnt，然后一系列循环爆炸就行了。然后想想是最优解，其实无论怎么引爆答案都是固定的，这个和先后次序无关的。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #define ...

解题报告：这道题着实是数位dp的入门题了，不得不说yxc的新方法真的太好用了，我们可以构建一颗包含数位的一棵树，然后层层递归下去，设每一个数位是从0~an-1 -1 的，这些我们后面的数都可以随便选，层层递归下去，然后每个题目都不一样都要预处理出来数左边的每一个值，最后答案就是左边加上右边，就是该数本身的大小。 #include<iostream> #include<cstring> #include<vector> using namespace std; const int N=35; int f[N][N]; int k,b; void init...

#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #define IL inline #define x first #define y second typedef long long ll; using namespace std; c...

#include<iostream> #include<cstring> #include<vector> using namespace std; const int N=11; int f[N][N][110]; int p; void init() { for(int i=0;i<=9;i++) f[1][i][i%p]++; for(int i=2;i<N;i++) for(int j=0;j<=9;j++) for(int m=0;m<p;m++) ...

解题报告：写这种题还是暴力香，虽然我也没有想到，现在懂了，然后二维前缀和可以不用memset，就因为这个tle的，这题做法就是维护前缀和（每个数在某段区间出现的个数）因为总共就200个数，然后把各个数的位置push进vector，每次对称着取两个位置加上中间的前缀和之差不断更新ans，就能解决这题啦！ #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #includ...