您的位置:首页 > 科技 > 能源 > CSP-J模拟赛day3——解析+答案

CSP-J模拟赛day3——解析+答案

2024/12/23 11:14:28 来源:https://blog.csdn.net/CylMK/article/details/140694503  浏览:    关键词:CSP-J模拟赛day3——解析+答案

小人快跑

思路

按照题意,贪心即可。需要注意的是,这道题目需要开long long。

Code

#include<bits/stdc++.h>
using namespace std;int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);long long n,t;cin>>n>>t;for (int i=1;i<=n;i++){int tmp;cin>>tmp;char a;long long b,num=INT_MIN;for (int j=1;j<=tmp;j++){cin>>a>>b;if (a=='+')num=max(num,t+b);else if (a=='-')num=max(num,t-b);else if (a=='*')num=max(num,t*b);else if (a=='%')num=max(num,t%b);else num=max(num,t/b);}t=num;if (t<=0){cout<<0;return 0;}}cout<<t;return 0;
}

开根号

思路

按照题意模拟即可。需要注意的是,这道题目需要开long long。

同时,在最后,需要一个gcd函数,得到最简假分数。

Code

#include<bits/stdc++.h>
using namespace std;int main(){long long x,n;cin>>x>>n;long long tmp=ceil(sqrt(x));long long t1,t2=1;for (int i=1;i<=n;i++){t1=tmp*tmp+t2*t2*x;t2=2*tmp*t2;tmp=t1;}long long q=0;if (t1>=t2)q=__gcd(t1,t2);else q=__gcd(t2,t1);if (t2/q==1)cout<<t1/q;else cout<<t2/q<<" "<<t1/q;return 0;
}

奶茶

思路

考虑结论:对于节点i,其子节点中有t个一定直接或者间接走到叶子节点,这个节点能够走到叶子节点的充分必要条件是 t > a i t>a_i t>ai.

然后就是朴实无华的递推过程了。

Code

#include<bits/stdc++.h>
#define int long longusing namespace std;int n,m,q;int a[1000005];int head[1000005],cnt;int naicha[1000005];//判断这个点是否有奶茶店 struct A{int to,nxt;
}ed[1000005];void add(int x,int y){ed[++cnt].to=y;ed[cnt].nxt=head[x];//更新 head 数组,使得 head[x] 指向最新添加的边的索引 cnt。 head[x]=cnt;
}int chudu[1000005];int loq[10005];int dfs(int u){if(naicha[u])return naicha[u];for(int i=head[u];i;i=ed[i].nxt){int x=ed[i].to;naicha[u]+=(dfs(x)?1:0);//dfs求解 }naicha[u]-=a[u];//删除拥堵路段 return naicha[u]=(naicha[u]>=1?1:0);//判断是否还有剩余 
}signed main(){cin>>n>>q;for(int i=1;i<=n;++i){cin>>a[i];//拥堵方式 }for(int i=2;i<=n;++i){int x,y;cin>>x>>y;add(x,y);chudu[x]++;//出度加1 }for(int i=1;i<=n;++i){if(chudu[i]==0)naicha[i]=1;//判断当前这个点是否有奶茶店 }for(int i=1;i<=q;++i){cin>>loq[i];}dfs(1);for(int i=1;i<=q;++i){if(naicha[loq[i]]==1)cout<<"YES"<<endl;//根据有没有奶茶店来判断 else cout<<"NO"<<endl;}return 0;
}

密码锁

思路

数据点1-2满足, n = 1 n = 1 n=1

送分,简单判断差的绝对值就好了。

数据点3-4满足, n = 2 n = 2 n=2

尝试加减1,10,11来得到正确答案,3重循环能过

数据点5-6满足, n = 4 n = 4 n=4

尝试加减1,10,100,1000,11,110,1100来得到正确答案,7重循环能过

数据点7-8满足, n = 6 n = 6 n=6

开1e6数组记录,类似最短路的算法或者记忆化搜索能过,但是对常数要求比较大

数据点9-12满足, 1 ≤ n ≤ 1000 1 \le n \le 1000 1n1000

允许一些 n 2 n^2 n2的DP通过,比如一些区间DP。做法有很多,但是会比较复杂。

数据点13-20满足, 1 ≤ n ≤ 1 × 1 0 5 1 \le n \le 1\times 10^5 1n1×105

考虑动态规划:dp[i][j]表示,从初始状态,到达“当前从左往右前 i-1 位都已经恢复,并且第 i 位目前是为 j ”这一状态的最小次数 (要求,状态转移时只拨第 i 位与 i-1 位,或者只拨动第 i 位)

时间复杂度是O(n)的,带有100的常数。

Code

#include<bits/stdc++.h>
#define int long longusing namespace std;const int N=1000000+5;int n;
char s[N];
int a[N], b[N];
int dp[N][10];signed main(){cin>>n;scanf("%s",s+1);for(int i=1;i<=n;++i)a[i]=s[i]-'0';scanf("%s",s+1);for(int i=1;i<=n;++i)b[i]=s[i]-'0';memset(dp,0x3f,sizeof(dp));for(int i=0;i<=9;++i)dp[1][i]=min((i-b[1]+10)%10,(b[1]-i+10)%10);for(int i=2;i<=n;++i)for(int j=0;j<=9;++j)for(int k=0,c,t;k<=9;++k){c=(a[i-1]-k+10)%10,t=(b[i]+c)%10;dp[i][j]=min(dp[i][j],dp[i-1][k]+c+min((j-t+10)%10,(t-j+10)%10));c=(k-a[i-1]+10)%10,t=(b[i]-c+10)%10;dp[i][j]=min(dp[i][j],dp[i-1][k]+c+min((j-t+10)%10,(t-j+10)%10));}printf("%lld",dp[n][a[n]]);return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com