0430 C组模拟赛 题解
T1 题解
题目说漏了，保证数组所有数都为正整数。
思考一下，首先最大的子段和肯定是整个数组，对于一个长度为 $l$ 的子段，删除两端其中·一个数得到的两个长度为 $l-1$ 的子段的和肯定小于原先的那个子段（显而易见，因为都是正整数）。
容易想到用一个平衡树（set），维护子段的左右端点（闭区间）和子段和，按子段和为第一关键字，左右端点为第二、第三关键字排序。最初压入整个数组（即最大的子段），每次取出堆顶的数后再把删除两端得到的新子段分别压入。每次压入时会去重所以不用担心重复的问题。这样做必然会先找到较大的子段后再找到较小的，原因上面已经证了。
code
code
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#include<set>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(ll i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline ll read(){
ll x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const ll N=1e5+5,inf=0x3f3f3f3f;
ll n,k,a[N],sum;
struct Node{
ll l,r,val;
bool operator <(const Node &p)const{
if(val!=p.val) return val>p.val;
if(l!=p.l) return l<p.l;
return r<p.r;
}
};
set<Node> q;
signed main(){
n=read();k=read();
forup(i,1,n){
a[i]=read();sum+=a[i];
}
q.insert(Node{1,n,sum});
forup(i,1,k){
set<Node>::iterator it=q.begin();
ll val=it->val,l=it->l,r=it->r;
q.erase(it);
printf("%lld ",val);
if(l<r){
q.insert(Node{l+1,r,val-a[l]});
q.insert(Node{l,r-1,val-a[r]});
}
}
}
T2 题解
很显然这是一道树形 dp。
设 $dp_{u,i}$ 表示考虑以点 $u$ 为根的子树，点 $u$ 取 $i$ 的方案数，有一个显然的转移方程。
$$dp_{u,i}=\prod\limits_{v \in children(u)}(\sum\limits_{1 \le j\le m,\left|j-i\right|\ge k}dp_{v,j})$$
我们直接 $O(nm^2)$ 套这个方程可以得 $20pts$.
注意到合法的 $j$ 是连续的两段，我们维护一个前缀和，复杂度变为 $O(nm)$ 就可以得 $40pts$。
假如我们打个表，容易发现，对于一个结点 $u$，有两个性质：
- $dp_1=dp_m,dp_2=dp_{m-1}\dots$（即 dp 值是对称的）
- dp 值的中间有一段是相等的。
这非常好理解，首先对称性很显然，因为具体大小不影响 dp 值，只有与上下界的距离影响。结论二因为叶子结点的 dp 值全为 $1$，所以叶子结点的父亲除去开头 $k$ 个和末尾 $k$ 个以外其他值都是相等的，再往上一层除去开头 $2k$ 个和末尾 $2k$ 个都是相等的，同理可以推到根节点。
通过这个证明，容易发现另一个性质：
- dp 值至多开头和结尾分别有 $k\cdot(n-1)$ 个与中间不相等。
所以我们可以只存开头 $k\cdot(n-1)$ 个值，中间只用存一个，转移也只算这 $k \cdot (n-1)+1$ 个值，复杂度 $O(n^2k)$。
另外我小数据用暴力过的，因为我不知道怎么把这个结论用在数据较小（指 $m < k\cdot(n-1)$）的情况。
code（比较屎山）
code
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(ll i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline ll read(){
ll x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const ll N=105,M=1e5+5,mod=1e9+7;
ll t,n,m,k,len;
vector<ll> e[N];
ll dp[N][M],pre[N][M];
void dfs(ll x,ll fa){
forup(i,1,len){
dp[x][i]=1;
}
for(auto v:e[x]){
if(v==fa) continue;
dfs(v,x);
forup(i,1,len){
int res=0;
if(i>k){
res=(res+pre[v][i-k])%mod;
}
if(i+k<=m){
int bk=m-(i+k-1);
if(k==0) bk--;
if(bk<=len){
res=(res+pre[v][bk])%mod;
}else if(i+k<=len){
res=(res+(pre[v][len-1]+mod-pre[v][i+k-1])%mod)%mod;
res=(res+pre[v][len-1])%mod;
res=(res+dp[v][len]*(m-len*2+2)%mod)%mod;
}else{
res=(res+pre[v][len])%mod;
res=(res+dp[v][len]*(bk-len)%mod)%mod;
}
}
dp[x][i]=dp[x][i]*res%mod;
}
}
forup(i,1,len){
pre[x][i]=(pre[x][i-1]+dp[x][i])%mod;
}
}
void dfs1(int x,int fa){
forup(i,1,m){
dp[x][i]=1;
}
for(auto i:e[x]){
if(i==fa) continue;
dfs1(i,x);
forup(j,1,m){
ll res=0;
if(j>=k){
res=(res+pre[i][j-k])%mod;
}if(j+k<=m){
if(k!=0){
res=(res+pre[i][m]+mod-pre[i][j+k-1])%mod;
}else{
res=(res+pre[i][m]+mod-pre[i][j+k])%mod;
}
}
dp[x][j]=(dp[x][j]*res)%mod;
}
}
forup(i,1,m){
pre[x][i]=(pre[x][i-1]+dp[x][i])%mod;
}
}
signed main(){
t=read();
while(t--){
n=read();m=read();k=read();
mem(dp,0);mem(pre,0);
forup(i,1,n){
e[i].clear();
}
forup(i,1,n-1){
ll u=read(),v=read();
e[u].push_back(v);e[v].push_back(u);
}
if(m>10000){
len=min((m+1)/2,(n-1)*k+1);
dfs(1,0);
printf("%lld\n",(pre[1][len-1]*2%mod+dp[1][len]*(m-len*2+2)%mod)%mod);
}else{
dfs1(1,0);
printf("%lld\n",pre[1][m]);
}
}
}
T3 题解
这道题给了很多部分分，每个部分分都有对应的做法，但是我只讲正解。
首先我们很好求以每个点为右下角的最大的正方形。
做法是这样的，设 $f_{i,j}$ 表示以点 $(i,j)$ 为右下角的正方形的最大可能边长，易得 dp 式子：
$$\forall a_{i,j}=0,f_{i,j}=0$$ $$\forall a_{i,j}=1,f_{i,j}=\min{f_{i-1,j},f_{i,j-1},f_{i-1,j-1}}+1$$
这个式子很显然就不说了，预处理复杂度 $O(n^2)$。
然后考虑如何求答案。发现可以二分答案，假如在 $(x_1,y_1)(x_2,y_2)$ 之间答案为 $r$，那么必定 $\exists(i,j),x_1+r \le i \le x_2,y_1+r \le j \le y_2,f_{i,j} \ge r$。这是显然的，因为首先必须要有一个 $f \ge r$，其次假如这个点太靠边那正方形就不完全在询问矩阵内了。
但是这样的复杂度 $O(n^2 \log n)$ 显然过不了，注意到我们只需要查询矩阵内最大的 $f$，这是一个二维 $rmq$，可以 $O(n^2\log^2n)$ 预处理，$O(1)$ 查询。
故总复杂度为 $O(n^2+n^2\log^2n+T)$，注意常数优化。
code
code
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1005,LN=15,inf=0x3f3f3f3f;
int n,m,a[N][N],f[N][N],qq;
int lg[N];
struct ST{
int g[LN][LN][N][N];
void init(){
forup(i,1,n){
forup(j,1,m){
g[0][0][i][j]=f[i][j];
}
}
for(int ln=0;(1<<ln)<=n;++ln){
int nn=max(ln-1,0),sn=1<<nn;
if(ln==0) sn=0;
for(int lm=0;(1<<lm)<=m;++lm){
int nm=max(lm-1,0),sm=1<<nm;
if(lm==0) sm=0;
if(lm==0&&ln==0) continue;
forup(i,1,min(n,n-sn*2+1)){
forup(j,1,min(m,m-sm*2+1)){
g[ln][lm][i][j]=max({g[nn][nm][i][j],g[nn][nm][i+sn][j],g[nn][nm][i][j+sm],g[nn][nm][i+sn][j+sm]});
}
}
}
}
}
int ask(int x1,int y1,int x2,int y2){
int ln=lg[x2-x1+1],lm=lg[y2-y1+1],sn=1<<ln,sm=1<<lm;
return max({g[ln][lm][x1][y1],g[ln][lm][x2-sn+1][y1],g[ln][lm][x1][y2-sm+1],g[ln][lm][x2-sn+1][y2-sm+1]});
}
}mst;
signed main(){
n=read(),m=read();
forup(i,2,max(n,m)){
lg[i]=lg[i>>1]+1;
}
forup(i,1,n){
forup(j,1,m){
a[i][j]=read();
if(a[i][j]==0) f[i][j]=0;
else f[i][j]=min({f[i-1][j],f[i][j-1],f[i-1][j-1]})+1;
}
}
mst.init();
qq=read();
forup(i,1,qq){
int x1=read(),y1=read(),x2=read(),y2=read();
int ll=0,rr=min(x2-x1+1,y2-y1+1),mm;
while(ll<rr){
mm=(ll+rr+1)>>1;
if(mst.ask(x1+mm-1,y1+mm-1,x2,y2)>=mm) ll=mm;
else rr=mm-1;
}
printf("%d\n",ll);
}
}
T4 题解
这题不难。
首先，这条最短路一定是以某个特殊城市开始，以某个特殊城市结束的，不然它必定不优。容易得到 $40pts$ 做法，对于每个特殊城市跑一遍 dijkstra，除了距离外，设 $dp_{i,j}$ 表示 $i$ 到 $j$ 的最短路至多经过多少个特殊城市，最后统计 $dp_{i,j}=k$ 的最小距离即可。复杂度 $O(n^2\log n)$（堆优化）。
考虑能否快速找到正解的起始点，发现假如我们对任意一个特殊点跑 dijkstra，距离它最远的点即为一个可行的起点，因为如果从其它点开始就要往那边绕一圈，那必定不优（感性理解一下），复杂度为 $O(n\log n)$。
code
code
#include<iostream>
#include<algorithm>
#include<string.h>
#define mem(a,b) memset(a,b,sizeof(a))
#include<queue>
#include<vector>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=1e5+5,inf=0x3f3f3f3f;
int n,m,K,a[N];
struct edge{
int v,w;
};
vector<edge> e[N];
struct Node{
int dis,u;
bool operator <(const Node &p)const{return dis>p.dis;}
};
int dist[N],vis[N],dp[N],nece[N];
priority_queue<Node> q;
void dij(int rt){
while(q.size()) q.pop();
mem(vis,0);mem(dist,0x3f);
mem(dp,0);
dist[rt]=0;
q.push(Node{0,rt});
while(q.size()){
int u=q.top().u;q.pop();
if(vis[u]) continue;
vis[u]=1;
if(nece[u]) dp[u]++;
for(auto i:e[u]){
int v=i.v,w=i.w;
if(dist[v]>=dist[u]+w){
dist[v]=dist[u]+w;
q.push(Node{dist[v],v});
dp[v]=max(dp[v],dp[u]);
}
}
}
}
signed main(){
n=read();m=read();
forup(i,1,m){
int u=read(),v=read(),w=read();
e[u].push_back(edge{v,w});
e[v].push_back(edge{u,w});
}
K=read();
forup(i,1,K){
a[i]=read();
nece[a[i]]=1;
}
dij(a[1]);
int mmm=1;
forup(i,1,K){
if(dist[a[i]]>dist[a[mmm]]) mmm=i;
}
dij(a[mmm]);
int ans=inf;
forup(i,1,K){
if(dp[a[i]]==K) ans=min(ans,dist[a[i]]);
}
printf("%d",ans);
}