#A. 最大子段和
最大子段和(正常)
for(int i=1;i<=n;i++) sum[i]=max(sum[i-1]+in[i],in[i]);
- \(sum[i]\)表示以第i个数为结尾的最大子段和,可以由前一个最大子段和转移过来\((sum[i-1]+in[i])\),也可以只包含自己\((in[i])\);
本题
-
用\(fr[i]\)表示以前i个数的最大子段和,\(ba[i]\)表示以第i个数为开头,结尾为\(n\)的最大子段和(求法与上面类似);
-
再做一次处理,分别用\(fr[i-1]\),\(ba[i+1]\)更新\(fr[i]\),\(ba[i]\),使得\(fr[i]\)表示以第\(i\)个数为结尾的最大子段和,\(ba[i]\)表示以第i个数为开头的最大子段和;
-
因为两段不相交,所以\(i\)把序列分成\(1 \to i\)和\(i+1 \to n\)两部分
-
枚举位置\(i\),\(i\)位置的最大子段和为\(fr[i]+ba[i+1]\);
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n;
int maxi;
int in[N];
int fr[N],ba[N];
signed main(){
// freopen("1.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) cin>>in[i];
fr[1]=in[1];
for(int i=2;i<=n;i++) fr[i]=max(fr[i-1]+in[i],in[i]); //1～i的最大子段和;
for(int i=2;i<=n;i++) fr[i]=max(fr[i-1],fr[i]); //以第i个数结尾的最大子段和;
ba[n]=in[n];
for(int i=n-1;i>=1;i--) ba[i]=max(ba[i+1]+in[i],in[i]); //i~n的最大子段和;
for(int i=n-1;i>=1;i--) ba[i]=max(ba[i+1],ba[i]); //以第i个数开头的最大子段和;
maxi=fr[1]+ba[2];
for(int i=2;i<=n-1;i++) maxi=max(maxi,fr[i]+ba[i+1]);
cout<<maxi<<"\n";
}
出处 P2642 双子序列最大和
#B. 等差数列
二阶等差数列(好像和下面没啥关系)
- 后项与前项的差是等差数列
1 3 7 13 21 31 ->原数列
2 4 6 8 10 ->后项与前项的差
2 2 2 2 ->差的差相同(等差数列)
如何实现在一个区间上加上一个等差数列的操作
- 给区间\([2,6]\)加上首项为\(s\),末项为\(e\),差为\(d\)的等差数列
| 下标 | \(a_1\) | \(a_2\) | \(a_3\) | \(a_4\) | \(a_5\) | \(a_6\) | \(a_7\) | \(a_8\) |
|---|---|---|---|---|---|---|---|---|
| 原数组的变化 | 0 | s | s+d | s+2*d | s+3*d | e | 0 | 0 |
| 一阶差分 | 0 | s | d | d | d | d | -e | 0 |
| 二阶差分 | 0 | s | d-s | 0 | 0 | 0 | -e-d | e |
-
实质:给一阶差分数组再做一次差分
- 原因:一阶差分后有好多位置都是公差d,再差分一次就可以消掉
-
得出:
- 给数组\([l,r]\)区间加上首项为\(s\),末项为\(e\),差为\(d\)的等差数列的操作为:
a[l]+=s; a[l+1]+=d-s; a[r+1]-=e+d; a[r+2]+=e;
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,m;
int in[N];
int l,r,s,e;
int eq;
int res;
signed main(){
// freopen("1.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>l>>r>>s>>e;
eq=(e-s)/(r-l);
in[l]+=s; in[l+1]+=-s+eq;
in[r+1]-=e+eq; in[r+2]+=e;
}
for(int i=1;i<=n+1;i++) in[i]+=in[i-1];
for(int i=1;i<=n+1;i++) in[i]+=in[i-1];
for(int i=1;i<=n;i++) res^=in[i];
cout<<res<<"\n";
}
出处 P4231 三步必杀
#C. 可爱序列
状态设计
-
\(dp[i][j][k][0/1]\)
-
第一维表示考虑到了第\(i\)个数
-
第二维表示第\(i\)个数填\(j\)
-
第三维表示前i个数的和为k
-
第四维表示增减关系(0为$ \geq $ , 1为\(<\))
转移
for(int i=1;i<=n;i++){
int l=0,r=40;
if(in[i]!=-1) l=r=in[i];
for(int j=l;j<=r;j++){ //枚举第i个数的范围
for(int k=j*(i-1);k<=40*(i-1);k++){ //前(i-1)个数的和的范围
//因为<序列中每个元素都不大于之前的数的平均值>,所以前(i-1)个数的平均值至少为j,和至少为(i-1)*j
for(int z=0;z<=j;z++) dp[i][j][j+k][0]=(dp[i][j][j+k][0]+dp[i-1][z][k][0]+dp[i-1][z][k][1])%MOD;
//第i-1个数<=第i个数
for(int z=j+1;z<=40;z++) dp[i][j][j+k][1]=(dp[i][j][j+k][1]+dp[i-1][z][k][0])%MOD;
//第i-1个数>第i个数
//因为<没有三个连续的递减的数>,所以:
//如果i>=i-1,i-1相对i-2即可增也可减;
//如果i<i-1,i-1相对i-2只能增,否则会出现连续递减
}
}
}
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
int n,ans;
int in[41];
int dp[41][41][1601][2];
signed main(){
// freopen("1.in","r",stdin);
cin>>n;
dp[0][0][0][0]=1;
for(int i=1;i<=n;i++) cin>>in[i];
for(int i=1;i<=n;i++){
int l=0,r=40;
if(in[i]!=-1) l=r=in[i];
for(int j=l;j<=r;j++){
for(int k=j*(i-1);k<=40*(i-1);k++){
for(int z=0;z<=j;z++) dp[i][j][j+k][0]=(dp[i][j][j+k][0]+dp[i-1][z][k][0]+dp[i-1][z][k][1])%MOD;
for(int z=j+1;z<=40;z++) dp[i][j][j+k][1]=(dp[i][j][j+k][1]+dp[i-1][z][k][0])%MOD;
}
}
}
for(int i=0;i<=40;i++){
for(int j=0;j<=40*n;j++){
ans=(ans+dp[n][i][j][0]+dp[n][i][j][1])%MOD;
}
}
cout<<ans<<"\n";
}
#D. 石子游戏
-
\((i,j)\)的石子\(-1\),导致\((i+1,j),(i,j+1)\)的石子\(+1\)
-
画图为:
| 图 | ||||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | 3 | 6 | 10 | |||
| 1 | 4 | 10 | ||||
| 1 | 5 | |||||
| 1 |
-
发现它其实就是个杨辉三角
-
用组合公式表示为:
| 图 | ||||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | \(C^0_0\) | \(C^1_1\) | \(C^2_2\) | \(C^3_3\) | \(C^4_4\) | \(C^5_5\) |
| 2 | \(C^0_1\) | \(C^1_2\) | \(C^2_3\) | \(C^3_4\) | \(C^4_5\) | |
| 3 | \(C^0_2\) | \(C^1_3\) | \(C^2_4\) | \(C^3_5\) | ||
| 4 | \(C^0_3\) | \(C^1_4\) | \(C^2_5\) | |||
| 4 | \(C^0_4\) | \(C^1_5\) | ||||
| 6 | \(C^0_5\) |
-
第i行第j列的数可以表示为\(C^{j-1}_{i+j-2}\)
-
设\(f(i,j)=C^{j-1}_{i+j-2}\)
-
则
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int MOD=1e9+7;
int n;
int jie[N];
int inv[N];
int in[N];
int ans;
int q_pow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans%MOD;
}
int C(int a,int b){
if(b<0) return 0;
return jie[a]%MOD*inv[b]%MOD*inv[a-b]%MOD;
}
signed main(){
// freopen("1.in","r",stdin);
cin>>n;
n++;
for(int i=1;i<=n;i++) cin>>in[i];
jie[0]=1; inv[0]=1;
for(int i=1;i<N;i++){
jie[i]=jie[i-1]*i%MOD;
inv[i]=q_pow(jie[i],MOD-2);
}
for(int i=1;i<=n;i++) ans=(ans+C(in[i]+i-1,in[i]-1))%MOD;
cout<<ans<<"\n";
}
出处 Placing Jinas
标签：13,ba,04,子段,int,23,个数,fr,long From： https://www.cnblogs.com/wangyangjena/p/17320165.html