17 热度

2014 Multi-University Training Contest 5

补上

1001

求逆序数

 

1002

LCA出个各个路径的深度,贪心思路,深度从深往浅.

 

1005

太坑,这题本身数据太水,然后比赛时配合出了问题。。。在做这题,被黄大队喊去做1009了。

一种方法是设置上下界,通过控制上下界来控制。

然后,当时,我的做法是模拟栈的思路,其实快敲出来了。先用全'('和')'来判断是否为None。个数为奇数也为None。然后就用栈的方法来模拟,最后就是剩余'?'的个数,=0时,就是Unique,> 2时就是Many,关键是两个时,就用判断这两个是否被包围过,被包围过就是Many,否则就是Unique。

 

1009

Java大数,

要求:f(x) = \sum_{i=1}^{n-1} i\oplus(n-i)

公式如下:

n = 2k + 1, f(n) = 4f(k) + 6k

n = 2k, f(n) = 2f(k) + 2f(k-1) + 4k - 4

一项可以通过另一项算出来。。

 

1010

水题,矩阵乘法优化下就行了。

 

Leave a Reply

Your email address will not be published. Required fields are marked *