4.3日早普及组模拟赛总结

4.3日早普及组模拟赛总结
这是比赛网址
这次比赛我考了260分，总体还不错。
第一题：统计单词数
题目内容
思路：直接模拟就可以了，注意要把字母统一成大写或小写。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int n1,n2,ansk=-1,ans;
char a[11],b[1000001];
int ck1(char x)
{
	if(x>='a'&&x<='z') return 1;
	if(x>='A'&&x<='Z') return 1;
	return 0;
}
int ck2(char x)
{
	if(x>='a'&&x<='z') return 1;
	if(x>='A'&&x<='Z') return 1;
	if(x==' ') return 1;
	return 0;
}
int main()
{
	n1=1;
	a[n1]=getchar(); 
	while(ck1(a[n1])==0) a[n1]=getchar();
	while(ck1(a[n1])==1)
	{
		n1++;
		a[n1]=getchar();
	}
	n1--;
	n2=1;
	b[n2]=getchar();
	while(ck2(b[n2])==0) b[n2]=getchar();
	while(ck2(b[n2])==1)
	{
		n2++;
		b[n2]=getchar();
	}
	b[n2]=' ';
	for(int i=1;i<=n1;i++)
	{
		if(a[i]>='A'&&a[i]<='Z') 
			a[i]=a[i]-'A'+'a';
	}
	for(int i=1;i<=n2;i++)
	{
		if(b[i]>='A'&&b[i]<='Z')
		{
			b[i]=b[i]-'A'+'a';
		}
	}
	int l=1;
	for(int i=1;i<=n2;i++)
	{
		if(b[i]==' ')
		{
			int len=i-l;
			if(len==n1)
			{
				//cout<<l<<" "<<i-1<<endl;
				int ck=0;
				for(int j=l,k=1;j<=i-1,k<=n1;j++,k++)
				{
					if(b[j]!=a[k])
					{
						ck=1;
						break;
					}
				}
				if(ck==0)
				{
					if(ansk==-1) ansk=l;
					ans++;
				}
			}
			l=i+1;
		}
	}
	if(ans==0) cout<<-1;
	else cout<<ans<<" "<<ansk-1;
} 

得分情况：100。
第二题：螺旋矩阵
题目内容
思路：

1. 对于50%的数据，直接模拟将矩阵求出。
2. 对于100%的数据，可以通过找规律求得答案。
   可以参考以下博客：
   博客1
   博客2
   得分情况：50。
   代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c[101][101];
int main()
{
	cin>>n>>a>>b;
	int x,y,z;
	x=1;
	y=1;
	z=1;
	c[x][y]=z;
	while(z<n*n)
	{
		while(c[x][y+1]==0&&y+1<=n&&z<n*n) c[x][++y]=++z;
		while(c[x+1][y]==0&&x+1<=n&&z<n*n) c[++x][y]=++z;
		while(c[x][y-1]==0&&y-1>=1&&z<n*n) c[x][--y]=++z;
		while(c[x-1][y]==0&&x-1>=1&&z<n*n) c[--x][y]=++z;
	}
	cout<<c[a][b];
}

第三题：寻找道路
题目内容
思路：

1. 60分，首先先储存一个数组$b$b，表示两个点是否连通（可间接联通），用$floyd$floyd算法，然后找到不符合要求的点，将这个点的所有边删除，最后再求一遍最短路径，还是用$floyd$floyd，时间复杂度为$O(n^3)$O(n3)
2. 满分方法：$SPFA$SPFA和$bfs$bfs。

可以参考：
博客1
博客2
得分情况：60。
代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,b[101][101],a[101][101],s,t,ans=INT_MAX,c[101];
int ck(int x)
{
	for(int i=1;i<=n;i++)
		if(a[x][i]==1)
			if(b[i][t]==0&&i!=t) 
				return 0;
	return 1; 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=INT_MAX;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		b[u][v]=1,a[u][v]=1;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(b[i][k]==1&&b[k][j]==1&&i!=j&&j!=k&&i!=k)
					b[i][j]=1;
	cin>>s>>t;
	for(int i=1;i<=n;i++)
		if(ck(i)==0) c[i]=0;
		else c[i]=1;
	for(int i=1;i<=n;i++)
		if(c[i]==0)
			for(int j=1;j<=n;j++)
				a[j][i]=INT_MAX,a[i][j]=INT_MAX;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i!=j&&i!=k&&k!=j&&a[i][k]!=INT_MAX&&a[k][j]!=INT_MAX)
					a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
	cout<<a[s][t];
}

第四题：跳房子
题目内容
思路：

1. 50分，二分答案+动态规划。假设我要求用了$g$g个金币的最大分数，那么可以得到转移方程：
   当$g<d,f_i=max(f_j+s_i)(0\leq j\leq i-1 ,d-g\leq x_i-x_j\leq d+g)$g<d,fi​=max(fj​+si​)(0≤j≤i−1,d−g≤xi​−xj​≤d+g)
   当 $g>=d,f_i=max(f_j+s_i)(0\leq j\leq i-1 ,1\leq x_i-x_j\leq d+g)$g>=d,fi​=max(fj​+si​)(0≤j≤i−1,1≤xi​−xj​≤d+g)
   然后根据转移方程二分答案，时间复杂度为$O(n^2\log^{1000000000}_2)\approx O(30n^2)$O(n2log21000000000​)≈O(30n2)
   代码如下：

#include<bits/stdc++.h>
#define N 1000000000
using namespace std;
int n,d,k,x[500001],s[500001],f[500001],ans=N;
int big(int g)
{
	for(int i=1;i<=n;i++) f[i]=-N;
	int ans=0;
	if(g<d)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<i;j++)
			{
				int y=x[i]-x[j];
				if(d-g<=y&&y<=d+g) f[i]=max(f[i],f[j]+s[i]);
			}
			ans=max(ans,f[i]);
		}
	}
	else if(g>=d)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<i;j++)
			{
				int y=x[i]-x[j];
				if(1<=y&&y<=d+g) f[i]=max(f[i],f[j]+s[i]);
			}
			ans=max(ans,f[i]);
		}	
	}
	return ans;
}
int main()
{
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++) cin>>x[i]>>s[i];
	if(big(0)>=k)
	{
		cout<<0;
		return 0;
	} 
	int l=1,r=N;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(big(mid)<k) l=mid+1;
		else r=mid-1,ans=min(ans,mid);	
	}
	cout<<ans;
}

2. 100分，似乎是单调队列优化，反正我不懂 。

可以参考这个博客
得分情况：50。