今天考了一场模拟赛，考的太菜了qwq，但讲解后发现题目都很水qwq，还需要继续努力qwq！

因为洛谷里没有这些题，我整理成了题单，随便跑了一些数据——>戳这里qwq

T1:字符串桶排

思路：

把字符串里的没一个字符，都用一个数组存有没有出现过，再统计个数，用map做会更简单一些

#include<bits/stdc++.h>
using namespace std;
int f[300],ans;
string st;
int main()
{
	cin>>st;
	for(int i=0;i<st.size();i++)
		if(!f[int(st[i])])ans++,f[int(st[i])]=1;
	cout<<ans<<endl;
	return 0;
}

T2:暴力打表

思路：

想不出好办法就试试暴力，然后发现个数并不多，就让它慢慢找出每一个数，发现只有23个满足条件，然后就直接输出就好了qwq。

#include<bits/stdc++.h>
using namespace std;
int f[1000010];
int n,x,tot;
int main()
{
	scanf("%d",&n);
	f[1]=1;
	f[2]=1;
	f[3]=1;
	f[4]=1;
	f[5]=1;
	f[6]=1;
	f[7]=1;
	f[8]=1;
	f[9]=1;
	f[153]=3;
	f[370]=3;
	f[371]=3;
	f[407]=3;
	f[1634]=4;
	f[4150]=5;
	f[4151]=5;
	f[8208]=4;
	f[9474]=4;
	f[54748]=5;
	f[92727]=5;
	f[93084]=5;
	f[194979]=5;
	f[548834]=6;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(f[x])printf("%d %d\n",x,f[x]),tot++; 
	}
	printf("%d\n",tot);
	return 0;
}

T3:好像还是暴力qwq

思路：

先按顺序把每个排序，但要记录是不是幸运数字，再枚举没相邻两个点，算出来它们中间有几个幸运数字（这个要仔细思考一下）

#include<bits/stdc++.h>
using namespace std;
struct node{bool f;int k;}e[50050];
int n,a,b,ans;
string st;
bool cmp(node a,node b){return a.k<b.k;}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)
	{
		cin>>st;
		scanf("%d",&e[i].k);
		if(st=="S")e[i].f=1;else e[i].f=0;
	}
	sort(e+1,e+n+1,cmp);
	if(e[1].f)ans+=e[1].k-a+1;
	if(e[n].f)ans+=b-e[n].k;
	for(int i=2;i<=n;i++)
	{
		if(e[i].f&&e[i-1].f)ans+=e[i].k-e[i-1].k;
		else if(e[i].f&&!e[i-1].f)ans+=(e[i].k-e[i-1].k)/2+1;
		else if(!e[i].f&&e[i-1].f)ans+=(e[i].k-e[i-1].k)/2;
	}
	printf("%d\n",ans);
	return 0;
}

然后兴致冲冲地交上去，发现错误一大堆qwq，然后看了看小数据，发现给出的数字会超出范围！！

C++真是一门难学的语言

这个怎么处理呢qwq？，其实也很简单，只要像上一步中算出相邻两个间幸运数字的区间的左端点和右端点，再判断一下可取的有哪些就好了！

#include<bits/stdc++.h>
using namespace std;
struct node{bool f;int k;}e[50050];
int n,a,b,ans;
string st;
bool cmp(node a,node b){return a.k<b.k;}
int xx(int x,int y)
{
	if(x>y||x>b||y<a)return 0;
	if(x>=a&&y<=b)return y-x+1;
	if(x<a)return y-a+1;
	if(y>b)return b-x+1;
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)
	{
		cin>>st;
		scanf("%d",&e[i].k);
		if(st=="S")e[i].f=1;else e[i].f=0;
	}
	sort(e+1,e+n+1,cmp);
	if(e[1].f)ans+=xx(a,e[1].k);
	if(e[n].f)ans+=xx(e[n].k+1,b);
	for(int i=2;i<=n;i++)
	{
		if(e[i].f&&e[i-1].f)ans+=xx(e[i-1].k+1,e[i].k);
		else if(!e[i].f&&e[i-1].f)ans+=xx(e[i-1].k+1,(e[i].k+e[i-1].k)/2);
		else if(e[i].f&&!e[i-1].f)ans+=xx((e[i].k+e[i-1].k+1)/2,e[i].k);
	}
	printf("%d\n",ans);
	return 0;
}

T4:最小生成树

思路：

老师给的题目是Subtask的，一组30分，一组70分qwq，我跑的数据也弄成这样了qwq，这样会大大降低我们的分数，每组数据必须全对才能得分qwq

C++真是一门难学的语言

我们先从小数据开始，30分时很好那的，跑一遍最小生成树就可以了，Prim和Kruskal都行，轻轻松松拿到30分（太少了qwq）。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dis[N],x[N],y[N];
int n,ans;
bool f[N];
void prim(int st)
{
	memset(dis,10,sizeof(dis));
	for(int i=1;i<=n;i++)dis[i]=min(abs(x[1]-x[i]),abs(y[1]-y[i]));
	memset(f,0,sizeof(f));
	f[st]=1; ans=0;
	for(int i=2;i<=n;i++)
	{
		int minn=2e9,k=0;
		for(int j=1;j<=n;j++)
			if(!f[j]&&dis[j]<minn){minn=dis[j];k=j;}
		f[k]=1;ans+=minn;
		for(int j=1;j<=n;j++)
			if(!f[j])dis[j]=min(dis[j],min(abs(x[k]-x[j]),abs(y[k]-y[j])));
	}
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
	}
	prim(1);
	printf("%d\n",ans);
	return 0;
}

然后，我们仔细读题，发现两点之间的代价是行的差和列的差的最小值，因为要代价最小，所以要连边就要连相邻的，这样就大大缩小了范围qwq

所以，我们只要把行排下序，求出最近行的2个点，建一条边，因为有n个点，只有n-1条边，列也同样如此。

这样，我们就得到了\(n\times2-2\)条边，再跑一遍最短路就可以了，可以用Prim+堆优化或Kruskal。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{int x,y,d;}a[N],b[N];
int n,f[N];
long long ans;
bool cmp1(node a,node b){return a.x<b.x;}
bool cmp2(node a,node b){return a.y<b.y;}
bool cmp3(node a,node b){return a.d<b.d;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		a[i].d=i;
		f[i]=i;
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n-1;i++)
	{
		b[i].x=a[i].d;
		b[i].y=a[i+1].d;
		b[i].d=a[i+1].x-a[i].x;
	}
	sort(a+1,a+n+1,cmp2);
	for(int i=n;i<=n*2-2;i++)
	{
		b[i].x=a[i-n+1].d;
		b[i].y=a[i-n+1+1].d;
		b[i].d=a[i-n+1+1].y-a[i-n+1].y;
	}
	sort(b+1,b+2*n-2+1,cmp3);
	for(int i=1;i<=n*2-2;i++)
	{
		int x=find(b[i].x),y=find(b[i].y);
		if(f[x]!=f[y])f[x]=y,ans+=b[i].d;
	}
	printf("%lld\n",ans);
	return 0;
}

qwq，下次，我一定要继续努力！

赛后感言

原文：https://www.cnblogs.com/cqh123/p/12644226.html