codeforces #322 div 2 D. Three Logos (枚举)

D. Three Logos
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area.

Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Your task is to determine if it is possible to put the logos of all the three companies on some square billboard without breaking any of the described rules.

Input

The first line of the input contains six positive integers x1, y1, x2, y2, x3, y3 (1 ≤ x1, y1, x2, y2, x3, y3 ≤ 100), where xi and yi determine the length and width of the logo of the i-th company respectively.

Output

If it is impossible to place all the three logos on a square shield, print a single integer “-1″ (without the quotes).

If it is possible, print in the first line the length of a side of square n, where you can place all the three logos. Each of the next n lines should contain n uppercase English letters “A”, “B” or “C”. The sets of the same letters should form solid rectangles, provided that:

  • the sizes of the rectangle composed from letters “A” should be equal to the sizes of the logo of the first company,
  • the sizes of the rectangle composed from letters “B” should be equal to the sizes of the logo of the second company,
  • the sizes of the rectangle composed from letters “C” should be equal to the sizes of the logo of the third company,

Note that the logos of the companies can be rotated for printing on the billboard. The billboard mustn’t have any empty space. If a square billboard can be filled with the logos in multiple ways, you are allowed to print any of them.

See the samples to better understand the statement.

Sample test(s)
input

output

input

output

hdu 5481||bestcoder #57 div 2 C Desiderium (概率)

Desiderium

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 427    Accepted Submission(s): 167

Problem Description

There is a set of intervals, the size of this set is n.

If we select a subset of this set with equal probability, how many the expected length of intervals’ union of this subset is?

We assume that the length of empty set’s union is 0, and we want the answer multiply 2n modulo 109+7.

 

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with a integer n ,which is size of set.

Then n lines follow, each contain two integers l,r describing a interval of [l,r].

1n100,000.

1,000,000,000lr1,000,000,000.

 

Output
For every test case output the answer multiply 2n modulo 109+7.

 

Sample Input
2
1
0 1
2
0 2
1 3

 

Sample Output

1 7

Hint

For the second sample, the excepted length is $frac{0+2+2+3}{4}=frac{7}{4}$.

比赛的时候并没有做出来…sad..
因为b题调了太久…这题基本就没时间了...果然还是太弱了QAQ
然后发现有时间也做不出…
题意真是好难懂...
转载一段题解:

一个含有n个区间的集合,从该集合中等概率地选取子集,求所有子集中的所有区间的构成的并集长度的和。

第二个样例解释:

集合中含有2个区间:一个是[0,2],编号为1,一个是[1,3],编号为2。

集合的子集有4个:

1、空集,集合中区间的并的长度为0

2、{区间1},集合中区间的并的长度为2

3、{区间2},集合中区间的并的长度为2

4、{区间1、区间2},集合中区间的并为[0,3],长度为3

考虑某一个区间对于答案的贡献:

若某个区间没有被其它区间覆盖,则该区间在子集中出现的总次数为:2^(n-1)次(总子集数-去掉该区间的子集总数)

若某个区间被覆盖了1次,即有2个区间重叠,那么该区间在子集中出现总次数为:2^(n-1)+2^(n-2)次(第1个区间在子集中出现的次数+第2个区间在子集中出现且第1个区间不出现的总次数)

…………

可以得到

若该区间被覆盖了k(k>=0)次,即有k+1个区间重叠,得到该区间在所有子集中出现的总次数:2^(n-1)+2^(n-2)+……+2^(n-k-1)

如何统计每一个区间的重叠次数?

对于输入的每一个区间的两个端点,给一个权值,左端点为1,右端点为-1。然后把所有端点按照位置从小到大排序。从左往右扫一遍,累加端点的权值,得到的当前的权值和就是当前所在区间的重叠次数。

累加每个区间的重叠次数*区间长度,即为所求。

codeforces #322 div 2 C. Developing Skills(乱搞)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya loves computer games. Finally a game that he’s been waiting for so long came out!

The main character of this game has n different skills, each of which is characterized by an integer ai from 0 to 100. The higher the numberai is, the higher is the i-th skill of the character. The total rating of the character is calculated as the sum of the values ​​of  for all i from 1 to n. The expression ⌊ x⌋ denotes the result of rounding the number x down to the nearest integer.

At the beginning of the game Petya got k improvement units as a bonus that he can use to increase the skills of his character and his total rating. One improvement unit can increase any skill of Petya’s character by exactly one. For example, if a4 = 46, after using one imporvement unit to this skill, it becomes equal to 47. A hero’s skill cannot rise higher more than 100. Thus, it is permissible that some of the units will remain unused.

