NC19814 最短路 题目地址： https://ac.nowcoder.com/acm/problem/19814 基本思路： 题意很明了就是让我们每次在图中查询任意两点的最短路。数据范围很大肯定不能使用算法，而且也不是树同样也不能使用快速求树上距离，但是题目保证了图联通，而且数据范围里，因此我们可以将这个联通图看做一棵树加上了一些边。那么首先我们对图跑一个生成树，将这些多出来的边先放在一边，单单对于树的部分，我们先用求树上距离的方法计算出的树上距离;然后我们将这些多出来的边加回来，然后对于每条边我们暴力找它的一个端点跑一遍单源最短路(边权为直接)，然后每次再用更新,的最小最短路就...

C 公因子 题目地址： https://ac.nowcoder.com/acm/contest/6112/C 基本思路： 我们根据多个数的性质,;我们容易发现，对所有数是不会影响后面那部分差分值的结果的;所以后面那部分差分值的其实就是我们能得到的最大;要找的其实就是要在数组的所有数中任选一个数使他成为这个的倍数，需要加的最小值;那么按照上面的意思模拟一遍就能得到答案了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #...

B 异或图 题目地址： https://ac.nowcoder.com/acm/contest/6112/B 基本思路： 这题的数据范围比较大有点卡常 #define int long long 成功让我T了五次，我以后再也不偷懒了QAQ; 这题我们稍做观察可以就可以发现，,两个位置要能联通，那么要么是就是，这时一步就能到达;要么必须是这时如果我们有一个中间位置，这个位置和或的异或是，就也能到达，这时的最短路长是2;除了这两种情况之外，根据异或运算的性质和举例尝试我们能发现不会再有其他情况可以到达了。所以每次对以上情况进行判断就是了。 参考代码： #pragma GCC optim...

A平方数 题目地址： https://ac.nowcoder.com/acm/contest/6112/A 基本思路： 的范围是,所以我们枚举以内的数将它们的平方数打出来，然后对于每个我们二分查找，然后在找到的位置附近暴力找的最小值就是了。写复杂了，由于并没有多次查询，所以不用二分直接找也可以。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(fa...

NC23413 小A买彩票 题目地址： https://ac.nowcoder.com/acm/problem/23413 基本思路： 要计算不亏本的概率，那么很基本的我们考虑将买张彩票所有可能的最终中奖金额和每个中奖金额的次数给记录，那么不亏本的情况次数去除以所有中奖情况次数就是不亏本的概率了。 那么如何求所有的可能中奖金额和次数，考虑一个简单的，设表示买张彩票，中奖金额为的情况次数，那么可以得到转移方程: 。最终获奖金额在以上的就是不亏本的了，所以最终答案就是: 上下除以化简就是答案了。 参考代码： #pragma GCC optimize(2) #pragma GCC op...

Forsaken喜欢数论 题目地址： https://ac.nowcoder.com/acm/problem/53079 基本思路： 其实就是一个素数筛，我们想一下在埃氏筛法的过程中，我们是从小到大的对于每个质数，将它的倍数都筛掉，那么这个质数其实就是这些被筛掉的非质数的质因子，并且由于我们是从小到大遍历的，所以很明显先出现的就是最小质因子，因此每次筛去非质数的时候累加这个质数就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespac...

B 一章 题目地址： https://ac.nowcoder.com/acm/contest/6012/B 基本思路： 分情况构造，我们先想如何在不制造出割边的情况下制造出割点，和在不制造出割点的情况下制造出割边。 在不制造出割边的情况下制造出割点，我们考虑让割点出现在两个三元环之间，也就是下面这个情况。 在不制造出割点的情况下制造出割边，我们尝试一下在割边只有一条的情况里是可以出现的，也就是两个点直接相连的情况。但是其余情况下，我们发现要出现割边，至少会生成一个割点，也就是下面的情况。 那么在既有割点又有割边的情况里我们就能这样构造。 然后再将上面推断中的几种特殊情况判断一...

