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）；



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

相关推荐

11-20 09:10
电子科技大学 前端工程师
点赞 评论 收藏
分享
11-18 14:40
北京大学 算法工程师
在聚力智能的真实体验
工作时间是早九晚六，要打卡，但有时候下班急了忘打卡，还得找领导审批，请假也得审批，感觉啥都得报备。虽然我们用钉钉办公，但大家的沟通基本上都是在微信上，工作和生活完全搅在一起了。组里大部分同事都是中年人，幸好我的领导是个年轻人，沟通起来没啥障碍。工资方面，基本工资150加上30元餐补，其他福利就没啥了，连下午茶都没有。不过公司提供的设施还不错，有开水、冰箱、微波炉和咖啡机。我的领导很有经验，从大学就开始做PM，她对我的培养方式都是引导式的。虽然我一开始写的需求有点差，但她很耐心引导我思考，很尊重我的想法。这里几乎不加班，六点半的时候工区的灯都熄了，大家都准时下班，还是挺不错的
PPTV工作强度 3人发布 你最想要的公司福利是？
点赞 评论 收藏
分享
头像
11-21 11:39
四川大学 Java
结束一切
明年七月份去上班，爽玩大半年了
是红鸢啊：忘了还没结束，还有字节的5k 违约金
点赞 评论 收藏
分享
11-01 08:48
门头沟学院 C++
释放两个offer
给大伙儿释放两个of #美团# #招银网络#
伤心的候选人在吵架：佬你不要的，能不能拿户口本证明过户给我。。球球了
点赞 评论 收藏
分享
11-20 00:15
中南大学 PHP
点赞 评论 收藏
分享
10 22 评论
分享

招聘动态

查看更多

字节跳动

2025校园招聘

杉川机器人

2025校园招聘

快手Star

2025届招聘

快手

销售类投递专区

库洛游戏

全站热榜

正在热议
# 25届秋招总结 #
267694次浏览 2248人参与
# 学历or实习经历，哪个更重要 #
44071次浏览 333人参与
# 北方华创开奖 #
23833次浏览 260人参与
# 地方国企笔面经互助 #
2921次浏览 7人参与
# 你觉得专业和学校哪个对薪资影响最大 #
28381次浏览 213人参与
# 选完offer后，你后悔学本专业吗 #
13912次浏览 100人参与
# 0offer是寒冬太冷还是我太菜 #
888538次浏览 7915人参与
# 你最想要的公司福利是？ #
42343次浏览 151人参与
# 查收我的offer竞争力报告 #
20086次浏览 257人参与
# 如何一边实习一边秋招 #
987741次浏览 12610人参与
# 应届生被毁约被毁意向了怎么办 #
28403次浏览 244人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3376次浏览 36人参与
# 没有实习经历，还有机会进大厂吗 #
807494次浏览 13857人参与
# 来聊聊机械薪资天花板是哪家 #
66198次浏览 447人参与
# 面试体验感最好的是哪家？ #
83794次浏览 819人参与
# 机械应届生薪资要多少才合适？ #
12559次浏览 61人参与
# 如果公司降薪，你会跳槽吗？ #
24851次浏览 236人参与
# 如何写一份好简历 #
605567次浏览 8526人参与
# 秋招OC许愿 #
228571次浏览 1881人参与
# 寒假躺平还是提前实习 #
59688次浏览 458人参与
# 你认为第一份工作重要吗 #
5467次浏览 50人参与
牛客网
牛客企业服务