添加链接描述 对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。 看例子 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 （已按大小排序） 假设对于第一组 取了前面3个，后面2个，然后其从很小到大排序，后面一组只可能是取前面2个，后面3个，从大到小排序。那么对于第一组的前3个（顺序）与后面一组的前3个（逆序），必然是第一组的前三个都是a，后面一组的前三个都是b,然后对于第一组后两个，和后一组后两个，第一组后两个必然是b,后一组后两个必然是a。将绝对值去掉一组的差值就等于b1+b2+b3+b4+b5-a1-a2-a3-a4-a5，所有情况...

题目 首先每个礼物被抽到的概率不是均等的，是先从n个人里等概率选出一个人，再从k个礼物等概率选出一个礼物，第1个人每个礼物选中概率1/(nk1) 第二人 1/(nk2)。对于一个礼物c产生的贡献= (1/(nki))【其被选中的概率】(num[c]/n)【正确给到孩子的概率】，需要先记录出每个礼物对应几个孩子，即该礼物的数量。把分母用逆元算即可。 Code: #include<iostream> #include<algorithm> #include<cmath> #include<iomanip> #include<map>...

题目 当能直接唱完就输出0。 当不能时从开始遍历相加直到sum>s,取前面最大值的那个下标，因为减去最大才更有利于后面唱的片段最多。 但要注意下范围：跳过片段该遍历到哪？跳过之后若想能比不跳过多，则需至少到达s+2（无跳过时s是最大不超出的片段数），因为跳过一个则需到s+1才和原来的片段相等，要大于需s+2。所以我们要找到从1—s+1中的最大数下标。 Code: #include<iostream> #include<algorithm> #include<cmath> #include<iomanip> #include<ma...

题目 很容易想到用堆处理，但会有操作使得数值远大于long long.此时灵活将范围缩小，细节见代码。 #include<iostream> #include<stack> using namespace std; typedef long long ll; const ll Max = pow(2, 32) - 1; stack<ll> sta; int main() { ll a = 0; int t;cin >> t; ll sum = 1; ll ans = 0; int f = 0; sta.push(1); ...

题目 分块整除⌈x+d/（x+1）​⌉=⌊x+(d+x)/(x+1)​⌋=1+⌊x+(d−1)/(x+1)​⌋ Code: #include<iostream> #include<cmath> using namespace std; typedef long long ll; const int Max = 1e6 + 5; const int Mod = 1e9 + 7; int main() { int t;cin >> t; while (t--) { int n, d;cin >> n >&gt...

题目 a * b+a+b=a * 10^n+b a * b+a=a*10^n b+1=10^n 故b=9 99 999 9999… 都满足情况，答案为a的个数乘1 —B中满足条件的b的数目 #include<iostream> #include<cmath> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll a[Max], b[Max], lst[Max]; int main() { int t;cin >> t; while (t--) { ...

题目 a[i][j] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目 b[i][j] 表示前i个数字中第i个数字为j的所有情况的非递增序列的数目 对于非递减数列aa，和非递增数列bb，只要第一个元素满足aa[1]>=bb[1]整个数列就满足aa中个元素>=bb中对应元素了。那么只需枚举a中第一个元素所有可能与之相对应满足条件的b中第一个元素即可。 另：递增序列第一个数字为j的所有情况=递减序列最后一个数字为j的所有情况 ，递减序列同理 Code #include<iostream> #include<cmath> using names...

题目 思路：二分每条绳子的长度，循环100次即可。 判断条件：每一段向下取整求最大可以裁剪的数量，如果所有数量大于等于k则满足l=mid,小于则不满足r=mid。使用流输出还需注意cout规定小数精度后是四舍五入的，但printf是只截取前多少位。 #include<iostream> #include<cmath> #include<iomanip> using namespace std; typedef long long ll; const int Max = 1e6 + 5; double lst[Max]; int n, k; int c(...

题目 二分距离 判断条件就是从一开始每发现一个>=d时放一头牛，如果能全部放完l=mid,否r=mid-1,mid=(l+r+1)/2。 #include<iostream> #include<cmath> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; const int Max = 1e6 + 5; double lst[Max]; int n, m, x; int check(int d) { ...

题目 一层层推导下去很容易发现规律，a[i]=2*a[i-2]+a[i-1]，看下面这张图，标着的序号代表以这个顶点为根的整颗子树所对应的阶次。6由两个4一个5组成，5由两个3一个4组成。那涂色得到的答案不就是上方的公式吗？但答案去是不对的，这还忽略了一个claw树，当达到6阶层时按照如下涂红色的去取会发现还多了一个claw，就是最上面的那个4个点，那么我们现在只要找到什么时候还要给答案加一个claw即可，当我们要求第i阶层时会发现只有当i-1 与 i-2最上面的点都是不取时可以多构成一个claw，然后相应的第i第阶层最上面的点变成取用状态，那我们只需额外去记录前两个的阶层最上面点是空还是不...

题目 预先做好一个所有偶数与前一个数差值和3以后奇数a[i]和前一个数差值的前缀和b[i]（代表插入数后的情况），然后遍历插入到所有数后面的情况，假设插入到第i个数那么前i个数的贡献用a[i-1]表示，插入中间的贡献用lst[i]-lst[i-1]-1表示，后面的贡献用b[n+2]-b[i]表示，算出最大贡献即可。 Code: #include<iostream> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll a[Max], b[Max], lst[Max]; int main(...

题目 两种解法： 1.用差分思想，l—r所有点加1用map[l]+1,mdp[r+1]-1表示，前缀和即是当前点所对应覆盖线段数。 Code: #include<iostream> #include<stack> #include<map> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll a[Max], b[Max]; pair<ll, ll> ls...

题目 思路：直接暴力从给出的时间一分钟一分钟加到第二天，判断条件为：如果之前时间有3,4,6,7,9直接排除（倒转后改时间无效），如果倒转后时间大于给出的时间范围也无效（倒转中单个数字变化为2->5 5->2 1,0,8不变，再让全部数字倒置一下），如果有满足条件则输出，没有则输出00：00. Code: #include<iostream> #include<cmath> #include<iomanip> #include<algorithm> #include<map> using namespace std;...

转载 https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html