Menu Sidebar
Menu

July 2015

[SPOJ] NOTATRI – Not a Triangle

原题: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 = […]

[SPOJ] FACVSPOW – Factorial vs Power

原题:http://www.spoj.com/problems/FACVSPOW/ 题目大意: 给正整数a, 求最小的正整数n, 使得n!>a^n 分析: 我看下面留言都说不计算fact, 用数学方法. 我就想两边取log, 左边的阶乘就是log(1)+log(2)….log(n), 右边的power就是n*log(a), 然后我写了下面的code public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); double power = 0; double fact = 0; int cur = 2; double temp = Math.log(n); while (true) { fact += Math.log(cur); // power = temp * cur; if (fact […]

[SPOJ] ABCDEF – ABCDEF

原题:http://www.spoj.com/problems/ABCDEF/ 题目大意:计算一个集合S,范围在[-30000,30000], 其中所有的可能的整数abcdef. 满足: (a*b+c)/d-e=f, where d !=0. 问多少种情况 分析: 公式题, 首先是整数取值, 所以就不难.先化简成a*b+c=d(e+f), 然后数一下左边集合中每个在右边的的个数. 注意: 这里是每个元素, 包括重复的. SPOJ真是卡空间, 用map直接TLE, 好好自己写counter吧. d不能是0 public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = in.readInt(); } Arrays.sort(nums); int[] […]

Codeforces Round #307 (Div. 2) C. GukiZ hates Boxes

原题:http://codeforces.com/contest/551/problem/C 题目大意: n堆箱子, m个学生要搬走箱子, 每个学生走过在箱子中间移动需要一秒, 移除一个箱子需要一秒, 问最少多少秒搬完. 分析: 这题有两个很tricky的地方. 一个是在搬走的时候, 不需要移动学生到别的地方. 所以如果学生在箱子上面, 在n秒内, 就能搬走n个箱子. 第二个是学生之间是同步进行搬箱子的. 解题的时候, 用的是穷举, 后来过不了TLE了. 看了答案才明白是二分搜索问题. 这里二分搜索用的是以下的原理: 如果在t秒内能完成任务, 那么肯定在大于t秒的时间内也能完成. 这就说明我们可以忽略那些大于t秒的情况.如何找到t呢. 因为题中告诉我们: at least one pile is non empty. 所以移动到这个non-empty pile需要1秒, 移动box 需要1秒, 所以我们的low bound是2. 那high bound是什么? 我们假设只有一个学生, 移动到n个地方需要n秒, 移除a1,a2…an个箱子需要a1+a2….+an秒, 所以high bound是(数组长度+box总数). 所以我们的range是在[2,Total(box+index)] 在每次搜索中,我们对m个学生依次分配任务, 从最后一个non-empty的pile开始移动尽可能多的箱子中. 因为我们已经知道时间是固定的, 所以问题转换成: 在已知时间内, 每个学生最多能拿多少箱子, 这里用贪婪的思想, 假设每个学生拿最多就可以. public void […]

Prufer Sequence 普吕弗序列

最近在翻看伯克利的组合数学课, 恰巧看到了这个. 当时对Prufer的认知, 仅限于他能压缩一个标号树(labeled tree), 后来看到Prufer证明Cayley公式: The number of labeled tree with n nodes is n^(n-2). 感觉这个东西还稍微有点用, lol. 要知道什么是Prufer Code, 首先要了接什么是labeled tree. 标号树就是一棵树, 把每个node从1开始标号. 因为是组合数学, 所以问的是, 对于标号n的树, 有几种可能的情况, 这个是Cayley公式. Prufer用Prufer Code证明了这个公式,当然这不是第一次证明. Prufer Code很好理解, 每次拿出编号最小的node, 然后把它的邻居放到序列里, 直到剩下两个点. 逆Prufer Code也好写, 先列1~n个数, 然后拿出(不放回)没有在序列中的最小的数, 和序列首项连起来, 然后删除序列首项, 直到最后剩下两个点, 然后把这2个顶点连起来. Prufer Code最大的应用就是它的唯一性, 即: 唯一的code对唯一的labeled tree. 这也是它被发明出来证明Cayley公式的原因. 所以任意给一个正整数序列, 都能对上一棵树… 其他应用…我还真是不知道…

Z Algorithm 一个和KMP,Boyer Moore并列的字符串搜索

