宁波工程学院2020新生校赛（重现赛）（A,B,C,D,E 二进制优化多重背包 ,F 模拟,G bfs,H 模拟, I 双向dij 方案数 J, K 思维 L 并查集）

2024-01-04 18:59
文章标签 2020 优化 模拟 bfs 思维 双向 背包 二进制 查集 方案 多重 校赛 宁波 新生 重现 工程学院 dij

本文主要是介绍宁波工程学院2020新生校赛（重现赛）（A,B,C,D,E 二进制优化多重背包 ,F 模拟,G bfs,H 模拟, I 双向dij 方案数 J, K 思维 L 并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

战绩：

 

A-恭喜小梁成为了宝可梦训练家~

签到题

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e2+10;
int a[N],n;
int main()
{int _=read();while(_--){n=read();int mx,mi;double sum=0;rep(i,1,n){a[i]=read();}mx=mi=a[1];rep(i,1,n){mx=max(mx,a[i]);mi=min(mi,a[i]);sum+=a[i];}printf("MAX:%d\n",mx);printf("MIN:%d\n",mi);printf("AVG:%.2f\n",sum/n);}
}

B-皮(A)卡(C)皮(M)~

签到题

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e2+10;
int a[N],n;
int main()
{int _=read();while(_--){string s;cin>>s;int vis[26];memset(vis,0,sizeof(vis));for(int i=0;i<s.size();++i){vis[s[i]-'A']++;}if(vis['A'-'A']==0) puts("A");else if(vis['C'-'A']==0) puts("C");else if(vis['M'-'A']==0) puts("M");else puts("-1");}
}

C-杰尼杰尼

做法:n比较小  n^2枚举 计算交点，map去重即可。

#include <bits/stdc++.h>using namespace std;#define ll long long
ll input(){ll x=0,f=0;char ch=getchar();while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return f? -x:x;
}#define PII pair <double,double>
#define fr first
#define sc second
#define mp make_pairmap <PII,int> p;
double k[107],b[107];int main(){int n=input();for(int i=1;i<=n;i++) k[i]=input(),b[i]=input();for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(k[i]==k[j]) continue;double x=(b[j]-b[i])/(k[i]-k[j]);double y=k[i]*x+b[i];//printf("%f %f\n",x,y);p[mp(x,y)]=1;}}if(p.size()==0) printf("No Fire Point.\n");else printf("%d\n",p.size());
}
/*
2
1 2
1 1
*/

D-古代遗迹：字符王国

