A题意：一个长度为n+m+k包含n个数字1,m个数字2和k个数字4的数组，最多可能有多少个子序列1412？签到题答案必为 n/2 * (n-n/2) * m * k #include <bits/stdc++.h> #define ll long long using namespace std; ll n,m,k,t; int main() { cin>>t; while(t--) { cin>>n>>m>>k; ll ans=0; if(n%2==0) ...

简单的二维前缀和 #include <bits/stdc++.h> #define ll long long const int N=1005; using namespace std; int n,m,k,cnt[N][N]; string s; int main() { ios::sync_with_stdio(false); cin>>n>>m>>k; for(int i=1;i<=n;++i) { cin>>s; for(int j=1;j<=m;+...

这是一道前缀和的问题a[i]表示距离的前缀和 s[i]表示物品移动到1的价值的前缀和 b[i]表示物品数量的前缀和在对于l-r移动到x 有三种情况x<=l: 先全部移到1 对于每个储存点多移动了a[x]的距离 即 ans=s[r]-s[l-1]-(b[r]-b[l-1])a[x]x>=r:先全部从1到x 每次多移了a[i]*b[i] 即s[i] ans=(b[r]-b[l-1])a[x]-(s[r]-s[l-1])l<x<r: 把前面两个的情况综合起来ps：注意多取模 有减法就 +mod)%mod #include<bits/stdc++.h> #d...

这是一篇学习题解（别人的bfs简洁明了 我的一坨糊1、字符串处理 提前记录起点终点 用结构体数组记录传送坐标并且使用完初始化2、提前用数组模拟行走 这样每次用循环即可省略一部分代码3、用数组记录当前地点当前的最低步数 好比较并且确保正确4、要重复使用的都做到了每次都有初始化（确保正确 #include<bits/stdc++.h> #define ll long long #define N 405 using namespace std; const int dx[5]={1,-1,0,0},dy[5]={0,0,1,-1}; int n,m,f[N][N],ex,ey,s...

唉 天天摸鱼导致一感冒 好点后再写题解都超时了虽然没牛币可以白嫖但还是写写自己的理解吧这题我们要抓住中序遍历的特点 以根节点划分左子树右子树这样就可以不断递归下去求解法就出来了 区间dp dp[i][j]表示i-j区间二叉树划分的分数最大前序遍历就是每次求最大时记录下根节点即可 #include <bits/stdc++.h> #define ll long long using namespace std; const int N = 35; int dp[N][N],pre[N][N],a[N],n; void dfs(int l,int r) { if(l&gt...

一道简单的贪心+搜索题 我们可以让齐齐每次以最小的炮数换掉司机最大的炮数首先 对齐齐和司机的阵地进行搜索 看可以分成多少块 每块内的炮一炸一起炸 块外的的炮不受影响题目就相当于每次用齐齐的最小连通块换司机的最大连通块代码有详细注释 #include <bits/stdc++.h> #define ll long long const int M=110; const int N=1000; using namespace std; int m,a[10][M],b[10][M],f1[N],f2[N]; string s; void f11(int x,int y,int ...

在看完谷歌翻译后 本英语菜鸡大概弄懂了这题的题意 n部电影 每部电影有多个不同放映时间 同一部电影只看一次看完 n和l 的范围 这一看就是状压dp 但dp方程表达什么？？这里我表达的是 最长放映时长我们用二进制枚举选了哪几部电影 放映时间选择最近的小于放映时长的（使用二分寻找）这样就出来了 代码有详细注释 #include <bits/stdc++.h> #define ll long long using namespace std; int a[25],n,l,dp[1<<22],f[25][1100]; int cal(int x){ int ...

