2023CSPJ题解

第一题：小苹果(apple)

思路

        本题直接推公式就能做。用两个变量分别存储所有苹果被拿走的天数和最后一个苹果被拿走的天数。本题不需要用数组标记，只需要每次将当前苹果数减去拿走的苹果数，得到拿走之后的苹果数，每次再判断一下最后一个苹果有没有被拿走即可。

代码

#include <iostream>
#include <cstdio>
using namespace std;
int n,a1,a2;
int main()
{
	freopen("apple.in","r",stdin);//文件输入输出
	freopen("apple.out","w",stdout);
	cin>>n;
	int t=n;//为了避免n丢失，将n赋值给t
	while(t)
	{
		a1++;
		if(a2==0&&t%3==1)//如果最后一个苹果可以拿了，就记录步数
		{
			a2=a1;
		}
		t=t-(t+2)/3;//减去拿走的苹果数量
	}
	cout<<a1<<" "<<a2<<endl;
	return 0;
}

第二题：公路(road) 

 思路

        贪心

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N=10005;
int n,d,v[N],a[N];
long long ans;
int main(int argc, char *argv[]) {
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	cin>>n>>d;
	for(int i=1; i<n; i++)
	{
		cin>>v[i];
	}
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	int minn=a[1],left=0;//分别是能加的最便宜的油和剩下的路程
	for(int i=1; i<n; i++)
	{
		minn=min(a[i],minn);//更新最小值
		if(left>=v[i])
		{
			left-=v[i];
			continue;
		}
		int t=(v[i]-left+d-1)/d;//
		ans+=1ll*t*minn;//更新钱数(1ll指int转long long)
		left=t*d+left-v[i];//更新剩余路程
	}
	cout<<ans<<endl;
	return 0;
}

第三题：一元二次方程(uqe)

思路

        纯大模拟

代码

#include <iostream>
#include <cstdio>
using namespace std;
int t,m,a,b,c;
int aa,bb,gd1,gd2;
int gcd(int a,int b)
{
	if(a%b==0)
	{
		return b;
	}
	return gcd(b,a%b);
}
int main(int argc, char *argv[]) {
    freopen("uqe.in","r",stdin);
    freopen("uqe.out","w",stdout);
	cin>>t>>m;
	while(t--)
	{
		cin>>a>>b>>c;
		int det=b*b-4*a*c;
		if(det<0)
		{
			cout<<"NO"<<endl;
			continue;
		}
		int a1=1;
		for(int i=2; i*i<=det; i++)
		{
			while(det%(i*i)==0)
			{
				a1*=i,det/=i*i;
			}
		}
		aa=2*a;
		bb=-b;
		if(aa<0)
		{
			aa=-aa;
			bb=-bb;
		}
		if(det==1)
		{
			det=0;
			bb+=a1;
		}
		gd1=gcd(abs(bb),aa);
		gd2=gcd(a1,aa);
		if(det==0)
		{
			if(bb%aa==0)
			{
				cout<<bb/aa;
			}
			else
			{
				cout<<bb/gd1<<"/"<<aa/gd1;
			}
		}
		else
		{
			if(bb!=0)
			{
				if(bb%aa==0)
				{
					cout<<bb/aa;
				}
				else
				{
					cout<<bb/gd1<<"/"<<aa/gd1;
				}
				cout<<"+";
			}
			if(a1/gd2!=1)
			{
				cout<<a1/gd2<<"*";
			}
			cout<<"sqrt("<<det<<")";
			if(aa/gd2!=1)
			{
				cout<<"/"<<aa/gd2;
			}
		}
		cout<<endl;
	}
	return 0;
}

第四题:旅游巴士

思路

         bfs+二分

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <string.h>
#include <vector>
using namespace std;
const int N=10005,K=105;
int n,m,k;
vector<int> e[N],t[N];
struct node{
	int x,k;
};
int dis[N][K];
bool bfs(int mid)
{
	memset(dis,-1,sizeof(dis));
	queue<node> q;
	dis[m][0]=mid*k;
	q.push(node{n,0});
	while(!q.empty())
	{
		int x=q.front().x,b=q.front().k;
		q.pop();
		if(dis[x][b]==0)
		{
			continue;
		}
		for(int i=0; i<e[x].size(); i++)
		{
			if(t[x][i]>=dis[x][b])
			{
				continue;
			}
			for(int i=0; i<e[x].size(); i++)
			{
				if(t[x][i]>=dis[x][b])
				{
					continue;
				}
				int y=e[x][i],p=(b+k-1)%k;
				if(dis[y][p]!=-1)
				{
					continue;
				}
				dis[y][p]=dis[x][b]-1;
				q.push(node{y,p});
			}
		}
	}
	if(dis[1][0]==-1)
	{
		return false;
	}
	else
	{
		return true;
	}
}
int main(int argc, char *argv[]) {
	freopen("bus.in","r",stdin);
	freopen("bus.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1; i<=m; i++)
	{
		int u,v,a;
		cin>>u>>v>>a;
		e[v].push_back(u);
		t[v].push_back(a);
	}
	int left=0,right=2e6;
	while(left<right)
	{
		int mid=(left+right)/2;
		if(bfs(mid))
		{
			right=mid;
		}
		else
		{
			left=mid+1;
		}
	}
	if(right==2e6)
	{
		cout<<-1<<endl;
	}
	else
	{
		cout<<l*k<<endl;
	}
	return 0;
}

        感谢阅读！欢迎轰炸评论区!