8月20网易笔试感觉题不错写一下还没找到hack数据代码附上

大二acm菜鸡，昨天学姐的面试题，今天瞅了一眼感觉题还不错，就写了一下，还没找到hack数据，感觉应该没什么问题。代码附上，自行查看
题目：题目是自己找的，听说每个人的题还不一样，仔细看清题目再看代码

题目找自网友
题目： 
//A题
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+7;
int dp[N][5];
signed main()
{
	string s , rs , ts;
	cin>>s;
	rs=s;
	ts=s;
	int slen=s.length();
	int flag=0;
	if(slen%3==0) flag=1;
	else if(slen%3==1) flag=2;
	else if(slen%3==2) flag=3; 
	int ans=0;
	if(flag==1)
	{
		for(int i=0;i<slen;i++)
		{
			if(i%3==1)
			{
				if(s[i]!='e') ans++;
				if(s[i-1]!='d'&&s[i+1]!='d') ans++;
				if(s[i-1]!='r'&&s[i+1]!='r') ans++;
			}
		}
		cout<<ans<<endl;
	}else if(flag==2)
	{
		for(int i=0;i<slen;i++)
		{
			if(i==0)
			{
				if(s[i+2]=='d'&&s[i]!='r') 
				{
					s[i]='r';
					dp[i][0]++;
				}else if(s[i+2]=='r'&&s[i]!='d') 
				{
					s[i]='d';
					dp[i][0]++;
				}else if(s[i+2]=='e'&&s[i]=='e')
				{
					s[i]='d';
					dp[i][0]++;
				}
				dp[i][1]=0;
				continue;
			}
			dp[i][0]=dp[i-1][0];
			dp[i][1]=dp[i-1][1];
			if(i%3==0)
			{
				if(s[i+2]=='d'&&s[i]!='r') 
				{
					s[i]='r';
					dp[i][0]++;
				}else if(s[i+2]=='r'&&s[i]!='d') 
				{
					s[i]='d';
					dp[i][0]++;
				}else if(s[i+2]=='e'&&s[i]=='e')
				{
					s[i]='d';
					dp[i][0]++;
				}
				if(rs[i-2]=='d'&&rs[i]!='r') 
				{
					rs[i]='r';
					dp[i][1]++;
				}else if(rs[i-2]=='r'&&rs[i]!='d') 
				{
					rs[i]='d';
					dp[i][1]++;
				}
                dp[i][1]=min(dp[i][1] , dp[i-1][0]);			
			}else if(i%3==1)
			{
				if(s[i]!='e') dp[i][0]++;
				if(rs[i+2]=='d'&&rs[i]!='r') 
				{
					rs[i]='r';
					dp[i][1]++;
				}else if(rs[i+2]=='r'&&rs[i]!='d') 
				{
					rs[i]='d';
					dp[i][1]++;
				}else if(rs[i+2]=='e'&&rs[i]=='e')
				{
					rs[i]='d';
					dp[i][1]++;
				}				
			}else if(i%3==2)
			{
				if(rs[i]!='e') dp[i][1]++;
				if(s[i-2]=='d'&&s[i]!='r') 
				{
					s[i]='r';
					dp[i][0]++;
				}else if(s[i-2]=='r'&&s[i]!='d') 
				{
					s[i]='d';
					dp[i][0]++;
				}
			}
		}
		cout<<dp[slen-1][1]<<endl;
	}else if(flag==3)
	{
		for(int i=0;i<slen;i++)
		{
			if(i==0)
			{
				if(s[i+2]=='d'&&s[i]!='r') 
				{
					s[i]='r';
					dp[i][0]++;
				}else if(s[i+2]=='r'&&s[i]!='d') 
				{
					s[i]='d';
					dp[i][0]++;
				}else if(s[i+2]=='e'&&s[i]=='e')
				{
					s[i]='d';
					dp[i][0]++;
				}
				dp[i][1]=0;
				dp[i][2]=0;
				continue;
			}
			dp[i][0]=dp[i-1][0];
			dp[i][1]=dp[i-1][1];
			dp[i][2]=dp[i-1][2];
			if(i%3==0)
			{
				if(ts[i]!='e') dp[i][2]++;
				if(s[i+2]=='d'&&s[i]!='r') 
				{
					s[i]='r';
					dp[i][0]++;
				}else if(s[i+2]=='r'&&s[i]!='d') 
				{
					s[i]='d';
					dp[i][0]++;
				}else if(s[i+2]=='e'&&s[i]=='e')
				{
					s[i]='d';
					dp[i][0]++;
				}
				if(rs[i-2]=='d'&&rs[i]!='r') 
				{
					rs[i]='r';
					dp[i][1]++;
				}else if(rs[i-2]=='r'&&rs[i]!='d') 
				{
					rs[i]='d';
					dp[i][1]++;
				}
                dp[i][1]=min(dp[i][1] , dp[i-1][0]);			
			}else if(i%3==1)
			{
				if(s[i]!='e') dp[i][0]++;
				if(rs[i+2]=='d'&&rs[i]!='r') 
				{
					rs[i]='r';
					dp[i][1]++;
				}else if(rs[i+2]=='r'&&rs[i]!='d') 
				{
					rs[i]='d';
					dp[i][1]++;
				}else if(rs[i+2]=='e'&&rs[i]=='e')
				{
					rs[i]='d';
					dp[i][1]++;
				}
				if(ts[i-2]=='d'&&ts[i]!='r'&&i>2) 
				{
					ts[i]='r';
					dp[i][2]++;
				}else if(ts[i-2]=='r'&&ts[i]!='d'&&i>2) 
				{
					ts[i]='d';
					dp[i][2]++;
				}				
				dp[i][2]=min(dp[i][2] , dp[i-1][1]);				
			}else if(i%3==2)
			{
				if(rs[i]!='e') dp[i][1]++;
				if(s[i-2]=='d'&&s[i]!='r') 
				{
					s[i]='r';
					dp[i][0]++;
				}else if(s[i-2]=='r'&&s[i]!='d') 
				{
					s[i]='d';
					dp[i][0]++;
				}
				if(ts[i+2]=='d'&&ts[i]!='r') 
				{
					ts[i]='r';
					dp[i][2]++;
				}else if(ts[i+2]=='r'&&ts[i]!='d') 
				{
					ts[i]='d';
					dp[i][2]++;
				}else if(ts[i+2]=='e'&&ts[i]=='e')
				{
					ts[i]='d';
					dp[i][2]++;
				}
			}			
		}
//		for(int i=0;i<slen;i++) cout<<dp[i][0]<<" "; cout<<endl;
//		for(int i=0;i<slen;i++) cout<<dp[i][1]<<" "; cout<<endl;
//		for(int i=0;i<slen;i++) cout<<dp[i][2]<<" "; cout<<endl;
		cout<<dp[slen-1][2]<<endl;
	}
	return 0;
}
//B题
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+7;
int a[N];
signed main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int maxn1=-1 , maxn2=-1;
	for(int i=1;i<=n;i++)
	{
		if(!(i%2)) maxn2=max(maxn2 , a[i]);
		if(i%2) maxn1=max(maxn1 , a[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!(i%2)) ans+=maxn2-a[i];
		if(i%2) ans+=maxn1-a[i];
	}
	cout<<ans<<endl;
	return 0;
}

