网易2021批笔试题解 msf工具之木马程序制作以及伪装 【JAVA】滴滴-2021校招在线笔试-DE数据开发试卷-0913 机器学习13 -- 无监督学习之自监督 2020年全国数学建模大赛 B题部分代码和模型的建立 jumpserver安装(centos) Redis 知识点总结 通过RabitMQ实现分布式事务 高焕堂《嵌入式UML设计》读书笔记_第一章 2020年中国5G在物联网行业:中国通信运营商5G投资达1.23万亿元(可下载) 面试题精选:数据伪造 繁忙的都市(并查集、Kruskal) BFS 力扣 200.岛屿数量 深度操作系统Deepin V20正式版 2020-09-13 【OS】Bankers Algorithm 用于调用的参数太少/写入位置时发生冲突/检测到无效的异常处理程序例程 后渗透之各种维持权限的后门原理即利用 MIPS Branch Target Buffer动态分支预测(BTB) Oracle实战优化:INSERT ALL关键字的应用 Linux中MySQL数据库的使用②-----数据的基本操作 理论+实验——MySQL备份与恢复 MySQL常用数据库函数 MySQL 备份与恢复(完全备份恢复--增量备份恢复+案例演示) MySQL之基础总结部分 Oracle实战优化:递归+分析函数+OLAP函数的应用 Linux中MySQL数据库的使用③-----编码和基本数据类型 理论+实验:MySQL备份与恢复(完整备份、增量备份) “数”聚永川 “智”引未来——永川区大数据智能化产业发展强劲 从一款防疫App感受新加坡大数据智能化气息 “数”聚永川“智”引未来——永川区大数据智能化产业发展强劲 从连接量变到数据质变 物联网将二次爆发 重磅发布!猎芯半导体首创全球最小支持5G物联网的多模多频射频PA芯片 从精准授信到助企惠民,江苏银行物联网金融派上大用场 Python Selenium UI自动化_WebDriver元素_8大定位方式+总结(持续更新完善) Python中的继承、抽象基类和接口 Datawhale学习笔记【阿里云天池 金融风控-贷款违约预测】task1 赛题理解 Pytorch - torchvision计算机视觉工具库 linux 重点笔记 Ubuntu18.04安装ROS Melodic(一路到站型) 小甲鱼笔记:数据结构——线性表(一)线性表的顺序存储结构,线性表顺序存储结构的增,删,插入元素操作 实战比特币脚本编程(1) JAVA WEB DAY 01_Tomcat & Servlet Java基础算法之堆排序(Heap Sort) synchronized批量重偏向与批量撤销 终于等到了!阿里P8历时九个月整理,Java面试宝典,核心知识点笔记在此 “数字心脏”动态解析消费密码,国家级消费市场大数据联合实验室在上海先行先试 全世界运行着大约230亿台物联网设备,安全问题如何解? 物联网产业园&thinkplus解决方案中心国学讲座如期而至 都是程序员,凭什么他能站在鄙视链的顶端?
您的位置:首页 >数据库 >

网易2021批笔试题解

总结:全是模拟…以及读入处理体验好差hhh

一套卷子(4/4AK)

T3

题目大意:给出一棵树,从0节点开始走m步,求可访问的最多节点数(一个节点访问多次仅算一次)n , m < = 1000n,m<=1000n,m<=1000

