111qqz的小窝

老年咸鱼冲锋!

hdu 1171 Big Event in HDU (母函数,01背包)

Big Event in HDU

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 26534    Accepted Submission(s): 9332

Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).

 

Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 — the total number of different facilities). The next N lines contain an integer V (0<V<=50 –value of facility) and an integer M (0<M<=100 –corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.

 

Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.

 

Sample Input
2
10 1
20 1
3
10 1
20 2
30 1
-1

 

Sample Output
20 10
40 40

 

Author
lcy

背包。

所有的设备不是放在第一部分,就是要放在第二部分。

那么对于第一部分,或者第二部分,每一个设备就只有放和不放两种情况。

然后感觉就是做一个容量为总数的一半的01背包

然后脑抽看到第一部分可以大于一半,觉得这么想是错的。。。

实际上并不是,因为第二部分总要比第一部分小,所以第二部分是不可能大于一半的。

所以我们对于第二部分做01背包。

 

 

 

还有一种母函数的做法:先得到每种价值有多种种方法,然后从总价值一半向下找到第一个方案数非0的价值,就是答案。
注意。。。数组开小不一定是re…tle,wa,re都有可能

注意。。。数组开小不一定是re…tle,wa,re都有可能

注意。。。数组开小不一定是re…tle,wa,re都有可能

 

 

 

hdu 1203 I NEED A OFFER! (01背包)

I NEED A OFFER!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 18287    Accepted Submission(s): 7320

Problem Description
Speakless很早就想出国,现在他已经考完了所有需要的考试,准备了所有要准备的材料,于是,便需要去申请学校了。要申请国外的任何大学,你都要交纳一定的申请费用,这可是很惊人的。Speakless没有多少钱,总共只攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每个学校都有不同的申请费用a(万美元),并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他可以收到至少一份offer的最大概率。(如果Speakless选择了多个学校,得到任意一个学校的offer都可以)。

 

Input
输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。

 

Output
每组数据都对应一个输出,表示Speakless可能得到至少一份offer的最大概率。用百分数表示,精确到小数点后一位。

 

Sample Input
10 3
4 0.1
4 0.2
5 0.3
0 0

 

Sample Output

44.0%

Hint

You should use printf(“%%”) to print a ‘%’.

 

Author
Speakless

 

Source

 

Recommend
JGShining   |   We have carefully selected several similar problems for you:  1171 2159 2955 1176 1114
01背包
最开始WA在初始化,dp数组全都赋值为1,忘赋了dp[0],导致如果恰好是花光所有钱得到答案的时候答案错误。
然后还一直WA。
后来发现是当N=0的时候,我直接取了所有A[I]=0对应的B[I]中最大的值。。。这显然是错的,少年你是脑抽吗。。。。。
然后修改了下,终于A掉了。。。。。

hdu 2546 饭卡 (01背包)

饭卡

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14225    Accepted Submission(s): 4945

Problem Description
电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。
某天,食堂中有n种菜出售,每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
 

 

Input
多组数据。对于每组数据:
第一行为正整数n,表示菜的数量。n<=1000。
第二行包括n个正整数,表示每种菜的价格。价格不超过50。
第三行包括一个正整数m,表示卡上的余额。m<=1000。 n=0表示数据结束。
 

 

Output
对于每组输入,输出一行,包含一个整数,表示卡上可能的最小余额。
 

 

Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
 

 

Sample Output
-45
32
 

 

Source
 
 
 
在入门dp。
显然是01背包。 cost和value都是价钱。
但是有限制条件。
很容易想到,为了使得余额最少,我们要把最贵的留在最后买。
读入的时候把最贵的菜价拿出来
然后剩下的n-1个菜,做一个容量为m-5的01背包。
注意如果m<5,直接输出即可。
 

HDOJ 4882 Loves Codefires

ZCC Loves Codefires
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 988 Accepted Submission(s): 500

 

Problem Description

Though ZCC has many Fans, ZCC himself is a crazy Fan of a coder, called “Memset137”.
It was on Codefires(CF), an online competitive programming site, that ZCC knew Memset137, and immediately became his fan.
But why?
Because Memset137 can solve all problem in rounds, without unsuccessful submissions; his estimation of time to solve certain problem is so accurate, that he can surely get an Accepted the second he has predicted. He soon became IGM, the best title of Codefires. Besides, he is famous for his coding speed and the achievement in the field of Data Structures.
After become IGM, Memset137 has a new goal: He wants his score in CF rounds to be as large as possible.
What is score? In Codefires, every problem has 2 attributes, let’s call them Ki and Bi(Ki, Bi>0). if Memset137 solves the problem at Ti-th second, he gained Bi-Ki*Ti score. It’s guaranteed Bi-Ki*Ti is always positive during the round time.
Now that Memset137 can solve every problem, in this problem, Bi is of no concern. Please write a program to calculate the minimal score he will lose.(that is, the sum of Ki*Ti).

Input

The first line contains an integer N(1≤N≤10^5), the number of problem in the round.
The second line contains N integers Ei(1≤Ei≤10^4), the time(second) to solve the i-th problem.
The last line contains N integers Ki(1≤Ki≤10^4), as was described.

 

Output

One integer L, the minimal score he will lose.

 

Sample Input

3
10 10 20
1 2 3

Sample Output

150

Hint
Memset137 takes the first 10 seconds to solve problem B, then solves problem C at the end of the 30th second. Memset137 gets AK at the end of the 40th second.
L = 10 * 2 + (10+20) * 3 + (10+20+10) * 1 = 150.

Author

镇海中学

 

Source

2014 Multi-University Training Contest 2

 

 

贪心题。

很容易想到的是,为了让答案尽可能的小,最好使e小的和K大的尽可能早的完成。也就是说E和K的大小对结果都会有影响。

我们按E/K排个序。

注意冒泡会TLE。。。别问我怎么知道的T T

也别问我为什么不用Sort….因为我不会写CMP函数。。。

噗,其实很简单嘛

poj 1065 Wooden Sticks

Wooden Sticks
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19008 Accepted: 8012
Description

There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l’ and weight w’ if l <= l’ and w <= w’. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are ( 9 , 4 ) , ( 2 , 5 ) , ( 1 , 2 ) , ( 5 , 3 ) , and ( 4 , 1 ) , then the minimum setup time should be 2 minutes since there is a sequence of pairs ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) .
Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1 <= n <= 5000 , that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l1 , w1 , l2 , w2 ,…, ln , wn , each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.
Output

