2021牛客寒假集训营4

2024-02-04 14:38
文章标签 牛客 2021 寒假 集训营

本文主要是介绍2021牛客寒假集训营4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

B.武辰延的字符串

在这里插入图片描述

思路：

比赛的时候一直想着要用到kmp，其实并不需要。题目要我们求的其实就是t i+j = s i+s j。那么只要枚举s和t的所有相同前缀，然后二分查找 t - si ,找到能匹配上s的前缀 sj 的最大长度，计入答案即可。

具体算法就是哈希和二分：

  • 哈希能够快速O(1)判断两个子串是否匹配

  • 二分是因为我们在找到某个前缀匹配时，前缀的前缀也一定匹配，所以可以二分找到最长前缀，因为比它长的前缀都不匹配，比它短的所有前缀都匹配，这就满足二分使用前提的单调性。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,mod=1e9+7;
LL sum1[N],sum2[N],fac[N],base=131;
LL ans1,ans2;
char s[N],t[N];
void check(int l,int r)
{ans1=sum1[r-l+1];ans2=(sum2[r]-sum2[l-1]*fac[r-l+1]%mod+mod)%mod;
}
int main()
{cin>>s+1>>t+1;int n=strlen(s+1),m=strlen(t+1);for(int i=1;i<=n;i++)sum1[i]=sum1[i-1]*base%mod+(s[i]-'a'+1);for(int i=1;i<=m;i++)sum2[i]=sum2[i-1]*base%mod+(t[i]-'a'+1);fac[0]=1;for(int i=1;i<=max(n,m);i++)fac[i]=fac[i-1]*base%mod;int k=min(n,m);LL res=0;for(int i=1;i<=k;i++){if(s[i]!=t[i]) break;if(s[1]!=t[i+1]) continue;LL l=i+1,r=min(m,i+n);while(l<r){LL mid=(l+r+1)/2;check(i+1,mid);if(ans1==ans2) l=mid;else r=mid-1;}res=res+l-i;}printf("%lld\n",res);system("pause");return 0;
}

F魏迟燕的自走棋

在这里插入图片描述
解法1：贪心+并查集

贪心很显然就是战力增加多的装备优先选择。由于每个装备最多试用与两个人，所以可以用并查集维护关系。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
struct node
{int idx;int w;
}a[N];
int num[N][5];
int siz[N],cnt[N],fa[N];
bool cmp(node a,node b)
{return a.w>b.w;
}
int find(int x)
{if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int k;scanf("%d",&k);for(int j=1;j<=k;j++) scanf("%d",&num[i][j]);scanf("%d",&a[i].w);a[i].idx=i;}sort(a+1,a+1+m,cmp);for(int i=1;i<=n;i++){fa[i]=i;siz[i]=1;} LL res=0;for(int i=1;i<=m;i++){int id=a[i].idx;if(num[id][2]==0){int fx=find(num[id][1]);if(cnt[fx]<siz[fx]){res=res+a[i].w;cnt[fx]++;}}else{int fx=find(num[id][1]);int fy=find(num[id][2]);if(fx!=fy&&(cnt[fx]<siz[fx]||cnt[fy]<siz[fy])){siz[fx]+=siz[fy];fa[fy]=fx;res=res+a[i].w;cnt[fx]+=cnt[fy]+1;}else if(fx==fy&&cnt[fx]<siz[fx]){res=res+a[i].w;cnt[fx]++;}}}printf("%lld\n",res);system("pause");return 0;
}

解法2：贪心+匈牙利算法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
struct node
{int idx;int w;
}a[N];
int num[N][5];
int used[N],ans[N];
bool cmp(node a,node b)
{return a.w>b.w;
}
bool found(int x)
{for(int i=1;i<=2;i++){int to=num[x][i];if(!used[to]&&to!=0){used[to]=1;if(ans[to]==0||found(ans[to])){ans[to]=x;used[to]=0;return 1;}}}return 0;
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int k;scanf("%d",&k);for(int j=1;j<=k;j++) scanf("%d",&num[i][j]);scanf("%d",&a[i].w);a[i].idx=i;}sort(a+1,a+1+m,cmp);LL res=0;for(int i=1;i<=m;i++){int id=a[i].idx;if(found(id)) res+=a[i].w;}printf("%lld\n",res);system("pause");return 0;
}

