CSP-J第二轮2019~2023全题解
2024-08-25 21:57:49
发布于：江苏
持续施工中，本人蒟蒻，写错了喷轻点
马上CSP考试了，连夜写了一下第二轮2019-2023的全部题解,希望对大家有所帮助，如若代码有误，请指出
AC君能顶一下吗（如果写的好的话）
题解均自己编写，没有复制题解 （dalao的题解看不懂）
CSP-J2019:
2019第一题 数字游戏
2019年第一题真水啊，但是根据著名的难度守恒定律，后面肯定难
循环一下字符串，计数一下有多少个1就行了
#include <bits/stdc++.h>
using namespace std;
int main(){
int sum=0;
for(int i=1;i<=8;i++){
char a = getchar();
if(a=='1') sum++;
}
cout<<sum;
return 0;
}
2019第二题 公交换乘
一道模拟题，看完题目之后思路是比较清晰的：
如果是要坐地铁，那么花钱直接坐（因为也没有关于地铁的优惠），得到的优惠票放到一个vector数组里保存
如果是要坐公交车，那么先遍历一下vector，看一下有没有能用的优惠票（公交车钱小于地铁钱，时间小于45分钟，没被用过），能用就用，没有能用的只能花钱。
#include <bits/stdc++.h>
using namespace std;
int n;
struct node{
int price,t,use;
};
vector<node> que;//地铁优惠券
int id;
long long sum;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x==0){
int x,y;
cin>>x>>y;
sum+=x;
que.push_back((node){x,y,0});
}else{
int x,y;
cin>>x>>y;
bool flag=0;
for(int i=id;i<que.size();i++){
if(y-que[i].t<=45){
if(x<=que[i].price&&que[i].use==0){
que[i].use=1;
flag=1;
break;
}
}else id++;//把票扔了
}
if(!flag) sum+=x;
}
}
cout<<sum;
return 0;
}
2019第三题 纪念品
一道神仙背包dp题，刚开始看到题目蒙了，难度在这里上去了
题目中说了，交易可以无限次，很明显是一道完全背包题目。
但是与完全背包不同的是，他可以当日买来又可以当日卖出。当然，买来的目的是为了找一个未来一天高价卖出，赚取利润。
所以设中我现在拥有的钱数 相当于 我的背包容量
我今天买来的纪念品消耗的钱 相当于 我的背包重量
我未来某一天把纪念品卖出去，赚取利润 相当于 我的背包价值
于是又回到了一道完全背包题目。
循环k天，每天使用完全背包看看今天能净赚多少钱，加到总钱数。最后输出总钱数就行了。
小细节：每次第i天结束后要把你的dp数组清空
#include <bits/stdc++.h>
using namespace std;
int t,n,m;//天数，数量，钱数
int dp[10005],a[1005][1005];
int main(){
cin>>t>>n>>m;
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
int sum=0;
for(int k=1;k<t;k++){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
for(int j=a[k][i];j<=m;j++){//完全背包正着遍历
dp[j]=max(dp[j],dp[j-a[k][i]]+a[k+1][i]-a[k][i]);
}
}
m+=dp[m];
}
cout<<m;
return 0;
}
2019第四题 加工零件
一道最短路。感觉比上一题简单
第一眼，使用递归直接解决
结果，再看一眼，就会爆炸：这么大的数据直接爆掉
于是思考这样一个问题：
7要做5阶段的零件1要不要做？其实就是问7到1有没有长度为5的路径?
8做6阶段的零件1要不要做？其实就是8到1有没有长度为6的路径？
那么怎么求路径呢？又要dfs？
想一想，如果7到1有路径，那么9到1也绝对有，但是8到1就不一定有。因为一个点到1有长度为6的路径，则在来回走两步，这个点到1一定有长度为8的路径（点可以来回走），在来回走两步，有一定有长度为10的路径。
那么，不需要求路径，求这个点到1的奇偶最短路即可，如果最短路小于要求的路径并且奇偶性相同，则可以到达。
小彩蛋：dijkstra不用优先队列也能过
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,m,q,dist[100005],dist2[100005];//dist记录奇数最短路，dist2记录偶数
vector<int> a[100005];
void dfs(){
memset(dist,0x3f,sizeof(dist));
memset(dist2,0x3f,sizeof(dist2));
queue<pii> que;
for(int i=0;i<a[1].size();i++){
dist[a[1][i]]=1;
que.push(make_pair(a[1][i],1));
}
while(que.size()){
auto f=que.front();
que.pop();
for(int i=0;i<a[f.first].size();i++){
if(f.second%2==0){//当前是偶数，则后面是奇数
if(f.second+1<dist[a[f.first][i]]){
dist[a[f.first][i]]=f.second+1;
que.push(make_pair(a[f.first][i],dist[a[f.first][i]]));
}
}else{//同理
if(f.second+1<dist2[a[f.first][i]]){
dist2[a[f.first][i]]=f.second+1;
que.push(make_pair(a[f.first][i],dist2[a[f.first][i]]));
}
}
}
}
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
dfs();
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
if(y%2==1){
if(dist[x]<=y) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}else{
if(dist2[x]<=y) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
CSP-J2020
2020第一题 优秀的拆分
第一眼看上去就感觉像二进制。
但其实不用那么复杂。
来看样例：，上面的一出现了，这是不符合的。，1也出现了，这也是不符合的。
也就是说如果输入的数是奇数，则不符合，直接退出。否则一直减去当前数能减得最大的2正整数次幂。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main(){
cin>>n;
if(n%2!=0){
cout<<-1;
return 0;
}
while(n){
int i=1;
while(true){
if(pow(2,i+1)>n) break;
i++;
}
n-=pow(2,i);
cout<<(int)pow(2,i)<<" ";
}
return 0;
}
2020第二题 直播获奖
也是一道水题。完了啊后面要很难！
如果每次输入一个人的成绩之后就要sort一下会爆炸。
那么可以从选手的成绩入手（数据非常小），使用桶排记录每个数的出现次数，然后从大到小遍历，加上次数，直到大于入围人数即可输出。
#include <bits/stdc++.h>
using namespace std;
int n,bucket[605],k;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
int x;
cin>>x;
bucket[x]++;
int sum=0;
for(int j=600;j>=0;j--){
if(bucket[j]!=0){
sum+=bucket[j];
if(sum>=max(1,i*k/100)){
cout<<j<<" ";
break;
}
}
}
}
return 0;
}
2020第三题 表达式
这道题我真的要疯了啊啊啊啊啊啊啊啊啊啊啊 神经题目硬控我一坤小时！！！！！！
这是一道关于后缀表达式&位运算的超级模拟题目。
处理：一说到后缀表达式，肯定就会像到树。（也就是连通图）由于他没有直接给我们数字，而是用字符代替，导致用树存比较方便。
重点：那么问题来了——每次询问给出取反一个数字，求答案。如果每次询问都再求一遍后缀表达式的值，复杂度上天了。
我们来想：题目给我们的是位运算，位运算必然有一个特性：短路。比如$1 | x = 1，无论x怎么取反，都与x无关。同理，无论x怎么取反，都与x无关。同样如此(负负得正)
那么，可以用求后缀树后，再用求树上的节点 变换后会不会影响结果 的标记。这样再问询q次，就能以的复杂度判断此节点取反有没有影响。
干讲估计听不懂，更多的见代码注释。
彩蛋1：码量长度第一次突破110...
彩蛋2：数组长度是字符串s的长度哦~
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
int n,m;
string s;
int w[1000005],a[1000005][2],q;//w是边权，a是邻接矩阵连边
char fuhao[1000005];//此节点是否为符号，是则标记
bool flag[1000005];//改变此节点结果是否改变
stack<int> que;
int dfs1(int x){//后缀表达式求值
if(!fuhao[x]) return w[x];//不是符号是值（也就是叶子节点）就返回
if(fuhao[x]=='!'){//取反运算
w[x]=!dfs1(a[x][0]);
}else{
int u=a[x][0],v=a[x][1];//左子右子节点
//运算
if(fuhao[x]=='&'){
w[x]=dfs1(u) & dfs1(v);
}else{
w[x]=dfs1(u) | dfs1(v);
}
}
return w[x];
}
void dfs2(int x){//标记出大问题的点
flag[x]=1;//当前点改变了会有大问题
if(!fuhao[x]) return;//不是符号（叶子节点）就停
if(fuhao[x]=='!'){
dfs2(a[x][0]);//取反号会有问题
}else{
int u=a[x][0],v=a[x][1];
if(fuhao[x]=='&'){
if(w[u]==1){//看v的表现
dfs2(v);
}
if(w[v]==1){
dfs2(u);//看u的表现
}
}else{
//同理
if(w[u]==0){
dfs2(v);
}
if(w[v]==0){
dfs2(u);
}
}
}
}
int main(){
getline(cin,s);
cin>>n;
m=n;//边初始值为n个节点
for(int i=1;i<=n;i++){
cin>>w[i];//每个节点的边权
}
for(int i=0;s[i];i+=2){
if(s[i]=='x'){//求这个节点的编号
int x=0;
i++;
while(s[i]!=' '){
x=x*10+s[i]-'0';
i++;
}
i--;
que.push(x);//把编号放进栈里面
}else if(s[i]=='&'){
int x=que.top();
que.pop();
int y=que.top();
que.pop();
//连边
m++;
a[m][0]=x;
a[m][1]=y;
//放入栈中
que.push(m);
fuhao[m]='&';
}else if(s[i]=='|'){
int x=que.top();
que.pop();
int y=que.top();
que.pop();
//依然连边
m++;
a[m][0]=x;
a[m][1]=y;
que.push(m);
fuhao[m]='|';
}else{
//同上
m++;
fuhao[m]='!';
int x=que.top();
que.pop();
a[m][0]=x;
que.push(m);
}
}
int sum=dfs1(m);//求值
dfs2(m);//收集当前编号改变有没有大问题
cin>>q;
for(int i=1;i<=q;i++){
int x;
cin>>x;
if(flag[x]){//如果有大问题
cout<< (sum^1) <<endl;//取反
}else{
cout<<sum<<endl;
}
}
return 0;
}
持续施工中，欢迎催更~
有帮助，赞一个