CSP-J 2023 题解
__graphite__ · · 题解
T1
这么水？！
赛时AC。
思路：小学数学题，我孙子都会做
认真点。
就是余数和商，小学二年级的知识（毕导：亻尔女子）
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,sum;
LL t(LL a)
{
if(a!=1)return 1+t(a-((a-1)/3+1));
else return 1;
}
int main()
{
scanf("%lld",&n);
printf("%lld ",t(n));
while((n-1)%3!=0)
{
sum++;
n-=(n-1)/3+1;
}
printf("%lld",sum+1);
return 0;
}T2
贪心。
赛时打挂了，15分。
正解：每次当跑不到下一个站点的时候就“跑回”目前遇到的最便宜的站点加油。
错因：看代码：
#include<stdio.h>
#include<bits/stdc++.h>
#define N 100010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void write(i128 x)
{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
LL n,d,v[N],a[N],lama=INF,dis,sum;
int main()
{
cin>>n>>d;
rep(i,1,n-1,1)cin>>v[i];
rep(i,1,n,1)cin>>a[i];
rep(i,1,n-1,1)
{
if(lama>a[i])
{
lama=a[i];
}
if(dis<v[i])
{
LL t=v[i]-dis;
t=(t/d)+((t%d)>0);
sum+=t*lama;
dis+=t*d;
}
dis-=v[i];//这里，我赛时放在if里面了...
}
cout<<sum<<endl;
return 0;
}T3
还真是大模拟？！小周老师是不是偷题了？！
就按照题目说的做啊。
没有任何思维难度。
哦有个坑就是正负号的问题。
赛时60分。
错因：见代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL t,m,a,b,c,CGfz,CGfm,f;
LL CGfz1,CGfz2,CGfm1,CGfm2;
double CG1,CG2;
int pf[10004200];
void init()
{
for(int i=0;i<=3030;i++)pf[i*i]=i;//这里，2000不够啊
}
LL CGd(LL a,LL b)
{
if(b==0)return a;
return CGd(b,a%b);
}
int main()
{
init();
scanf("%lld%lld",&t,&m);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&c);
LL s=b*b-4*a*c;
if(s<0)
{
printf("NO\n");
continue;
}
if(s==0)
{
CGfz=-b;
CGfm=2*a;
f=CGd(CGfz,CGfm);
CGfz/=f;
CGfm/=f;
if(CGfm<0&&CGfz>0)
{
CGfm=-CGfm;
CGfz=-CGfz;
}
if(CGfm==1)
{
printf("%lld\n",CGfz);
}
else
{
printf("%lld/%lld\n",CGfz,CGfm);
}
continue;
}
if(pf[s])
{
CGfz1=-b-pf[s];
CGfz2=-b+pf[s];
CGfm1=2*a;
CGfm2=2*a;
f=CGd(CGfz1,CGfm1);
CGfz1/=f;
CGfm1/=f;
if(CGfm1<0&&CGfz1>0)
{
CGfm1=-CGfm1;
CGfz1=-CGfz1;
}
f=CGd(CGfz2,CGfm2);
CGfz2/=f;
CGfm2/=f;
if(CGfm2<0&&CGfz2>0)
{
CGfm2=-CGfm2;
CGfz2=-CGfz2;
}
CG1=CGfz1*1.0/CGfm1;
CG2=CGfz2*1.0/CGfm2;
if(CG1>CG2)CGfm=CGfm1,CGfz=CGfz1;
else CGfm=CGfm2,CGfz=CGfz2;
if(CGfm==1)
{
printf("%lld\n",CGfz);
}
else
{
printf("%lld/%lld\n",CGfz,CGfm);
}
continue;
}
if(b!=0)
{
CGfz=-b;
CGfm=2*a;
f=CGd(CGfz,CGfm);
CGfz/=f;
CGfm/=f;
if(CGfm<0&&CGfz>0)
{
CGfm=-CGfm;
CGfz=-CGfz;
}
if(CGfm==1)
{
printf("%lld+",CGfz);
}
else
{
printf("%lld/%lld+",CGfz,CGfm);
}
}
CGfz=1;
CGfm=2*a;
for(int i=2;i<=3030;i++)
{
while(s%(i*i)==0)
{
s/=(i*i);
CGfz*=i;
}
}
f=CGd(CGfz,CGfm);
CGfz/=f;
CGfm/=f;
if(CGfz==CGfm)
{
printf("sqrt(%lld)\n",s);
continue;
}
if(CGfz%CGfm==0)
{
CGfz=labs(CGfz/CGfm);
if(CGfz==1)printf("sqrt(%lld)\n",s);
else printf("%lld*sqrt(%lld)\n",CGfz,s);
continue;
}
if(CGfz==1)
{
CGfm=labs(CGfm);
printf("sqrt(%lld)/%lld\n",s,CGfm);
continue;
}
printf("%lld*sqrt(%lld)/%lld\n",labs(CGfz),s,labs(CGfm));
}
return 0;
}T4
赛时没正解，骗了10分。
由于作者懒放个同学写的题解链接
代码：
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void write(i128 x)
{
if(x>=10)write(x/10);
putchar(x%10+'0');
}
LL n,m,k,dis[10010][110];
bool f[10010][110];
vector<pll >e[10010];
priority_queue<pll,vector<pll >,greater<pll > >q;//赛时这里是普通queue，然后TLE力
void add(LL u,LL v,LL w)
{
e[u].push_back({v,w});
}
void dij(LL s)
{
dis[s][0]=0;
q.push({0,s});
while(!q.empty())
{
LL u=q.top().second,p=q.top().first;
q.pop();
if(f[u][p%k])continue;
f[u][p%k]=1;
for(auto d:e[u])
{
LL v=d.first,w=d.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;
rep(i,1,m,1)
{
LL u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
dij(1);
if(!f[n][0])cout<<-1<<endl;
else cout<<dis[n][0]<<endl;
return 0;
}闲话：TB认为用queue能AC但我TLE10分了，傻逼TB。