咕咕咕~ A. 第k小数 （快排，STL之nth_element） 题意： 给定一个序列，求第k小数的值。 思路： 1.会把sort卡掉，可以用快速排序的思想来做。 2 .C++的STL里有一个 nth_element ，可以线性寻找第k小数，get了。 代码： 1 . https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43822588  2 . const int maxn=5e6+100; int a[maxn],n; int main(){ int T=read(); while(T--){ int n,k;...

2020年春混合个人训练第三十场 感觉题都很好就是我不会qwq 问题 A: 选举 时间限制: 1 Sec 内存限制: 128 MB提交 状态 题目描述 C国的总统选举委员会最近遇到了一些麻烦。他们在统计各省对H先生的支持率（百分比）时，把支持率四舍五入到了整数。等他们公布结果后，该国媒体发现这些省份的支持率之和不等于100（百分比）！在媒体黑幕声的质疑下，他们不得不找你寻求帮助。你将得到各省四舍五入后的支持率，请计算这些省份的支持率在四舍五入前的和是否可能等于100？支持率是以百分比的形式统计的。请注意，各省的支持率可以是一个包含任意多位的有限小数。一个小数在四舍五入到整数时，若小数点后第一位...

图论——负环与01分数规划 Sightseeing Cows 思路： 01分数规划可以考虑二分答案，先判断边界的范围是（0，1000 ] 再来看二分的过程。 关键就在于判断是否存在一个环点权之和/边权之和>mid，此时答案在右半区间，否则答案在左半区间。 整理一下式子会发现    因为本题里既有点权又有边权，我们可以考虑把每个点的点权放到出边上。即 即把每条边的权重看作是f[i] - mid * t[i] ，问题即转化为图中是否存在正环。 思想跟求负环一样的。 代码： #include<bits/stdc++.h> using namespace std; const int...

图论——负环以及玄学优化 负环的定义 一个图中存在一个环，里面包含的边的边权总和<0 。在含有负环的图，是无法求出最短路的，因为只要是重复走这个环，最短路就会不断缩小。 负环的求法 基于Bellman-Ford算法 若n次迭代，算法仍旧未结束，则图中存在负环，反正咋不存在负环。 基于SPFA算法。 1.统计每个点入队的次数，如果某个点入队n次（也可以大于），说明存在负环。 2.统计当前每个点的最短路所包含的边数，如果某点的最短路包含的边数>=n，说明存在负环。 关于算法2，进阶指南的解释如下： 根据抽屉原理，如果某点的最短路包含的边数>=n,那么这条最短路必然重复经过某个点p...

题意： 有n个建筑需要修理，修理需要时间，如果在限制时间里没有修理完成，就报废了。问最多能够修理多少个建筑。 思路： 贪心。先按时间限制从小到大排序，对于某个建筑，不能修理的话就跟之前修理并且修理花费时间最长比较，如果前者花费时间小，就将后者移除。 维护修理花费时间可以用堆维护。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7; struct node{ ll t1,t2; bool operator < (const node &a...

牛客——货币系统（思维+DP） 题意： 求一个集合b，使得该集合能够表示出的数与给出的集合a能够表示出的数相同，输出该集合最少有多少个元素。 思路： 首先我们可以知道，如果集合里的一个数可以由集合里的其他数表示出来，那么前者就没有存在的必要了。 所以，在最优解里，集合b里面的元素一定是在集合a里的，因为只有这样，才能最小化集合b的元素个数。可以这样想，如果集合b里面的某个元素b[1]是由a[1] + a[2] 而来，而且a[1]、a[2]又可以由集合b的元素表示出来，那么b[1]的存在就没有意义了。 综上，可以从小到大排序后，判断a[i]能否被前面的数表示出来，如果可以的话，一定不选这个数；否...

牛客—— Protecting the Flowers （贪心） 题意： 农夫有n头牛在破坏花朵，每头牛每分钟破坏d[i]朵花，农夫把这头牛运回牛棚的时间为t[i]（单程）,问如何运才能使得被破坏的花最少。 思路： 考虑贪心。 其实贪心无非几种排序关键字，某单个数值，某些数值之加减乘除。 对于本题，我们选择完两个牛，无论怎么排序，时间都是(t[1]+t[2])*2,，对后续的时间没有影响，所以我们只需要考虑如何安排这两头牛的顺序使得花被破坏的最少。 在两头牛中考虑的话，假设这两头牛为牛1和牛2，不难想到可以根据单位时间破坏花的数量来进行从大到小的排序，首先送走的是单位时间破坏花的数量最多的牛才...

这两种都是BFS的优化方法。 双向广搜 相当于从起点和终点轮流进行扩展，最后如果两边各自有一个状态发生重复的话，说明这两个搜索过程相遇了，由此可以合并出起点到终点的最小步数。 一般适用于最小步数模型，即把这个状态看做无向图的一个点。 再有一个小优化就是每一次扩展时选择当前队列里元素个数较少的一方来扩展。 Nightmare Ⅱ 字串变换 A* 把BFS里的队列改为优先队列（小根堆），每次取优先队列的队头元素。 存储的时候存储从起点到当前点的真实距离和从当前点到终点的估价距离。 排序关键字是两个距离之和，估计的是当前这条路径从起点到终点的估价距离。 A*就是在扩展时每次都选择两个距离之和最小的点...

矩阵距离（多源BFS） 题意： 给定一个01矩阵，求每个位置到所有1的最短曼哈顿距离。 思路： 朴素的做法是分别以每个1为起点遍历一遍，最后保留最小值，时间复杂度O（n^2）。 在图论里，如果求所有点到最近起点的最短距离，可以建立一个虚拟源点，从虚拟源点往每个起点连一条边权为0的边，这时候再求一遍最短路即可。 借鉴上述思想，我们可以只需要把所有起点的距离都初始化为0，再把所有起点都放入队列里，这样就可以求得到最近起点的最短距离。 关于该题的读入，可以使用字符串读入，也可以使用代码里的%1d读入。 代码：https://ac.nowcoder.com/acm/contest/view-submi...

Codeforces Round #644 (Div. 3)  A. Minimal Square  题意： 给定一个矩形，长宽分别是a,b。求一个最小的正方形，使得其能够包含两个这样的矩形。求出其面积。 思路： 假设长是a，宽是b，考虑2b和a之间的大小关系即可。因为要可以包含两个矩形，所以不难推出max（2*b,a）就是正方形的边长。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=50; void AC(){ int n;cin>>n; wh...

[CQOI2009]中位数图 （思维） 思路： 感觉这个题很偏向思维，原谅本蒟蒻看了题解后才想明白。 首先要考虑到的就是题目中的大小关系都只是一个相对的关系，所以大于b的数对答案的贡献都是一样的，小于b的数对答案的贡献都是一样的。不妨就设大于b的数的值为1，小于b的数的值为-1，等于b的数的值为0。 所以问题就转化成了求一个区间和为0的而且内部元素有0的长度为奇数的区间个数。 因为1和-1要相互抵消，而区间内又必须含有0，所以区间的长度就一定是奇数。 所以可以以0为起点，分别统计前后缀，前缀和为x时，后缀和一定为-x才能符合题意。所以分别用l,r两个数组表示和为x的数的个数，最后遍历一遍求出结...

UP:好像01的东西都会有些奇奇怪怪的优化，比如双端队列BFS就是一个很秀的算法。https://blog.csdn.net/weixin_45675097/article/details/106265696 前言：（bitset的学习） 很容易看出来是背包问题，我们用dp[i] [j] 表示只由前i个数字构成j，分界点就是第i个数字是否选择。当dp[i-1] [j-x*x ]==1时可以转移到dp[i] [j] 。但这样的话复杂度就是O（n^5），有些爆表了。 根据雨巨的思路，可以用bitset来优化，bitset就是一个只含有0和1的类型，类似bool数组，但是空间出奇的小。 常用函数： ...

题意： 给定每个题可以解出（独立和偷听）的概率，求解出0~12题的概率。 思路： 首先可以算出每个题解出的概率，即1-解不出该题的概率，即 ///计算独立的每道题解出来的概率 for(int i=1;i<=12;i++){ double tmp=(1-a[i])*(1-b[i])*(1-c[i]); ac[i]=1-tmp; } 再考虑如何计算解出0~12题的概率。因为数据范围很友好，可以用dfs或状压枚举或dp。 思路一：DP 考虑用dp[i] [j]表示只做前i个题做对了j个题的概率。那么很容易可以推出分界点就是第i个题是否做对。 如果第i个题做不对，那么dp[i] [j]就可以由d...

算法周周练7 （EAD） E：数字比较 思路：x,y范围都是1e9，而且还是计算次方，直接计算肯定是不行的。根据高中数学知识，可以两边同时取对数，就化成了比较ylogx和xlogy的大小。 代码： ///ylogx和xlogy #include<bits/stdc++.h> typedef long long ll; using namespace std; int main(){ ll x,y; cin>>x>>y; ll a=y*log(x); ll b=x*log(y); if(a==b) puts("="); else if(a>b) puts...