题意 有n（2<=n<=8000)只奶牛，每只奶牛都有一个1到n的编号；站成一排，对于第i只奶牛，给出在它之前且编号小于它的奶牛的数量，求这一排每只奶牛的编号。（由于第一只奶牛前面一定没有奶牛，故输入仅给出n-1个数） 解题思路 看到dalao们在用主席树，二分+树状数组，我只能说，我不会啊啊啊！！〒▽〒 但是，不要停下来啊我们来模拟一下样例，一共有5只奶牛，我们记录一下放入的是第几只奶牛对于第一只奶牛，在它之前没有奶牛，便直接放入：1对于第二只奶牛，由样例，在它之前有1只奶牛编号比它小，在它之前实际也只有一只奶牛，便排到末尾：1 2对于第三只奶牛，由样例，在它之前有2只奶...

题目描述 解题思路 每次操作需要将一个球拿出来然后放在最上面，观察一下，我们发现按照题目中给出的顺序排列即消耗体力最少，因为若在第一次操作的小球上面还有球，则在移动第一次操作的小球时，就会另加上最上面的小球的重量，同理在给出的序列的其他地方插入小球，也会使消耗体力增加。 顺序有了，模拟一下即可得出结果。假设i，j为相同类型的小球，操作序列为。。。i。。。。j。。。，那么取j球时所花的体力为i的后一个球到j球的重量和；我们可以开一个数组，存该类型的球上一次出现的位置。 但是 还有一个坑点，从i到j遍历时，可能有一种类型的球出现了多次，但该球只能做一次贡献(o_ _)ﾉ AC代码 #i...

存一下单调队列板子 题意 一个长度为n的序列，求每k个连续的元素的最大值和最小值。 解题思路 用两遍单调队列分别维护最大值和最小值。 AC代码 #include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int a[1000010],que[1000010]; //单调队列中存数组下标 int main() { ios::sync_with_stdio(false); cin.tie(0); co...

前言 比赛的时候只得了80分，想不出怎么优化，看了榜1大佬的思路明白了一些东西，才有了这篇题解(⊙﹏⊙) 题目描述 解题思路 1.容易看出，我们可以将数组排序后，进行dp，假设当前位置是第i个数，可以枚举前i-1个数，取与i的最大公约数大于1的数j，则f[i]=max(f[i],f[j]+1).这样可以得80分。(其余两个点超时)2.接下来就需要考虑怎样优化dp的过程，暴力的方法一大部分时间花在了枚举前i-1个数上，如果我们分解质因数，每次转移只需要枚举这个数的质因子即可。 AC代码 #include <bits/stdc++.h> #define io ios::sync_w...

题目描述 1到9每种牌各有k张，T和A各得到5张，其中4张明确，1张不明确，求T获胜的概率。 解题思路 1.结果为T获胜的情况数除（9k-8)*（9k-9)。2.数据范围很小，可以直接枚举T和A的第五个数，计算T和A的分数。3.若T的分数大，设T选i，A选j，则对结果的贡献为i的个数乘j的个数，但若i=j，则则对结果的贡献为i的个数乘（j的个数-1）。 AC代码 #include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ...

解题思路 1.只有有两个及以上不同质因子的数才会有贡献2.对于最小公倍数，若将每个数质因数分解，最小公倍数即为每一个质因子的最高幂次相乘，可用线性筛筛取素数3.如何确定每一个质因子的最高幂次，因为该数要有两个及以上不同质因子，可将其乘以除他之外最小的素数确定，如：确定2的最高幂次可乘以3，最高幂次为对n/3取对数；确定5的最高幂次可乘以2，最高幂次为对n/2取对数4.最后一点，用线性筛筛素数时，不必筛到n，因为如果一个素数大于n/2，那么由他组成的有两个及以上不同质因子的数必定大于n，即线性筛筛到n/2即可 AC代码 #include <bits/stdc++.h> #define...

解题思路 求每一个数的最小质因子，想到了雨巨讲的线性筛。借这个题存一下线性筛模板 int v[maxn]; //存放每个数的最小质因子 int prime[maxn]; //存放素数 int cnt; //素数个数 for(int i=2;i<=n;i++){ if(v[i]==0){ v[i]=i; prime[++cnt]=i; //如果这个数没有被访问过，则为素数，存下来 } for(int j=1;j<=cnt;j++){ //遍历已经存的素数，将其作为最小质因子筛去合数 ...

题意 珂朵莉给了你一个序列，求出每个子区间的逆序对个数，然后加起来输出对于100%的数据，n <=1000000 ,0 <= 序列中每个数 <= 1000000000 解题思路 树状数组+离散化先考虑简单的问题，如果是单独求逆序对，即离散化之后，边往树状数组中插元素边统计逆序对该题要统计所有区间的逆序对首先考虑如果一对元素....ai....aj...构成逆序对会为结果贡献多少个逆序对？当然是包含ai，aj的子区间的个数在ai前面有i-1 个元素，aj后面有n-j个元素，即子区间个数为i（n-j+1）个接下来列举几个例子试一下发现，如果ai，ak都与aj构成逆序对，那么结果为...