做法：统计S串前缀各个字符的个数即可。然后枚举t串长度的区间，判断区间内 各个字符 不同的数量数是否在1以内，且只有两个字符数量不同，或者字符数量都相同也是对答案产生了贡献

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=2e5+10;
char s[N],t[N];
int vs[30],vis[N][26],tmp[26];
int main()
{int _=read();while(_--){scanf("%s%s",s+1,t+1);int ls=strlen(s+1);int lt=strlen(t+1);for(int i=0;i<=ls;++i){for(int j=0;j<26;++j) vis[i][j]=vs[j]=0;}for(int i=1;i<=lt;++i) vs[t[i]-'a']++;for(int i=1;i<=ls;++i){for(int j=0;j<26;++j) vis[i][j]=vis[i-1][j];vis[i][s[i]-'a']++;}int ans=0;for(int i=1;i+lt-1<=ls;++i){int l=i,r=i+lt-1;for(int j=0;j<26;++j) tmp[j]=vis[r][j]-vis[l-1][j];int s1=0,s2=0,flag=1;for(int j=0;j<26&&flag;++j){if(tmp[j]>vs[j]){if(tmp[j]-vs[j]>1) flag=0;else s1++;}else if(tmp[j]<vs[j]){if(vs[j]-tmp[j]>1) flag=0;else s2++;}}//printf("i:%d s1:%d s2:%d\n",i,s1,s2);if(flag&&(s1==1&&s2==1||s1==0&&s2==0))ans++;}printf("%d\n",ans);}
}

E-皮卡丘这么可爱，当然要.....

做法：二进制优化多重背包，详细博客：博客

F-Doctor Rabbit 的统计

做法：简单模拟没人写系列，按照题意模拟即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e2+10,M=2000;
char s[N];
struct node{int sex,t,ty;
}a[N];int na[M],nv[M],n;void print(int x)
{int h=x/60;int m=x%60;printf("%02d:%02d\n",h,m);
}
int main()
{n=read();int num=0;int start=8*60+10,en=19*60;rep(i,1,n){int h,m;scanf("%s %d %d:%d %d",s,&a[i].sex,&h,&m,&a[i].ty);if(a[i].ty>37) continue;a[i].t=h*60+m+2;if(a[i].t>en) continue;if(a[i].sex==0) nv[a[i].t]++;else na[a[i].t]++;num++;}int en1=21*60;int mx=0,mi=0;for(int i=start;i<=en1;i+=10){//printf("i: ");//print(i);int flag=0;for(int j=i;j>=i-9;--j){if(na[j]){mi=i+3;flag=1;break;}}if(flag) break;}for(int i=start;i<=en1;i+=10){for(int j=i;j>=i-9;--j){if(nv[j]){mx=max(mx,i+5);}}}if(!num) puts("-1");else{printf("%d\n",num);if(mi) print(mi); else puts("-1");if(mx) print(mx); else puts("-1");}}

G-遗迹逃亡

做法:bfs经典入门水题

#pragma GCC optimize(2)
#include<bits/stdc++.h>#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}const int N=5e2+10;
int n,m,si,sj,ei,ej;
char s[N][N];
int dir[4][2]={1,0,0,1,-1,0,0,-1},vis[N][N];
void bfs()
{queue<pair<int,int> >que;que.push({si,sj});vis[si][sj]=1;while(que.size()){auto now=que.front();que.pop();if(now.first==ei&&now.second==ej){puts("Yes");return ;}for(int i=0;i<4;++i){int x=now.first+dir[i][0];int y=now.second+dir[i][1];if(x<=0||y<=0||x>n||y>m||s[x][y]=='#') continue;if(vis[x][y]) continue;vis[x][y]=1;que.push({x,y});}}puts("No");
}
int main()
{n=read(),m=read();rep(i,1,n) {scanf("%s",s[i]+1);for(int j=1;j<=m;++j){if(s[i][j]=='s') si=i,sj=j;if(s[i][j]=='g') ei=i,ej=j;}}bfs();
}

 

H-阿罗拉联盟赛

做法：又一个题意看起来复杂，做起来很水，但是没人写的一个题。

按照题意模拟即可。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e5+10;
char X;
int n,A[N],B[N];
struct node
{int l,r,x,id;}a[N],b[N];
bool cmp1(node a,node b)
{if(a.x!=b.x) return a.x>b.x;return a.id<b.id;
}bool cmp2(node a,node b)
{if(a.x!=b.x) return a.x<b.x;return a.id<b.id;
}int main()
{cin>>n>>X;rep(i,1,n) a[i].l=read();rep(i,1,n) a[i].r=read();rep(i,1,n) b[i].l=read();rep(i,1,n) b[i].r=read();rep(i,1,n) A[i]=read();rep(i,1,n) B[i]=read();rep(i,1,n) a[i].x=a[i].l+a[i].r,a[i].id=i;rep(i,1,n) b[i].x=b[i].l+b[i].r,b[i].id=i;sort(a+1,a+1+n,cmp1);sort(b+1,b+1+n,cmp2);int id1=1,id2=1;int sum1=0,sum2=0,ans1=0,ans2=0;if(X=='A') {while(id1<=n&&id2<=n){//printf("id1:%d id2:%d\n",id1,id2);int mi=a[A[id1]].l;sum1+=mi;b[B[id2]].r-=mi;if(b[B[id2]].r<=0) id2++,ans2++;if(id2>n) break;mi=b[B[id2]].l;sum2+=mi;a[A[id1]].r-=mi;if(a[A[id1]].r<=0) id1++,ans1++;}}else{while(id1<=n&&id2<=n){int mi=b[B[id2]].l;sum2+=mi;a[A[id1]].r-=mi;if(a[A[id1]].r<=0) id1++,ans1++;if(id1>n) break;mi=a[A[id1]].l;sum1+=mi;b[B[id2]].r-=mi;if(b[B[id2]].r<=0) id2++,ans2++;}}printf("%d %d %d %d\n",sum1,sum2,ans1,ans2);}

I-雪拉比的求救

做法:由于两个目标是相向而行的，那么对s、t分别跑dij 并保存方案数

方案数怎么求？两种情况：

1、在点上 （s到点i方案数）*（t到点i方案数）* s到点i方案数）*（t到点i方案数） 为什么乘了两边？因为当从t到达i  从i 到达s 时又是一次方案数

2、在边上 判断能否在这边上相遇即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
const ll inf=0x3f3f3f3f,mod=1e9+7;
vector<pair<int,int> >G[N];
int n,m,s,t;
int vis[N];
ll dis[2][N],dp[2][N];
void dij(int s,ll d[],ll dp[])
{for(int i=1;i<=n;++i) d[i]=1e18,vis[i]=0;//初始化priority_queue<pair<ll,int> >que;que.push({0,s});d[s]=0;dp[s]=1;while(que.size()){auto now=que.top();que.pop();int u=now.second;if(vis[u]) continue;vis[u]=1;for(auto it:G[u]){int v=it.first;if(d[v]>d[u]+it.second){d[v]=d[u]+it.second;que.push({-d[v],v});dp[v]=dp[u];//printf("v:%d u:%d dp[u]:%lld\n",v,u,dp[u]);}else if(d[v]==d[u]+it.second) dp[v]=(dp[v]+dp[u])%mod;}}
}
int main()
{scanf("%d%d",&n,&m);scanf("%d%d",&s,&t);for(int i=1;i<=m;++i){int u,v,w;scanf("%d%d%d",&u,&v,&w);G[u].push_back({v,w});G[v].push_back({u,w});}dij(s,dis[0],dp[0]);dij(t,dis[1],dp[1]);ll L=dis[0][t];ll ans=((dp[0][t]%mod)*(dp[1][s]%mod))%mod;for(int i=1;i<=n;++i){if(dis[1][i]==dis[0][i]&&dis[1][i]*2==L){ans=(ans-dp[0][i]*dp[0][i]%mod*dp[1][i]%mod*dp[1][i]%mod+mod)%mod;}for(auto now:G[i]){int v=now.first,w=now.second;if(dis[0][i]+w+dis[1][v]==L&&dis[0][i]*2<L&&dis[1][v]*2<L){ans=(ans-dp[0][i]*dp[0][i]%mod*dp[1][v]%mod*dp[1][v]%mod+mod)%mod;}}}printf("%lld\n",ans);}

 

J-小梁的背包

做法：经典01背包，但是他这数据 的理论时间复杂度 不支持他标程能过，可能是t个数据的n之和小于1e4

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e4+10;
int n,s;
ll w[N],v[N];
pair<ll,ll>ans[N];
int main()
{int _=read();while(_--){n=read(),s=read();rep(i,1,n) w[i]=read(),v[i]=read();rep(i,0,s) ans[i].first=0,ans[i].second=0;rep(i,1,n){for(int j=s;j>=w[i];--j){if(ans[j-w[i]].first+v[i]>ans[j].first){ans[j].first=ans[j-w[i]].first+v[i];ans[j].second=ans[j-w[i]].second+1;}}}printf("%lld %lld\n",ans[s].first,ans[s].second);}
}

K-训练师的变强秘诀：时间管理

做法：有点需要思维思考，主要是没想到  排序后 还可以动态的更新后一个的游戏结束时间

//#pragma GCC optimize(2)
#include <bits/stdc++.h>using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int n;
struct node{ll s,e,ti,en;
}a[maxn];
bool cmp(node x,node y){if(x.en!=y.en) return x.en<y.en;return x.s<y.s;
}
int main(){scanf("%d",&n);int f=0;for(int i=1;i<=n;i++){scanf("%d%d",&a[i].s,&a[i].e);a[i].ti=(a[i].e-a[i].s+2)/2;//至少玩的时长a[i].en=a[i].s+a[i].ti;//结束时间}sort(a+1,a+1+n,cmp);for(int i=1;i<n;i++){if(a[i].en+a[i+1].ti>a[i+1].e){//当前结束时间+下一个需要玩的时长大于结束时间，无解f=1;break;}else if(a[i].en>a[i+1].s) a[i+1].en=a[i].en+a[i+1].ti;//更新下一个结束的时间}if(f==0) printf("YES\n");else printf("NO\n");return 0;
}

 

L-小梁的道馆

做法:连通块、并查集水题。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e3+10;
int n,m,t,sz[N],cnt;
vector<int>G[N];
void bfs(int u,int cnt)
{queue<int>que;que.push(u);while(que.size()){int now=que.front();que.pop();sz[now]=cnt;for(int v:G[now]){if(!sz[v]){que.push(v);}}}
}
int main()
{n=read(),m=read(),t=read();for(int i=1;i<=m;++i){int u=read(),v=read();G[u].push_back(v);G[v].push_back(u);}for(int i=1;i<=n;++i){if(!sz[i]) bfs(i,++cnt);}while(t--){int u=read(),v=read();if(sz[u]==sz[v])puts("YES");else puts("NO");}
}

 

这篇关于宁波工程学院2020新生校赛（重现赛）（A,B,C,D,E 二进制优化多重背包 ,F 模拟,G bfs,H 模拟, I 双向dij 方案数 J, K 思维 L 并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/570280。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题：墙体两侧特征混淆误匹配，导致建图和定位偏差，表现为过门跳变、外月台走歪等 ·解决思路：预期的根治方案IGICP需要较长时间完成上线，先使用切分地图的工程化方案，即墙体两侧切分为不同地图，在某一侧只使用该侧地图进行定位 方案思路 切分原理：切分地图基于关键帧位置，而非点云。 理论基础：光照是直线的，一帧点云必定只能照射到墙的一侧，无法同时照到两侧实践考虑：关
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

摘要 近日，万博智云推出了基于AWS的无代理跨云容灾解决方案，并与拉丁美洲，中东，亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础，将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合，为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日，万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频，介绍了
阅读更多...
poj2576(二维背包)

poj2576(二维背包)

题意：n个人分成两组，两组人数只差小于1 ， 并且体重只差最小 对于人数要求恰好装满，对于体重要求尽量多，一开始没做出来，看了下解题，按照自己的感觉写，然后a了 状态转移方程：dp[i][j] = max(dp[i][j],dp[i-1][j-c[k]]+c[k]);其中i表示人数，j表示背包容量，k表示输入的体重的 代码如下： #include<iostream>#include<
阅读更多...
hdu2159（二维背包）

hdu2159（二维背包）

这是我的第一道二维背包题，没想到自己一下子就A了，但是代码写的比较乱，下面的代码是我有重新修改的 状态转移：dp[i][j] = max(dp[i][j], dp[i-1][j-c[z]]+v[z]); 其中dp[i][j]表示，打了i个怪物，消耗j的耐力值，所得到的最大经验值 代码如下： #include<iostream>#include<algorithm>#include<
阅读更多...
csu(背包的变形题)

csu(背包的变形题)

题目链接 这是一道背包的变形题目。好题呀 题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法 #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>//#include<u>#include<map
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2