The output should contain the minimum setup time in minutes, one per line.
Sample Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1
Sample Output

2
1
3

 

 

 

贪心题。题目很容易懂,就不翻译了。略水,一遍AC,久违的快感!!!hhhh ,嘛,我为注意节制的(哪和哪!)

把w和l分别按第一关键字和第二关键字排序。

然后扫描一遍,如果符合w[i]>=wk[k]&&l[i]>=lk[k]就更新wk[k]和lk[k],分别表示的是第K的操作下能达到的最大w和l.

如果不符合,则需要增加一分钟的工作时间。同样不要忘记更新。

codeforces 447 B. DZY Loves Strings

简单贪心。

因为填的字母没有次数限制,所以最优策略很容易想到,就是在最后面填最大的。

不用实际去填,算出ans就可以。

hdu 1009 FatMouse’ Trade

 

 

简单贪心….

需要注意的是数据是非负,所以有0的情况要考虑周全,基本都要特殊处理。

多WA了三次,不知道为什么交C++可以过,交G++就不行。

hdu 1050 Moving Tables

 

 

一开始算法想的有点问题。

坑点在于走廊两侧都有房间

也就是说room1和room2对应的位置是一样的

1 to 3 4to6 是没法同时完成的。

做法就是整个扫一遍,看哪个位置的重复次数最大,*10就是答案。

hdu 5120 – Intersection

题意:求两个相等的圆环的相交的面积….
简单计算几何+容斥原理?
扇形面积公式记错调了半天2333333333
     这题不难…倒是从学长那里收获了几点关于代码规范的问题… 
