## Codeforces 847J Students Initiation 二分答案 最大流

Codeforce 847J Students Initiation

## 思路&建图

1. 看到最大值最小，最小值最大，首先想到炸天哥猜想：二分！！
2. 二分这个最大值$mid$，检验这个猜测值是否满足要求
3. 从源点相这$n$个点引一条边，容量为$mid$。
4. 对于第$i$条边来说，其编号为$n+i$，从其两个断点分别引一条边到这个点，容量为$1$。再从这个点到汇点连一条边，容量为$1$。
5. 跑最大流，如果最大流和边的数目相同，即这个猜测值可行。此时，对于每一条边对应的点来说，这条边的方向就应该是从[流量来的那个点]到[没有流量流过来的那个点]。

## HDU6040 Hints of sd0061 分治排序

http://acm.hdu.edu.cn/showproblem.php?pid=6040

# Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

### Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with $m$ coming contests. sd0061 has left a set of hints for them.
There are $n$ noobs in the team, the $i$-th of which has a rating $a_i$. sd0061 prepares one hint for each contest. The hint for the $j$-th contest is a number $b_j$, which means that the noob with the $(b_j + 1)$-th lowest rating is ordained by sd0061 for the $j$-th contest.
The coach asks constroy to make a list of contestants. constroy looks into these hints and finds out: $b_i + b_j \leq b_k$ is satisfied if $b_i \neq b_j,$ $b_i < b_k$ and $b_j < b_k$.
Now, you are in charge of making the list for constroy.

### Input

There are multiple test cases (about $10$).
For each test case:
The first line contains five integers $n, m, A, B, C$. $(1 \leq n \leq 10^7, 1 \leq m \leq 100)$
The second line contains $m$ integers, the $i$-th of which is the number $b_i$ of the $i$-th hint. $(0 \leq b_i < n)$
The $n$ noobs' ratings are obtained by calling following function $n$ times, the $i$-th result of which is $a_i$.

### Output

For each test case, output "Case #$x$: $y_1$ $y_2$ $\cdots$ $y_m$" in one line (without quotes), where $x$ indicates the case number starting from $1$ and $y_i$ $(1 \leq i \leq m)$ denotes the rating of noob for the $i$-th contest of corresponding case.

## CodeForces 756B Travel Card 二分 DP

http://codeforces.com/problemset/problem/756/B

# B. Travel Card

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.

The fare is constructed in the following manner. There are three types of tickets:

1. a ticket for one trip costs 20 byteland rubles,
2. a ticket for 90 minutes costs 50 byteland rubles,
3. a ticket for one day (1440 minutes) costs 120 byteland rubles.

Note that a ticket for x minutes activated at time t can be used for trips started in time range from t to t + x - 1, inclusive. Assume that all trips take exactly one minute.

To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is a, and the total sum charged before is b. Then the system charges the passenger the sum a - b.

You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

### Input

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.

Each of the following n lines contains the time of trip ti (0 ≤ ti ≤ 109), measured in minutes from the time of starting the system. All ti are different, given in ascending order, i. e. ti + 1 > ti holds for all 1 ≤ i < n.

### Output

Output n integers. For each trip, print the sum the passenger is charged after it.

### Examples

input

output

input

output

Note

In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.

## HDU 5853 Jong Hyok and String 后缀数组 二分 RMQ

http://acm.split.hdu.edu.cn/showproblem.php?pid=5853

# Jong Hyok and String

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

### Problem Description

Jong Hyok loves strings. One day he gives a problem to his friend you. He writes down n strings Pi in front of you, and asks m questions. For i-th question, there is a string Qi. We called strange set(s) = {(i, j) | s occurs in Pi and j is the position of its last character in the current occurence}. And for ith question, you must answer the number of different strings t which satisfies strange set(Qi) = strange set(t) and t is a substring of at least one of the given n strings.

### Input

First line contains T, a number of test cases.

For each test cases, there two numbers n, m and then there are n strings Pi and m strings Qj.(i = 1…n, j = 1…m)

1 <= T <= 10
1 <= n <= 100000
1 <= m<= 500000
1 <=|Pi|<=100000
1 <=|Qi|<=100000
ni=1|Pi|≤100000
File size is less than 3.5 megabytes.

### Output

For each test case, first line contains a line “Case #x:”, x is the number of the case.

For each question, you should print one integer in one line.

1
2 2
aba
ab
a
ab

Case #1:
1
2

### Hint

strange set(“a”) ={(1, 1), (1, 3), (2, 1)}.
strange set(“ab”) ={(1, 2), (2, 2)}.
strange set(“b”) ={(1, 2), (2, 2)}.

### Source

2016 Multi-University Training Contest 9