2023CSP-S 复赛模测（日记和×××） - 模拟赛记录

Preface

这套题说实话挺水的，它的水不仅仅是在数据上（实际得分比期望得分高了 \(50+\) 分），而且正解也神奇得不像个正解（全是各种分类讨论卡子任务的，感觉像是出题人水平不够一样）。

日记和最短路（shortway）

（话说最短路的英语不应该是 shortest path 吗？）

题目中给了一个 DAG，然后要求用两种方式跑最短路。

看到 DAG，又要求最短路，第一时间想到先拓扑排序再做 DP，似乎只需要 \(O(N+M)\) 的时间复杂度。

然而这里有一个大问题：因为边权是一个字符串，而在组成最短路和比较路径大小的时候最坏时间复杂度是 \(O(\sum \lvert w_i \rvert)\)，所以按照以上方法的实际时间复杂度应当是 \(O(N+M\sum \lvert w_i \rvert)\)，虽然不可能卡得满，但是硬要算的话，期望得分应当只有 \(16\) 分才对。

然而，用这样的方法可以卡到 \(96\) 分，可见数据几乎完全没有卡字符串比较和合并的时间复杂度。

正解似乎是要拆点什么的，但是我不会，所以就只放上面说的 \(96\) 分代码了：

#include<queue>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;

const int N=1e5+5,M=5e5+5;
int n,m;

struct Allan{
	int to,nxt;
	string val;
}edge[M];
int head[N],idx;
inline void add(int x,int y,string &z)
{
	edge[++idx]={y,head[x],z};
	head[x]=idx;
	return;
}

int indeg[N];
queue<int> q;
int top_order[N],top_idx;
void TopSort(int src)
{
	q.push(src);
	indeg[src]--;
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		top_order[++top_idx]=x;
		for(int i=head[x];i;i=edge[i].nxt)
		{
			int y=edge[i].to;
			indeg[y]--;
			if(!indeg[y])
				q.push(y);
		}
	}
	return;
}

string sp1[N];
bool cmp1(const string &x,const string &y,const string &z)
{
	if(z=="-") return true;
	else if(x.length()+y.length()!=z.length())
		return x.length()+y.length()<z.length();
	else return x+y<z;
}
void Solve1()
{
	for(int p=1;p<=top_idx;p++)
	{
		int x=top_order[p];
		for(int i=head[x];i;i=edge[i].nxt)
		{
			int y=edge[i].to; string z=edge[i].val;
			if(cmp1(sp1[x],z,sp1[y])) //sp[x]+z<sp[y]
				sp1[y]=sp1[x]+z;
		}
		if(x!=n) sp1[x].clear();
	}
	return;
}

string sp2[N];
bool cmp2(const string &x,const string &y,const string &z)
{
	if(z=="-") return true;
	else return x+y<z;
}
void Solve2()
{
	for(int p=1;p<=top_idx;p++)
	{
		int x=top_order[p];
		for(int i=head[x];i;i=edge[i].nxt)
		{
			int y=edge[i].to; string z=edge[i].val;
			if(cmp2(sp2[x],z,sp2[y])) //sp[x]+z<sp[y]
				sp2[y]=sp2[x]+z;
		}
		if(x!=n) sp2[x].clear();
	}
	return;
}

int main()
{
	freopen("shortway.in","r",stdin);
	freopen("shortway.out","w",stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	
	cin>>n>>m;	
	for(int i=1;i<=m;i++)
	{
		int x,y; string z;
		cin>>x>>y>>z;
		add(x,y,z);
		indeg[y]++;
	}
	
	TopSort(1);
	for(int i=1;i<=n;i++)
		sp1[i]=sp2[i]="-";
	sp1[1]=sp2[1]="";
	Solve1();
	Solve2();
	cout<<sp1[n]<<' '<<sp2[n]<<endl;
	
	return 0;
}