- 浏览: 1638644 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (405)
- C/C++ (16)
- Linux (60)
- Algorithm (41)
- ACM (8)
- Ruby (39)
- Ruby on Rails (6)
- FP (2)
- Java SE (39)
- Java EE (6)
- Spring (11)
- Hibernate (1)
- Struts (1)
- Ajax (5)
- php (2)
- Data/Web Mining (20)
- Search Engine (19)
- NLP (2)
- Machine Learning (23)
- R (0)
- Database (10)
- Data Structure (6)
- Design Pattern (16)
- Hadoop (2)
- Browser (0)
- Firefox plugin/XPCOM (8)
- Eclise development (5)
- Architecture (1)
- Server (1)
- Cache (6)
- Code Generation (3)
- Open Source Tool (5)
- Develope Tools (5)
- 读书笔记 (7)
- 备忘 (4)
- 情感 (4)
- Others (20)
- python (0)
最新评论
-
532870393:
请问下,这本书是基于Hadoop1还是Hadoop2?
Hadoop in Action简单笔记(一) -
dongbiying:
不懂呀。。
十大常用数据结构 -
bing_it:
...
使用Spring MVC HandlerExceptionResolver处理异常 -
一别梦心:
按照上面的执行,文件确实是更新了,但是还是找不到kernel, ...
virtualbox 4.08安装虚机Ubuntu11.04增强功能失败解决方法 -
dsjt:
楼主spring 什么版本,我的3.1 ,xml中配置 < ...
使用Spring MVC HandlerExceptionResolver处理异常
问题:Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
Input
There are multiple test cases, the first line is the number of test cases.
The first line of each test case contains two integers, N and K (1 ≤ N ≤ 10000, 2 ≤ K ≤ 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
Output
Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.
Sample Input
2
4 7
17 5 -21 15
4 5
17 5 -21 15
Sample Output
Divisible
Not divisible
这道题目就是在给定的一堆数中,添加+ -号,判断一下结果是否能整除给定的K.
这道题首先给人的感觉是穷举/搜索,但是给的数在10000以内,穷举的话是2^n,最坏情况10000个数,如果不可整除,计算出来时间是相当长的.
而把指数级复杂度变为多项式级别的可以考虑动态规划.
这道题的动态规划信息非常隐蔽,因为如果直接把这些数的运算划分为子问题的话,这些子问题都将是不重复的.而动态规划是通过记住子问题的最优解来避免重复计算而提高效率的.
但仔细分析这道题,我们发现其实没有必要真正求出表达式的值,我们只要把每一步计算结果
的对k的余数记住就行了.这样每一步的计算结果就在0~K之间了.如果我们把这个计算过程表示为树形结构的话
a1
/ \
a1-a2 a1+a2
/ \ / \
a1-a2-a3 a1-a2+a3 a1+a2-a3 a1+a2+a3
...................................
这样第j层就会有2^j个计算的结果,而如果我们每次计算的时候都对k求模,这样这2^j个值
都在0~k-1之间,而如果一层中的两个节点的值一样,那么显然可以在计算第一个节点的值是否能被k整除后把这个结果保存下来,再遇到这样同一个值的可以直接查找到,事实上这样重复的节点计算是相当多的--(指数级别2^j的数在常量0~k范围).这样我们把一棵树的宽度约束在了1~k的范围了,而高度是N,所以复杂度变成了多项式级别O(k*N)了:
代码如下:
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5.
You are to write a program that will determine divisibility of sequence of integers.
Input
There are multiple test cases, the first line is the number of test cases.
The first line of each test case contains two integers, N and K (1 ≤ N ≤ 10000, 2 ≤ K ≤ 100) separated by a space.
The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it's absolute value.
Output
Write to the output file the word "Divisible" if given sequence of integers is divisible by K or "Not divisible" if it's not.
Sample Input
2
4 7
17 5 -21 15
4 5
17 5 -21 15
Sample Output
Divisible
Not divisible
这道题目就是在给定的一堆数中,添加+ -号,判断一下结果是否能整除给定的K.
这道题首先给人的感觉是穷举/搜索,但是给的数在10000以内,穷举的话是2^n,最坏情况10000个数,如果不可整除,计算出来时间是相当长的.
而把指数级复杂度变为多项式级别的可以考虑动态规划.
这道题的动态规划信息非常隐蔽,因为如果直接把这些数的运算划分为子问题的话,这些子问题都将是不重复的.而动态规划是通过记住子问题的最优解来避免重复计算而提高效率的.
但仔细分析这道题,我们发现其实没有必要真正求出表达式的值,我们只要把每一步计算结果
的对k的余数记住就行了.这样每一步的计算结果就在0~K之间了.如果我们把这个计算过程表示为树形结构的话
a1
/ \
a1-a2 a1+a2
/ \ / \
a1-a2-a3 a1-a2+a3 a1+a2-a3 a1+a2+a3
...................................
这样第j层就会有2^j个计算的结果,而如果我们每次计算的时候都对k求模,这样这2^j个值
都在0~k-1之间,而如果一层中的两个节点的值一样,那么显然可以在计算第一个节点的值是否能被k整除后把这个结果保存下来,再遇到这样同一个值的可以直接查找到,事实上这样重复的节点计算是相当多的--(指数级别2^j的数在常量0~k范围).这样我们把一棵树的宽度约束在了1~k的范围了,而高度是N,所以复杂度变成了多项式级别O(k*N)了:
代码如下:
#include<iostream> #include<string> using namespace std; int flag[10005][105]; int a[1005]; int n,K,N; //@return 返回是否可以整除K,@parm level递归形成二叉数的层数,vaule为该层一个计算出节点的值 int f(int level,int value){ if(flag[level][value] != -1) return flag[level][value];//如果已经记录过了,就直接返回 int check,t1,t2; t1 = (value + a[level]) % K;//进行+运算并对K取余数 t2 = (value - a[level]) % K;//进行-运算并对K取余数 t1 = t1 < 0 ? t1 + K : t1;//余数都改成正的 t2 = t2 < 0 ? t2 + K : t2; if(level == N) check = (value % K == 0) ? 1 : 0;//如果第N层,递归出口,判断 value 是否可以整除K else if(f(level + 1,t1) == 1) check = 1;//如果level + 1层计算结果可以整除K,则标记check为1,同时可以跳过另一个分支,因为0-a,0+a对最终判断否是否可以整除K的效果是一样的 else if( f(level + 1,t2) == 1 ) check = 1; else check = 0;//左右分支均不可以整除 check=0; return flag[level][value] = check;//返回并记录本层的check值 } int main(){ int m; int i,j; string result; cin >> n; for(i = 0; i < n; i++){ cin >> N >> K; for(j = 0; j < N; j++){ cin >> a[j]; if((a[j] %= K) < 0) a[j] += K; } for(j = 0; j <= N; j++) for(m = 0; m <= K; m++) flag[j][m] = -1; result = f(1,a[0]) == 1 ? "Divisible" : "Not divisible" ; cout << result << endl; } return 0; }
发表评论
-
二分查找之变型题目
2010-10-24 12:40 2117二分查找算法在各个公司的笔试面试题大量出现,通常不是简单一眼就 ... -
一道笔试题(创新工厂)解法
2010-10-21 17:44 1816一个帖子http://www.iteye.com/topic/ ... -
[zz]大数据量,海量数据 处理方法总结
2010-08-27 22:24 2242大数据量的问题是很多面试笔试中经常出现的问题,比如baidu ... -
Trie and suffix array
2010-04-13 20:54 1898字典数Trie和后缀数组suffix array是处理字符串操 ... -
金币问题
2009-11-09 08:41 1990今年某公司的笔试题: 一个矩阵地图,每一个元素值代表金币数, ... -
楼梯问题
2009-11-09 08:19 1543hl给我的几道某公司的算法题: 1、 有个 100 级的 ... -
一道考察模拟乘法的题目
2009-11-07 22:37 1395今天hl和我讨论一道题目: 写道 整形数组如a={1,4, ... -
链表归并
2009-11-07 21:40 1002以前gx同学问的某某公司的笔试题,写一下练练(纯手写,没编译过 ... -
找出出现次数超过一半的数字
2009-11-07 21:23 1863hl同学问我一道这个题,想了一种方法,感觉还是不错的,只扫描一 ... -
有道难题以超低分晋级
2009-06-10 11:36 1534有道难题比赛居然晋级了,可以领到一个t-shirt。 -
逆序数/逆序数对
2009-06-09 23:17 3739逆序数是个常遇到的问题,主要有两种解法: O(n^2)的方法: ... -
有道难题topcoder
2009-05-31 23:55 2426今天做了有道topcoder的题目,也是第一次在topcode ... -
百度之星第一场题目
2009-05-31 00:03 3593由于不符合参赛条件,未能参加百度之星,看了题目还挺有意思,把题 ... -
一个对字符串很好的Hash函数ELFHHash
2009-05-03 21:41 2242#include<stdio.h> #defin ... -
最大流Ford-Fulkerson算法
2009-04-22 17:33 9627算法导论对最大流算法有很详细的介绍,今天实现了最大流Ford- ... -
大数/高精度加减乘除取模[收藏]
2009-04-16 19:38 5027#include <iostream> #i ... -
带重复数字的全排列
2009-04-16 18:58 3860上次gx同学问我一道又重复数字的全排列的问题,我当时用set保 ... -
差分约束系统
2009-04-15 16:00 3686(本文假设读者已经有以下知识:最短路径的基本性质、Bellma ... -
二分图匹配
2009-04-15 15:40 3699二分图最大匹配的匈牙利算法 二分图是这样一个图,它的顶点可以分 ... -
线段树
2009-03-24 10:58 1656把问题简化一下: 在自然数,且所有的数不大于30000的 ...
相关推荐
算法设计第二版的第八章: 求解最长公共子序列问题-求dp设计报告,简单分析,运行代码可在我的博客,找对应的文章
自己总结,个人感觉比较实用,尤其是热分析
在不久的将来,我希望将其扩展到一个简单的DPLL(T)SMT求解器。 这将涉及: Tseitin转换 一种特殊的预处理模式,仅产生同等的问题,而不产生同等的问题 可能也是一种特殊的后处理模式 扩展了主DP
4.Dynamic Programming (缩写为 DP ,动态规划) 主要用于最短路问题、背包问题、生产与储存等类问题的求解; 5.Facility Location and Layout (缩写为 FLL ,设备场地布局) 应用于设备场地设计、功能布局、...
该文档描述了ANSYS操作过程中经常遇见的错误以及可能的原因分析。对于ANSYS使用过程具有较大意义的帮助
这种连接是由一个名为Nodes_fad的模块Nodes_fad ,它基于 Marc 的Node模块。 编译 在您的机器上 您将需要ocaml>=4.08.1和opam ,请参阅 。 安装所需的库: sudo apt-get install -y build-essential sudo m4 libgtk...
基于Matlab的金融数量分析 第3版 :学习课件,其中附有Matlab程序代码 -复旦大学 第1章金融市场与金融产品,pptx 第2章 MATLAB基础知识概述 pptx 第3章 MATLAB与Exce文件的数据交换ppi 第4章 MATLA B与数据库的数据...
该问题属于NP-hard问题,采用动态规划算法(DP)和模拟退火算法(SA)求解该问题,通过实验分析不同规模时DP的执行时间与SA的执行时间和求解误差的变化趋势,比较SA与其他实践中常用的经典规则的求解效果.最后得出DP适合...
programing)是运筹学的一个分支,是求解决策过程最优化的数学方法 利用分阶段求解缩小决策问题的规模, 利用分治策略将原问题分解为若干较小规模但类似于原问题的子问题 自底向上 什么时候用动态规划 子问题有重叠,...
在非线性岩土/石力学问题中,网格质量是影响计算结果的一个重要因素.本文分析了弥散裂缝模型水力压裂数值求解方法中单元高宽比(AR)对计算结果的影响.材料的弹性部分采用线弹性和多孔弹性两种本构关系,屈服和破坏准则...
骆 骥 -《由"汽车问题"浅谈深度搜索的一个方面——搜索对象与策略的重要性》 毛子青 -《动态规划算法的优化技巧》 俞 玮 -《基本动态规划问题的扩展》 张一飞 -《求N!的高精度算法》 ## 2002 戴德承 -《退...
考虑到弹塑性流动理论有关联与非关联之分,本文提出利用锥型互补法求解弹塑性问题。具体以Drucker-Prager弹塑性模型为例,首先利用最大塑性功耗散原理和圆锥对偶理论等工具,建立了弹塑性本构方程的等价二阶锥互补...
在做力学计算分析中,有时候需要自己定义材料的应力应变关系,即修改其本构模型。本程序是用FORTRAN 编写的关于弹塑性材料的本构模型。
(给定一个定义在[L, R]上的单调函数f(x), 求方程f(x)=0的根) B1068 快排(数列接近有序) 此时最坏的时间复杂度为O(n^2), 原因是主元没有把当前区间划分为两个长度接近的子区间。 B1069 快排 >组合问题的分治法 B1090 ...
书中选择MPI(Message Passing Interface)、POSIX线程和OpenMP这三个应用最广泛的编写可移植并行程序的标准作为编程模型,并在不同例子中反映了并行计算的不断变化的应用组合。本书结构合理,可读性强,加之每章精心...
该攻击混合了仅在400条迹线上训练的模板攻击和一种新颖的约束求解器。 提取偏移量的方法是尝试所有16种掩码可能性,计算纯xor掩码值,然后根据学习的模板和给定的迹线计算这16个字节的概率。 概率最高的蒙版是正确的...
数独重构代码matlab EE215 上海交通大学EE215课程代码。 目录 :针对MATLAB中实现的Sudoku...++中的DP解决方案) :课程分配1-使用GA解决校准问题。 :蒙特卡洛方法的课堂练习。 :课程分配2-分析和优化时钟同步系统。
8.4.2 线谱对分析的求解 8.5 LPCC参数 8.6 MFCC参数 8.7 ASCC参数 8.8 感觉加权的线性预测(PLP)特征 8.8.1 PLP参数 8.8.2 RASTA-PLP参数 8.9 动态差分参数 8.10 高阶信号谱类特征 8.10.1 WV谱的定义及其...
通过对萃取过程的分析和必要简化、假设,给出求解模型的初始条件和边界条件。模拟了9种物料的超临界萃取过程。首次得出萃取率和平均粒径的线性关系,利用该关系准确预测了不同平均粒径和流量下的萃取曲线。明确给出...
经历了一个多世纪的漫长发展道路,电路理论已经发展成为一门体系完整、逻辑严密、具有强大生命力的学科。 在工程技术领域和实际生活中,电路理论都有非常广阔的应用。从简单的照明电路,到复杂的电力系统;从单个的...