#网易笔试# 记：4.18网易互娱笔试满分，官网流程结束“笔试不通过”🤣🤣太搞了

题目：https://ac.nowcoder.com/acm/problem/112558题意：t次询问[x,p,k]，找出比x大且与p互质的第k个数分析： 假设答案为ans，那么就是求[x+1,ans]之间恰好有k个数与p互质，同时ans刚好要与p互质； 范围为1e6，同时随着ans的增大与p互质个数只会越来越大，满足单调性，所以考虑二分ans； 关于二分的solve，我们可以求出[1,x]之间与p互质的个数，这个枚举p的因子容斥解决就行，ans也同理，接着只要判断俩者的差是否大于等于k，逼近k就行。 #include<bits/stdc++.h> using namespa...

题意：算出树上长度为2的权值和最大权值分析： 长度为2的路径可以把它标识为经过某一点，那么统计和计算就简单多了，直接枚举点，然后该点的儿子就俩俩组成长度为2的路径。 #include<bits/stdc++.h> using namespace std; #define pb push_back #define MP make_pair #define lson root<<1,l,midd #define rson root<<1|1,midd+1,r typedef long long ll; const int mod=10007; const ...

前置知识：01trie树分析： 01trie树提供给我们的功能为我们塞进去一些数，然后我们可以logn内查询与其最大的异或和值。 那不刚好可以满足我们o（n^2）暴力吗。。 #include<bits/stdc++.h> typedef long double ld; #define INF (1ll<<60)-1 const int M=1e6+6; #define MP make_pair #define pb push_back using namespace std; const int N=1e5+5; int num[M],cnt=1; int d[M]...

题：https://ac.nowcoder.com/acm/problem/110867题意：给定n个数序列，m个询问[l,r]问l~r中距离最短的且a[x]==ay，输出最短距离（n,m<=5e5）分析： 同一种数的话只需要和其相邻比较； 其次，思考怎么这个pair会在选定的范围内； 考虑离线处理查询，以r作为排序基准，那么只需要在某对pair的左边处添加这对pair的贡献，然后线段树搜查询范围查询[l,r]最小值即可。 时间复杂度：mlogn+nlogn （主要思考：区间贡献询问到且不影响区间查询）Code： #include<bits/stdc++.h> using...

题目：https://ac.nowcoder.com/acm/problem/110615题意：给定a数组，可操作m次让w个连续的位置+1，问最大化的最小值是多少。分析： 明显，最小值越大越难满足，满足单调性，考虑二分； check就从前往后考虑当前位置是否满足最小，不满足则选择以当前位置为连续区间的开始w连续个加1（这里我用线段树怎么都过不了。。）用BIT实现。 #include<bits/stdc++.h> using namespace std; #define pb push_back #define MP make_pair #define lson root...

题：https://ac.nowcoder.com/acm/problem/24950题意：给n点，m边无向图，dis[u,v]代表从u到v的路径上边的最大值，现在给定整数k，代表可以抵消掉k条边，问dis[1,n]的最小值。分析：n<=1000,不能直接地对原图进行最短路，我们可以考虑二分考虑答案midd；那么我们把图上边大于midd的边设为权值为1，其余为0；那么走这个图的最短路，就是找最少数量的边大于midd，midd越小最少数量最多，也满足二分的单调性。CODE: #include<bits/stdc++.h> using namespace std; #define...

题目：道路和航线题：https://ac.nowcoder.com/acm/problem/50381题意：给定有向边（可负权边），无向边（不可负权边），问从S点到任意一点的最短路边权，若不能到达则输出“NO PATH”分析：负权边不可用dijkstra最短路来求，只能依靠spfa来求，其中queue版本会超时，所以采用deque版本来优化。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #inclu...