G九峰与蛇形填数

在这里插入图片描述

思路：

  1. 暴力，每个点取值取到的肯定是最后一个覆盖到它的区域，所以直接取那个数即可。还有一个细节就是剪枝，先预处理区域的大小，如果这个点不在区域则直接break，不用赋值。
    （但我觉得这个题数据如果再恶心点，暴利应该是不行的，所以下面还有线段树维护的做法）

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+10;
int x[N],y[N],k[N];
int maze[N][N];
int main()
{int n,m;scanf("%d%d",&n,&m);int maxx=0,maxy=0,minx=2500,miny=2500;for(int i=1;i<=m;i++){scanf("%d%d%d",&x[i],&y[i],&k[i]);maxx=max(maxx,x[i]+k[i]-1);minx=min(minx,x[i]);maxy=max(maxy,y[i]+k[i]-1);miny=min(miny,y[i]);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int l=m;l>=1;l--){if(i<minx||i>maxx||j<miny||j>maxy) break;if(i>=x[l]&&i<=x[l]+k[l]-1&&j>=y[l]&&j<=y[l]+k[l]-1){maze[i][j]=k[l]*(i-x[l]);if (i - x[l] & 1) maze[i][j] += y[l] + k[l] - j;else maze[i][j] += j - y[l] + 1;break;}}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",maze[i][j]);printf("\n");}//system("pause");return 0;
}

可以开2000棵线段树（每一个横坐标开一棵线段树），然后用lazy标记维护区间。时间复杂度应该是nmlog(n)。但是奇怪的是，就这题来说暴力要比这稍微快一点。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=3e3+10;
struct node
{struct point{int l,r,lazy;}tr[N<<2];void pushdown(int k){if(tr[k].lazy){tr[k<<1].lazy=tr[k].lazy;tr[k<<1|1].lazy=tr[k].lazy;tr[k].lazy=0;}}void build(int k,int l,int r){tr[k].l=l,tr[k].r=r;tr[k].lazy=0;if(l==r) return ;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);}void modify(int k,int l,int r,int x){if(l<=tr[k].l&&r>=tr[k].r){tr[k].lazy=x;return ;}pushdown(k);int mid=(tr[k].l+tr[k].r)>>1;if(l<=mid) modify(k<<1,l,r,x);if(r>=mid+1) modify(k<<1|1,l,r,x);}int query(int k,int x){if(tr[k].l==tr[k].r)return tr[k].lazy;pushdown(k);int mid=(tr[k].l+tr[k].r)>>1;if(x<=mid) return query(k<<1,x);else return query(k<<1|1,x);}
}tree[N];
int x[M],y[M],k[M];
void solve(int l,int i,int j)
{int res=k[l]*(i-x[l]);if (i - x[l] & 1) res+=y[l]+k[l]-j;else res+=j-y[l]+1;printf("%d ",res);
}
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)tree[i].build(1,1,n);for(int i=1;i<=m;i++){scanf("%d%d%d",&x[i],&y[i],&k[i]);for(int j=x[i];j<=x[i]+k[i]-1;j++)tree[j].modify(1,y[i],y[i]+k[i]-1,i);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int f=tree[i].query(1,j);if(f==0) printf("0 ");else solve(f,i,j);}printf("\n");}//system("pause");return 0;
}

H.吴楚月的表达式

在这里插入图片描述

思路：

每一个表达式都可以化作是多个表达式的和。比如一个非空的表达式前缀可以表示成a+b的形式

  • 如果后面接了一个+x，则变成a+b+x
  • 如果后面接了一个-x，则变成了a+b+(-x)
  • 如果后面接了一个x,则变成了a+bx
  • 如果后面接了一个/x，则变成了a+b/x

