昨天积攒的 rp 生效了！
Rank
A. Fate
签到题。
次短路计数，感觉做过类似的，不过这里次短路定义为最短路长度 +1，赛时把自环想成环了，原谅我犯唐。
还是用 dijkstra，我们这次开两个 dis 数组存最短路和次短路长度，然后两个 cnt 数组存二者的个数，稍微想想就能想到一共的四种可能：
- 更新后长度小于最短路长度，那么现将用最短路更新次短路，然后将这条路径置为最短路，数量为更新路径的数量。
- 长度等于最短路，直接数量 +1。
- 长度小于次短路，将这条路置为次短路，数量为更新路径的数量。
- 长度等于次短路，直接数量 +1。
点击查看代码
const int N=2e5+5;
const int mod=1e9+7;
int n,m,st,ed;
int hh[N],to[N<<1],ne[N<<1],w[N<<1],cntt;
ll dis[N][2],yz[N][2],cnt[N][2];
struct rmm
{
ll d,num,zl;
bool operator<(const rmm &a)const{return d>a.d;}
};
namespace Wisadel
{
void Wadd(int u,int v,int va)
{
to[++cntt]=v;
w[cntt]=va;
ne[cntt]=hh[u];
hh[u]=cntt;
}
void Wdij(int x)
{
priority_queue<rmm>q;
memset(dis,0x3f,sizeof dis);
dis[x][0]=0,cnt[x][0]=1;
q.push((rmm){0,x,0});
while(q.size())
{
ll u=q.top().num,zl=q.top().zl;q.pop();
if(yz[u][zl]) continue;
yz[u][zl]=1;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(dis[v][0]>dis[u][zl]+w[i])
{// 最短
dis[v][1]=dis[v][0];
cnt[v][1]=cnt[v][0];
q.push((rmm){dis[v][1],v,1});
// 先更新次短
dis[v][0]=dis[u][zl]+w[i];
cnt[v][0]=cnt[u][zl];
q.push((rmm){dis[v][0],v,0});
}
else if(dis[v][0]==dis[u][zl]+w[i])
cnt[v][0]=(cnt[v][0]+cnt[u][zl])%mod;
else if(dis[v][1]>dis[u][zl]+w[i])
{// 次短
dis[v][1]=dis[u][zl]+w[i];
cnt[v][1]=cnt[u][zl];
q.push((rmm){dis[v][1],v,1});
}
else if(dis[v][1]==dis[u][zl]+w[i])
cnt[v][1]=(cnt[v][1]+cnt[u][zl])%mod;
}
}
}
short main()
{
// freopen("Fate9.in","r",stdin),freopen(".out","w",stdout);
n=qr,m=qr;st=qr,ed=qr;
memset(hh,-1,sizeof hh);
fo(i,1,m)
{
int a=qr,b=qr;
Wadd(a,b,1),Wadd(b,a,1);
}
Wdij(st);
if(dis[ed][0]+1==dis[ed][1])
printf("%lld\n",cnt[ed][1]);
else printf("0\n");
return Ratio;
}
}
int main(){return Wisadel::main();}
B. EVA
也挺水的，感觉之前做过这个类型的，这个多处理些细节就好了。
首先挺显然的，最优策略时开始撒网的地点肯定有一条鱼。
发现 \(n\le 2000\)，所以考虑枚举左端点的鱼，然后对剩下的鱼求出有贡献的答案范围，复杂度是 \(O(n^2)\) 的。
有几个注意的点。
首先对于速度相同的两条鱼，显然只看初始位置就好了。
实现上，为了防止精度出现误差，存位置的变量尽量使用 double 类型。
对于两条鱼，有 \(\triangle s=x_2-x_1+t\times \left(v_2-v_1\right)\)，做出贡献的范围为 \(\triangle s\in \left[0,a\right]\)，那么移个项可得 \(t\in\left[\frac{x_1-x_2}{v_2-v_1},\frac{a+x_1-x_2}{v_2-v_1}\right]\)，这样我们便可以依据时间算出贡献，存储用个 map 就好。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int Ratio=0;
const int N=2e4+5;
const double eps=1e-9;
int n,m,ans=-1e9;
struct rmm
{
int w,x,v;
}fis[N];
map<double,int>mp;
namespace Wisadel
{
short main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d%d",&fis[i].w,&fis[i].x,&fis[i].v);
for(int i=1;i<=n;i++)
{
mp.clear();
int w=fis[i].w,x=fis[i].x,v=fis[i].v;
int now=w;
for(int j=1;j<=n;j++)
{
if(i==j) continue;
if(fis[j].v==v&&fis[j].x>=x&&fis[j].x<=x+m)
{// 速度相同的情况
now+=fis[j].w;
continue;
}
double fw1=1.0*(x-fis[j].x)/(fis[j].v-v),fw2=1.0*(m+x-fis[j].x)/(fis[j].v-v);
if(fw1>fw2) swap(fw1,fw2);
// 左右边界
if(fw2>=0)
{
if(fw1<1.0*0) fw1=1.0*0;
mp[fw1]+=fis[j].w,mp[fw2+eps]-=fis[j].w;
// 右边界 +eps 即为超出答案范围一点点的位置
}
}
int anss=now;
for(auto [a,b]:mp) now+=b,anss=max(anss,now);
// 根据边界界定找最优答案
ans=max(ans,anss);
}
printf("%d\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
C. 嘉然登场
一眼计数题，赛时想推 \(k=1\) 结论，推了近二十分钟发现假了，重复不算，然后摆。
感觉赛时 AK 大佬的题解是目前看过最易懂的题解，搬了。
D. Clannad
感觉暴力都想假了，只推出链的做法。
找到链头和链尾，映射一个顺序到原来的城镇编号上。
对于序列，我们直接找到两点映射间最大的坐标差 +1 即为答案的值。
那么查询，容易想到线段树，我们只需要建立一个存映射后编号的最大值和最小值的线段树，每次查找这两个值，就能得出答案了。
点击查看部分分代码
已经读入了部分数据。
namespace Wistask3
{
int num[N],tot,st,ed;
int minn[N<<2],maxx[N<<2];
void Wdfs(int u,int fa)
{
num[u]=++tot;
if(u==ed) return;
for(int i=hh[u];i!=-1;i=ne[i])
{
int v=to[i];
if(v!=fa) Wdfs(v,u);
}
}
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
void Wpushup(int rt)
{
minn[rt]=min(minn[ls],minn[rs]);
maxx[rt]=max(maxx[ls],maxx[rs]);
}
void Wbuild(int rt,int l,int r)
{
if(l==r)
{
minn[rt]=maxx[rt]=num[a[l]];
return;
}
Wbuild(ls,l,mid),Wbuild(rs,mid+1,r);
Wpushup(rt);
}
int Wqmax(int rt,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return maxx[rt];
int res=-1e9;
if(x<=mid) res=max(res,Wqmax(ls,l,mid,x,y));
if(y>mid) res=max(res,Wqmax(rs,mid+1,r,x,y));
return res;
}
int Wqmin(int rt,int l,int r,int x,int y)
{
if(x<=l&&r<=y) return minn[rt];
int res=1e9;
if(x<=mid) res=min(res,Wqmin(ls,l,mid,x,y));
if(y>mid) res=min(res,Wqmin(rs,mid+1,r,x,y));
return res;
}
short main()
{
// cout<<"+====="<<endl;
fo(i,1,n)
{
if(in[i]==1&&!st) st=i;
else if(in[i]==1&&!ed) ed=i;
if(st&&ed) break;
}
Wdfs(st,0);
Wbuild(1,1,m);
while(q--)
{
int a=qr,b=qr;
int sma=Wqmin(1,1,m,a,b),big=Wqmax(1,1,m,a,b);
printf("%d\n",big-sma+1);
}
return Ratio;
}
}
末
今天发挥出正常实力了，果然早起是有用的。
不过部分分还是拿的不全，比赛要专心拼啊。
完结撒花~
rp 这么有用，继续点踩吧（雾