原题: http://www.spoj.com/problems/ONP/ 题目大意: 一个代数表达式转换成Reverse Polish Notation. 分析: wiki上就有规则. 其实这个题只有三个规则: 看到(, 忽略 看到操作符(加减乘除)入栈 看到), 出栈,打印 其余直接打印 public class ONP { public void solve(int testNumber, InputReader in, OutputWriter out) { String s = in.readLine(); out.printLine(infixToPostfix(s)); } public String infixToPostfix(String infix) { Stack<Character> st = new Stack<>(); StringBuffer sb = new StringBuffer(); String opt = “+-*/^”; for (int i […]
原题: http://www.spoj.com/problems/FAVDICE/ 题目大意: 给一个n面的骰子, 问扔多少次至少每个面出现一次 分析: Coupon collector’s problem 假设有6个面, 那么第一次扔的面肯定是我们想要的, 这时可以看成是6/6,即6个面中出现6个我们都想要的, 其中的一个面出现的概率是1/(6/6) = 1, 因为这时候没有其他面出现过. 第二次扔的面有两种情况, 一种是已经出现过, 1/6, 另一种是没有出现过5/6, 那么我们当然要没有出现过的, 就是5/6中选一个, 1/(5/6), 以此类推就是n*(h(n)), 然后算下调和函数h的值就好了 public class FAVDICE { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); out.printFormat(“%.2f\n”,n*calculateH(n)); } private double calculateH(int n) { double res = 0.0; for (double i = […]
原题: http://www.spoj.com/problems/FCTRL/ 题目大意: 给一个数字n,问你n!后边有多少个0. 分析: 这就是Leetcode那个Factorial Trailing Zeroes 我们看n!是由多少个5的倍数组成的. 就知道后边有几个0. 纯数学题. 没意思 public class FCTRL { public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int sum = 0; while(n != 0) { sum += n / 5; n = n / 5; } out.printLine(sum); } }
原题: http://www.spoj.com/problems/HASHIT/ 题目大意:设计个一个hash函数, 可以insert, exist 和 delete. 然后通过执行一系列命令, 返回key的数量和table的内容. 分析: 这里需要注意的是nextpos的函数需要mod 101, public class hashit { final int mod = 101; final int num = 19; int count = 0; String[] hash = new String[mod]; public void solve(int testNumber, InputReader in, OutputWriter out) { reset(); int m = in.readInt(); for (int i = 0; i < […]
原题: http://www.spoj.com/problems/PALIN/ 题目大意: 给任意一个数, 找到比这个数大的最小的一个回文数字. 分析: 这题要考虑的情况很多, 比如例子中的808, 我们需要把0改成1, 因为如果我们改动最后的8, 前边的8也要增加, 所以改变的总量会更大, 只能改变0. 所以第一条就是, 我们要从数字的中间改. 另一个是2133变成2222. 这个改变的过程是2133->2132->2112->2222, 这里, 我们用的是meet in mid的策略, 我们要比较前边和后边的数字, 如果他们是一样的, 那么就忽略, 如果他们不一样, 前边比后边大, 就把后边改成前边的, 这样相当于增加了,所以就结束了. 如果后边大, 把前边赋值后边, 但是继续程序.最后一种情况是, 99999->100001. 我们把所有的9变成0, 然后最后的9变成1,然后前边加1. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int i = 0; i < t; i++) […]
原题: http://www.spoj.com/problems/DIVSUM/ 题目大意: 给一个数n,找到它所有的除数的合. 比如number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22. 分析: 第一次提交的时候, 老老实实找每个divisor, 结果tle了. 后来想想20/2 = 10, 一次可以把2和10都找到, 所以lgn就可以有. 先上第一次代码: public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int […]
原题: http://www.spoj.com/problems/SBANK/ 题目大意: 给n个银行交易帐号信息, 要求排序, 并且统计出现次数, 输出要有序,并且输出次数. 分析: 其实就是设计一个数据结构, 是Key-Value的, 并且有序. Key-Value就是Map了, 有序 自然就是TreeMap. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); for (int p = 0; p < t; p++) { int n = in.readInt(); Map<String, Integer> map = new TreeMap<String, Integer>(); for (int i = 0; i < n; […]
原题: http://www.spoj.com/problems/PRIME1/ 题目大意: 给一个范围1 <= m <= n <= 1000000000, n-m<=100000, 找这个范围内的所有质数. 分析: spoj真是卡时间也卡空间. 做了起码五六次, 不是tle就是heap爆了. 观察了一下, 发现取值范围实在太大了, 1*10^9. 后来怀疑是不是用aks test, 试了, 还是不行. 发现问题是在方法上. 首先不能求1~n的所有质数, 然后打印出大于等于m的, 这样太慢, 其次Sieve of Eratosthenes(SoE)求的是[2,n]的. 我们需要使用的是[m,n]的.这里需要观察一下,对于每个[2,sqrt(n)]的质数p, 都有以下特点: 对于m,我们可以找到一个lower bound, 这个bound是m前边最大的能被p整除的数.比如m=5,p=2, 那么5/2 = 2(取整), 2*2 =4, 那么4就是我们要找的lower bound. 这个bound有一个特性, 就是我们用过lower bound + k*p 就可以知道p在[m,n]中出现的位置. 比如刚才的例子, m=5, n=10, 那么lower bound = 4, 4+2 […]
原题: http://www.spoj.com/problems/TEST/ 题目大意: 输出序列, 直到42 分析: 开始刷spoj. 最后一个学期也没TA了, 最后一个学期, 各种老师不给Master TA/RA. 烦恼 烦恼. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); while (n != 42){ out.printLine(n); n = in.readInt(); } }
原题:http://www.spoj.com/problems/NOTATRI/ 题目大意:给一个数组, 找到其中不能组成三角形的3-tuple的个数. 分析:睡前A一道. 简单的计算. 两边之和<第三边, 先排序一下数组, 然后把第三边取数组最后一个, 也是最大一个数. 然后两个指针left和right, meet in middle, 个数是 right-left, 因为每次当满足条件时, 所有在right和left中的元素, 都可以看成以当前i为第三边和当前的left为一条边时, 移动right往left靠拢,这些可能的组合, 都是满足条件的, 因为right靠谱left是一个递减的过程. public void solve(int testNumber, InputReader in, OutputWriter out) { int t = in.readInt(); while (t != 0){ int[] nums = IOUtils.readIntArray(in,t); out.printLine(solve(nums)); t = in.readInt(); } } private int solve(int[] nums){ int res = […]