所以不管怎么样都可以变成a+b的形式。那么假设当前节点为x，父节点为fa，显然如果fa->x的符号是 + 或者是 - 的话，直接从res[fa]+w[x]或res[fa]-w[x]即可，同时将b更新为w[x]或是-[x]。但是当符号是*或/时，那么它就会与fa的b扯上关系，那么就要先减去然后重新加上。具体细节见代码

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
const LL mod=1e9+7;
LL w[N],fa[N];
char op[N];
int head[N],cent;
LL quick_pow(LL x,LL y)
{LL ans=1;while(y){if(y%2) ans=ans*x%mod;x=x*x%mod;y=y/2;}return ans;
}
struct node
{int to,next;
}tr[N];
void add(int u,int v)
{tr[cent].to=v;tr[cent].next=head[u];head[u]=cent++;
}
LL res[N],num[N];
void dfs(int x)
{for(int i=head[x];~i;i=tr[i].next){int to=tr[i].to;if(op[to-1]=='+'){res[to]=(res[x]+w[to])%mod;num[to]=w[to]%mod;}else if(op[to-1]=='-'){res[to]=(res[x]-w[to]+mod)%mod;num[to]=(-1*w[to]+mod)%mod;}else if(op[to-1]=='*'){res[to]=(res[x]-num[x]+num[x]*w[to]%mod+mod)%mod;num[to]=num[x]*w[to]%mod;}else if(op[to-1]=='/'){res[to]=(res[x]-num[x]+num[x]*quick_pow(w[to],mod-2)%mod+mod)%mod;num[to]=num[x]*quick_pow(w[to],mod-2)%mod;}dfs(to);}
}
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&w[i]);for(int i=1;i<n;i++)scanf("%d",&fa[i]);for(int i=1;i<n;i++)cin>>op[i];memset(head,-1,sizeof(head));for(int i=1;i<n;i++)add(fa[i],i+1);res[1]=w[1];num[1]=w[1];dfs(1);for(int i=1;i<=n;i++)printf("%lld ",res[i]);//system("pause");return 0;
}

这篇关于2021牛客寒假集训营4的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

2021-02-16物料档案条码添加和蓝牙条码标签打印，金蝶安卓盘点机PDA，金蝶仓库条码管理WMS系统

2021-02-16物料档案条码添加和蓝牙条码标签打印，金蝶安卓盘点机PDA，金蝶仓库条码管理WMS系统

物料档案条码添加和蓝牙条码标签打印，金蝶安卓盘点机PDA https://member.bilibili.com/platform/upload-manager/article 本期视频我们来讲解一下汉点机PDA条码添加和条码标签蓝牙便携打印： 在实际使用中,我们商品有两种情况: 一种是商品本身就有条码, 比如：超市卖的可口可乐，牛奶等商品，商品本身就有69开头的国标码,那么我们就可以使用盘点
阅读更多...
第13关：存储过程1、第14关：存储过程2。(2021数据库期末一)

第13关：存储过程1、第14关：存储过程2。(2021数据库期末一)

目录 首先需要学习和了解的知识 第13关：存储过程1 任务描述 答案  第14关：存储过程2 任务描述 答案 本篇博客的答案博主是学习别人得来的，敢于借鉴和学习哈哈！！ 首先需要学习和了解的知识 了解什么是存储过程以及存储过程的基本语法。（作者博客专栏或者b站学习）了解在命令行中，执行创建存储过程的SQL时。需要通过关键字 delimiter 指定SQL语句的结束
阅读更多...
【牛客网 2017年校招模拟笔试(第一场)】超级素数幂

【牛客网 2017年校招模拟笔试(第一场)】超级素数幂

超级素数幂 描述 如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。 输入 输入一个正整数n(2 ≤ n ≤ 10^18) 分析 暴力枚举幂q，将n开q次方之后得到p，检查p是否为素数，并且检查p的q次幂是否等于n。 *要注意精度问题，代码待之后补充。
阅读更多...
【牛客网 2017年校招模拟笔试(第一场)】 序列和

【牛客网 2017年校招模拟笔试(第一场)】 序列和

