Openjudge 求排列的逆序数

发表评论

求排列的逆序数
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足 j < k 且 ij > ik， 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。

现给定1,2,…,n的一个排列，求它的逆序数。

输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。 第二行是n个不同的正整数，之间以空格隔开，表示该排列。 输出 输出该排列的逆序数。 样例输入 6 2 6 3 4 5 1 样例输出 8 提示 1. 利用二分归并排序算法（分治）； 2. 注意结果可能超过int的范围，需要用long long存储。 来源 习题(15-4) 继续阅读 →

Openjudge 汉诺塔问题 题解

发表评论

6261:汉诺塔问题
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615
这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。

假定圆盘从小到大编号为1, 2, …

输入
输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。
输出
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。
样例输入
2 a b c
样例输出
a->1->c
a->2->b
c->1->b
真心是经典问题啊！

先贴代码：
继续阅读 →

Openjudge 爬楼梯 题解

发表评论

3089:爬楼梯
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。

输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30 输出 不同的走法数，每一行输入对应一行输出 样例输入 5 8 10 样例输出 8 34 89 这个好像就有点类似于动态规划的感觉咯。但是其实这还是动规里最简单的题。但是初学感觉有点难度了。233 继续阅读 →

Openjudge 菲波那契数列

发表评论

1755:菲波那契数列
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数是多少。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 20) 输出 输出有n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数的大小 样例输入 4 5 2 19 1 样例输出 5 1 4181 1 继续阅读 →

00后在知乎 假装万能组 感想

发表评论

最近这两天知乎被00后刷屏了，甚至在2月11日知乎的大V轮子哥都来参观并回答了问题“如何看待00后《知乎 •「假装万能组」成立宣言》？”：

现在，作为这个事件的亲历者，想从自己个人的角度尽量客观来陈述一下这前前后后发生的事实，并抒发我自己的一些感受。
首先是这个00er微信交流群的创建：根据施子怡的文章千赞以上99/00后答主及其高赞回答 一览（含小姑娘们的照骗XD）的发布时间，应在2月4日，我从我的知乎推荐里刷到了这条消息。感叹00后如此之牛的同时，我顺手点开了知乎评论区。瞬间就看到了Becal老杨的建议：

在看似没有人响应该同学创建00er群的情况下，我就自己创建了一个QQ群，并发在了评论区底下，欢迎他们加入。

事情不久就有了新的变化，我的一位朋友拉我进入微信群，当时微信群里还只有二十多个人。（这部分没有截图，只能口述，请谅解）当时群的主办者也许根本就没有想到要成立一个所谓的“假装万能组”（00后在知乎 ·「假装万能组」成立宣言）。当时我们就在不断的商议入群的标准。在商议的过程中，有人说：

最后主办者刘梓珊、施子怡（下文简称刘、施）就决定先让我们这些不符合标准的童鞋退群，然后经由他们商议一天之后，大概得出了这个结果：

我本来是想打破砂锅也要进群的，但是看到了当时一位同学对群的评价：

因为上述的硬性标准和这位同学的否定，我就没有想着再进群了，之后的一切动向，都是我从各种微信截图中得来的。
发上截图来：


其它的截图就不发了，太多了。发上来也没有什么意义。
后来发生了一系列事件，例如：
ziwen建小群退大群事件：


其它关于ziwen和flyinet的事件我就不说了，毕竟我也不太清楚嘛。主要就是扒皮嘛。现在这两个人是一个人撑不下去了，把知乎简介改了；另外一个人死撑着吧。
不过，还好，专栏发出的第一篇文章【低龄留学】初中就出国的姑娘在过怎么样的生活？让我们这些旁观者又看到了新一代00后的希望。（自己就是00后）

现在说一说我个人的感受吧，也是从知乎上总结下来的：
原问题集锦：如何看待00后《知乎 •「假装万能组」成立宣言》？
（1）管理者没有干货
（2）有些人手把权利不放松，各种面具伪装

（3）领域不同

说实话，看到了知乎上各种不同的观点，真是大开眼界啊。很多人比我写的好多了，希望大家积极关注这件事情的进展。
请关注：如何看待00后《知乎 •「假装万能组」成立宣言》？
最后说一句，仁者见仁，智者见智。
嗯，就这样。

Openjudge 逆波兰表达式

发表评论

