进同人圈去创作
进同人圈去创作
线段树或树状数组求逆序数
求逆序数的方法有分治,归并,本文只介绍线段树或树状数组求逆序数的办法,众所周知,线段树和树状树可以用来解决区间操作问题,就是因为这两个算法区间操作的时间复杂度很低O(logN),才让这种方法具有可行性。
首先先来看一个序列 6 1 2 7 3 4 8 5,此序列的逆序数为5+3+1=9。冒泡法可以直接枚举出逆序数,但是时间复杂度太高O(n^2)。冒泡排序的原理是枚举每一个数组,然后找出这个数后面有多少个数是小于这个数的,小于它逆序数+1。仔细想一下,如果我们不用枚举这个数后面的所有数,而是直接得到小于这个数的个数,那么效率将会大大提高。
总共有N个数,如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢?不妨假设有一个区间 [1,N],只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0,然后把第i个数之前出现过的数都在相应的区间把它的值定为1,那么问题就转换成了[i+1,N]值的总和。再仔细想一下,区间[1,i]的值+区间[i+1,N]的值=区间[1,N]的值(i已经标记为1),所以区间[i+1,N]值的总和等于N-[1,i]的值!因为总共有N个数,不是比它小就是比它(大或等于)。
现在问题已经转化成了区间问题,枚举每个数,然后查询这个数前面的区间值的总和, i-[1,i] 既为逆序数。
线段树预处理时间复杂度O(NlogN),N次查询和N次插入的时间复杂度都为O(NlogN),总的时间复杂度O(3*NlogN)
树状数组不用预处理,N次查询和N次插入的时间复杂度都为O(NlogN),总的时间复杂度O(2*NlogN)
线段树:
1 | // 线段树 |
树状数组:
1 | // 树状数组 |
线段树/树状数组的另一种用法不会,它的逆向问题更不会
Win7自动更新坏了,引导Mac OS X的chameleon好了
原来之前用ultraiso修改的wowpc.iso都是没用的,得用transMac改写hfs+文件才是
我本以为 存在WPS office for Mac而不存在Microsoft office for Mac,真实情况正好相反...
难以容忍的两个WA
Problem C
1 | int main() |
1 |
|
=====================================
Problem F
罕见的PE,输出末尾不能有多余空格,防不胜防
1 |
|
1 | int main() |
Problem E
裸的并查集
1 | const int maxn=2e5; |
=====================
还有个来不及提交的![个人原因,15:26才加入比赛
Problem H
1 | const int maxn=2e4; |
假如没有阿拉伯数字,我们要怎么表示数字呢
小明想了一个方法如下:
1 -> A
2 -> B
3 -> C
….
25 -> Y
26 -> Z
27 -> AA
28 -> AB
….
现在请你写一个程序完成这个转换
输入的第一个数为一个正整数T,表明接下来有T组数据。
每组数据为一个正整数n ( n <= 1000)
对于每个正整数n,输出他对应的字符串
没什么神奇的,本质还是进制转换
心急如焚之时,代码风格无比混乱;那个26的倍数的特殊处理,是个大痛点,AC一次耗时25min
1 |
|
=======================分隔符==============================
题E
自我感觉正确,可是未能在结束前提交。。
1 | int n; |
题A
耗时16min,循环队列,简直没有TLE/MLE的理由
1 | int n; |