Your task is to determine the optimal way of using the improvement units so as to maximize the overall rating of the character. It is not necessary to use all the improvement units.

Input

The first line of the input contains two positive integers n and k (1 ≤ n ≤ 105, 0 ≤ k ≤ 107) — the number of skills of the character and the number of units of improvements at Petya’s disposal.

The second line of the input contains a sequence of n integers ai (0 ≤ ai ≤ 100), where ai characterizes the level of the i-th skill of the character.

Output

The first line of the output should contain a single non-negative integer — the maximum total rating of the character that Petya can get using k or less improvement units.

Sample test(s)
input

output

input

output

input

output

Note

In the first test case the optimal strategy is as follows. Petya has to improve the first skill to 10 by spending 3 improvement units, and the second skill to 10, by spending one improvement unit. Thus, Petya spends all his improvement units and the total rating of the character becomes equal to lfloor frac{100}{10} rfloor +  lfloor frac{100}{10} rfloor = 10 + 10 =  20.

In the second test the optimal strategy for Petya is to improve the first skill to 20 (by spending 3 improvement units) and to improve the third skill to 20 (in this case by spending 1 improvement units). Thus, Petya is left with 4 improvement units and he will be able to increase the second skill to 19 (which does not change the overall rating, so Petya does not necessarily have to do it). Therefore, the highest possible total rating in this example is .

In the third test case the optimal strategy for Petya is to increase the first skill to 100 by spending 1 improvement unit. Thereafter, both skills of the character will be equal to 100, so Petya will not be able to spend the remaining improvement unit. So the answer is equal to .

 

不能超过100没看到…

贡献若干次wa…蠢哭了.

然后写蠢了…

最后觉得这样写比较好:

开一个结构体数组… a,b

a用来记录原始值,b用来记录mod10的余数与10的差..

整个填充过程分两步骤

第一步是把余数不为0的填充到10..

这部分要先填充…显然比先填充余数为0的更优.而且先填充余数大的..也就是b小的…

以b为关键字…从小到达排序..

然后填充的时候记得更新 a的值到整十  

同时用一个sum累加更新后的a[i] 到100的距离…

sum/10是一个限制条件

而k/10是第二个限制条件

所以答案最后加上 min(k,sum)/10;

codeforces #322 div 2 B. Luxurious Houses (思路)

B. Luxurious Houses
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.

Let’s enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

The new architect is interested in n questions, i-th of them is about the following: “how many floors should be added to the i-th house to make it luxurious?” (for all i from 1 to n, inclusive). You need to help him cope with this task.

Note that all these questions are independent from each other — the answer to the question for house i does not affect other answers (i.e., the floors to the houses are not actually added).

Input

The first line of the input contains a single number n (1 ≤ n ≤ 105) — the number of houses in the capital of Berland.

The second line contains n space-separated positive integers hi (1 ≤ hi ≤ 109), where hi equals the number of floors in the i-th house.

Output

Print n integers a1, a2, …, an, where number ai is the number of floors that need to be added to the house number i to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then ai should be equal to zero.

All houses are numbered from left to right, starting from one.

Sample test(s)
input

output

input

output

codeforces #322 div 2 A. Vasya the Hipster(纱布题)

A. Vasya the Hipster
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Vasya the Hipster decided to count how many socks he had. It turned out that he had a red socks and b blue socks.

According to the latest fashion, hipsters should wear the socks of different colors: a red one on the left foot, a blue one on the right foot.

Every day Vasya puts on new socks in the morning and throws them away before going to bed as he doesn’t want to wash them.

Vasya wonders, what is the maximum number of days when he can dress fashionable and wear different socks, and after that, for how many days he can then wear the same socks until he either runs out of socks or cannot make a single pair from the socks he’s got.

Can you help him?

Input

The single line of the input contains two positive integers a and b (1 ≤ a, b ≤ 100) — the number of red and blue socks that Vasya’s got.

Output

Print two space-separated integers — the maximum number of days when Vasya can wear different socks and the number of days when he can wear the same socks until he either runs out of socks or cannot make a single pair from the socks he’s got.

Keep in mind that at the end of the day Vasya throws away the socks that he’s been wearing on that day.

Sample test(s)
input

output

input

output

input

output

Note

In the first sample Vasya can first put on one pair of different socks, after that he has two red socks left to wear on the second day.

实在没有可以解释的…

[转自codeforces] How to come up with the solutions: techniques