NC18386 字符串 题目地址： https://ac.nowcoder.com/acm/problem/18386 基本思路： 比较明显的一个尺取，枚举左指针，然后将右指针向后试探，记录个字母的出现次数，每次一下子串是否合法，取合法子串的最短长度就好了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false) #define int lo...

C 二维动点 题目地址： https://ac.nowcoder.com/acm/contest/5961/C 基本思路： 这道题难点在分类讨论和细节，特别注意这句话"选择一个不和当前所在位置重叠的点"。 那么考虑一下答案有几种可能，并且分别会在什么情况出现： (1).首先如果终点就是那么很明显答案就是; (2).如果终点在其中一个点和起点的连线上那么明显移动次就能到达，这个情况我们用直接记录斜率就行了，记住不要记浮点数，除记录最简分数的，防止丢精度。 (3). 然后如果存在两个点，这两个点中的一个和起点的连线，和另一个点和终点的连线相交，那么我们到达交点，然后从这个交点位置就能抵达终...

NC17315 背包 题目地址： https://ac.nowcoder.com/acm/problem/17315 基本思路： 这道题我们要分类讨论，先看为奇数的情况: 我们考虑先按照物品价值排序物品，那么要找最大中位数就是确定一个位置，如果这个位置能作为中位数，那么也就是说它左边的个物品的最小重量，右边的个物品的最小重量和自身重量的和一定要小于等于背包容量。 我们考虑如何求左边的个物品的最小重量，和右边的个物品的最小重量，这个实际上我们只要使用优先队列优化一下前后缀和，在达到数量的情况下，每次去掉队列里最大的元素就行了。 但是我们看为偶数的情况： 这个情况下我们同样先确定左边个物品...

NC19158 失衡天平 题目地址： https://ac.nowcoder.com/acm/problem/19158 基本思路： 这道题我们首先要证明一件事情，就是最终能被拿走的武器总重量一定是能在一次内拿走的。 本来想证明一下，可是发现自己太菜了好像证不来QAQ，但是多带几个数据并且脑补一下基本上还是能确定这个结论的正确性的。 那么接下来就是思路比较清晰的，我们设表示加到第个物品，左右物品间的绝对差是，那么对于每个物品我们就有不加入，加入左边，加入右边这三种状态。 那么根据以上容易得到转移方程: 。 那么最终答案。 参考代码： #pragma GCC optimize(2) ...

NC113552 Steps to One 题目地址： https://ac.nowcoder.com/acm/problem/113552 基本题意： 给定一个空集合，和一个数;每次等概率的从中选择一个数加入集合;如果集合里所有数的不等于就一直加入直到为为止;求结束时集合的期望大小。 基本思路： 有一说一我数论确实一窍不通，真的是鼓起了很大的勇气来挑战这道题，这里记录一下自己一步步分析的过程。 首先我们，设记录集合为时的集合期望大小(也就是操作步数)，那么我们从小的往大的方向转移，就应该能得到这样的转移方程 : ，我们思考 一定是恒成立的，而由于时是自己转移自己，所以要分的情...

L Sumo and Coins 题目地址： https://ac.nowcoder.com/acm/contest/5954/L 基本思路： 首先我们可以把翻转次转换为翻转一次，这样我们能明确NULL这种情况是不可能发生的，然后如果n是偶数那么我们思考一下一定是能做到ALL的，但是如果n是奇数，我们可以带几个数字试一下，我们能发现只能将初始偶数个的那一面全部翻到另一面，也就是哪一面初始为奇数那么就能全部翻转到哪一面。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h&g...

J Sumo and Balloon 题目地址： https://ac.nowcoder.com/acm/contest/5954/J 基本思路： 计算几何，难点主要是确定嘴到墙面的距离是多少，也就是要算一个点到平面的距离。这个其实我们根据高中的几何知识就能求解了(我直接套板子了不愿推了，大家可以推一下OWO)。然后这个距离其实就是球的最大直径，知道了这个接下来根据球的体积公式就能直接运算了，我这里想多了还写了个二分，二分了吹气的秒数，大家不要学。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <...