UVA Notes

最近在uva上做了几十个非常简单的题。记录如下

369 - Combinations

这个就是计算排列组合中的C(N,M)。高中的数学知识了,蛮力计算就可以。但是题目故意迷惑人,真有人按照题目所说的,去计算 N!,然后再除以M!。这就有点2B了。以C(20,2)来说,计算20/1 * 19/2 即可。另外,利用C(N,M)=C(N,N-M),有时也可减少一部分计算量。一个特殊情形C(N,N)=1。

11547 - Automatic Answer

int x=(int)strtol(line.c\_str(),NULL,10);
x=abs(((x*(double)567/9+7492)*235/47-498)/10);
int r=x%10;

495 - Fibonacci Freeze

因为N不大,所以直接按照递归式计算fib(n)即可,不需要用分治做。但是这里涉及了大整数运算,必须自己实现一套类似于gmp那样的东西。于是我花了将近一周的时间,读openssl的big number相关代码,读gmp的paper。最重要的是这么几个函数:加法、除以单字长的整数、bignumber to decimal string。在实现除法的时候我借助于汇编写的,因为我需要计算一个128位的整数除以64位的整数的结果。除法和加法不同,一旦溢出还会core dump。所以 openssl在做这件事情之前还对这两个数做了normalize,但是我怀疑真的有必要吗? p.s.大数运算中,除法是最最复杂的。算法导论中没有讲这个问题,但是计算机程序设计的艺术中第二卷有。

499 - What's The Frequency, Kenneth?

出题的人应该是个emacs fans,对vi狠狠吐槽了一番。题目很简单,就是统计26个字母的出现频率,无难点。

374 - Big Mod

同余群就相当于N的一个有限子群一样。所以\( B^p \mod M = (B \mod M)^p \) 。这个问题就变成了很普通的,求某整数的N次方的问题。最笨的方法,写一个for循环,迭代,那么计算p次方就是O(p)的复杂度。更好的方法是用分治的方法做,代码如下:

inline uint64_t calc(uint64_t b,uint64_t p,uint64_t m){
    uint64_t r=1;
    while(p){
            if(p&1) r=(r*b)%m;
            p<<=1;
            b=(b*b)%m;
    }
    return r;
}

10327 - Flip Sort

计算逆序的个数。N不大,所以用insert sort实现即可。

11364 - Parking

题目很长很啰嗦,(最大值-最小值)*2 即可。

12289 - One-Two-Three

寻找最相似的字符串,先根据长度判断是不是three,然后从one和two中挑选最相似的一个。

12250 - Language Detection

我把所有的“HELLO” 插入到一个hashmap中,然后每读一行就去hashmap中查找一下。手动写if...else肯定可以做的更高效,就看打算在这个问题上花多少时间了。

10976 - Fractions Again?!

让y在[k+1,2*k]范围内遍历,然后计算y*k/(y-k)。

256 - Quirksome Squares

这个可以作弊。没几个数,预先算好然后输出即可。

482 - Permutation Arrays

很简单。在读第二行数据的时候,按照第一行给出的位置直接插入到数组的对应位置即可。

417 - Word Index

我本来想求出递推式,后来发现比较难。打表做的。

579 - ClockHands

先求出每小时时针是多少度,每分钟时针是多少度,每分钟分针是多少度,然后前两者加起来和后面一个算差值。

11799 - Horror Dash

求数组的最大值。

11727 - Cost Cutting

在三个数字中求median。简单的if...else

10107 - What is the Median?

求动态中位数。我的做法是用两个heap。一个最大堆,一个最小堆。一个是下半部分,一个是上半部分。然后动态调整。比较通用的做法是算法导论上说的,在二叉搜索树上的每个节点记录这个节点的子树的size,然后二分查找。

483 - Word Scramble

简单的数组逆序。

10189 - Minesweeper

计算扫雷游戏中每个格子周围有多少个雷。简单遍历即可。我为了简单,给原始的棋盘的四周各加了一行(列)。这样数组访问就一定不会越界了。

10783 - Odd Sum

等差数列求和。直接套公式。const int n=(end-start)>>1; result=start*(n+1) + n*(n+1);

10340 - All in All

判断一个字符串是不是另一个字符串的subsequence。一个for循环套一个strchr.

10082 - WERTYU

用map做查找替换。

111 - History Grading

这个我提交了很多次都是wrong anwser,比较郁闷。读懂题意很重要哇…太绕了。

591 - Box of Bricks

求均值然后相减,然后累加。

113 - Power of Cryptography

我是直接用double计算pow的…

299 - Train Swapping

计算逆序的个数。我直接用插入排序做的。

10929 - You can say 11

我按照规律,从右向左计算了一遍。

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