Abel公式
公式S=\sum_{i=1}^{m}a_ib_i=a_mB_m-\sum_{i-1}^{m-1}(a_{i+1}-a_i)B_i
DP(01)最长不下降子序列及其变种
变种一就是01串,方法在下面,懒得解释了,自己看注释吧题目:问最少能把01串划成几个0101…类型的字符串12345678910111213//关键点,类似最长不下降子序列的题目,但是由于是01串,只要管有几个0结尾和1结尾的串就好了ll c0=0,c1=0;for(int i=0;i<t.length();i++){ if(t[i]=='1'){ if(c0) c0--;//接到0结尾的后面 c1++;//多了一个以1结尾的串 } else{ if(c1) c1--;//接到1结尾的后面 c0++;//多了一个以0结尾的串 } } return c0+c1; 变种二是有有限个结尾的dp 例如牛客周赛题目:把字符串变成相邻字母的ASCALL码之差都一样,求最小操作次数 因为只有26个字母,所以可以直接滚动数组+dp,然后设dp[i][j]表示以第i位结尾改成char('a'+j)的最少修改次数,或者也可以设成改为char('...
DP变种,n过大找规律题
题目:要用qcjjkkt,和td构造字符串,每出现一个qcjjkkt获得a快乐度,每个td获得b快乐度即只有三种物品,体积为2,7,8,价值为a,b,a+b,数量无限,n上限为$10^9$,求最大价值 方法:完全背包 但是发现貌似超时,此时发现若n为56倍数很好解决,所以先提取完整的56,剩下部分单独计算. 然后发现qcjjkkt和td可以连接,要是前面56的循环选的是qcjjkkt最后如果剩下1位置,可以填入d,所以得加上特判,太麻烦了,所以改为计算最后112个就行 AC代码: 12345678910111213void solve(){ ll n,a,b; cin>>n>>a>>b; vector<ll> dp(120,0); ll ans=0; if(n>112){ ans=(n/56-1)*max({28*b,8*a,7*(a+b)}); n-=(n/56-1)*56; } for(int i=2;i<=n;i++) dp[i]=m...
多源dfs
正常的广搜就是一个起点,像树一样按层先法遍历今天我们要学习的是多源广搜. 什么是多源dfs顾名思义,从多个起点开始搜索,也是求最短路的一种方法. 什么时候适用?个人认为是起点不确定,而且终点有多个的情况, 此时终点是确定的,因此只要同时计算,最后每个起点都会被遍历到,得到的就是最短路了 例题1: 给定01矩阵,求每个0到最近的1的距离. 例题2: 有 n 个城市，编号为 1 到 n，城市之间通过 m条无向道路连接，每条道路的边权为 1，对于一个城市的繁华度是该城市所连接的道路数量。我们将每个城市的繁华度列出并去重后，从小到大排序得到 $a_1,a_2,…,a_k$，现在将所有繁华度为 $a_i$(1≤i≤k) 的城市称作 i 级城市。Bingbong 现在需要你帮助他回答对于任意编号为 x(1≤x≤n) 的城市，从该城市出发，前往比该城市级别更高的城市的最短路径长度，或报告无法到达。 注意：此处 k 级城市为最高级城市。 例题2实现起来可能会有一些麻烦,但是发现一个事情是不存在跨过大繁华度城市达到终点的情况,因此,只要每次从大到小,在路径变短时才需要入队,简化了实现.
最大子段和
方法1:处理当前位置之前的前缀和的最小值,每次计算当前位置到这个位置的子段和即可代码:12345678910111213const ll inf=1e9+1;void solve(){ ll n; cin>>n; vector<ll> a(n+1); for(int i=1;i<=n;i++) cin>>a[i]; ll minn=0,now=0,ans=-inf; for(int i=1;i<=n;i++){ now+=a[i]; ans=max(ans,now-minn); minn=min(minn,now); } cout<<ans<<endl;} 注意几个细节,首先minn存储的是到目前为止的最小值,应该默认为0,在所有数字全为正数的情况下,表示空串的前缀和为0.先计算ans再计算minn,这是因为不能产生空串,保证取的是前面的前缀和. 方法2:传统dp法: 代码:123456789101112#include<...
根号分治
常见于含有两数相乘的题目中,或者数据范围在根号上下时可采用不同复杂度的算法平衡总复杂度 例题1:D. Another Problem about Beautiful Pairs 求i,j对,满足$a_ia_j==i-j(i>j)$,n最大是$210^5$注意到,在$a_i$较大时,适合直接暴力枚举,因为没枚举几次就超过边界了,在$a_i$较小时,不适枚举, 所以划分一个界限,大于$\sqrt{n}$的枚举,小于$\sqrt{n}$的只计算$\sqrt{n}$次,这么划分的作用是两边刚好全部包括在内如果$a_i$小的话$a_j$可能大,但是这部分被大于$\sqrt{n}$的部分枚举到了,减少了无效枚举所以代码: 12345678910111213141516void solve(){ ll n,ans=0; cin>>n; vector<ll> a(n+1); for(int i=1;i<=n;i++) cin>>a[i]; ll fj=sqrt(n); for(int i=1;i<=n;i++){...
