T1
这道题真的很简单 考试的时候线段树打挂了想杀人
我们可以分别求a序列的前缀和(suma)和b序列的前缀和(sumb) 现在问题就转化为(suma[i]-suma[j]>0, sumb[i]-sumb[j]>0) 使得(i,j) 差的绝对值最大
对于这种多维偏序问题，可以采用(CDQ)分治或者是 先对(suma)从小到大排序 然后以(sumb)为下标，把(id) 甩进树状数组或者线段树（可能被卡常），然后对于当前(num[i]) ，我们只需要知道所有满足(b_j<b_i)的数字(num[j])使得其id最小
然后就完了(QAQ) 我想杀人
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=500010;
LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
LL n,tree[maxn<<1],lsh[maxn],ls,tot,ans;
struct node{
LL id,a,b;
}num[maxn<<1];
inline bool cmpl(node x,node y){
return x.a<y.a || (x.a==y.a && x.id<y.id);
}
LL query(LL x){
LL minn=1e18;
for(;x;x-=x&-x)
if(tree[x])
minn=min(minn,tree[x]);
return minn;
}
void add(LL x,LL y){
for(;x<=n;x+=x&-x){
if(!tree[x]) tree[x]=y;
else tree[x]=min(tree[x],y);
}
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequenceown.out","w",stdout);
n=read();
for(LL i=1;i<=n;i++) num[i].a=read()+num[i-1].a,num[i].id=i;
for(LL i=1;i<=n;i++) num[i].b=read()+num[i-1].b,lsh[++tot]=num[i].b;
sort(num+1,num+1+n,cmpl);sort(lsh+1,lsh+1+tot);
ls=unique(lsh+1,lsh+1+tot)-lsh-1;
for(LL i=1;i<=n;i++)
num[i].b=lower_bound(lsh+1,lsh+1+ls,num[i].b)-lsh;
add(num[1].b,num[1].id);
ans=0;
for(LL i=2;i<=n;i++){
ans=max(ans,num[i].id-query(num[i].b));
add(num[i].b,num[i].id);
}
printf("%lld",ans);
}
T2
这道题是一道区间dp。如何思考呢？暴力算法一般都可以给我们启发：对于这道题的暴力算法，我们需要枚举每一个父亲，令父亲为(i),那么我们有需要分别递归([1,i-1])和([i+1,n]) ，以此类推。而这种暴力算法就是重复计算了很多的相同的区间 例如我们计算([2,5])和([3,5])能够构成的搜索二叉树，但是在计算([2,5])的时候我们已经计算过([3,5])的情况了，可以优化。而这种暴力算法长得又很像区间dp，因此我们可以用区间dp进行优化。而根据暴力的思路，我们也可以推出dp方程:(f[i][j]=min(f[i][k-1]+f[k+1][j])+presum[j]-presum[i-1]) 这里(k∈[i,j])。因为如果你要枚举当前的父节点的话，显然会使得区间([i,j])的所有点深度++，因此需要加上这些点的点权。
这是(o(n^3))的算法，只能得40(pts)，如何优化。显然（？），这是区间类（2D1D）动态规划，考虑如何用四边形不等式来优化。令(val[i][j])=(presum[j]-presum[i-1]),显然(val[i][j])满足四边形不等式，并且对于任意(a<=b<=c<=d),有(val[a][d]>=val[b][c])那么这个式子具有决策单调性。令其决策为(k[i][j]),显然(k[i][j]<k[i+1][j]<k[i+1][j+1]),因此在枚举决策的时候，可以进行优化，复杂度为(o(n^2)) 另外关于(f)赋初值，不能乱赋。对于(f[i][j])显然(i<=j) 。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=5010;
inline LL read(){
LL x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
LL n,f[maxn][maxn],de[maxn][maxn],presum[maxn];
int main(){
n=read();
for(LL i=1;i<=n;i++)
for(LL j=i;j<=n;j++)
f[i][j]=1e18;
for(register LL i=1;i<=n;i++){
presum[i]=read()+presum[i-1];
de[i][i]=i;f[i][i]=presum[i]-presum[i-1];
}
register LL len,i,j,k;
for(len=1;len<n;len++){
for(i=1;i+len<=n;i++){
j=i+len;
for(k=de[i][j-1];k<=de[i+1][j];k++){
if(f[i][j]>f[i][k-1]+f[k+1][j])
{
f[i][j]=f[i][k-1]+f[k+1][j];
de[i][j]=k;
}
}
f[i][j]+=presum[j]-presum[i-1];
}
}
printf("%lld",f[1][n]);
}
T3
令(f[i][j])表示从(i)到(j)的期望步数，显然(f[i][j]=frac{egin{equation*}sum{f[v][j]}end{equation*}}{deg[i]})，然后通过这个式子，我们可以推出很多个方程。对于(j)为终点，相当于将j哪一行的系数全部改为0，然后枚举j+高斯消元 复杂度(o(n^4)),这样是过不了的，考虑如何优化。 显然采用分治来枚举j可以使得复杂度为(o(n^3logn)),然而我并不会（逃
//#include<bits/stdc++.h>
#include<iostream>
#define L long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int q=998244353;
int n,m,f[310][310],g[10][310][310],x[310][310];
bool y[310][310];
inline int power(int a,int b)
{
if(!b)
return 1;
int c=power(a,b>>1);
c=(L)c*c%q;
if(b&1)
c=(L)c*a%q;
return c;
}
inline void dfs(int l,int i)
{
int j;
x[l][i]=f[i][0];
for(j=1;j<=n;j++)
if(j!=i && f[i][j])
{
if(!y[l][j])
dfs(l,j);
x[l][i]=(x[l][i]-(L)f[i][j]*x[l][j])%q;
}
y[l][i]=1;
}
inline void calc(int l,int r,int p)
{
int i,j,k,m=(l+r)>>1;
if(l==r)
{
y[l][l]=1;
for(i=1;i<=n;i++)
if(!y[l][i])
dfs(l,i);
return;
}
for(i=l;i<=r;i++)
{
g[p][i][0]=f[i][0];
for(j=l;j<=r;j++)
g[p][i][j]=f[i][j];
}
for(i=l;i<=m;i++)
{
k=power(f[i][i],q-2);
f[i][0]=(L)f[i][0]*k%q;
for(j=i;j<=r;j++)
f[i][j]=(L)f[i][j]*k%q;
for(j=i+1;j<=r;j++)
if(f[j][i])
{
f[j][0]=(f[j][0]-(L)f[i][0]*f[j][i])%q;
for(k=r;k>=i;k--)
f[j][k]=(f[j][k]-(L)f[i][k]*f[j][i])%q;
}
}
calc(m+1,r,p+1);
for(i=l;i<=r;i++)
{
f[i][0]=g[p][i][0];
for(j=l;j<=r;j++)
f[i][j]=g[p][i][j];
}
for(i=r;i>m;i--)
{
k=power(f[i][i],q-2);
f[i][0]=(L)f[i][0]*k%q;
for(j=l;j<=i;j++)
f[i][j]=(L)f[i][j]*k%q;
for(j=i-1;j>=l;j--)
if(f[j][i])
{
f[j][0]=(f[j][0]-(L)f[i][0]*f[j][i])%q;
for(k=l;k<=i;k++)
f[j][k]=(f[j][k]-(L)f[i][k]*f[j][i])%q;
}
}
calc(l,m,p+1);
for(i=l;i<=r;i++)
{
f[i][0]=g[p][i][0];
for(j=l;j<=r;j++)
f[i][j]=g[p][i][j];
}
}
int main()
{
//freopen("walk.in","r",stdin);
//freopen("walk.out","w",stdout);
int i,j,k;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&j,&k);
f[j][j]++;
f[j][0]++;
f[j][k]--;
}
calc(1,n,0);
for(i=2;i<=n;i++)
printf("%d
",(x[i][1]+q)%q);
return 0;
}
这是标程