As I work with students I often face the situation when if a problem doesn’t seem clear to a student at the first sight, it makes them unable to solve it. Indeed, you always hear about specific methods and techniques. But you don’t hear about how to think in order to apply them. In this note I’ll try to sum up my experience of solving programming contest problems. However, some pieces of advice will also be applicable for olympiads in mathematics and your first steps in academic research.

So you’ve read a problem and you don’t know how to solve it. Try the following techniques, some of them can often come handy.

Technique 1: “Total Recall”

Try to remember some similar problems that you had to solve. Quite many problems do not have a brand new idea. So probably, you can use your experience of solving a similar problem to solve this one.

Technique 2: “From Specific to General”

Let’s say that you’ve found the solution for the problem (hurray!). Let’s consider some particular case of a problem. Of course, you can apply the algorithm/solution to it. That’s why, in order to solve a general problem, you need to solve all of its specific cases. Try solving some (or multiple) specific cases and then try and generalize them to the solution of the main problem. Such specific cases can be regarded as the simplifications of the problem, i.e. we can reason by the following principle: “if I don’t know how to solve a complex problem, I think I’ll simplify it and find the solutions of the simplified version”.

The popular examples of simplifications (specific cases):

  • you get a problem for a tree. Consider its variant where the tree degenerates into a path;
  • the problem has weights? Consider a variant where all the weights are equal either to one or to an arbitrary number, or there are only two distinct weights (and so on).

Note that the solution of a specific case almost always isn’t easier than the solution of a general one, so you need to try and find a solution that would be as easy and effective as possible.

Technique 3: “Bold Hypothesis”

Don’t be shy of making bold hypotheses that seem true to you. You do not have to prove your solutions during contests, tap your inner intuition. When you’ve come up with your hypothesis, try to prove it — it may either work out well or give you an idea of how to disprove it. Do test the hypothesis on a wide set of tests as it would be a pain to waste time on implementing a solution based on a hypothesis and only after that disprove the hypothesis.

Examples:

  • the solution always exists;
  • item the number of states isn’t large.
Technique 4: “To solve a problem, you should think like a problem”

I’m serious, put yourself in the shoes of the character of the problem, imagine that it’s your job to handle the input sets. Think about how you’d act in this case. Try to process some small samples on your own. If the problem is about a game, play it. Sometimes I try to visualize a process or a model for better understanding. It’s a little like how movies show the way scientists think. Try to think in images, imagine the solution, see it unfolding.

Technique 5: “Think together”

This technique is only applicable to team contests. In group of two or three persons start saying some clear facts about the problem. For example: “if n is even, then the answer is always 0”, “if n is prime, then the solution should go like that”, and so on. Sometimes your teammates will pick up ideas and develop them and this strategy can get you through the problem.

Technique 6: “Pick a Method”

Try coming through popular algorithms or methods that can apply to the problem in any way. It is useful to see the problem limits. Having picked a method, try thinking on the solution assuming that the problem is solved using this method. Your reasonings should be somewhat like this: “Let’s assume that the problem is solved by divide and conquer. Then let us solve this problem recursively for the left and right half. Now all that’s left is to find a way to unite these solutions. I wonder how we can do that…”

Technique 7: “Print Out and Look”

Quite often (especially in problems with a small input: one/two numbers) there are some patterns in the composition of the solution. To see a pattern, you sometimes need to write some naive method of solving a problem, generate answers for a large number of tests on large limits and meditate on your answers for a while. In order not to keep the computer busy, a good strategy is to print out the acquired results and meditate this time on the print outs.

Sometimes it is a good idea to print not only the answer, but also some extra information, such as a manner of acquiring a solutions.

Technique 8: “Google”

This technique can only be used if the round/contest rules allow it. If the problem is about sequences, then you can look for solutions (see technique 7) on the site https://oeis.org/. It helps to understand the formal model of the problem and google the correct mathematical terms

uva 489

In Hangman Judge,” you are to write a program that judges a series of Hangman games. For each game, the answer to the puzzle is given as well as the guesses. Rules are the same as the classic game of hangman, and are given as follows:

  1. The contestant tries to solve to puzzle by guessing one letter at a time.
  2. Every time a guess is correct, all the characters in the word that match the guess will be turned over.” For example, if your guess is o” and the word is book”, then both o”s in the solution will be counted as solved.”
  3. Every time a wrong guess is made, a stroke will be added to the drawing of a hangman, which needs 7 strokes to complete. Each unique wrong guess only counts against the contestant once. 
  4. If the drawing of the hangman is completed before the contestant has successfully guessed all the characters of the word, the contestant loses.
  5. If the contestant has guessed all the characters of the word before the drawing is complete, the contestant wins the game.
  6. If the contestant does not guess enough letters to either win or lose, the contestant chickens out.

