Problem H 数学题 有好多人自称喜欢数学,一有数学题来了跑的比谁都快。然而,万神认为这 些人 naive ,于是出了一道数学题卡他们。题目很简单: 设 T 是 Tribonacci 数列,求 对 10 9 + 7 取模的结果。 Tribonacci 数列的定义见 http://oeis.org/A000213。 (Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=a(2)=1. ) 输入格式 输入文件包含多组数据(最多 100 组),请处理到文件结束。 每组数据只有 1 行,包含两个整数 l, r,用空格分割。 保证 0 ≤ l ≤ r ≤ 10 18 。 输出格式 对于每组数据输出 1 行,包含一个整数,即 S(l, r) 对 10 9 + 7 的模。 输入样例 0 2 3 5 输出样例 3 17 思想:矩阵快速幂 /** 继续阅读 >>


杜仑 16/04/22 14:07:28
Problem G 合并模板 XDU Fate 有 n 个 ACM/ICPC 比赛的模板,每个都是一个独立的 PDF 文 件。为了便于打印,万神希望将这些模板合并成一个 PDF 文件。万神有一个工 具,可以将至多 k 个 PDF 文件合并为 1 个,合并后的文件大小是原来 k 个文 件的大小之和。万神发现,这个工具每次运行的时间正比于输出文件的大小。设 每输出 1KB 需要 1 单位时间,那么万神至少要多少时间才能合并完所有的文件 呢? 输入格式 输入文件包含多组数据(最多 100 组),请处理到文件结束。 每组数据包含 2 行,第 1 行包含两个整数 n、k,用空格分割。 第二行包含 n 个整数 s 1 · · · s n ,用空格分割,表示原始的 n 个模板文件的大 小(单位为 KB)。 保证 1 ≤ n ≤ 1000,2 ≤ k ≤ 1000,1 ≤ s i ≤ 10 9 。 输出格式 对于每组数据输出 1 行,表示合并所有文件需要的最短时间。 输入样例 继续阅读 >>


杜仑 16/04/22 14:00:21
想要做一个群博(本身是有的,由于CSDN的rss订阅不符合规范没法进行抓取,自己打算手动实现抓取操作),但是通过HttpClient进行网页源码获取的时候竟然发现返回的是403 forbidden,有点尴尬了。然后网上查找资料之后发现说是要设置请求参数,然后想着是不是HttpClient是不是有什么setParameter方法,找了一下果然有,然后向下面这样设置了参数: HttpClient httpclient = new DefaultHttpClient(); httpclient.getParams().setParameter("User-Agent","Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.11 (KHTML, like Gecko) Chrome/23.0.1271.64 Safari/537.11"); 然而无济于事,既然作为一个请求有请求参数,那么是不是应该也有请求头部呢,没错,终于找到解决403 forbidden的办法了,通常情况下,通过浏览器去请求一 继续阅读 >>


朱新全 16/04/22 10:40:36
联结: 一种机制,用来在一条SELECT语句中关联表,因此称之为联结。它在数据库中不存在。联结由MySQL根据需要建立,它存在于查询的执行过程中。 创建联结: (使用WHERE联结)SELECT vend_name, prod_name, prod_priceFROM vendors, productsWHERE vendors.vend_id = products.vend_idORDER BY vend_name, prod_name;(保证所有联结都有WHERE子句,不然查询到的结果是两个表的笛卡尔积(第一个表的行乘以第二个表的行))(使用INNER JOIN ... ON ...联结)SELECT vend_name, prod_name, prod_priceFROM vendors INNER JOIN productsON vendors.vend_id = products.vend_idORDER BY vend_name, prod_name; MySQL可以联结多个表,但是联结 继续阅读 >>


