姓名：王胤皓，校区：和谐校区，考试时间：$2024$ 年 $10$ 月 $5$ 日 $9:00:00$~$12:30:00$，学号：$S07738$

请关注作者的 B 站，谢谢~链接

CSP-J Day $5$ 模拟赛补题报告

前言

考了我们班 Rank $2$。

分数

T1 milk: $Accepeted100$
T2 traary: $Accepeted100$
T3 usagi: $Wrong\_Answer25$
T4 missiles: $Wrong\_Answer5$

T1

题面

思路

首先排序，然后贪心，累加一下，就行了。

赛时 $Accepeted$ 代码

#include<bits/stdc++.h>
using namespace std;
struct node{int num,money;
}a[200005];
bool cmp(node a,node b){if(a.money==b.money) return a.num>b.num;else return a.money<b.money;
}
int main(){freopen("milk.in","r",stdin);freopen("milk.out","w",stdout);cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int n,m;cin>>n>>m;for(int i=1; i<=n; i++){cin>>a[i].num>>a[i].money;}sort(a+1,a+n+1,cmp);long long ans=0ll;for(int i=1; i<=n; i++){if(m>=a[i].num){m-=a[i].num;ans+=1ll*a[i].num*a[i].money;}else{ans+=1ll*m*a[i].money;break;}}cout<<ans<<"\n";return 0;
}

T2

题面

思路

我的思路

• 如果 $op=1$，那么进行以下操作：
  • 如果上一次已经结束了，那么计数器数组 $nu{m}_x$ 加上 $k$。
  • 如果没有结束，那么计数器数组 $nu{m}_x$ 加上 $day-l_x$
  • 然后重新赋值 $l_x=day,r_x=day+k$。
• 如果 $op=2$：
  • 如果上一次魔法已经结束了，那么 $nu{m}_x$ 加上 $k$。
  • 如果没有结束，那么计数器数组 $nu{m}_x$ 加上 $day-l_x$
  • 重新赋值为一个特大值。
• 如果 $op=3$:
  • 如果上一次魔法已经结束了，那么 $nu{m}_x$ 加上 $k$。
  • 如果没有结束，那么答案加上 $day-l_x$
  • 输出 $day+nu{m}_k+ans$

代码

#include<bits/stdc++.h>
using namespace std;
int l[100005],r[100005],num[100005];
int main(){freopen("traary.in","r",stdin);freopen("traary.out","w",stdout);int n,m,k;cin>>n>>m>>k;memset(l,0x3f3f3f3f,sizeof l);memset(r,0x3f3f3f3f,sizeof r);int day=1;while(m--){int op,x;cin>>op>>x;if(op==1){if(day>=r[x]){num[x]+=(r[x]-l[x]);}else if(r[x]!=0x3f3f3f3f){num[x]+=(day-l[x]);}l[x]=day;r[x]=day+k;}else if(op==2){if(day>r[x]){num[x]+=(r[x]-l[x]);}else if(day<=r[x]&&r[x]!=0x3f3f3f3f){num[x]+=(day-l[x]);}r[x]=l[x]=0x3f3f3f3f;	}else{int ans=day-1;ans+=num[x];if(day<=r[x]&&r[x]!=0x3f3f3f3f){ans+=(day-l[x]);}else if(day>r[x]){ans+=(r[x]-l[x]);num[x]+=(r[x]-l[x]);l[x]=r[x]=0x3f3f3f3f;}else{l[x]=r[x]=0x3f3f3f3f;}cout<<ans<<"\n";}day++;}return 0;
}

T3

题面

思路

二维费用滚动数组优化的01背包，和我一开始的做法一样，写成了完全背包。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10005];
int b[10005];
int n,H;
int dp[2][100005][9]={0}; 
int f[2][7];
int maxx=0;
signed main(){cin>>n>>H;int sumB=0;for(int i=1; i<=n; i++){cin>>a[i];}for(int i=1; i<=n; i++){cin>>b[i];sumB+=b[i];}if(H>=sumB){memset(f,-0x3f,sizeof f);f[0][0]=0;for(int i=1; i<=n; i++){int t=i&1;for(int j=0;j<7;j++){f[t][j]=max(f[t^1][j],f[t^1][(((j-a[i])%7)+7)%7]+a[i]);}}cout<<f[n&1][0]<<'\n';return 0;}memset(dp,-0x3f,sizeof dp);dp[0][0][0]=0;for(int i=1; i<=n; i++){int t=i&1;for(int j=0;j<=H; j++){for(int k=0; k<7; k++){if(j<b[i]) dp[t][j][k]=dp[t^1][j][k];else dp[t][j][k]=max(dp[t^1][j][k],dp[t^1][j-b[i]][(((k-a[i])%7)+7)%7]+a[i]);}}}for(int i=0;i<=H; i++) maxx=max(maxx,dp[n&1][i][0]);cout<<maxx<<'\n';return 0;
}

T4

题面

思路

两次 BFS，然后最后统计一下，就完了。

注意：从终点开始搜索！

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=1e5+5;
#define ll long long;
struct node{int to,nxt;
}edge[N<<2];
int n,m,cnt=1,head[N],hd=1,tail,q[N],dis[N],pre[N],tot[N],ans[N];
void add(int u,int v){edge[cnt].to=v;edge[cnt].nxt=head[u];head[u]=cnt++;
}
void bfs(){memset(dis,-1,sizeof dis);dis[n]=0;q[++tail]=n;while(hd<=tail){int u=q[hd++];for(int i=head[u]; i;i=edge[i].nxt){int v=edge[i].to;if(dis[v]==-1){dis[v]=dis[u]+1;pre[v]=u;q[++tail]=v;}}}
}
int main(){cin>>n>>m;while(m--){int u,v;cin>>u>>v;add(u,v);add(v,u);}bfs();tot[n]=1;for(int i=1; i<=tail;i++){int u=q[i],flag=0;for(int j=head[u];j;j=edge[j].nxt){int v=edge[j].to;if(dis[u]==dis[v]+1){ans[u]=max(ans[u],ans[v]);(tot[u]+=tot[v])%=mod;if(v!=pre[u]) flag=1;}}ans[u]+=flag;}cout<<tot[1]<<" "<<ans[1]<<"\n";return 0;
}

请关注作者的 B 站，谢谢~链接