RePorridge

Nothing change but our heart

2016年3月13日

少说话,多做事。
posted @ 2016-03-13 22:18 Porridge 阅读(224) | 评论 (0)编辑 收藏

2013年11月1日

Problem Description
Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value.
Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.


Input
Each line in the input describes one collection of marbles to be divided. The lines consist of six non-negative integers n1, n2, ..., n6, where ni is the number of marbles of value i. So, the example from above would be described by the input-line ``1 0 1 2 0 0''. The maximum total number of marbles will be 20000.

The last line of the input file will be ``0 0 0 0 0 0''; do not process this line.


Output
For each colletcion, output ``Collection #k:'', where k is the number of the test case, and then either ``Can be divided.'' or ``Can't be divided.''.

Output a blank line after each test case.


Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0


Sample Output
Collection #1:
Can't be divided.

Collection #2:
Can be divided.

题目大意:输入价值为1-6的玻璃球的数量,然后让你判断能否将它们平分成价值相等的两份

思路:刚开始想到的是普通的0-1背包,遍历每个玻璃球然后刷新状态就可以的。结果交上去TLE了

然后网上找到了半天说是要用二进制优化。然后让我来解释一下我理解的二进制优化吧

用mar[i]表示价值为i的玻璃球的总数量。二进制优化就是把你的等价值的玻璃球分成系数为1,2,4,8,...,2^(k-1),mar[i]-2^k+1.其中k 为满足 mar[i]-2^k+1 > 0 的最大值.

这样就可以分别组合成1,2,3,4,5,6,7,...,mar[i]了。玻璃球就被分为1*i,2*i,4*i,8*i,...,2^(k-1)*i,(mar[i]-2^k+1)*i

然后就可以根据0-1背包的原理做了。这样就不会超时了

Dividing
posted @ 2013-11-01 12:44 Porridge 阅读(336) | 评论 (0)编辑 收藏

2013年10月6日

首先我们来了解一下素数(质数)的概念:一个数除了1和本身之外没有别的因数
除了素数之外的数就是合数:合数可以由多个素数相乘得如 A = p1^n1 * p2 ^ n3 * p3^n3 ……

我们预先把所有的大于等于2的数都标记为素数。
这样我们就可以想到先找到第一个素数2则,4,6,8,10……就都不是素数了。
下面是实现的方法。别人那里学来的。
--------------------------------------------------------------------------------------------
2016-5-11修改代码 for循环不能用<=越界访问
Onprime
posted @ 2013-10-06 21:43 Porridge 阅读(500) | 评论 (0)编辑 收藏

2013年9月23日

好久没有上来写东西了。中秋放假以后有点放松自己了。今天先看了入门经典的书都一题就拿上来作为新的开始吧。

