月度归档:2016年06月

SparseTable口胡笔记

先声明纯属口胡,借鉴于大神blog,写得很详细。

首先说一下这个sparse—table算法不能处理一些动态更新的题目(比如单点更新,区间更新之类的。但是处理静态的查询还是很给力的,毕竟预处理O(nlogn),查询是O(1)的。

预处理是通过dp解决的。我们先定义dp[i][j]数组的含义:表示从i开始的长度为2^j的区间的最大值(根据题目要求),也就是从i到i+2^j-1.然后我们可以看出dp[i][j]可以从dp[i][j-1](也就是从i到i+2^(j-1)-1这样的长度为2^(j-1)的区间)和dp[i+(1<<(j-1))][j-1](也就是从i+2^(j-1)到2^j-1这样长度为2^(j-1)的区间)中的最大值得到。

在实际写的时候第二维要放在外层,这是因为根据状态转移方程我们是通过两个2^(j-1)的长度区间得到的一个2^j的长度区间,所以必须保证j-1的情况全部算完再算j。这样的话是O(nlogn)的复杂度。

然后再说查询,对于[l,r]这样一个闭区间我们需要找到一个最小的k让它可以完全覆盖这个区间长度,也就是k=log(r-l+1),然后我们只需要比较dp[l][k]和dp[r-(1<<k)+1][k]即可。

贴一个丑陋的板子。

 

Codeforces Round #356 (Div. 2) 除草

以后cf的题目补完题后在发上来。。。

A. Bear and Five Cards(暴力枚举)

A little bear Limak plays a game. He has five cards. There is one number written on each card. Each number is a positive integer.

Limak can discard (throw out) some cards. His goal is to minimize the sum of numbers written on remaining (not discarded) cards.

He is allowed to at most once discard two or three cards with the same number. Of course, he won’t discard cards if it’s impossible to choose two or three cards with the same number.

Given five numbers written on cards, cay you find the minimum sum of numbers on remaining cards?

Input

The only line of the input contains five integers t1, t2, t3, t4 and t5 (1 ≤ ti ≤ 100) — numbers written on cards.

Output

Print the minimum possible sum of numbers written on remaining cards.

Examples
input

output

input

output

input

output

Note

In the first sample, Limak has cards with numbers 7, 3, 7, 3 and 20. Limak can do one of the following.

  • Do nothing and the sum would be 7 + 3 + 7 + 3 + 20 = 40.
  • Remove two cards with a number 7. The remaining sum would be 3 + 3 + 20 = 26.
  • Remove two cards with a number 3. The remaining sum would be 7 + 7 + 20 = 34.

You are asked to minimize the sum so the answer is 26.

In the second sample, it’s impossible to find two or three cards with the same number. Hence, Limak does nothing and the sum is7 + 9 + 1 + 3 + 8 = 28.

In the third sample, all cards have the same number. It’s optimal to discard any three cards. The sum of two remaining numbers is10 + 10 = 20.

直接暴力

B. Bear and Finding Criminals(构造)

There are n cities in Bearland, numbered 1 through n. Cities are arranged in one long row. The distance between cities i and j is equal to|i - j|.

Limak is a police officer. He lives in a city a. His job is to catch criminals. It’s hard because he doesn’t know in which cities criminals are. Though, he knows that there is at most one criminal in each city.

Limak is going to use a BCD (Bear Criminal Detector). The BCD will tell Limak how many criminals there are for every distance from a citya. After that, Limak can catch a criminal in each city for which he is sure that there must be a criminal.

You know in which cities criminals are. Count the number of criminals Limak will catch, after he uses the BCD.

Input

The first line of the input contains two integers n and a (1 ≤ a ≤ n ≤ 100) — the number of cities and the index of city where Limak lives.

The second line contains n integers t1, t2, …, tn (0 ≤ ti ≤ 1). There are ti criminals in the i-th city.

Output

Print the number of criminals Limak will catch.

Examples
input

output

input

output

Note

In the first sample, there are six cities and Limak lives in the third one (blue arrow below). Criminals are in cities marked red.

Using the BCD gives Limak the following information:

  • There is one criminal at distance 0 from the third city — Limak is sure that this criminal is exactly in the third city.
  • There is one criminal at distance 1 from the third city — Limak doesn’t know if a criminal is in the second or fourth city.
  • There are two criminals at distance 2 from the third city — Limak is sure that there is one criminal in the first city and one in the fifth city.
  • There are zero criminals for every greater distance.

So, Limak will catch criminals in cities 1, 3 and 5, that is 3 criminals in total.

In the second sample (drawing below), the BCD gives Limak the information that there is one criminal at distance 2 from Limak’s city. There is only one city at distance 2 so Limak is sure where a criminal is.

 

可以把这条数轴按照距离起点的长度进行分段处理,然后扫一遍计算一下即可。

C. Bear and Prime 100(数学+交互)

This is an interactive problem. In the output section below you will see the information about flushing the output.

Bear Limak thinks of some hidden number — an integer from interval [2, 100]. Your task is to say if the hidden number is prime or composite.

Integer x > 1 is called prime if it has exactly two distinct divisors, 1 and x. If integer x > 1 is not prime, it’s called composite.

You can ask up to 20 queries about divisors of the hidden number. In each query you should print an integer from interval [2, 100]. The system will answer “yes” if your integer is a divisor of the hidden number. Otherwise, the answer will be “no“.

For example, if the hidden number is 14 then the system will answer “yes” only if you print 2, 7 or 14.

When you are done asking queries, print “prime” or “composite” and terminate your program.

You will get the Wrong Answer verdict if you ask more than 20 queries, or if you print an integer not from the range [2, 100]. Also, you will get the Wrong Answer verdict if the printed answer isn’t correct.

You will get the Idleness Limit Exceeded verdict if you don’t print anything (but you should) or if you forget about flushing the output (more info below).

Input

After each query you should read one string from the input. It will be “yes” if the printed integer is a divisor of the hidden number, and “no” otherwise.

Output

Up to 20 times you can ask a query — print an integer from interval [2, 100] in one line. You have to both print the end-of-line character and flush the output. After flushing you should read a response from the input.

In any moment you can print the answer “prime” or “composite” (without the quotes). After that, flush the output and terminate your program.

To flush you can use (just after printing an integer and end-of-line):

  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal;
  • See the documentation for other languages.

Hacking. To hack someone, as the input you should print the hidden number — one integer from the interval [2, 100]. Of course, his/her solution won’t be able to read the hidden number from the input.

Examples
input

output

input

output

Note

The hidden number in the first query is 30. In a table below you can see a better form of the provided example of the communication process.

The hidden number is divisible by both 2 and 5. Thus, it must be composite. Note that it isn’t necessary to know the exact value of the hidden number. In this test, the hidden number is 30.

59 is a divisor of the hidden number. In the interval [2, 100] there is only one number with this divisor. The hidden number must be 59, which is prime. Note that the answer is known even after the second query and you could print it then and terminate. Though, it isn’t forbidden to ask unnecessary queries (unless you exceed the limit of 20 queries).

第一次写交互题,题目限制只能问20次,而且这个数是小于等于100的,而2-100之间有25个素数。所以我们肯定不能暴力来问。既然数字小于100,代表肯定不会出现11*13这样的两个两位素数相乘的情况,那么我们可以先枚举一遍2,3,5,7。如果这样问了一遍还是没有找到因子那肯定就是一个素数了。如果找到两个因子就一定是合数。如果只有一个因子可能有三种情况,一种是的确是2,3,5,7中的一个数,或者为2,3,5,7中的某一个数的次方(我们只需要枚举平方即可),再或者就是2,3,5,7中的一个数为猜测的数的一个因子,如果是2我们只需判断11-50内的素数即可,2的话就是11-33,以此类推。最多19次。对于这种数据范围很小的题目,只要耐心发现一些性质即可。

D. Bear and Tower of Cubes(构造+dfs)

Limak is a little polar bear. He plays by building towers from blocks. Every block is a cube with positive integer length of side. Limak has infinitely many blocks of each side length.

A block with side a has volume a3. A tower consisting of blocks with sides a1, a2, …, ak has the total volume a13 + a23 + … + ak3.

Limak is going to build a tower. First, he asks you to tell him a positive integer X — the required total volume of the tower. Then, Limak adds new blocks greedily, one by one. Each time he adds the biggest block such that the total volume doesn’t exceed X.

Limak asks you to choose X not greater than m. Also, he wants to maximize the number of blocks in the tower at the end (however, he still behaves greedily). Secondarily, he wants to maximize X.

Can you help Limak? Find the maximum number of blocks his tower can have and the maximum X ≤ m that results this number of blocks.

Input

The only line of the input contains one integer m (1 ≤ m ≤ 1015), meaning that Limak wants you to choose X between 1 and m, inclusive.

Output

Print two integers — the maximum number of blocks in the tower and the maximum required total volume X, resulting in the maximum number of blocks.

Examples
input

output

input

output

Note

In the first sample test, there will be 9 blocks if you choose X = 23 or X = 42. Limak wants to maximize X secondarily so you should choose 42.

In more detail, after choosing X = 42 the process of building a tower is:

  • Limak takes a block with side 3 because it’s the biggest block with volume not greater than 42. The remaining volume is42 - 27 = 15.
  • The second added block has side 2, so the remaining volume is 15 - 8 = 7.
  • Finally, Limak adds 7 blocks with side 1, one by one.

So, there are 9 blocks in the tower. The total volume is is 33 + 23 + 7·13 = 27 + 8 + 7 = 42.

比赛的时候没做出来,没什么想法。

补题的时候看题解知道了一个性质:就是对于m而言,我们只有两种可能最优选择,一种是放a^3的木块,一种是(a-1)^3的木块。a是当前限制下的最大木块边长。因为我们想要放的木块尽可能多而且X要尽可能大,那么我们每次做出选择后剩余的限制体积应该尽可能大。

那么对于当前限制m1而言:

如果选择放a^3的木块,剩余限制体积m2=m1-a^3。

如果选择放(a-1)^3的木块,剩余限制体积m2=a^3-1-(a-1)^3=3*a^2-3*a。

如果选择放(a-2)^3的木块,剩余限制体积m2=(a-1)^3-1-(a-2)^3=3*a^2-9*a+6.

把选择2和选择3相减,得到6a-6,而这个数一定是大于等于0,所以选择2肯定不会比选择3差。

有了这个性质,我们直接dfs得到决策树即可。

E不大会做,放到小学期补题计划中去吧…这段时间就刷刷水题消磨人生吧。。。

uva 442 Matrix Chain Multiplication(栈)

Description

Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose.

For example, let A be a 50*10 matrix, B a 10*20 matrix and C a 20*5 matrix. There are two different strategies to compute A*B*C, namely (A*B)*C and A*(B*C).

The first one takes 15000 elementary multiplications, but the second one only 3500.

Your job is to write a program that determines the number of elementary multiplications needed for a given evaluation strategy.

Input Specification

Input consists of two parts: a list of matrices and a list of expressions.

The first line of the input file contains one integer n ( tex2html_wrap_inline28 ), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.

The second part of the input file strictly adheres to the following syntax (given in EBNF):

Output Specification

For each expression found in the second part of the input file, print one line containing the word “error” if evaluation of the expression leads to an error due to non-matching matrices. Otherwise print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

Sample Input

Sample Output

计算出一个矩阵相乘的表达式中乘法操作的次数。
我们可以用一个栈来处理表达式。