真有你的网易…省选原题都拿来出啊…(不过我做过hhh

直接放原题链接了: C Q O I 2017CQOI2017CQOI2017 小Q的棋盘

简要题解: 策略是:先考虑直接直接按最长链走,如果走完最长链有多的步数,可以在一开始先走支链,贡献按2步/一个节点算。

故有以下代码:

for(int i=0;i<=n;i++) mx=Math.max(mx,dep[i]);if(m<=mx-1) System.out.println(m+1);else System.out.println(Math.min(n,mx+(m-mx+1)/2));

然后dfs算一波就行了。

import java.io.*;import java.util.*;public class zbr01{public static int []x=new int [100005];static List []g=new List[100005];public static int []dep=new int [100005];public static int []used=new int [100005];public static int n,m;public static void dfs(int u){used[u]=1;for(int i=0;i<g[u].size();i++){int v=(int)g[u].get(i); if(used[v]==1) continue;dep[v]=dep[u]+1; dfs(v);}}public static void main(String[] args){Scanner S=new Scanner(System.in);int n=S.nextInt(),m=S.nextInt(); n--;for(int i=0;i<=n;i++) g[i]=new ArrayList <Integer>();for(int i=1;i<=n;i++){int u=S.nextInt(),v=i;g[u].add(v); g[v].add(u);}dep[0]=1; dfs(0); int mx=0;for(int i=0;i<=n;i++) mx=Math.max(mx,dep[i]);if(m<=mx-1) System.out.println(m+1);else System.out.println(Math.min(n,mx+(m-mx+1)/2));}}

T2

题目大意:给出字符串s,求一个最长的连续子串使得其中的 a , b , c , x , y , za,b,c,x,y,za,b,c,x,y,z出现次数均为偶数。(复杂度要求 O ( n )O(n)O(n))

它又又又又来了!hash又是你!!! 将abcdef的出现次数%2,进行hash处理,就能用一个数字表示一个状态了。 (日常学好hash笔试必过)

import java.io.*;import java.util.*;public class zbr01{public static int []x=new int [100005];public static void main(String[] args){Scanner S=new Scanner(System.in);String s=S.nextLine(); int l=s.length();int a=0,b=0,c=0,d=0,e=0,f=0,ans=0;for(int i=0;i<=64;i++) x[i]=-1; x[0]=0;for(int i=0;i<l;i++){char p=s.charAt(i);if(p=='a') a++; else if(p=='b') b++;else if(p=='c') c++; else if(p=='x') d++;else if(p=='y') e++; else if(p=='z') f++;a%=2; b%=2; c%=2; d%=2; e%=2; f%=2;int nw=32*a+16*b+8*c+4*d+2*e+f;int tmp=x[nw];if(tmp==-1) x[nw]=i;else if(nw==0) ans=Math.max(ans,i-tmp+1);else ans=Math.max(ans,i-tmp);}System.out.println(ans);}}

T4

题目大意:裸二分图匹配…略略略(连题面都懒得改了吗hhh,直接男女配对了hhh)

下面是网络流大板子+恶心的读入处理emm…

#pragma GCC optimize(2)#include<bits/stdc++.h>#define ll long long#define maxn 1000005#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 int read(){int 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;}struct node{int from,to,cap,flow;};vector <node> edges;vector <int> mp[maxn];int n,m,s,t,d[maxn],cur[maxn];bool vis[maxn];queue <int> que;inline void add_edge(int u,int v,int w){edges.push_back((node){u,v,w,0});edges.push_back((node){v,u,0,0});int pp=edges.size();mp[u].push_back(pp-2);mp[v].push_back(pp-1);}inline bool bfs(){for(int i=0;i<=t;i++) d[i]=inf,vis[i]=0; d[s]=0; vis[s]=1; que.push(s);while(!que.empty()){int u=que.front(); que.pop();for(int i=0;i<mp[u].size();i++){node v=edges[mp[u][i]];if(v.cap-v.flow>0&&!vis[v.to]){d[v.to]=d[u]+1;vis[v.to]=1; que.push(v.to);}}}if(vis[t]) return true;return false;}inline int dfs(int u,int w){int flow=0,r=0;if(u==t||w==0) return w;for(int i=0;i<mp[u].size();i++){node &v=edges[mp[u][i]];if(d[v.to]==d[u]+1&&(r=dfs(v.to,min(v.cap-v.flow,w)))>0){flow+=r;edges[mp[u][i]].flow+=r;edges[mp[u][i]^1].flow-=r;w-=r;if(w==0) break;}}return flow;}inline int max_flow(){int ff=0;while(bfs()){memset(cur,0,sizeof(cur));ff+=dfs(s,inf);}return ff;}int a[maxn],b[maxn],ca,cb;map <int,int> pa,pb;int main(){freopen("t1.in","r",stdin);string S=""; getline(cin,S);int l=S.length(),nw=0;for(int i=0;i<l;i++){if(S[i]==' '){a[++ca]=nw;pa[nw]=ca;nw=0;}else nw=nw*10+S[i]-'0';}a[++ca]=nw; pa[nw]=ca;nw=0; getline(cin,S);for(int i=0;i<l;i++){if(S[i]==' '){b[++cb]=nw;pb[nw]=cb;nw=0;}else nw=nw*10+S[i]-'0';}b[++cb]=nw; pb[nw]=cb; nw=0;S=ca+cb+1; t=ca+cb+2;rep(i,1,ca) add_edge(s,i,1);rep(i,1,cb) add_edge(ca+i,t,1);int Q=read();while(Q--){int u=read(),v=read();add_edge(pa[u],ca+pb[v],1);}printf("%d\n",max_flow());return 0;}

T1

题目大意:给出一颗二叉树,问两个儿子都是叶节点的节点数量。

毫无水平的大模拟…略略略…扔到最后hhh

import java.io.*;import java.util.*;public class zbr01{public static int []x=new int [100005];static List []g=new List[100005];public static int []dep=new int [100005];public static int []cnt=new int [100005];public static int n,m;public static void dfs(int u,int fa){if(g[u].size()==1&&u!=1){for(int i=0;i<g[u].size();i++){int v=(int)g[u].get(i);cnt[v]++;}}for(int i=0;i<g[u].size();i++){int v=(int)g[u].get(i); if(v==fa) continue;dep[v]=dep[u]+1; dfs(v,u);}}public static void main(String[] args){Scanner S=new Scanner(System.in);int n=S.nextInt(),m=S.nextInt();for(int i=0;i<=n;i++) g[i]=new ArrayList <Integer>();for(int i=1;i<=m;i++){int u=S.nextInt();String tmp=S.next(); int v=S.nextInt();g[u].add(v); g[v].add(u);}dep[0]=1; dfs(1,0); int ans=0;for(int i=1;i<=n;i++) if(cnt[i]==2) ans++;System.out.println(ans);}}

另一套C++题的T4:

题目大意:求两个字符串的编辑距离,有的字符串可以无视。

读入非常恶心…然后编辑距离就是大家都会的非常经典的dp了…详见代码

巨长码农题

#pragma GCC optimize(2)#include<bits/stdc++.h>#define ll long long#define maxn 1000005#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 int read(){int 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;}map <string,int> p;string a[maxn],b[maxn];int dp[1005][1005],ca,cb;int main(){string s; getline(cin,s); int l=s.length();string tmp="";for(int i=0;i<l;i++){if(s[i]==' '){p[tmp]=1;tmp="";}else tmp+=s[i];}p[tmp]=1; tmp="";getline(cin,s); l=s.length();for(int i=0;i<l;i++){if(s[i]==' '){a[++ca]=tmp;tmp="";}else tmp+=s[i];}a[++ca]=tmp; tmp="";getline(cin,s); l=s.length();for(int i=0;i<l;i++){if(s[i]==' '){b[++cb]=tmp;tmp="";}else tmp+=s[i];}b[++cb]=tmp; tmp="";rep(i,0,ca) rep(j,0,cb) dp[i][j]=inf; dp[0][0]=0;rep(i,1,ca) dp[i][0]=dp[i-1][0]+(p[a[i]]==0);rep(i,1,cb) dp[0][i]=dp[0][i-1]+(p[b[i]]==0);rep(i,1,ca) rep(j,1,cb){if(p[a[i]]) dp[i][j]=min(dp[i][j],dp[i-1][j]);else dp[i][j]=min(dp[i][j],dp[i-1][j]+1);if(p[b[j]]) dp[i][j]=min(dp[i][j],dp[i][j-1]);else dp[i][j]=min(dp[i][j],dp[i][j-1]+1);if(p[a[i]]&&p[b[j]]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);}cout<<dp[ca][cb]<<endl;return 0;}

END:网易读入太恶心了…码量也好大emm…以及这hash是不是已经连着出10多场了hhh…公司之间大家这么有默契???

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。