CSP-J 2023真题解析

T1 小苹果

一、题目链接

P9748 [CSP-J 2023] 小苹果

二、题目大意

现有 $n$ 个苹果从左到右排成一列，编号为从 $1$ 到 $n$。

每天都会从中拿走一些苹果。拿取规则是，从左侧第 $1$ 个苹果开始、每隔 $2$ 个苹果拿走 $1$ 个苹果。随后将剩下的苹果按原先的顺序重新排成一列。

现求多少天能拿完所有的苹果，而编号为 $n$ 的苹果是在第几天被拿走的

数据范围：$1\le n\le 10^9$

三、题目分析

• 根据题目意思很容易想到时间复杂度为 $O(n)$ 的暴力模拟方法，这样就已经足够拿到 $90$ 分了
• 因为满分的要求是 $10^9$，所以这大概是需要 $\log$ 级的时间复杂度
• 仔细观察之后，你能发现每次会大约拿走 $\frac{1}{3}$ 的苹果，所以最终拿的次数是 $O(\log n)$ 级别的，所以只要我们能按轮次处理计科得到满分
• 每一轮具体拿走的苹果数量是 $\lceil \frac{n}{3}\rceil$，因为是从第一个开始拿的
• 注意，每一轮之后 $n$ 都会更新
• 不难发现最后一个苹果只会在 $n\mathrm{mod}3=1$ 时被取走，所以再判断一下即可。
• 时间复杂度 $O(\log n)$

四、正解程序

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>using namespace std;
typedef long long ll;
int main()
{ll n;scanf("%lld",&n);ll t=n,ans1=0,ans2=0;while(t){ll x=(t+2)/3;ans1++;if(ans2==0 && t%3==1)ans2=ans1;t-=x;}printf("%lld %lld\n",ans1,ans2);return 0;
}

T2 公路

一、题目链接

P9749 [CSP-J 2023] 公路

二、题目大意

现有一条公路上一共有 $n$ 个站点，编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i+1$ 的距离为 $v_i$ 公里。每个站点都可以加油，编号为 $i$ 的站点一升油的价格为 $a_i$ 元，且每个站点只出售整数升的油。

现要从站点 $1$ 开车到站点 $n$，一开始油箱为空。油箱可以装下任意多的油，且每升油可以让车前进 $d$ 公里。问至少要花多少钱加油

数据范围：$1\le n\le 10^5,1\le d\le 10^5,1\le v_i\le 10^5,1\le a_i\le 10^5$

三、题目分析

• 为了消费最小，所以我们一定要尽可能加便宜的油，毕竟油箱无限大
• 所以很显然我们可以有一个贪心的思路，选择一个递减的油价序列进行加油，即加油跑到下一个比当前的油更便宜的地方（尽可能刚好把油耗光）再加油
• 这样当然可以实现，但稍微有一点点复杂，我们可以做一点等价
• 我们到一个加油站的时先不加油，等到缺油的时候再从之前经过的最便宜的加油站虚空加油。如果出现更便宜的加油站，我们就更新即可。以上两个思路显然是等价的。
• 时间复杂度 $O(n)$

四、正解程序

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>using namespace std;
typedef long long ll;
const ll maxn=100010;
ll n,d,v[maxn],a[maxn];
int main()
{scanf("%lld%lld",&n,&d);for(ll i=1;i<=n-1;i++)scanf("%lld",&v[i]);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);ll price=a[1],rest=0,ans=0;for(ll i=1;i<=n-1;i++){price=min(a[i],price);if(rest>=v[i]){rest-=v[i];continue;}ll temp=(v[i]-rest+d-1)/d;ans+=temp*price;rest=temp*d+rest-v[i];}printf("%lld\n",ans);return 0;
}

T3 一元二次方程

一、题目链接

P9750 [CSP-J 2023] 一元二次方程

二、题目大意

如题所示，一个字都别漏，纯纯的模拟题

三、题目分析

• 读完题之后不难发现这就是纯纯的模拟，跟着做就完了

• 做模拟题最关键的问题是，很多时候你不知道它在说什么，你大概率美学过，没看过。但这不重要，你只需要读完全部题目即可，它一定会给足所有信息，只需认真读题。

• 毕竟有时候还有大学知识，而好多参赛者都是小学生。要有耐心和信心。

• 实在理解不了求根公式的话，可以针对题目给你的特殊性质 $C$ 来骗分，代入所有 $[-2000,2000]$ 的整数来判断是否有解，以及求最大的解，这样可以得到 $50$ 分

• 你还需要枚举 $\Delta$ 的平方因子来开方，使得 $\sqrt{\Delta }$ 变得最简，这需要 $O(m)$ 的思想。

• 但是模拟题的问题在于，你很难拿到满分，你有一下问题需要注意

  • 如果出现 $\sqrt{1}$，请让它变成 $1$

  • 如果出现乘法和除法的 $1$ 请将它省略

  • $a$ 可能是负数，所以较大的解不一定是 $\frac{-b+\sqrt{\Delta }}{2a}$，而是 $\frac{-b-\sqrt{\Delta }}{2a}$

  • 根据题目意思，你应该保证分母为正

