嘻嘻嘻嘻嘻嘻嘻

分类

题解(7)

/ 注册

全部文章（共7篇）

[题解]List Of Integers

题目：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互...

2020-09-24

3 791

[题解]联合权值

题意：算出树上长度为2的权值和最大权值分析：长度为2的路径可以把它标识为经过某一点，那么统计和计算就简单多了，直接枚举点，然后该点的儿子就俩俩组成长度为2的路径。 #include<bits/stdc++.h> using namespace std; #define pb pu...

2020-09-17

1 714

【题解】The XOR-longest Path

前置知识：01trie树分析： 01trie树提供给我们的功能为我们塞进去一些数，然后我们可以logn内查询与其最大的异或和值。那不刚好可以满足我们o（n^2）暴力吗。。 #include<bits/stdc++.h> typedef long double ld; #define...

2020-09-16

1 796

【题解】Closest Equals

题：https://ac.nowcoder.com/acm/problem/110867题意：给定n个数序列，m个询问[l,r]问l~r中距离最短的且a[x]==ay，输出最短距离（n,m<=5e5）分析：同一种数的话只需要和其相邻比较；其次，思考怎么这个pair会在选定的范围内；考虑...

2020-09-16

2 868

【题解】Present

题目：https://ac.nowcoder.com/acm/problem/110615题意：给定a数组，可操作m次让w个连续的位置+1，问最大化的最小值是多少。分析：明显，最小值越大越难满足，满足单调性，考虑二分； check就从前往后考虑当前位置是否满足最小，不满足则选择以当前位...

2020-09-15

1 636

【题解】Telephone Lines

题：https://ac.nowcoder.com/acm/problem/24950题意：给n点，m边无向图，dis[u,v]代表从u到v的路径上边的最大值，现在给定整数k，代表可以抵消掉k条边，问dis[1,n]的最小值。分析：n<=1000,不能直接地对原图进行最短路，我们可以考虑二分考...

2020-09-13

1 700

道路和航线题解

题目：道路和航线题：https://ac.nowcoder.com/acm/problem/50381题意：给定有向边（可负权边），无向边（不可负权边），问从S点到任意一点的最短路边权，若不能到达则输出“NO PATH”分析：负权边不可用dijkstra最短路来求，只能依靠spfa来求，其中queu...

2020-09-10

1 642