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。

相关文章

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
GPU 计算 CMPS224 2021 学习笔记 02

GPU 计算 CMPS224 2021 学习笔记 02

并行类型 （1）任务并行 （2）数据并行 CPU & GPU CPU和GPU拥有相互独立的内存空间，需要在两者之间相互传输数据。 （1）分配GPU内存 （2）将CPU上的数据复制到GPU上 （3）在GPU上对数据进行计算操作 （4）将计算结果从GPU复制到CPU上 （5）释放GPU内存 CUDA内存管理API （1）分配内存 cudaErro
阅读更多...
2021-8-14 react笔记-2 创建组件 基本用法

2021-8-14 react笔记-2 创建组件 基本用法

1、目录解析 public中的index.html为入口文件 src目录中文件很乱，先整理文件夹。 新建components 放组件 新建assets放资源   ->/images      ->/css 把乱的文件放进去  修改App.js 根组件和index.js入口文件中的引入路径 2、新建组件 在components文件夹中新建[Name].js文件 //组件名首字母大写
阅读更多...
2021-08-14 react笔记-1 安装、环境搭建、创建项目

2021-08-14 react笔记-1 安装、环境搭建、创建项目

1、环境 1、安装nodejs 2.安装react脚手架工具 //  cnpm install -g create-react-app 全局安装 2、创建项目 create-react-app [项目名称] 3、运行项目 npm strat  //cd到项目文件夹    进入这个页面  代表运行成功  4、打包 npm run build
阅读更多...
牛客小白月赛100部分题解

牛客小白月赛100部分题解

比赛地址：牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>
阅读更多...
牛客小白月赛100（A,B,C,D,E,F三元环计数）

牛客小白月赛100（A,B,C,D,E,F三元环计数）

比赛链接 官方讲解 这场比较简单，ABC都很签到，D是个不太裸需要预处理的 B F S BFS BFS 搜索，E是调和级数暴力枚举，F是三元环计数。三元环考的比较少，没见过可能会偏难。 A ACM中的A题 思路： 就是枚举每个边变成原来的两倍，然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2，比如 1 4 8 这组数据，也不能只给第二短边乘 2 2 2，比
阅读更多...
[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程

[SWPUCTF 2021 新生赛]web方向(一到六题) 解题思路，实操解析，解题软件使用，解题方法教程

题目来源 NSSCTF | 在线CTF平台因为热爱，所以长远！NSSCTF平台秉承着开放、自由、共享的精神，欢迎每一个CTFer使用。https://www.nssctf.cn/problem   [SWPUCTF 2021 新生赛]gift_F12 这个题目简单打开后是一个网页  我们一般按F12或者是右键查看源代码。接着我们点击ctrl+f后快速查找，根据题目给的格式我们搜索c
阅读更多...
笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机（二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机（二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用，那个马的关系，后面就注意，dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ
阅读更多...
2014级寒假特训之并查集专题

2014级寒假特训之并查集专题

Problem A: Double和XXZ的生日宴请 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 9   Solved: 7 [ Submit][ Status][ Web Board] [ Edit] [ TestData] Description Double 和 XXZ同一天生日，他们俩30岁生日那天，当年
阅读更多...
每日OJ_牛客_求和（递归深搜）

每日OJ_牛客_求和（递归深搜）

目录 牛客_求和（递归深搜） 解析代码 牛客_求和（递归深搜） 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数，如果累加和大于等于目标，结束递归。此时如果累加和正好等于目标，则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程，找到所有的组合。 #include <iostream>#include <cmath>#in
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2