求序列和 描述 我们要找连续的一段长度大于等于L小于等于100整数和等于N,容易观察到合法的长度范围很小,于是我们从L开始枚举,然后找到第一个输出即可。 我的代码 最初提交了一次代码，用vector保存了所有满足条件的序列，输出长度最小的，提交之后说内存超出限制，看了一眼题目，发现内存貌似是限制在2w多k？伤心，之前做题没遇到过内存还有这么严格的限制。 修改了一下，其实这个代码并没
阅读更多...
Acrobat Pro DC 2021：Mac/Win平台上全面高效的PDF编辑器

Acrobat Pro DC 2021：Mac/Win平台上全面高效的PDF编辑器

Acrobat Pro DC 2021是一款在Mac和Windows平台上广受欢迎的PDF编辑器，它凭借其全面的功能和高效的性能，为用户提供了卓越的PDF处理体验。 一、编辑功能全面强大 Acrobat Pro DC 2021允许用户轻松创建、编辑、合并、转换、签署和分享PDF文件。无论是对PDF文档中的文字、图像、表格和链接进行编辑，还是添加、删除、移动和调整页面，都能轻松完成。此外，该软件
阅读更多...
【Rust日报】2021-01-29 微软正在组建一支强大的Rust团队

【Rust日报】2021-01-29 微软正在组建一支强大的Rust团队

微软正在组建一支强大的Rust团队 Wesley Wiser在推特上宣布加入微软，并宣布它们正在组建Rust编译器团队。https://www.reddit.com/r/rust/comments/l7c8ro/microsoft_is_building_a_great_rust_team/ Redox OS 最近公布了2020年的财务明细 主要的收入是通过捐赠，包括Patreon网站，payp
阅读更多...
【Rust日报】2021-01-26 太素桌面系统：基于RISC-V架构的Rust系统内核

【Rust日报】2021-01-26 太素桌面系统：基于RISC-V架构的Rust系统内核

太素桌面系统：基于RISC-V架构的Rust系统内核（十二） 编写“太素”桌面操作系统的文章更新到第十二期。本期文章在前文成果的基础上，开始编写一个简单的桌面系统结构。这包括桌面、窗口和其中的控件，以及文字标签的显示方式。 太素OS是一个RISC-V架构、Rust编写的操作系统内核。作者在系列文章中介绍，“太素”的名字来源于道家五太之一，可以演化万物。这个项目实现了包含图形处理器在内的外部设备控
阅读更多...
【Rust日报】 2021-01-21 Rust 的产品实践：1Password

【Rust日报】 2021-01-21 Rust 的产品实践：1Password

Rust 的产品实践：1Password 我们采访了 1Password 的工程副总裁 Michael Fey。通过采访去了解他们为什么选择 Rust 开发他们的产品，Rust 对于以安全为中心的应用程序有哪些好处，以及如果你正在用 Rust 开发类似的东西，你应该研究哪些有用的库，有哪些可取的经验。 原文：https://serokell.io/blog/rust-in-production-
阅读更多...
【Rust日报】2021-01-19 中国移动云Rust语言新硬件分布式数据库社招

【Rust日报】2021-01-19 中国移动云Rust语言新硬件分布式数据库社招

使用Rust的科学计算 文章作者是一位物理学研究生，他往常都在Matlab和Python上做科学计算。作者使用Rust重写了生物膜虚拟程序。为此，作者推出了bacon-sci库。 博客地址: https://aftix.xyz/home/bacon/ 创建私有cargo仓库的最佳方法 Reddit网友给出了自己的讨论。 推文地址: https://www.reddit.com/r/rust/co
阅读更多...
【Rust日报】 2021-01-17 Rust 要上太空了！ RocketLab 招聘 Rust 工程师

【Rust日报】 2021-01-17 Rust 要上太空了！ RocketLab 招聘 Rust 工程师

Rust 要上太空了！RocketLab 招聘 Rust 工程师 Rocket Lab 是小型卫星发射领域的全球领导者。团队有500人，而且每周都在增加。 当然，这是在美国的工作。期待国内也会有！ 链接：https://www.rocketlabusa.com/careers/positions/flight-software-engineer-ii-auckland-new-zealand-3
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2