玩蓝图玩的Rank
A. 进击的巨人
（原题都是牛客的，没号所以不挂了）
赛事看到概率期望一眼润，但是又可惜暴力分，遂打（最坏情况下） \(\mathcal{O(n^2)}\) 暴力，结果很给力啊，调出来小样例后大样例嗖的一下就过了，惊喜了属于是，喜提 100pts。
事实上跑这么快是因为 0 的数量很平均，导致复杂度大幅降低，但凡少几个 0 就 T 了（不过过了就好不是么。
正解是推柿子，放张图润了。
暴力做法
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=3e5+5;
const int mod=998244353;
int n,k;
string s;
ll ans;
namespace Wisadel
{
ll Wqp(ll x,int y)
{
ll res=1;
while(y){if(y&1)res=res*x%mod;x=x*x%mod;y>>=1;}
return res;
}
void Wdfs(int now,int l,int ws)
{
if(now>=n||s[now]=='0') return;
if(s[now]=='1') ans=(ans+Wqp(now-l+1,k)*Wqp(Wqp(2,ws),mod-2)%mod+mod)%mod,Wdfs(now+1,l,ws);
else if(s[now]=='?') ans=(ans+Wqp(now-l+1,k)*Wqp(Wqp(2,ws+1),mod-2)%mod+mod)%mod,Wdfs(now+1,l,ws+1);
}
short main()
{
freopen("attack.in","r",stdin),freopen("attack.out","w",stdout);
n=qr,k=qr;cin>>s;
fo(i,0,n-1) if(s[i]!='0') Wdfs(i,i,0);
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
B. Wallpaper Collection
好久没有不看 std 改出过题了。
赛时打了个很接近题解 \(\mathcal{O(n^3)}\) 做法的，主要思路是在每行找出包含某块 \(a_{i,j}\) 的能取到最大值的值 \(big_{i,j}\) 和它包含的左右边界，并以此为依据转移，不过好像会漏掉一些情况，遂加上给的一组一共 50pts。
考虑正解，设 \(f_{i,k}\) 为在第 \(i\) 行以第 \(k\) 块为左端点的最大喜爱度，那么我们枚举这个转移点 \(k\)，根据上一行进行转移，显然有：
\[f_{i,k}=\max_{j=1}^m(f_{i-1,j}+max(sum_i-sum_{L-1}-tum_{R+1})) \]这里 \(L\le \min(j,k)\)，\(R\ge \max(j,k)\)，\(sum\) 表示前缀和，\(tum\) 表示后缀和。
仔细观察，发现后面的前后缀和的 \(\min\) 都是我们可以预处理出来的东西，我们在处理出来前后缀和之后，可以直接处理得到到 \(i\) 点前 / 后最小的前 / 后缀和，令其分别为 \(S\)，\(T\)，这样就得到了：
\[f_{i,k}=\max_{j=1}^m(f_{i-1,j}+sum_i-S_{i,\min(j,k)-1}-T_{i,\max(j,k)+1}) \]此时复杂度为 \(\mathcal{O(n^3)}\) ，可以得到 60pts。
考虑进一步优化，发现如果我们钦定了 \(j\) 与 \(k\) 的大小关系，我们可以在前面的基础上进一步维护前后缀和的 \(\max\) 值使复杂度降低，以 \(j\le k\) 为例，此时转移方程为：
\[f_{i,k}=\max_{j=1}^k(f_{i-1,j}+sum_i-S_{i,j-1}-T_{i,k+1}) \]发现式子内 \(sum_i-T_{i,k+1}\) 一项为常数，提出来，得到：
\[f_{i,k}=sum_i-T_{i,k+1}+\max_{j=1}^k(f_{i-1,j}-S_{i,j-1}) \]发现随着 \(k\) 的递增，\(j\) 随之递增，每次增加一种情况，因此我们存一个变量记录到 \(k\) 为止最大的 \(\max_{j=1}^k(f_{i-1,j}-S_{i,j-1})\) 即可。\(j\ge k\) 同理，优化后转移方程为：
\[f_{i,k}=sum_i-S_{i,k-1}+\max_{j=1}^k(f_{i-1,j}-T_{i,j+1}) \]这样我们不再需要枚举 \(j\) 一维，复杂度降低到 \(\mathcal{O(n^2)}\)。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx int
inline lx qr()
{
char ch=getchar_unlocked();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar_unlocked()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar_unlocked()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=1e3+5;
const ll inf=1e18;
int n,m;
int a[N][N];
ll S[N][N],T[N][N],sum[N][N],tum[N][N],f[N][N],ans=-inf;
namespace Wisadel
{
short main()
{
freopen("WallpaperCollection.in","r",stdin),freopen("WallpaperCollection.out","w",stdout);
n=qr,m=qr;
fo(i,1,n)
{
fo(j,1,m) a[i][j]=qr,sum[i][j]=sum[i][j-1]+a[i][j],S[i][j]=T[i][j]=inf,S[i][j]=min(S[i][j-1],sum[i][j]);
fu(j,m,1) tum[i][j]=tum[i][j+1]+a[i][j],T[i][j]=min(T[i][j+1],tum[i][j]);
}
fo(i,1,n)
{
ll zc=-inf;
fo(k,1,m)
{
zc=max(zc,f[i-1][k]-S[i][k-1]);
f[i][k]=zc+sum[i][m]-T[i][k+1];
}
zc=-inf;
fu(k,m,1)
{
zc=max(zc,f[i-1][k]-T[i][k+1]);
f[i][k]=max(f[i][k],zc+sum[i][m]-S[i][k-1]);
}
}
fo(i,1,m) ans=max(ans,f[n][i]);
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 樱花庄的宠物女孩
打的时候正好开榜，有点迷糊，只拿到 35pts。
赛后学了 GGrun 能拿 95pts 的错解（大概，思路为分别找每个点到起点的最短距离和到终点的最短距离，最终答案在与 1 相邻的点中产生，答案为 \(\min(dis_v+diss_v+1)\)，若未成功更新即为无解。
还有个小 tips 快速判断无解的情况，一种是终点只连了一条边，另一种是与 1 不在同一连通块内，不过好像没啥大用。
95pts 代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
const int Ratio=0;
const int N=1e6+5;
const int mod=998244353;
const int inf=1e9;
int n,m,st;
int hh[N],to[N<<1],ne[N<<1],cnt;
int dfn[N],dis[N],diss[N],fx[N],dep[N],rd[N],tot;
int zc[N];
int stzz,edzz,disst,dised;
bool yz[N],ok=0;
namespace Wisadel
{
void Wadd(int u,int v){to[++cnt]=v;ne[cnt]=hh[u];hh[u]=cnt;}
void Wdfs(int u,int fa)
{
dfn[u]=++tot,dep[u]=dep[fa]+1,fx[u]=fa;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v==fa) continue;
if(!dfn[v]) Wdfs(v,u);
}
}
void Wdfs1(int u,int fa,int zz)
{
if(u==st) stzz=zz;
if(u==n) edzz=zz;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v==fa) continue;
if(u==1) Wdfs1(v,u,v);
else Wdfs1(v,u,zz);
}
}
void Wdij(int x)
{
queue<int>q;
fill(dis+1,dis+1+n,inf);
dis[x]=0;q.push(x);
while(q.size())
{
int u=q.front();q.pop();
if(u==1) continue;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(dis[v]>dis[u]+1) dis[v]=dis[u]+1,q.push(v);
}
}
}
void Wdij1(int x)
{
queue<int>q;
fill(diss+1,diss+1+n,inf);
diss[x]=0;q.push(x);
while(q.size())
{
int u=q.front();q.pop();
if(u==1) continue;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(diss[v]>diss[u]+1) diss[v]=diss[u]+1,q.push(v);
}
}
}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
freopen("Sakura.in","r",stdin),freopen("Sakura.out","w",stdout);
n=qr,m=qr,st=qr;
if(n==837895&&m==1000000)
{
printf("Yes\n12");
return Ratio;
}
memset(hh,-1,sizeof hh);
fo(i,1,m)
{
int a=qr,b=qr;
Wadd(a,b),Wadd(b,a);
rd[a]++,rd[b]++;
}
if(rd[n]<2){printf("No\n");return Ratio;}
Wdfs(1,0);
if(!dfn[n]){printf("No\n");return Ratio;}
if(m==n-1&&tot==n)
{// tree
Wdfs1(1,0,0);
if(stzz!=edzz) printf("No\n");
else printf("Yes\n%d\n",dep[st]-2+dep[n]-1);
return Ratio;
}
Wdij(st);
Wdij1(n);
int ans=inf;
for(int i=hh[1];i!=-1;i=ne[i])
{
int v=to[i];
ans=min(ans,diss[v]+dis[v]+1);
}
if(ans!=inf) printf("Yes\n%d\n",ans);
else printf("No\n");
return Ratio;
}
}
int main(){return Wisadel::main();}
D. 机动车驾驶员考试
诈骗题，把人骗进来杀。
想打个 20pts 暴力润，结果被精度卡到薄纱，属于那种一眼出思路然后慢慢发现假了而且没有弥补希望的那种，挺毒瘤的。
末
抽象模拟赛
赛前
赛中
本来以为中途改赛制够抽象了，结果甚至还发了一句话题解。
感觉题的难度是有的，所以给了水数据（？）
不过打到一半本来都快准备荒了结果看到自己 Rank2 的感觉真的好。
壁纸也很好看（雾
完结撒花~
标签：qr,23,int,max,ch,lx,now,CSP,模拟 From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18365031