[CSP-J 2023] 小苹果
模拟分组,第n个什么时候取到,就是什么时候处在分组第一个
#include<bits/stdc++.h> using namespace std; int n,ans,k; int main(){ cin>>n; while(n){ ans++; if(k==0&&n%3==1)k=ans; if(n%3==0)n-=n/3; else n-=n/3+1; } cout<<ans<<" "<<k; return 0; }
[CSP-J 2023] 公路
贪心策略,每次在下一个更便宜的加油站加油,而且在那之前尽量把油耗光
用一个数组记录下依次要去的加油站,还有要记录的是开了这段路后还可以开剩下的距离
#include <bits/stdc++.h> typedef long long LL; using namespace std; const int maxn=1e5+10; LL n,d; LL dis[maxn],c[maxn],nex[maxn],di[maxn]; int main() { LL ans=0; scanf("%lld %lld",&n,&d); for(int i=1;i<n;i++){ scanf("%lld",&dis[i]); } for(int i=2;i<=n;i++){ di[i]=di[i-1]+dis[i-1]; } for(int i=1;i<=n;i++){ scanf("%lld",&c[i]); } //贪心策略:查找每一个依次去的加油站次序 int last_po=1; int last_mon=c[1]; for(int i=2;i<n;i++){ if(c[i]<last_mon){ nex[last_po]=i; last_po=i; last_mon=c[i]; } } nex[last_po]=n; //最后去的加油站 LL dist=0; LL can_d=0; //剩下的能开的距离 for(int i=1;i<n;){ dist=di[nex[i]]-di[i]; //距离 ans+=(dist-can_d+d-1)/d*c[i]; //注意向上取整 can_d+=(dist-can_d+d-1)/d*d; can_d-=dist; i=nex[i]; //向后走 } printf("%lld\n",ans); return 0; }
[CSP-J 2023] 一元二次方程
完全是模拟,注意细节就可以,比如0,1
#include<bits/stdc++.h> using namespace std; int T,m,a,b,c,d,k,t; int gcd(int a,int b){ return b? gcd(b,a%b):a; } void js(){ cin>>a>>b>>c; if(a<0){ a=-a;b=-b;c=-c; //分母不为负数 } d=b*b-4*a*c; k=1; if(d<0){ cout<<"NO"<<endl;return; } for(int i=2;i*i<=d;i++){ while(d%(i*i)==0){ //是while k*=i; d/=(i*i); } } if(d==0||d==1){ //有理数 t=abs(gcd(2*a,-b+k*d)); cout<<(-b+k*d)/t; if(2*a/t!=1) cout<<"/"<<2*a/t; cout<<endl; return; } //-b/2a+k*sqrt(d)/2a t=abs(gcd(2*a,-b)); if(-b/t!=0){ cout<<-b/t; if(2*a/t!=1) cout<<"/"<<2*a/t; cout<<"+"; } t=abs(gcd(k,2*a)); if(k/t!=1) cout<<k/t<<"*"; cout<<"sqrt("<<d<<")"; if(2*a/t!=1) cout<<"/"<<2*a/t; cout<<endl; return; } int main() { cin>>T>>m; while(T--){ js(); } return 0; }
[CSP-J 2023] 旅游巴士
分层图计算,类似dijkstra
#include<bits/stdc++.h> #include<vector> using namespace std; typedef long long LL; const int maxn=2e4+10; LL n,m,k; LL dis[maxn][110];//到达i的时间modk的值为j的最短时间 bool vis[maxn][110]; vector<pair<LL,LL> > e[maxn]; priority_queue<pair<LL,LL>,vector<pair<LL,LL> >,greater<pair<LL,LL> > > q; void adde(LL u,LL v,LL w){ e[u].push_back({v,w}); } void dijkstra(LL s){ dis[s][0]=0; q.push({0,s}); //第一个点是距离,第二点是到达的地方 while(!q.empty()){ LL u=q.top().second; LL p=q.top().first; q.pop(); if(vis[u][p%k]) continue; vis[u][p%k]=1; for(int i=0;i<e[u].size();i++){ LL v=e[u][i].first,w=e[u][i].second,t=(p+1)%k; if(p>=w){ t=p; } else t=((w-p+k-1)/k)*k+p; //向上取整 if(dis[v][(t+1)%k]>t+1){ dis[v][(t+1)%k]=t+1; q.push({t+1,v}); } } } } int main() { memset(dis,0x3f,sizeof(dis)); cin>>n>>m>>k; LL u,v,w; for(int i=0;i<m;i++){ cin>>u>>v>>w; adde(u,v,w); } dijkstra(1); if(!vis[n][0]) cout<<"-1"; else cout<<dis[n][0]<<endl; return 0; }