admin 管理员组文章数量: 887021
宁波工程学院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 二进制优化多重背包
版权声明：本文标题：宁波工程学院2020新生校赛（重现赛）（A,B,C,D,E 二进制优化多重背包 ,F 模拟,G bfs,H 模拟, I 双向dij 方案数 J,K 思维 L 并查集） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1730896791h1401865.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论