//C题
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int MAXN=0x3f3f3f3f3f3f3f3f;
const int N=1e6+7;
int a[N];
int b[N];
int res=0;
int get(int n){return (int)log10(n)+1;}
map<string , bool>mp;
map<string , bool>mp2;
void dfs_a(string s)
{
	int slen=s.length();
	if(slen==1) return;
	for(int i=0;i<slen;i++)
	{
		string s2=s;
		s2.erase(s2.begin()+i);
		if(mp[s2]==0)
		{
			mp[s2]=1;
//			cout<<res<<endl;
			a[++res]=stoi(s2);
			dfs_a(s2);
		}		
	}
}
int mnt=0;
void dfs_b(string s)
{
	int slen=s.length();
	if(slen==1) return;
	for(int i=0;i<slen;i++)
	{
		string s2=s;
		s2.erase(s2.begin()+i);
		if(mp2[s2]==0)
		{
	    	b[++mnt]=stoi(s2);
	    	mp2[s2]=1;
	    	dfs_b(s2);
		}
	}
}
signed main()
{
	string sa , sb;
	cin>>sa>>sb;
    res=0 , mnt=0;
    a[0]=stoi(sa);
    b[0]=stoi(sb);
    dfs_a(sa);
    dfs_b(sb);
    int ans=MAXN , flag=0;
	for(int i=0;i<=res;i++)
	{
		for(int j=0;j<=mnt;j++)
		{			
			if(a[i]==0||b[j]==0) ans=min(ans , get(a[0])-get(a[i])+get(b[0])-get(b[i]));
			else if((a[i]%b[j]==0)||(b[j]%a[i]==0)) ans=min(ans , get(a[0])-get(a[i])+get(b[0])-get(b[j]));
		}
	}
//	cout<<res<<endl;
//	for(int i=0;i<=res;i++) cout<<a[i]<<" ";cout<<endl;
//	for(int i=0;i<=mnt;i++) cout<<b[i]<<" ";cout<<endl;
//    cout<<cnt<<" "<<mnt<<endl;
	if(ans==MAXN) cout<<-1<<endl;else cout<<ans<<endl;
//	cout<<ans<<endl;
	return 0;
}
//D题
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+7;
int a[N] , b[N] , c[N];
int n , cnt=0;
map<int , int>mp;
void discrete()
{	
	sort(a+1 , a+n+1);
	for(int i=1;i<=n;i++)
	{
		if(i==1||a[i]!=a[i-1]) b[++cnt]=a[i];
	}
}
int query(int x){return lower_bound(b+1 , b+cnt+1 , x)-b;}
struct SegmentTree
{
	int p , l , r;
	int real_num;
	int all;
	int num;
};SegmentTree trie[N<<2];
void build(int p , int l , int r)
{
	trie[p].l=l , trie[p].r=r;
	if(l==r) 
	{
		trie[p].all=mp[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1 , l , mid);
	build(p<<1|1 , mid+1 , r);
	trie[p].num=trie[p<<1].num+trie[p<<1|1].num;
}
void change(int p , int x)
{
	if(trie[p].l==trie[p].r)
	{
		trie[p].real_num++;
		trie[p].num=(trie[p].all-trie[p].real_num)*trie[p].real_num;
		return;
	}
	int mid=(trie[p].l+trie[p].r)>>1;
	if(x<=mid) change(p<<1 , x);
	else change(p<<1|1 , x);
	trie[p].num=trie[p<<1].num+trie[p<<1|1].num;	
}
int sum=0;
void ask(int p , int L , int R)
{
	if(trie[p].l>=L&&trie[p].r<=R)
	{
		sum+=trie[p].num;
		return;
	}
	int mid=(trie[p].l+trie[p].r)>>1;
	if(L<=mid) ask(p<<1 , L , R);
	if(R>mid) ask(p<<1|1 , L , R);
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		c[i]=a[i];
	}
	cnt=0;
	discrete();
	for(int i=1;i<=n;i++) mp[query(c[i])]++;
	build(1 , 1 , cnt);
//	cout<<cnt<<"--"<<endl;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		sum=0;
		ask(1 , query(c[i])+1 , cnt);
		ans+=sum;
//		cout<<sum<<endl;
		change(1 , query(c[i]));
	}
	cout<<ans<<endl;
	
	return 0;
}
一句话题解：
A题：就是简单的逻辑dp，dp[i][j]表示修改到第i个字符，可跳过j个字符情况的最优ans ，我觉得难点就在写的麻烦。。思路挺明了的。时间复杂度o（n）
B题cf*800：跑两个最大值就出来了，奇数位和偶数位最大值，也是一种贪心吧算是，不细说了，看到做法就应该明白了。时间复杂度o（n）
C题：纯dfs暴力，dfs出所有可能出现的字符串（我加了个去重怕超时实际好像不用）时间复杂度o（2的slen-1次方（由组合定理可知））
D题：权值线段树板子题，离散化 ，建立空树，出现一个数插入一个数，维护数字的出现次数，未出现次数以及总个数，查询的时候找某个数字比他大的数字的出现过的次数*未出现过的次数的和就可以了时间复杂度o（nlogn）；