听说了学长在北京区域赛时把PI定义错了一位结果一直WA的教训…. 以后还是写acos(-1)吧
局部变量和全局变量因为【想怎么其变量名想得整个人都不好了】就起成了一样的…被学长给了差评。
哦,对!还有一个就是发现了cmath库里有一个奇葩的函数名叫y1.。。。。。。。
——————————————————————————————————————————————
竟然CE了  提示 error:pow(int,int) is ambiguous
看来我对语言的掌握程度还是不行呀…..

“就是一个函数声明为pow(double, double)你必须传两个double参数进去。但你传int也可以,int会转型会double,但c++有重载。声明了两个函数pow(double, double),pow(long long, double),你传两个int进去编译器不知道把int转为double还是转为long long”
“解决办法是把int转型成double (xxx) 或者long long (xxx)” 也可以 简单粗暴的xxx.0

 

(int,int)->(double,int)?(double,double)

 

图片

 

 

 

hdu 5119 – Happy Matt Friends(dp解法)

Description

Matt has N friends. They are playing a game together.

Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.

Matt wants to know the number of ways to win.

Input

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10 6).

In the second line, there are N integers ki (0 ≤ k i ≤ 10 6), indicating the i-th friend’s magic number.

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.

正解貌似是高斯消元….不会的说….PYY说不就是解方程么….然后我去看了下…..挺多概念没学线代的话还是挺眼生的…(orzpyy大神)记得高三的时候做过一个用矩阵加速求线性递推式的东西….当时10^18的数据秒过….还是挺让我惊讶了一下…
扯远了… 这题dp也能做,有点类似01背包(dp真是够渣,寒假看看能不能抽时间弄一下,依然是最大的短板)
只不过状态转移方程是 dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]]
然后正常些貌似会MLE。。。。。用到了滚动数组
其实滚动数组,完全…没有理解的难度啊
竟然是我第一次使用,大概是因为基本没怎么做过DP的题吧,而滚动数组这个优化貌似主要在Dp的题里需要…
然后在搜滚动数组的时候,看到一篇博客里用异或来表示两个状态我觉得这一点也很赞…..
我自己想的话的大概就要又加,又mod,然后还得再来一个变量了吧…..差评满满
还有位运算….是挺神的东西….目前还处于一知半解的阶段….ORZ  M67大神

 

hdu 5113 Black And White

题意是说用k重颜色填充n*m的方格,第i种颜色要用ci次,保证ci(i属于1..k)的和为n”m,问是否有可行解,若有,输出任意一种。
第一感觉是dfs.。。而且数据范围还那么小。但是鉴于我上次dfs写成汪的经历….嗯 不过群里有学长说似乎剪枝不太好想?
我一开始分了四类,o行o列,e行e列,e行o列,o行e列,(o是odd,e是even)然后将c[i]排序,先填大的C[I],感觉这样应该更容易找到解。交了一发,WA掉了。。发现当k较小的时候,也就是c[i]都相对较大的时候,先填大的C[I]的策略会出现错误。于是我换了下….按c[i]的大小从两边往中间…然后我还发现其实o行o列和e行e列可以归为一类,同理,后两种也可以归为一类。又交,又WA2333333  然后想了好久。。。 发现对于上面说的两类的处理顺序不同会得到不同的结果…….只有一种是对的。于是加了个judge函数判断冲突…如果冲突就换个顺序…..再交,A了。

过程中出现了两个语法上的错误….一个是=写成了==(从来都是把==写成=。。。)
另一个是无参数的函数依然要写()。。。。。。

确实不难….的确是我生疏了。

hdu 2138 How many prime numbers

2

_____________________________
ACM STEPS里的…这题前面一道是求LCM….结果接下来就是这么一道。。。
朴素会超….筛法会爆….题目顺序真是按照难度来的?
于是想到 Miller-Rabin素数测试…….
这个方法是基于费马小定理
我的理解就是…
如果我要判断n是否为素数
只要取k个数 如果满足 a^(n-1)mod n =1 那么n就很可能为素数。
证明什么的…暂时还是算了吧…论文里貌似扯了一大堆
第一次用,竟然真的A了。。。。
感觉更好的办法也许是先打一个比较小的素数表,然后每次random选取若干个进行判断…那样应该更可靠些?
本来想WA掉之后再改的。。。没想到这么写就A掉了。。。。杭电数据略水?

 

粤ICP备18103363