树状数组简单应用，逆序数转换为：求前i个数小于x的和。 #include<bits/stdc++.h> #define lowbit(x) x&(-x) using namespace std; typedef long long ll; const int maxn=2e5+10; int sum[maxn],cnt=maxn-1; void add( int x ) { while( x<=cnt ) sum[x]++,x+=lowbit(x); } int query( int x ,int ans=0 ) { while( x ) ans+=sum[x],...

大致题意： 给定 头牛，每头牛每分钟都会造成破坏 ，农夫可以将牛拉回牛栏里面花费的时间是 .请问农夫拉回牛的顺序是多少可以使得破坏最少。 分析：贪心。考虑第 头牛和第 头牛，哪头先拉入牛栏.如果 先 后，那么破坏为：.如果 先 后，那么破坏为： .要使得破坏程度最少，即：化简： 那么我们就按照上式子进行排序从小到大拉入牛进牛栏。然后依次算破坏程度即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; pair<int,int> ...

D. The Best Vacation 大致题意：规定一个日历有 个月，每个月有 天，在第 个月的第 天活动你可以获得 的贡献，你只能连续 天活动，请问你能获得的最大贡献是多少. 分析：方法一：尺取法.考虑我们选的天数是连续，那么对应月份也是连续的，并且假设中间月份的天数都是取得到的，但是还可以再两边去取天数，显然我们应该是去最左边的天数，因为贡献是从 开始递减的，而右边的天数是从 开始递增的。那么我们依次遍历月份，用双指针去维护可满足的连续天数并计算对应贡献.但是月份天数就跟环一样，是首尾相接的，对于环而言的尺取，我们一般都是多开一倍空间，数组循环一遍，然后从 的位置开始计算贡献(这样可...

题目大意：有n中货币，每种货币都有无限多个，问是否可以简化货币个数，使得能表示的数个数不变。 分析：容易想到货币中最小的面值肯定要留下，那么考虑第二小的货币是否可以去掉，如果第二小的货币是最小货币的倍数，那么就能去掉。那么考虑第i小的货币是否能够留下，那么我们是要查看已留下的货币能否表示当前的货币，那么这个就是一个多重背包问题。先将所有物品按照面值排序，然后从小到大枚举物品进行背包前判断改物品是否能被表示，如果可以那么这个物品就不拿， 否则进行背包。 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7...

题目大意：给定n个任务，每个任务完成所需时间和截止完成时间，求最多能完成多少个任务. 分析：考虑贪心策略。我们每次选择任务完成一定是要最后完成任务的时间尽可能的小，并且当前的时间加上完成当前选择任务的时间一定要小于任务的截止时间才有效。这个我们可以将所有任务按照截止时间排序。那么对于当前时间加上任务完成所需时间小于截止时间的任务可以直接进行完成。那么如果当前时间加上任务完成所需时间大于截止时间的时候，我们是否可以从已经完成任务中 选择一个最大完成任务所需时间的任务 踢出，然后将新任务加入进来.那么执行这种操作一定是要已完成的最大完成任务所需时间要大于将新任务完成的时间，这样可以使得当前完成所有...

题目大意：小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和 。后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间， 参考wxyww的优美代码. https://blog.nowcoder.net/n/b1816a1594eb41389e78659f45467d06 分析：异或和题目经典套路按二进制位进行计算。对每一个数进行二进制拆分，然后每一位依次做前缀和。 表示前i个长度为偶数的前缀区间异或值为j的个数是多少。并且由于区间长度必须是偶数，那么做前缀和的时候 应该由 进行转移累加.一个非常优美的实现就是前缀和从下标 开始进行。那么对于当前...

至少满足n个条件的方案数：https://ac.nowcoder.com/acm/contest/5633/D参考大佬博客：https://blog.nowcoder.net/n/198900626592405580362e442063bb76容斥: https://atcoder.jp/contests/abc172/tasks/abc172_e

A.第k小数 大致题意：多组输入，求序列中的第k小数。 分析：两种解法，一个是快速排序求第k小，一个是STL自带的nth_element函数，O(n)求第k小的. 快排求第k小...... #include<bits/stdc++.h> using namespace std; const int maxn=5e6+10; int arr[maxn]; inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ ...

大致题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 分析：将奇数序列排序，对于比中位数小的元素 和 比中位数大的元素 的个数是相同的，那么我们将比中位数小的元素 置为-1，比中位数大的元素置为1， 那么合法的序列就是序列元素和为0. 我们找到的合法的连续子序列一定是包含中位数b的，。假设中位数b的位置为 .左区间边界一定选择的是 中的位置。右区间边界一定选择的是 中的位置。 计算所有合法的区间， 那么我们只先标记中位数b到右区间可能位置的元素和，遍历 位置前缀和标记一遍. 然后再遍历左区间边界的所有可能...

A : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43814592B : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43814608C : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43797846D : https://ac.nowcoder.com/acm/contest/view-submission?submissionId=...

题目大意:给定一张个点 条边的无向图，小sun可以选择一个起始点出发，每次行走都是夸两条边行走，问小sun要遍历所有点，需要添加多少条边. 分析:题目没有说图一定连通，那么要遍历所有点肯定要使得图连通，那么要连通的加边数为：所有连通块的个数-1.加完边后，图上所有点都是连通的.假如图上没有环，那么每次跨两条边行走，可以证明能行走的点是图上点的一半.那么如何也能走到另一半的点呢。考虑图上有环，如果是偶环，举个例子:n=4,m=4,(1,2),(2,3),(3,4),(4,1).无论选择哪个点都只能走图上一半的点。我们考虑奇环，举个简单例子:n=3 m=3 (1,2) (2,3) (3,1) ....

题目大意:给定n个元素的序列，判断序列的所有连续的子序列是否全是好序列。好序列:序列存在唯一元素-------存在 满足序列中其他所有元素 ， . 分析:考虑对区间进行分治.首先是最大的区间 我们需要找到区间内唯一的元素，假如位置为 ,那么连续区间的左端点在选取,区间右端点在选取，所构成的区间一定是好区间，当然也包括 作为左区间边界或者右区间边界构成的区间，这些都是好序列.那么我们下一步要知道的是区间 区间中连续的子序列是否满足好序列.那么这个就是分治的递归.对于当前区间我们要找到是否有元素在该区间是唯一，然后进行分治判断即可.判断是否唯一，显然我们要预处理对于每一个元素作为唯一元素的连续...

一共有 n个数，第 i 个数是 可以取 中任意的一个值。设 ，求 S 种类数。 分析:分组背包问题，的值表示前i个数是否能表示j, 我们要求最后能表示的数的种类数，就是求 .考虑每一个dp状态只有两种0和1.那么我们可以用bitset优化背包，将第二维的值变成二进制下1的位置.那么转移状态: .那么最后的答案就是 的1的个数，直接调用count()计算即可。另外附一题同样的bitset背包优化的题. https://ac.nowcoder.com/acm/contest/4912/C题解暂时鸽了 #include<bits/stdc++.h> using namespa...

题目大意：12个题目，给定每个题目能做出来的概率，求总共做对 0-12 道题的概率.分析：一共12道题，我们可以二进制枚举做对题目的所有情况 ,然后每一种情况的算出做对题数的概率，然后累加输出即可. #include<bits/stdc++.h> using namespace std; const int maxn=2e5+10; double a[13][10]; double ans[13][10]; double res[13]; int main() { for( int i=1;i<=12;i++ ) cin>>a[i][0]; ...