1696:逆波兰表达式
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ – * /四个。
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
输出
输出为一行，表达式的值。
可直接用printf(“%f\n”, v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
提示
可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解。
来源
计算概论05

感受到咱们国家的前缀表达式和递归真是博大精深啊！！！！
继续阅读 →

程序设计与算法（二）递归部分总结

发表评论

最近参加了中国大学MOOC的程序设计与算法（二）：http://www.icourse163.org/learn/PKU-1001894005?tid=1001994002#/learn/announce
该课程的目标：
本课程将讲述枚举、递归、分治、动态规划、搜索这几种算法。这些算法的基本思想容易理解，用它们来解决的问题，可以很容易，也可以很难。本课程中一部分的例题，难度与中学信息学奥赛NOIP提高组的较难题相当，也和ACM国际大学生程序设计竞赛中的中等题相当。掌握了本课程的内容，学员的算法水平和实现能力将超过国内大部分高校计算机专业本科毕业生。
第一周的枚举考试没有赶上，就从第二周的递归开始写，然后就把递归部分的视频看完了、考试题都写完了。
本人没有系统的学习过这一部分内容。个人感觉到递归本身应该不是特别不好理解。但是这个郭老师在递归中掺杂了一些动态规划的内容，例如分苹果，分解因数，划分整数等等问题，基本上是初次接触动态规划，之前只写过动规的01背包，其他的就不会了。所以这些转移方程很难写。根本写不出来，都是看到网上的解答才能自己慢慢思考一点。希望以后思维能力能够有所长进。
部分例题：Openjugde题库：
666:放苹果 http://noi.openjudge.cn/ch0202/666/
1751:分解因数 http://noi.openjudge.cn/ch0202/1751/
简单的整数划分问题 http://cxsjsxmooc.openjudge.cn/2017t2springhw3/2/ （可能只有题面，不能够再提交）
这三个问题的递推式总结在我之前的一篇文章里：MOOC学习递归中涉及动态规划部分经典题目

MOOC学习递归中涉及动态规划部分经典题目

发表评论

2017-07-14更新放苹果问题：参考http://www.cnblogs.com/wxgblogs/p/5742618.html
放苹果
设函数f(M,N)为把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放的分法的数量。（5，1，1和1，5，1 是同一种分法。）
求该函数的递推式
解答：

f(m,n)={
m==0||n==1 -> 1;
m f(m,m); //将m个苹果装到多于m个的盘子中必定不能装满，所以把m个苹果装到m个盘子里就好
m>=n -> f(m-n,n) + f(m,n-1); //分成两种情况，f(m-n,n)是没有空盘子：把n个盘子里每个都装上一个苹果，剩下的m-n个苹果再装到n个盘子里；f(m,n-1)是有空盘子，把那一个不装扔出来就好。
}

简单的整数划分问题
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。设函数f(m,n)为将整数m划分为每个数最大为n的划分数。
求该函数的递推式
解答：

f(m,n)={
m==1|| n==1 -> 1; //m==1时，只能分成1个1；n==1时,只能分成m个1。
m f(m,m); //n>m时，将n调至m
m==n -> 1+f(m,n-1); //当m==n时，因为整数m可以自己算作一个划分，那么就要把n-1传递下去
m>n -> f(m-n,n)+f(m,n-1); //m>n时，可以在当前状态下分出去n或者不分出去n，对应两个f();
}

分解因数
给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * … * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意a = a也是一种分解。 解答：设函数f(m,n)为将整数m划分成小于等于整数n的划分数。
f(m,n)={
n==1 -> 0; //划到1就不能再往下分了
m==1 -> 1;
m%n==0 -> f(m/n,n) + f(m,n-1); //当m可以整除n的时候，可以除完了划分下去，也可以不除
m%n!=0 -> f(m,n-1); //只能不除
}

Openjudge Boolean Expressions

发表评论

Boolean Expressions
查看 提交 统计 提问
总时间限制: 1000ms 内存限制: 65536kB
描述
The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next:
Expression: ( V | V ) & F & ( F | V )

where V is for True, and F is for False. The expressions may include the following operators: ! for not , & for and, | for or , the use of parenthesis for operations grouping is also allowed.

To perform the evaluation of an expression, it will be considered the priority of the operators, the not having the highest, and the or the lowest. The program must yield V or F , as the result for each expression in the input file.
输入
The expressions are of a variable length, although will never exceed 100 symbols. Symbols may be separated by any number of spaces or no spaces at all, therefore, the total length of an expression, as a number of characters, is unknown.

The number of expressions in the input file is variable and will never be greater than 20. Each expression is presented in a new line, as shown below.
输出
For each test expression, print “Expression ” followed by its sequence number, “: “, and the resulting value of the corresponding test expression. Separate the output for consecutive test expressions with a new line.

Use the same format as that shown in the sample output shown below.
样例输入
( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))
样例输出
Expression 1: F
Expression 2: V
Expression 3: V
来源
México and Central America 2004

这题递归写的真心累啊！

继续阅读 →