191030-模拟测试10
T1 序列
题目描述
解析
首先问题转换为寻找一个最大的区间
[
l
,
r
]
[l,r]
[l,r]使得
s
u
m
a
[
r
]
>
s
u
m
a
[
l
−
1
]
,
s
u
m
b
[
r
]
>
s
u
m
b
[
l
−
1
]
suma[r]>suma[l-1],sumb[r]>sumb[l-1]
suma[r]>suma[l−1],sumb[r]>sumb[l−1](
s
u
m
a
[
i
]
,
s
u
m
b
[
i
]
suma[i],sumb[i]
suma[i],sumb[i]为前缀和数组),那么我们只需要用树状数组维护即可
题解
#include<bits/stdc++.h>
#define int long long
#define INF 1e8
using namespace std
;
struct node
{
int b
,aa
,bb
,w
;
}s
[1000009];
int n
,a
[1000009],ans
,tree
[1000009],len
;
bool comp(const node
&x
,const node
&y
)
{
if(x
.aa
!=y
.aa
) return x
.aa
<y
.aa
;
if(x
.bb
!=y
.bb
) return x
.bb
<y
.bb
;
return x
.w
<y
.w
;
}
int lowbit(int i
)
{
return i
&(-i
);
}
void minn(int x
,int val
)
{
while(x
<=len
)
{
tree
[x
]=min(tree
[x
],val
);
x
+=lowbit(x
);
}
}
int query(int x
)
{
int sum
=INF
;
while(x
>0)
{
sum
=min(sum
,tree
[x
]);
x
-=lowbit(x
);
}
return sum
;
}
signed main()
{
int x
;
scanf("%lld",&n
);
for(int i
=1;i
<=n
;i
++)
{
scanf("%lld",&x
);
s
[i
].aa
=s
[i
-1].aa
+x
;
}
for(int i
=1;i
<=n
;i
++)
{
scanf("%lld",&x
);
s
[i
].w
=i
;
s
[i
].bb
=s
[i
-1].bb
+x
;
a
[i
]=s
[i
].bb
;
}
sort(a
+1,a
+n
+1);
len
=unique(a
+1,a
+n
+1)-a
-1;
for(int i
=1;i
<=n
;i
++)
s
[i
].b
=lower_bound(a
+1,a
+len
+1,s
[i
].bb
)-a
;
sort(s
+1,s
+n
+1,comp
);
memset(tree
,127,sizeof(tree
));
for(int i
=1;i
<=n
;i
++)
{
ans
=max(ans
,s
[i
].w
-query(s
[i
].b
));
minn(s
[i
].b
,s
[i
].w
);
if(s
[i
].aa
>=0&&s
[i
].bb
>=0)
ans
=max(ans
,s
[i
].w
);
}
printf("%lld",ans
);
return 0;
}
T2 二叉搜索树
题目描述
解析
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示将
i
−
j
i-j
i−j中的所有节点建成一颗二叉搜索树，所需要付出的代价的最小值，因此可以用区间dp解决该题，
f
[
i
]
[
j
]
=
m
i
n
(
f
[
i
]
[
k
−
1
]
+
f
[
k
+
1
]
[
j
]
+
x
[
i
.
.
j
]
)
f[i][j]=min{(f[i][k-1]+f[k+1][j]}+x[i..j])
f[i][j]=min(f[i][k−1]+f[k+1][j]+x[i..j])表示我们当前要以k为根节点，合并
i
.
.
.
k
−
1
,
k
+
1...
j
i...k-1,k+1...j
i...k−1,k+1...j的节点为一棵二叉搜索树，因为合并后，每个节点会向下一层，因此我们要多付出的代价为
x
i
+
.
.
.
+
x
j
x_i+...+x_j
xi+...+xj,可以用前缀和来维护，即
s
u
m
j
−
s
u
m
i
−
1
sum_j-sum_{i-1}
sumj−sumi−1; 但这样的时间复杂度为
O
(
n
3
）
O(n^3）
O(n3）,因此我们要考虑优化。 因为不会斜率优化dp ，因此考虑四边形不等式优化dp，然而我不会证明该题对于四边形不等式成立，因此可以通过打表来寻找规律，最后发现它具有决策单调性，因此时间复杂度优化至
O
（
n
2
）
O（n^2）
O（n2）
题解
#include<bits/stdc++.h>
#define INF 1e18
using namespace std
;
long long f
[5011][5011],sum
[5100],n
;
int g
[5011][5011],v
;
inline long long read()
{
long long f
=1,re
=0;
char ch
;
for(ch
=getchar();(ch
<'0'||ch
>'9')&&ch
!='-';ch
=getchar());
if(ch
=='-')
{
f
=-1;
ch
=getchar();
}
for(;(ch
>='0'&&ch
<='9');ch
=getchar())
re
=(re
<<3)+(re
<<1)+ch
-'0';
return re
*f
;
}
signed main()
{
long long x
;
n
=read();
for(int i
=1;i
<=n
;i
++)
{
x
=read();
sum
[i
]=sum
[i
-1]+x
;
f
[i
][i
]=x
;
g
[i
][i
]=i
;
}
for(int i
=1;i
<n
;i
++)
for(int j
=1;(v
=j
+i
)<=n
;j
++)
{
f
[j
][v
]=INF
;
for(int k
=g
[j
][v
-1];k
<=g
[j
+1][v
];k
++)
if(f
[j
][v
]>f
[j
][k
-1]+f
[k
+1][v
])
{
f
[j
][v
]=f
[j
][k
-1]+f
[k
+1][v
];
g
[j
][v
]=k
;
}
f
[j
][v
]+=(sum
[v
]-sum
[j
-1]);
}
printf("%lld",f
[1][n
]);
return 0;
}
附上暴力代码
#include<bits/stdc++.h>
#define int long long
#define INF 1e18
using namespace std
;
int f
[5010][5011],sum
[5100],n
;
int read()
{
int f
=1,re
=0;
char ch
;
for(ch
=getchar();!isdigit(ch
)&&ch
!='-';ch
=getchar());
if(ch
=='-')
{
f
=-1;
ch
=getchar();
}
for(;isdigit(ch
);ch
=getchar())
re
=(re
<<3)+(re
<<1)+ch
-'0';
return re
*f
;
}
signed main()
{
int x
;
n
=read();
for(int i
=1;i
<=n
;i
++)
{
x
=read();
sum
[i
]=sum
[i
-1]+x
;
f
[i
][i
]=x
;
}
for(int i
=1;i
<n
;i
++)
for(int j
=1;(j
+i
)<=n
;j
++)
{
f
[j
][i
+j
]=INF
;
for(int k
=j
;k
<=(i
+j
);k
++)
f
[j
][i
+j
]=min(f
[j
][i
+j
],f
[j
][k
-1]+f
[k
+1][i
+j
]);
f
[j
][i
+j
]+=(sum
[i
+j
]-sum
[j
-1]);
}
printf("%lld",f
[1][n
]);
return 0;
}
T3 走路
题目描述
解析
话说这道题，我是真不会， 不过该题还是有可以让我这个菜鸡学习的地方，首先问题要求的是期望，因此我们需要知道求期望的方法，看下面一张图： f[i]表示从起点(可以是选择的任意一点)到i点所走的期望边数 因此f[k]可以先跨过一条边，有
1
3
\frac{1}{3}
31的概率走到u,v,w点来得到
f
[
u
]
,
f
[
v
]
,
f
[
w
]
f[u],f[v],f[w]
f[u],f[v],f[w]的期望值，因此
f
[
k
]
=
1
3
∗
(
f
[
u
]
+
f
[
v
]
+
f
[
w
]
)
+
1
f[k]=\frac{1}{3}*(f[u]+f[v]+f[w])+1
f[k]=31∗(f[u]+f[v]+f[w])+1，其他点也可以类比，最后解一个多元一次方程即可。
题解
#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()
{
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\n",(x
[i
][1]+q
)%q
);
return 0;
}
