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

姓名：王胤皓，校区：和谐校区，考试时间：$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 站，谢谢~链接

原文地址：https://blog.csdn.net/ainiyoung/article/details/142691651

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！