- 浏览: 467821 次
- 性别:
- 来自: 西安
文章分类
最新评论
-
752258:
...
Java文件操作(FIle类) [转] -
darrendu:
帮我解决了问题
启动出了问题:unexpected inconsistency;RUN fsck MANUALLY -
_lostman:
怎么反着来?
如果我现有一个第三方的库,如何在JAVA中调用? ...
java中JNI调用c++的dll -
caoruntao:
brother涛,你太牛了。博客访问量竟然有6W多。不得了呀
java clone -
passlicense:
好文章!顶~
unicode和ISO 8859-1
【转】http://fuliang.iteye.com/blog/143188
问题: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)了:
代码如下:
package com.iteye.caoruntao.zoj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @author caoruntao * */ public class ZOJ2042_Divisibility { private static int N; private static int K; private static int[][] flag = new int[10005][105]; private static int[] a = new int[10005]; public static int compute(int level, int value){ if(flag[level][value] != -1){ return flag[level][value]; } int check; int t1 = (value + a[level]) % K; int t2 = (value - a[level]) % K; t1 = t1 < 0 ? t1 + K : t1; t2 = t2 < 0 ? t2 + K : t2; if(level == N){ if(value%K == 0){ check = 1; }else{ check = 0; } } else if(compute(level+1, t1) == 1){ check = 1; } else if(compute(level+1, t2) == 1){ check = 1; } else{ check = 0; } return flag[level][value]=check; } /** * @param args */ public static void main(String[] args) { int n; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = ""; String result = ""; try { str = br.readLine(); n = Integer.parseInt(str); for(int i=0; i<n; i++){ str = br.readLine(); String[] strArr = str.split(" "); N = Integer.parseInt(strArr[0]); K = Integer.parseInt(strArr[1]); str = br.readLine(); strArr = str.split(" "); for(int j=0; j<N; j++){ a[j] = Integer.parseInt(strArr[j]); } for(int j=0; j<=N; j++){ for(int m=0; m<=K; m++){ flag[j][m] = -1; } } result = compute(1, a[0]%K)==1 ? "Divisible" : "Not divisible"; System.out.println(result); } } catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); } } }
发表评论
-
全概率公式和Bayes公式
2011-09-22 21:39 1352假设导致事件A发生的“ ... -
卡塔兰数
2011-09-22 21:18 1644[转]http://gpww.blog.163.com/blo ... -
海量数据处理之Bloom Filter详解
2011-09-22 08:40 979【转】http://blog.csdn.net/v ... -
十七道海量数据处理面试题与Bit-map详解
2011-09-22 08:39 1383[转]http://blog.csdn.net/v_july_ ... -
判断素数
2011-09-15 15:15 1065#include <math.h> bool ... -
输出100000以内的素数
2011-09-15 15:13 2500#include <fstream.h> ... -
判断单链表是否存在环,判断两个链表是否相交问题详解
2011-09-06 09:36 1141[转]http://www.cppblog.com/human ... -
分解质因数
2011-09-03 14:46 958#include <stdio.h> ... -
把字符串转换成整数
2011-08-24 19:26 1482【转】http://zhedahht.blog.163.com ... -
用两个栈实现队列
2011-08-24 19:18 1117【转】http://zhedahht.blog.163.com ... -
反转链表
2011-08-24 17:24 901【转】http://zhedahht.blog.163.com ... -
最长公共子串
2011-08-24 17:01 1085【转】http://zhedahht.blog.1 ... -
左旋转字符串
2011-08-24 16:57 1064【转】http://zhedahht.blog.1 ... -
跳台阶问题
2011-08-24 16:37 1000【转】http://zhedahht.blog.163.com ... -
和为n连续正数序列
2011-08-24 16:23 765【转】http://zhedahht.blog.163.com ... -
二元树的深度
2011-08-24 16:09 942【转】http://zhedahht.blog.163.com ... -
调整数组顺序使奇数位于偶数前面
2011-08-24 16:05 1449【转】http://zhedahht.blog.163.com ... -
从尾到头输出链表
2011-08-24 15:58 868【转】http://zhedahht.blog.163.com ... -
在O(1)时间删除链表结点
2011-08-24 15:49 868【转】http://zhedahht.blog.163.com ... -
找出数组中两个只出现一次的数字
2011-08-24 15:24 1028【转】http://zhedahht.blog.1 ...
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
acm中zoj1002的可运行C++程序
一个非常非常非常非常实用的zoj结题代码
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
浙江大学ZOJ源码题解,按照题目类型和难易分类。
能AC 通过的c++代码,包括zoj1002,1091,1789
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
leetcode杯 这里记录各种AC代码哦! 怎么说千千都是新人那! 懵懂无知感觉时间过得真的好快,不知不觉就已经大二了唉~ 只是不想在考试之后看到自己会挂科 o(╯□╰)o 每次更换头像都会找很久很久惹...zoj 蓝桥杯 计蒜客
zoj的代码实现,很好,而且很全面,全部实现。
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
第一套动态规划:ZJU1558 难度:比较简单博弈问题:ZJU1913 难度:中等偏难递归计算:ZJU1500 难度:中等最小生成树:ZJU1914 难度:中等第二套动态规划:ZJU1107 难度:中等偏难 另外,以下是一些其它浙大ACM的...
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法