#网易笔试#
全部评论
终于看懂了线段树，原来是预先求出所有数的出现次数，这样就维护左次数就行了。
点赞 回复 分享
发布于 2022-08-22 17:29 湖南
A题麻烦了？直接贪心构造。奇串直接redered或dereder两种情况check一下，偶串枚举分割点变成两个奇串。。。
点赞 回复 分享
发布于 2022-08-22 09:07 上海

相关推荐

11-04 21:45
浙江大学 嵌入式工程师
嵌入式女工程师在私企的工作强度
嵌入式女工程师刚入职五个月，分享一下我在私企工作的强度，👇🏻下面是我的一天：7:50：起床时间到，真的起不来一点。8:15：准时出门，骑上我心爱的小电驴（化妆是不可能画的）8:30：抵达公司，准时打卡。然后去吃早饭（但是公司早饭有点点难吃）9:00：开始到工位干活，一般是不定时干以下事情：1.写代码：如果有新需求烦躁程度：⭐⭐一般来说，只要明确了需求，写代码过程并不是最烦躁的，只需要按部就班即可。最烦躁的在下面：2.验证代码：把写好的代码自己先烧录到机器里验证烦躁程度：⭐⭐⭐因为一定会有bug！大概率还是我太菜了，一次性完美没bug的情况简直是少之又少，一直调试找bug3.拉通对齐开会：跟...
牛客激励计划
点赞 评论 收藏
分享
10-30 11:14
思特奇_招聘经理
点赞 评论 收藏
分享
09-26 14:34
浙大宁波理工学院 Java
26届学院本只能试试转正实习了
太难了学院本😭
WhiteAlbum...：学院本2中大厂垂直实习➕acm比赛 秋招0面试
点赞 评论 收藏
分享
09-19 12:15
门头沟学院 Java
等阿里和字节的就可以打牌了
迷茫的大四🐶：这下是真的打牌了，我可以用感谢信和佬一起打牌吗
点赞 评论 收藏
分享
10-31 21:09
快手_机器学习算法部_机器学习算法工程师(准入职员工)
霸王茶姬内推，霸王茶姬内推码
市场部/管培生/运营岗📖&nbsp;1.&nbsp;HR初面（电话/视频）：基础筛选，约20分钟&nbsp;2.&nbsp;部门主管复试（现场/视频）：专业能力考核，约30-40分钟&nbsp;3.&nbsp;总经办终面（现场）：综合评估与岗位匹配度，约20分钟&nbsp;TL参考：投递→1天内HR面→3天内复试→终面→2-3天出结果&nbsp;-&nbsp;“简单自我介绍一下”&nbsp;✅&nbsp;重点：突出与岗位相关的经历（如活动策划、数据分析），结合品牌调性（国风、年轻化）举例。&nbsp;-&nbsp;“你了解霸王茶姬吗？最近的市场热点是什么？”&nbsp;✅&nbsp;必答知识点：&nbsp;-&nbsp;品牌定位：“原味鲜奶茶”赛道，对标星巴克的“东方茶饮文化”&nbsp;-&nbsp;爆款单品：伯牙绝弦（年销1亿杯+）&nbsp;-&nbsp;近期热点：春节翻译争议（Lunar&nbsp;...
投递大连飞创信息技术有限公司等公司10个岗位
点赞 评论 收藏
分享
评论
10
22
分享