KMP和Boyer Moore应该是最常见的两个子串搜索算法. 相比之下, KMP比较适合用在字符串基数少的string, 比如DNA, 然后BM相反. 和z相比, z的优势也就是短点… 今天看到GeeksforGeeks上介绍了Z function(Z algorithm).我都快忘了还有这个了. Z algorithm的时,空间复杂度和KMP类似, 采用的技术也类似.简单来说, Z algorithm采用了一个Z数组来保留已知子串信息. 和KMP一样, 我们需要预先计算Z数组. 如何计算Z数组?, Z数组的思想就是Longest Common Prefix (最长公共前缀,下面简称lcp). Z数组中在i位的元素表示lcp(s[0,s.length-1], s[i,s.length-1]). 就是包含i位的子串与串s的最长公共前缀. 比如 s: abbabbaa z: [0, 0, 0, 4, 0, 0, 1, 1] 在第二个a的时候, z是4, 表示abba是和s的最长公共子串, 即:lcp(abbabbaa,abbaa) = |abba|= 4. 如何使用z数组呢? 其实很简单, 只要把目标串s和匹配串p放在一个串中, 中间加个特殊符号, 就可以做子串搜索了.比如: s: abc p:abaedfbabcabd our string: […]

Codeforces Round #307 (Div. 2) B. ZgukistringZ

原题: http://codeforces.com/contest/551/problem/B 题目大意: 给3个string,a,b,c. 问用a的字母通过交换,最多可以得到多少个b或者c? 分析: 本来感觉是dp的题, 后来想想不用那么复杂, 先用三个26个字符数组, 存下三个字符串的字频, 然后用三个变量,num, nums_a, nums_b存下对应a,b,c的个数. 然后暴力破解就可以, 因为题目是求最多b或者c. 我们假设从0个b开始,一步步递增. 看看最多能有多少个. 这里需要注意的是, b的取值应该是从[0,count_b[j]*i > count_a[j]](0个b, 到i个b的第j个字母超过了i个a的第j个字母). 最后输出的时候, 先输出b,再是c, 最后把a剩下的字符输出就行了 public void solve(int testNumber, InputReader in, OutputWriter out) { String a = in.readString(); String b = in.readString(); String c = in.readString(); int[] ca = new int[26]; int nums = 0; int […]

Codeforces Round #307 (Div. 2) A. GukiZ and Contest

原题: http://codeforces.com/contest/551/problem/A 题目大意: 给n个人, 每个人都有rank, rank最高的人是1, 同一个rank的人得分一样, 不同rank的人,得分是前边rank人数的合, 问返回的数组是什么. 分析: 我看题目是sorting, 我没sort唉. 一共rank才2000, 用个count数组记录一下, 然后从后往前(从大rank到小rank)扫数组,每次扫都取合传给下一个rank. 然后再走一般数组打印出来对应的rank就行了. public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); int[] count = new int[2005]; int[] nums = new int[n]; for (int i = 0; i < n; i++) { int t = in.readInt(); count[t]++; nums[i] = […]

Codeforces Round #308 (Div. 2) C. Vanya and Scales

原题: http://codeforces.com/contest/552/problem/C 题目大意: 给两个数字,w和m, 再给一堆砝码, 砝码的重量是w^0,w^1,w^2….w^100, 且每种只有1个.是否能放到天平上来称出m(天平平衡). 砝码能放天平的两边. 分析: 首先观察一下题, 一看就是进制问题, 上来先把m变成w进制. 然后我们知道每个砝码只有一个, 所以我们要考虑怎么放才能平衡, 举个栗子, m是7, w是3, 我用一个叫into的数组, 把m变成w进制, 变成后就是 1,2,0, 因为 1*3^0 + 2*3^1. 然后我们观察一下这个数字, 假设我们把m放在天平的左边, 那么相当于左边已经放上了1个3^0 和2个3^1, 通过观察我们发现, 如果数组元素为1, 那么我们可以通过直接放一个相同的砝码在右边的天平, 天平就可以平衡. 如果数组元素为0, 那么我们可以不放任何砝码在右边就能使天平平衡. 如果数组元素为w, 那么我们尝试去放一个比当前砝码大1的砝码到右边的天平上, 比如, 如果w=3, 数组的第二位,3^1的值是3, 那么3*3^1 = 3^2. 不失一般性的, 假设w = w, 数组第i位 w^i的值是w, 那么w*(w^i) = w^(i+1). 如果数组元素为w-1, 那么我们放当前砝码在左边, 并且尝试放一个大1的砝码在右边. 这时,相当于天平的右边欠了左边一个差为w^(i+1), […]

Codeforces Round #308 (Div. 2) B. Vanya and Books

原题:http://codeforces.com/contest/552/problem/B 题目大意: 给个数字n, 求这n个数字的digits个数的合 分析: 比如1234, digit是1的区间是[1,9], 一共9个, 2的区间是[10,99]一共90*1个digit, 3的区间是[100,999]一共900*2个digit, n的区间是[10^n,10^(n+1)-1]一共10^(n+1) – 10^(n)*(n-1)个digit. 那么1234 落在区间4, [1000,9999]中. 可以用1234-1000+1得到4个digit的数字的个数, 然后乘以4,得到digit为4的digit数, 然后与前边的区间的合相加, 就是答案 第一次写: public void solve(int testNumber, InputReader in, OutputWriter out) { long n = in.readLong(); long t = n; long res = 0; int digits = 1; while (n / 10 != 0) { res += (9 […]

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

July 2015
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  
© 2025 书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.