暑假集训CSP提高模拟11

组题人： @KafuuChinocpp

\(T1\) P152. Fate \(24pts\)

• 强化版： HDU1688 Sightseeing

• 设 \(dis_{i,0/1}\) 表示从 \(s\) 到 \(i\) 的最短路/次短路长度， \(f_{i,0/1}\) 表示从 \(s\) 到 \(i\) 的最短路/次短路条数。

• \(dijkstra\) 过程中按照路径长度与最短路、次短路的大小关系四种情况进行反讨。

• 由于需要统计最短路及次短路，vis 数组同样需要记录当前是最短路还是次短路去更新状态

• 最后判断一下次短路长度是否等于最短路长度减一。

  点击查看代码

  const ll p=1000000007;
  struct node
  {
  	ll nxt,to,w;
  }e[400010];
  struct quality
  {
  	ll dis,x,id;
  	bool operator < (const quality another) const
  	{
  		return dis>another.dis;
  	}
  };
  ll head[400010],vis[400010][2],dis[400010][2],f[400010][2],cnt=0;
  void add(ll u,ll v,ll w)
  {
  	cnt++;
  	e[cnt].nxt=head[u];
  	e[cnt].to=v;
  	e[cnt].w=w;
  	head[u]=cnt;
  }	
  void dijkstra(ll s)
  {
  	ll x,id,i;
  	priority_queue<quality>q;
  	memset(dis,0x3f,sizeof(dis));
  	memset(vis,0,sizeof(vis));
  	dis[s][0]=0;
  	f[s][0]=1;
  	q.push((quality){dis[s][0],s,0});
  	while(q.empty()==0)
  	{
  		x=q.top().x;
  		id=q.top().id;
  		q.pop();
  		if(vis[x][id]==0)
  		{
  			vis[x][id]=1;
  			for(i=head[x];i!=0;i=e[i].nxt)
  			{
  				if(dis[e[i].to][0]>dis[x][id]+e[i].w)
  				{
  					dis[e[i].to][1]=dis[e[i].to][0];
  					f[e[i].to][1]=f[e[i].to][0];
  					dis[e[i].to][0]=dis[x][id]+e[i].w;
  					f[e[i].to][0]=f[x][id];
  					q.push((quality){dis[e[i].to][0],e[i].to,0});
  					q.push((quality){dis[e[i].to][1],e[i].to,1});
  				}
  				else
  				{
  					if(dis[e[i].to][0]==dis[x][id]+e[i].w)
  					{
  						f[e[i].to][0]=(f[e[i].to][0]+f[x][id])%p;
  					}
  					else
  					{
  						if(dis[e[i].to][1]>dis[x][id]+e[i].w)
  						{
  							dis[e[i].to][1]=dis[x][id]+e[i].w;
  							f[e[i].to][1]=f[x][id];
  							q.push((quality){dis[e[i].to][1],e[i].to,1});
  						}
  						else
  						{
  							if(dis[e[i].to][1]==dis[x][id]+e[i].w)
  							{
  								f[e[i].to][1]=(f[e[i].to][1]+f[x][id])%p;
  							}
  						}
  					}
  				}
  			}
  		}
  	}
  }
  int main()
  {
  	ll n,m,s,t,u,v,i;
  	cin>>n>>m>>s>>t;
  	for(i=1;i<=m;i++)
  	{
  		cin>>u>>v;
  		add(u,v,1);
  		add(v,u,1);
  	}
  	dijkstra(s);
  	cout<<(dis[t][1]-1==dis[t][0])*f[t][1]<<endl;
  	return 0;
  }
  

\(T2\) P153. EVA \(5pts\)

• 原题： [ABC274F] Fishing

• 从贪心的角度分析，网的一端和至少一条鱼重合一定不劣。

• 考虑枚举与左端点重合的鱼，然后固定这条鱼，令其他鱼与其做相对运动，处理出进入网的左右 \(t\) 边界，差分后，由于左端点已经固定，所以直接继承即可。

• 特判速度相等的情况。

• 略卡精度。

  点击查看代码

  const double eps=1e-10;
  int w[2010],x[2010],v[2010];
  map<double,int>d;
  map<double,int>::iterator it;
  int main()
  {
  	int n,a,ans=0,sum,i,j;
  	double l,r;
  	cin>>n>>a;
  	for(i=1;i<=n;i++)
  	{
  		cin>>w[i]>>x[i]>>v[i];
  	}
  	for(i=1;i<=n;i++)
  	{
  		d.clear();
  		sum=w[i];
  		for(j=1;j<=n;j++)
  		{
  			if(i!=j)
  			{
  				if(v[i]==v[j])
  				{
  					if(x[i]<=x[j]&&x[j]<=x[i]+a)
  					{
  						sum+=w[j];
  					}
  				}
  				else
  				{
  					l=1.0*(x[i]-x[j])/(v[j]-v[i]);
  					r=1.0*(x[i]+a-x[j])/(v[j]-v[i]);	
  					if(l-r>eps)//左右端点颠倒了要颠倒回来
  					{
  						swap(l,r);
  					}
  					if(r>=0)//保证存在区间
  					{
  						l=max(l,0.0);
  						d[l]+=w[j];
  						d[r+eps]-=w[j];
  					}
  				}
  			}
  		}
  		ans=max(ans,sum);
  		for(it=d.begin();it!=d.end();it++)
  		{
  			sum+=it->second;
  			ans=max(ans,sum);
  		}
  	}
  	cout<<ans<<endl;
  	return 0;
  }
  

\(T3\) P166. 嘉然登场 \(5pts\)

• 原题： [ARC148E] ≥ K

\(T4\) P178. Clannad \(0pts\)

• 原题： luogu P9340 [JOISC 2023 Day3] Tourism

总结

• \(T1\)
  • 没想到在 \(dijkstra\) 过程中同样也能更新次短路，说明对 \(dijkstra\) 节点标记的认识不清楚。
  • 在最短路 \(DAG\) 上统计答案上仅考虑到了最短路径上的点，没考虑到非最短路径上的点也能转移过来。

后记

• 奖励的限制越来越苛刻了。

  

  以下图片来源

  

• 题目背景夹带私货。