• 时间复杂度 $O(Tm)$

四、正解程序

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>using namespace std;
typedef long long ll;
ll T,m;
ll gcd(ll a,ll b)
{if(a%b==0)return b;return gcd(b,a%b);
}
int main()
{scanf("%lld%lld",&T,&m);while(T--){ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);ll det=b*b-4*a*c;if(det<0){printf("NO\n");continue;}ll q1=-b,q2=1,q3=2*a;for(ll i=2;i*i<=det;i++)while(det%(i*i)==0)q2*=i,det/=i*i;if(q3<0)q3=-q3,q1=-q1;if(det==1)det=0,q1+=q2;ll gcd1=gcd(abs(q1),q3);ll gcd2=gcd(q2,q3);if(det==0){if(q1%q3==0)printf("%lld",q1/q3);elseprintf("%lld/%lld",q1/gcd1,q3/gcd1);}else{if(q1!=0){if(q1%q3==0)printf("%lld",q1/q3);elseprintf("%lld/%lld",q1/gcd1,q3/gcd1);printf("+");}if(q2/gcd2!=1)printf("%lld*",q2/gcd2);printf("sqrt(%lld)",det);if(q3/gcd2!=1)printf("/%lld",q3/gcd2);}printf("\n");}return 0;
}

T4 旅游巴士

一、题目链接

P9751 [CSP-J 2023] 旅游巴士

二、题目大意

有一张图，图上有 $n$ 个点，$m$ 条边。$1$ 号点为起点，$n$ 号点为终点。每个点有一个时刻 $a_i$，要求不能早于这个时刻通过此点，且不允许在同种任何地方停留。

现要从起点一直走到终点，要求到达终点的时刻一定是 $k$ 的非负整数倍。问最早到终点的时刻是多少，如果不存在这样的方案，输出 $-1$。

数据范围：$2\le n\le 10^4,1\le m\le 2\times 10^4,1\le k\le 100,1\le u_i,v_i\le n,0\le a_i\le 10^6$

三、题目分析

• 完成题目一开始应该去尝试简化题目，将其转化为熟悉且简单的模型。如果不考虑 $a_i$ 和 $k$ 的非负整数倍，那么这将是一个很简单的单源最短路题目
• 根据题目给的特殊数据提示，我们先考虑 $a_i=0$ 的情况
• 对于到达某一个点的两个时刻 $x,k+x(x<k)$ 来说，$k+x$ 一定不如 $x$ 。也就是说，对于$\mathrm{mod}k$ 同余的时刻来说，只需要保留其最短时刻即可。所以我们可以用一个数组 $d_{i,j}$ 来表示到第 $i$ 个点时刻$\mathrm{mod}k=j$ 的最短时间，运行一遍 $BFS$ 最后输出 $d_{n,0}$ 即可。这样就能拿到 $35$ 分了。
• 那么 $a_i\ne 0$ 会造成什么影响呢？其实我们完全可以推迟 $k$ 的非负整数被的出发时间来满足这个要求。比如当前的边需要的时间是 $w$ 大于目前时间 $tim$ ，那么就需要让出发时间延后 $\lceil \frac{w-tim}{k}\rceil \cdot k$ 单位时间。
• 但是这样一来，延后出发时间之后不一定是最短的路径了，可能有其他的最短路径，那么就不能使用 $BFS$ 每个点只更新一次的方式了。因为每个点需要多次更新，可以想到使用 $dijkstra$ 算法来解决这个最短路问题，因为时间复杂度的关系，我们这里需要使用堆优化，利用 set 或者 priority_queue。
• 时间复杂度 $O(nk\log nk)$

四、正解程序

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>using namespace std;
typedef long long ll;
const ll maxn=20010;
struct node
{ll v,w;ll next;
}e[2*maxn];
ll p[maxn],t=0;ll d[maxn][110];
bool vis[maxn][110];void insert(ll u,ll v,ll w)
{e[t].v=v;e[t].w=w;e[t].next=p[u];p[u]=t++;
}
struct New
{ll id,mod,len;bool operator<(const New &x) const{return len>x.len;}
};
int main()
{memset(p,-1,sizeof(p));memset(d,0x3f,sizeof(d));ll n,m,k;scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=m;i++){ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);insert(u,v,w);}priority_queue<New> q;d[1][0]=0;q.push({1,0,d[1][0]});while(!q.empty()){ll u=q.top().id,mod=q.top().mod;q.pop();if(vis[u][mod])continue;vis[u][mod]=true;for(ll i=p[u];i!=-1;i=e[i].next){ll v=e[i].v,w=e[i].w;ll tim=d[u][mod],now=(mod+1)%k;if(tim<w)tim+=(w-tim+k-1)/k*k;if(d[v][now]>tim+1){d[v][now]=tim+1;q.push({v,now,d[v][now]});}}}if(d[n][0]>1e18)d[n][0]=-1;printf("%lld\n",d[n][0]);return 0;
}