张根 16/04/21 22:17:45
在多道程序的存储管理模式中,分区分配算法显得尤为重要。这里主要说一下动态分区分配算法。 主要有下面五种分配算法: 首次适应算法 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应算法 对于这几种方式的算法,可以说各自有其优缺点,或许它的优点正好就是它的缺点呢! 首次适应算法 顾名思义,首次适应是从空闲链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止,然后按照作业的大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍然留在空闲链中。若从头到尾都不能找到一个能满足空间要求的分区,则此次内存分配失败。该算法倾向优先使用内存中低地址部分的空闲分区,从而保留了高址部分的大空闲区,为后续到达的大作业分配大的内存空间创造了条件。那么相反,每次都从空闲链首开始查找,低地址部分不断的被划分就会导致产生许多难以利用的、很小的空闲分区,同时也会增加每次查找的开销。 循环首次适应算法 没错,比前一个多了循环两个字,即就是在前一个算法的基础上添加了循环的功能,使用该算法为进程分配内存空间时,不再从头开始,而是从上次分配的位置为起点的下一个分区 继续阅读 >>


朱新全 16/04/21 22:15:15
题目: Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. 题目大意:   给定一条链表,将链表相邻的两个节点交换,返回交换后的链表。 思路:   本题比较简单,大致解题方向有两种:交换节点的值、交换节点的指向。   1、交换节点的值:最简单的方法就是交换两个节点的值,达到交换的目的。   2、交换相邻节点的指向,在即当p2 = p1->next时执行p1-> 继续阅读 >>


张根 16/04/21 19:08:23
        最近面试等各种事情就少了,于是静下心来学一点自己喜欢的... 继续阅读 >>


孙磊 16/04/21 09:45:44
题目:   Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 题目大意:   给定k条有序链表,求k条链表有序合并后的链表。 思路:   看到这道题感觉蛮亲切的,因为已经不止一次遇到链表有序合并的问题了,所以思路还是有的。   第一个思路就是借助两个链表的合并,先将两个链表合并为结果链表,然后再将下一条链表合并到结果链表上,直到所有的链表都合并结束。   当然,第一个思路的时间复杂度很高,所以肯定又是轰轰烈烈的超时了。所以,诞生了第二个思路:根据合并排序的思想,将链表从头和尾合并,每次合并之后都放在原来链表数组的前半部分,下一次循环直接合并前半部分,直到所有的链表合并完成。 代码1: //每次合并一个链表到结果链表上,结果超时 class Solution { public: ListNode* mergeKLists(std::vector&l 继续阅读 >>


张根 16/04/20 23:43:45
Problem F 6 方格填数 问题描述 万神在纸上画了一个 3 × 3 的表格,希望把 1 · · · 9 填入表格中,每个数只填 一次。然而,这样会有 9! = 362880 种不同的填数方案。万神觉得方案太多了, 于是又写下 9 个正整数 a 1 · · · a 9 ,并规定填数方案合法的充要条件是:对于表格 中任意一对相邻的数 x, y,必须满足 a x 和 a y 互质,即它们的最大公约数是 1。 那么,还有多少种合法的填数方案呢? 相邻定义为两个数所在的格子有公共边。 输入格式 输入包含多组数据(最多 100 组),请处理到文件结束。 每组数据只有 1 行,包含 9 个正整数 a 1 · · · a 9 ,用空格分割。 保证 1 ≤ a i ≤ 10 9 。 输出格式 对于每组数据输出 1 行,包含 1 个整数,即合法的填数方案的个数。 输入样例 1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 2 2 2 2 继续阅读 >>


杜仑 16/04/20 20:13:08
Problem E 问题描述 万神需要生成两个串 a、b,使得 a 不包含任何在 b 中出现过的字符。现在 万神已经有两个串 A、B,他希望令 b = B,然后将所有在 b 中出现过的字符从 A 中删掉,以得到 a。 输入格式 输入包含多组数据(至多 100 组),请处理到文件结束。 每组数据只有 1 行,包含串 A、B,用空格分割。 保证 A、B 只包含小写字母,且 1 ≤ |A|, |B| ≤ 10 5 。 输出格式 对于每组数据输出 1 行。若 a = ∅,则输出 “EMPTY” (不含引号),否则输 出串 a。 输入样例 abababa aa ccccc a aaaaa a 输出样例 bbb ccccc EMPTY 打表大法好! /************************************************************************* > File 继续阅读 >>


杜仑 16/04/20 20:09:39