招聘动态

查看更多

字节跳动火山引擎

2026校园招聘

联想

2026届校园招聘

字节跳动

2026校园招聘

联想

26届AI专项｜内推码NK2026

快手

2026届校园招聘

中欧基金

2026届卓越之星校招

联想

2026届校园招聘

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 我来点评面试官 #
8564次浏览 73人参与
# 工作后，谈恋爱还和学生时代一样吗？ #
38533次浏览 363人参与
# 京东开奖 #
445069次浏览 2497人参与
# 今年秋招是回暖还是遇冷 #
18163次浏览 113人参与
# 你的领导最像哪种动物，为什么? #
23382次浏览 132人参与
# 你实习是赚钱了还是亏钱了？ #
18388次浏览 174人参与
# 阿里云工作体验 #
31254次浏览 106人参与
# 职场破冰，你们都聊什么？ #
28041次浏览 149人参与
# 秋招开始捡漏了吗 #
57657次浏览 399人参与
# 来聊聊你目前的求职进展 #
685870次浏览 6921人参与
# 用一句话形容你的团队氛围 #
11544次浏览 138人参与
# 我的AI电子员工 #
20533次浏览 151人参与
# 找工作八股要背到什么程度？ #
10280次浏览 174人参与
# 同bg的你秋招战况如何？ #
165731次浏览 961人参与
# 上班摸鱼，你都在干些什么？ #
28563次浏览 223人参与
# 毕业论文进行时 #
1332次浏览 19人参与
# 教师节，你送祝福了吗 #
10672次浏览 75人参与
# 你找工作是从容有余 or 匆忙滚爬？ #
6408次浏览 69人参与
# 三一重工求职进展汇总 #
22175次浏览 82人参与
# 上班后，才发现大学__白学了 #
10217次浏览 63人参与
# 三一集团提前批进度交流 #
39783次浏览 228人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务