这一看是一个简简单单的dp 转移方程一下子就推出来了但是一写就发现 范围怎么这么大（憨批如我还真开了一次1e9的数组)这题击中了我的盲区 but 我的巨佬队友说这题太基础了（在洛谷有三万多提交这题主要是离散化（名词真熟悉 不会在翻阅了十几篇题解过后 我终于明白了离散化就是在一个大范围内 目标点之间的距离够大导致怎么走都满足题目要求 于是就将大间隔改成小间隔 于是数据范围就缩小了 可以用数组操作了在这题我们可以证明 当两个石子范围超过st时 任意距离都可以到达 于是间隔就可以改成st (s<t s==t特判一下就行了代码有详细注释 #include<bits/std...

一开始看错了题目 以为一个城市只能算一次（瞎子视力然后得出一个结论最多折返一次 然后计算 然后wawa只会看样例才发现 一个城市能多次到达 那么m够大的话最后一定变成了在i到i+1之间来回 那么我们就枚举每个区间 是否正确？错了然后苦思 然后看题解（后面的情况没想到啊啊啊因为还有个问题没有考虑 我们本身的p位置是在两个城市之间 按照之前思路的话是一直向着一路走 但有可能向另一边第一个走一个来回的距离小于后面重复走的区间的距离有人说这样我们可以向另一边走两个等多个 我们可以证明 当你向另一边走多个都小于这个区间的话 那么这种情况就在之前或者之后的循环中经历（因为走了大于等于一个区间了）...

一看就知道是dp 但就不知道怎么写啊啊啊啊看到设方程为dp[N][2][2] 时瞬间就知道了有了这个方程在按着条件写就行了具体情况看注释 #include <bits/stdc++.h> #define ll long long ll const N=1e6+5; ll const mod=1e9+7; using namespace std; ll dp[N][2][2]; string a; /* 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈焰 ？：未...

这题一看不会 在看了半天像dp 想半天推不出转移方程 不知道怎么写经过对大佬们的博客的学习 终于弄懂了一种解决方法（大佬怎么写都是对的 渣渣怎么写都是错的QAQ三个数组：dp[i][j][k] 第i个木板k个格子粉刷j次 正确格子数 sum[i][j] 第i个木板j个格子1的数量 ins[i][j] 前i个木板粉刷j次 正确格子数 详细解析看代码（代码里解释的很清楚 #include <bits/stdc++.h> #define ll long long ll const N=55; ll const M=2505; using name...

在这题我们要选择两个区间 首先我们知道 右区间一定在左区间右边于是 我们枚举i作为分界线 i左边最大的长度为k的的区间 i右边最大的长度为k的的区间解题的思路出来了 那么该如何用程序表达用cnt数组表示前缀和那么i左边的最大区间和表达为 dp1[i]=max(dp1[i-1],cnt[i]-cnt[i-k]);那么i右边的最大区间和表达为 dp2[i]=max(dp2[i+1],cnt[i+k-1]-cnt[i-1]);答案就为 ans=max(ans,dp1[i]+dp2[i+1]);PS：记得将dp1 dp2 ans 都初始化为负无穷大 #include <bits/std...

这是一道区间dp的题我们设置这样一个数组 dp[l1][r1][l2][r2] 来代表字符串 s1 s2 选择的范围那么递推方程怎么来 对于这样一个方程 它只能由这四种情况得来dp[l1+1][r1][l2][r2-1] dp[l1+1][r1-1][l2][r2]dp[l1][r1][l2+1][r2-1] dp[l1][r1-1][l2+1][r2]如果相对应的字符相等而且它的子情况有一种是真的 dp[l1][r1][l2][r2] 为真所以递推方程就得到了PS：注意区间dp的枚举是区间长度 #include <bits/stdc++.h> using names...

这是一个贪心题按容纳人数排序 当新加入的人的容纳人数小于总人时 去除人数差个战力最小的人每次加入人都会记录一下最大值最后就求出了军团战力的最大值 #include <bits/stdc++.h> #define ll long long ll const N=1e5+5; using namespace std; ll n,v[N],s[N]; priority_queue<ll, vector<ll>, greater<ll> > q; struct T{ int v,s; }k[N]; bool cmp(T a,T b){ ret...