Your task as the Hangman Judge” is to determine, for each game, whether the contestant wins, loses, or fails to finish a game.

 

Input

Your program will be given a series of inputs regarding the status of a game. All input will be in lower case. The first line of each section will contain a number to indicate which round of the game is being played; the next line will be the solution to the puzzle; the last line is a sequence of the guesses made by the contestant. A round number of -1 would indicate the end of all games (and input).

 

Output

The output of your program is to indicate which round of the game the contestant is currently playing as well as the result of the game. There are three possible results:

 

 

Sample Input

 

 

Sample Output

 

水题还wa.真是药丸.药丸啊…

hdoj 5479 || bestcoder #57 div 2 A Scaena Felix(模拟)

模拟.
直接搞…
并不明白坑在哪里...
排在我前面被hack了100多人…

hdu 5480|| bestcoder   #57 div 2 Conturbatio(前缀和||树状数组)

比较水.
唯一一点需要注意的是…
可能有重复元素…
因为我的思路是用两棵一维树状数组搞..
每个点标记为1
然后看矩形的两个方向中是否至少有一个方向上和等于长度…
所以这样如果有重复元素的话,不处理会出错.. 
 
但实际上又没修改..直接前缀和就好了...
树状数组个毛线...
不过看到还有人线段树搞得233333
 
 

codeforces #321 div 2 B. Kefa and Company(尺取法)

B. Kefa and Company
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Kefa wants to celebrate his first big salary by going to restaurant. However, he needs company.

Kefa has n friends, each friend will agree to go to the restaurant if Kefa asks. Each friend is characterized by the amount of money he has and the friendship factor in respect to Kefa. The parrot doesn’t want any friend to feel poor compared to somebody else in the company (Kefa doesn’t count). A friend feels poor if in the company there is someone who has at least d units of money more than he does. Also, Kefa wants the total friendship factor of the members of the company to be maximum. Help him invite an optimal company!

Input

The first line of the input contains two space-separated integers, n and d (1 ≤ n ≤ 105, ) — the number of Kefa’s friends and the minimum difference between the amount of money in order to feel poor, respectively.

Next n lines contain the descriptions of Kefa’s friends, the (i + 1)-th line contains the description of the i-th friend of type misi(0 ≤ mi, si ≤ 109) — the amount of money and the friendship factor, respectively.

Output

Print the maximum total friendship factir that can be reached.

Sample test(s)
input

output

input

output

Note

In the first sample test the most profitable strategy is to form a company from only the second friend. At all other variants the total degree of friendship will be worse.

In the second sample test we can take all the friends.

 

尺取直接搞…

然后因为没开longlong wa了一发…

因为看错条件,money差值等于d也会被鄙视...所以不能取等号…

都是傻逼错误…药丸,药丸啊…

poj 2739 Sum of Consecutive Prime Numbers (尺取法)

>一开始迷之wa…
先找出素数下标的上界就可以A…
然后纠结了20分钟...
然后发现是预处理的素数少了一个素数..
我预处理是处理到<10005的素数...
最大数10000,而超过10000的第一个素数是10007
这样判断终止条件就会死循环…
sad

poj 2100 Graveyard Design (two pointers ,尺取法)

不多说,直接代码。

poj 2566 Bound Found (前缀和,尺取法(two pointer))

题意 :给定一个长度为n的区间.然后给k次询问,每次一个数t,求一个区间[l,r]使得这个区间和的绝对值最接近t

没办法直接尺取.

先预处理出来前缀和

如果要找一对区间的和的绝对值最最近t

等价于找到两个数i和j,使得sum[i]-sum[j]的绝对值最接近t,且i<>j

那么对前缀和排序…然后尺取

因为答案要输出下标

所以之前先存一下下标.

然后对于i,j

所对应的区间为[min(pre[i].id,pre[j].id)+1,max(pre[i],id,pre[j].id)];

poj 3320 Jessica’s Reading Problem (尺取法)

Jessica’s Reading Problem
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 8787   Accepted: 2824

Description

Jessica’s a very lovely girl wooed by lots of boys. Recently she has a problem. The final exam is coming, yet she has spent little time on it. If she wants to pass it, she has to master all ideas included in a very thick text book. The author of that text book, like other authors, is extremely fussy about the ideas, thus some ideas are covered more than once. Jessica think if she managed to read each idea at least once, she can pass the exam. She decides to read only one contiguous part of the book which contains all ideas covered by the entire book. And of course, the sub-book should be as thin as possible.