字母重排
输入一个字典(用******结尾),然后再输入若干单词。每输入一个单词w,你都需要在字典中找出所有可以用w的字母重排后得到的单词,并按照字典序从小到大的顺序在一行中输出(如果不存在,输出:()。输入单词之间用空格或空行隔开,且所有输入单词都由不超过6个小写字母组成。注意,字典中的单词不一定按字典序排列。

样例输入:
tarp given score refund only trap work earn course pepper part 
******
resco nfudre aptr sett oresuc
样例输出:
score
refund
part trap trap
:(

course

代码写的比较乱也没有注释,其实就是简单的字符串处理,利用ASCII码比较大小。
题意就是给定几个单词,然后再给出一行************************,再给输入一些单词,然后判断是否能够与上面给定的单词的字母重排后组成这个单词。
我的解决办法就是直接通过字母排序,因为两个单词如果字母排序后利用strcmp比较得0那么肯定可以重排组成。

resortletter.cpp
posted @ 2013-09-23 21:29 Porridge 阅读(377) | 评论 (0)编辑 收藏

2013年9月8日

Problem B
Back to High School Physics
Input: standard input
Output: standard output

A particle has initial velocity and constant acceleration. If its velocity after certain time is v then what will its displacement be in twice of that time?

Input
The input will contain two integers in each line. Each line makes one set of input. These two integers denote the value of v (-100 <= v <= 100) and t(0<=t<= 200) ( t means at the time the particle gains that velocity)

Output
For each line of input print a single integer in one line denoting the displacement in double of that time.

Sample Input
0 0
5 12

Sample Output
0
120

其实题目很简单,差点被误导了。

题意:一个物体有初速度v,然后再2*t的时间内走的位移。没有加速度。

physics.cpp
posted @ 2013-09-08 21:15 Porridge 阅读(552) | 评论 (0)编辑 收藏
ox of Bricks

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8910 Accepted Submission(s): 3032


Problem Description
Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. “Look, I've built a wall!”, he tells his older sister Alice. “Nah, you should make all stacks the same height. Then you would have a real wall.”, she retorts. After a little consideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?



Input
The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1≤n≤50 and 1≤hi≤100.

The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.

The input is terminated by a set starting with n = 0. This set should not be processed.


Output
For each set, print the minimum number of bricks that have to be moved in order to make all the stacks the same height.
Output a blank line between each set.


Sample Input
6
5 2 4 1 7 5
0


Sample Output
5


题意:给你一些参差不齐的砖块然后让你把它们摆成每堆都一样高。

算法:直接算出他们的平均值,然后找到高于平均值每堆,把高出的数量加起来就是答案了

BoxOfBricks.cpp
posted @ 2013-09-08 21:04 Porridge 阅读(464) | 评论 (0)编辑 收藏
算菜价

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11284 Accepted Submission(s): 6168


Problem Description
妈妈每天都要出去买菜,但是回来后,兜里的钱也懒得数一数,到底花了多少钱真是一笔糊涂帐。现在好了,作为好儿子(女儿)的你可以给她用程序算一下了,呵呵。


Input
输入含有一些数据组,每组数据包括菜种(字串),数量(计量单位不论,一律为double型数)和单价(double型数,表示人民币元数),因此,每组数据的菜价就是数量乘上单价啊。菜种、数量和单价之间都有空格隔开的。


Output
支付菜价的时候,由于最小支付单位是角,所以总是在支付的时候采用四舍五入的方法把分头去掉。最后,请输出一个精度为角的菜价总量。


Sample Input
青菜 1 2
罗卜 2 1.5
鸡腿 2 4.2


Sample Output
13.4

这里就是利用了sscanf和sprintf函数 用法和scanf printf类似 

sprintf的功能是将变量写到字符串中去 用法 sprintf(char*,/*输出格式如*/"%d",/*要输出的量如*/2)这样输出的结果就是"2\0"; 

而sscanf恰好相反是将字符串中的内容写入变量 sscanf(char*,"%d",&n) 就是将char*中的内容写入n 我是利用sprintf先保留一位小数输出然后再存回去。

我去百度了一下,直接把每次的钱加起来最后保留一位小数居然可以过。
代码
HDU2090exp.cpp

我的算法的代码
HDU2090.cpp
posted @ 2013-09-08 20:56 Porridge 阅读(1027) | 评论 (0)编辑 收藏
不要62

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13604 Accepted Submission(s): 4362


Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。


Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。


Output
对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。


Sample Input
1 100
0 0

Sample Output
80


本题如果直接暴力搜索会超时。我的办法是事先把0到10000000中的所有含有'4'或者"62"的筛选出来

然后建立一个数组a[] a[i]表示从0到i有多少个可用的车牌

这样输入的时候直接读这个数组输出 a[m]-a[n-1]就可以了。

HDU2089.cpp
posted @ 2013-09-08 20:46 Porridge 阅读(462) | 评论 (0)编辑 收藏
A Knight's Journey
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 26210 Accepted: 8950
Description

Background
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?


Problem
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.
Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .
Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.
If no such path exist, you should output impossible on a single line.
Sample Input

3
1 1
2 3
4 3
Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4
Source

TUD Programming Contest 2005, Darmstadt, Germany



因为题目要求 print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line.即输出字典序最小的一组答案

字典序最小就是按位比较ASCII码,相等的比较下一位,知道不相等的为止或者长度比另一个长 比如 "abc" < "bbc" "abcd" > "abc" 因为要是有路径的话长度都是一样所以不需要考虑路径长度的问题。

直接考虑每个路径,在搜索的时候只要优先往A副1的方向走,这样获得的第一条路径就是字典序最小的路径了。按照图上的路径。有的题解是转过来的,其实只要写程序的时候注意一下就行了。

这个题目我WA了N多次的原因是Scenario自己打的没有复制,然后输错了。太二了

POJ2488.cpp
posted @ 2013-09-08 20:31 Porridge 阅读(387) | 评论 (0)编辑 收藏
单词数

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 22457 Accepted Submission(s): 5433


Problem Description
lily的好朋友xiaoou333最近很空,他想了一件没有什么意义的事情,就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。


Input
有多组数据,每组一行,每组就是一篇小文章。每篇小文章都是由小写字母和空格组成,没有标点符号,遇到#时表示输入结束。


Output
每组只输出一个整数,其单独成行,该整数代表一篇文章里不同单词的总数。


Sample Input
you are my friend
#


Sample Output
4

题意就很简单了。计算没有重复的单词数量。我的做法是按位遍历,遇到字母串就记录字母串到temp里面,存到一个字符串数组中。

遇见新的单词与已经存放的单词对比如果没有重复就加入。这里要考虑的是最后。比如 "abc def"在遍历结束后最后再加一次判断def是否重复

本题主要是输入一行的函数fgets(char*,MAXNLENGTH,stdin)函数的使用,也可以使用getline或者cin.getline使用方法可以百度

我仅介绍fgets的使用方法char*就是char数组的头,MAXLENGTH是最大输入的量,stdin是控制台

由fgets输入得到的字符串的\0前面还有一个\n所以需要把这个\n改成\0 str[strlen(str)-1] = '\0';

然后就是cctype或者ctype.h头文件的函数里面有isalpha(char)判断是不是字母isdigit(char)判断是不是数字还有其他的一些函数这里就介绍两个 其他的可以度娘 谷歌

HDU2072.cpp
posted @ 2013-09-08 19:59 Porridge 阅读(689) | 评论 (0)编辑 收藏
仅列出标题  下一页

导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