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

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

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

前言

考了我们班 Rank $3$。

分数

T1 ip: $Accepeted100$
T2 same: $Accepeted100$
T3 box: $Wrong\_answer10$
T4 party: $Wrong\_answer20$

T1

题面

思路

开一个映射数组，下标存的是 ip 地址，内容存的是名称，然后每次询问，直接输出下标所对应的名称，就可以了。

赛时 $Accepeted$ 代码

#include<bits/stdc++.h>
using namespace std;
map<string,string> m;
int main(){freopen("ip.in","r",stdin);freopen("ip.out","w",stdout);int n;cin>>n;while(n--){string a,b;cin>>a>>b;m[b]=a;}int q;cin>>q;while(q--){string c;cin>>c;cout<<m[c]<<"\n";}return 0;
}

T2

题面

思路

利用双指针找到两个个长度都为 $k$ 的不相等的区间，然后双指针后，$k$ 就是 $l$ 减 $1$，然后按照题目描述模拟，然后逐次判断，最后输出。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005];
int main(){freopen("same.in","r",stdin);freopen("same.out","w",stdout);cin.tie(0);ios::sync_with_stdio(false);int t;cin>>t;while(t--){int n;cin>>n;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=n; i++) cin>>b[i];int l=1,r=n;while(l<r){if(a[l]!=b[l]&&a[r]!=b[r]){l++,r--;}else{break;}}l--;for(int i=1,j=n-l+1; i<=l; i++,j++){swap(a[i],a[j]);} bool flag=0;for(int i=1; i<=n; i++){if(a[i]!=b[i]){flag=1;break;}}if(flag==1) cout<<"No\n";else cout<<"Yes\n";}return 0;
}

T3

题面

思路

错误思路

按照合并果子的策略，每次合并 $m$ 个，最终不够 $m$ 个，直接都合起来。

用优先队列实现小顶堆。

正确思路

按照合并果子的策略，每次合并 $m$ 个，最终不够 $m$ 个，添上不够的数量个 $0$，然后再重新执行一遍。

用优先队列实现小顶堆。

代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<long long,vector<long long>,greater<long long> > pq,pqq;
int main(){int n,m;cin>>n>>m;long long w;for(int i=1; i<=n; i++){cin>>w;pq.push(w*1ll);pqq.push(w*1ll);}int flag=0;long long cnt=0ll;while(pq.size()>1){long long sum=0ll;int len=pq.size();for(int i=1; i<=min(m,len); i++){sum+=pq.top();pq.pop();}for(int i=len+1; i<=m; i++){flag++;}pq.push(sum);}for(int i=1; i<=flag; i++){pqq.push(0);} while(pqq.size()>1){long long sum=0ll;int len=pqq.size();for(int i=1; i<=m; i++){sum+=pqq.top();pqq.pop();}pqq.push(sum);cnt+=sum;}cout<<cnt<<"\n";return 0;
}

T4

题面

思路

dfs+分组背包，就没了（唐题）

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=514;
int n,m,cnt,a[N][N],sz[N][2],col[N];
bool f[N],vis[N];
bool dfs(int u,int c){vis[u]=1;col[u]=c;sz[cnt][c]++;for(int i=1; i<=n; i++){if(i!=u&&(!a[i][u]||!a[u][i])){if(vis[i]){if(col[u]==col[i]) return false;}else if(!dfs(i,1-c)) return false;}}return true;
}
int main(){scanf("%d",&n);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){cin>>a[i][j];}}for(int i=1; i<=n; i++){if(!vis[i]){cnt++;if(!dfs(i,0)){cout<<"No\n";return 0;}}}m=n>>1;f[0]=1;for(int i=1; i<=cnt; i++){for(int j=m;j;j--){if(j<sz[i][0]&&j<sz[i][1]) break;if(j>=sz[i][0]) f[j]|=f[j-sz[i][0]];if(j>=sz[i][1]) f[j]|=f[j-sz[i][1]];}}for(int j=m; j>=1; j--){if(f[j]){cout<<"Yes\n"<<n-j;return 0;}}return 0;
}

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