A very hard-working boy had manually indexed for her each page of Jessica’s text-book with what idea each page is about and thus made a big progress for his courtship. Here you come in to save your skin: given the index, help Jessica decide which contiguous part she should read. For convenience, each idea has been coded with an ID, which is a non-negative integer.

Input

The first line of input is an integer P (1 ≤ P ≤ 1000000), which is the number of pages of Jessica’s text-book. The second line contains P non-negative integers describing what idea each page is about. The first integer is what the first page is about, the second integer is what the second page is about, and so on. You may assume all integers that appear can fit well in the signed 32-bit integer type.

Output

Output one line: the number of pages of the shortest contiguous part of the book which contains all ideals covered in the book.

Sample Input

Sample Output

分类: C/C++

 

转载一段讲解
 
     我们先来介绍一下尺取法。尺取法,顾名思义,像尺子一样,一块一块的截取。是不是解释的有点让人纳闷~。。没关系,下面我们通过这个题目来体会尺取法的魅力。

 

题目翻译:

  给定长度为n的数列整数a0,a1,a2,a3 ….. an-1以及整数S。求出综合不小于S的连续子序列的长度的最小值。如果解不存在,则输出0。

 

  限制条件:

    10

    0

    S<10^8

 

这里我们拿第一组测试数据举例子,即 n=10, S = 15, a = {5,1,3,5,10,7,4,9,2,8}

 

   这幅图便是尺取法怎么“取”的过程了。

  整个过程分为4布:

    1.初始化左右端点

    2.不断扩大右端点,直到满足条件

    3.如果第二步中无法满足条件,则终止,否则更新结果

    4.将左端点扩大1,然后回到第二步

 

用尺取法来优化,使复杂度降为了O(n)。

最后,再给一个尺取法的定义以便更好理解:返回的推进区间开头和结尾,求满足条件的最小区间的方法称为尺取法。

以上为网上关于尺取法的原理介绍,还是比较好理解的,邢如蚯蚓的爬动。

 

 

  然后这道题可以先用set ,统计出不同的知识点有多少个,总是记为total

  然后根据一段区间内的知识点数目sum是否达到total来移动两个pointer head 和tail

  因为知识点的标号比较大,数组下表存不下,所以开个map来统计相应知识点出现的数量…

  然后还有个...

  误以为if (cnt[a[tail++]]++==0) sum++;和

  if (cnt[a[tail]]==0)

  {

    sum++;

    cnt[a[taill]]++;

    tail++;

  }

  是等价的...

幸好没去队群里问...不然又要被嘲讽一番了..

区别在于.前者无论cnt[a[tail]]是否为0,tail和cnt都会++;

而后者..只有在cnt[a[tail]]为0时,tail和cnt才会++

迟取法

http://www.cnblogs.com/shuzy/p/3812924.html

就是两个指针表示区间[l,r]的开始与结束然后根据题目来将端点移动,是一种十分有效的做法。适合连续区间的问题

3320

这道意思是一本书有n页,每一页上有一个知识点标号a[i]可能重复,要求选择一个最小的区间使得能够覆盖所有知识点

分析:[l,r]区间推进,统计区间中能够覆盖的知识点数,对于每一个l,r都是满足可以覆盖所有知识点的最小r,处理好区间知识点数的统计就好了

复制代码

复制代码

2566

给你一个数组(可为负数)m次询问,每次询问一个区间使得区间和的绝对值最接近给定的值,有多种随意输出一种

分析:预处理前缀和sum[i]这样可以O(1)查询区间和,然后sum数组从小到大排序(因为abs(sum[i]-sum[j])=abs(sum[j]-sum[i])所以顺序不影响答案,但可以方便尺取)然后就是O(n)推进,每次有最小值是更新答案区间信息就可以了

复制代码

复制代码

2739

给你一个数,询问有多少个连续质数序列和等于该数例如53=5 + 7 + 11 + 13 + 17 

分析:筛法求质数,然后直接twopoint就可以了,统计可以相等的个数

复制代码

复制代码

2100

给你一个数,询问有多少种连续自然数的平方和等于这个数,输出所有可能

分析:由上面的基础很简单了,对于每个数枚举区间,求和,推进区间,如果可以的话将区间记录最后输出就可以了,注意使用long long ,复杂度O(1e7)

复制代码

复制代码