Namomo Spring Camp 2022 Div1 每日一题记录 (2022.03.05-2022.03.11)

## 摘桃子

1 s, 1024 MB

### 复杂度

$$O(n\log n)$$ (使用 map)

Show code

## 路径计数 2 (CF559C)

1 s, 512 MB

### 解题思路

• $$i$$ 个障碍物的坐标为 $$(x_i,y_i)$$
• $$f_i$$ 为从 $$(1,1)$$ 走到第 $$i$$ 个障碍物合法方案

$f_i=\binom{x_i+y_i-2}{x_i-1}-\sum_{x_i\geq x_j; y_i\geq y_j}\binom{x_i+y_i-x_j-y_j}{x_i-x_j}f_j$

### 复杂度

$$O(m^2)$$

Show code

## 函数求和

1 s, 1024 MB

$$\sum_{i = 0}^{2^k - 1}f(i)$$. 由于答案可能很大，输出答案取模 $$998244353$$ 后的值

### 复杂度

$$O(nk)$$

Show code

## XOR Inverse (CF1416C)

2 s, 512 MB

### 数据范围

$$1\leq n\leq 3\cdot 10^5$$, $$0\leq a_i\leq 10^9$$

01-trie

### 复杂度

$$O(n\log n)$$

Show code

## Closest Equals (CF522D)

2 s, 512 MB

• $$a_i = a_j$$;
• $$l \leq i, j \leq r$$ $$(i \neq j)$$;

$$|i - j|$$ 的最小值，如果区间中不存在相等的两个数，则输出 $$-1$$

### 解题思路

RMQ + 二分

std::lower_boundstd::upper_boundcomp 签名要求不一致，但作用要求一致 (即 若第一参数先序于第二个则返回 ​true)

• std::lower_bound<ForwardIter, T> 要求的是 bool comp(const ForwardIter& t1, const T& t2)
• std::upper_bound<ForwardIter, T> 要求的是 bool comp(const T& t1, const ForwardIter& t2)

### 复杂度

$$O(n\log n+m)$$

Show code

## CCPC Harbin 2021 G, Damaged Bicycle (CodeForces Gym 103447G)

3 s, 1024 MB

Ring Ring Ring ... The bell rang at half past six in the morning. After turning off the alarm, George went on to sleep again. When he woke up again, it was seven fifty and there were ten minutes left for class!

George immediately got up from bed, dressed, packed his backpack, brushed his teeth and washed his face. Then, he immediately rushed out of the dormitory and embarked on the road to the teaching building. On the way, he turned on his mobile phone to locate and saw several yellow shared bicycles nearby. Therefore, he headed to a bicycle and took out his mobile phone to scan the QR code on the bicycle. Unfortunately, the bicycle wasn't unlocked, and a line of words "this bicycle is damaged and can't be unlocked" was displayed on the screen

Without riding a bicycle, he was late. What a bad day!

Indeed, some bicycles in the school are damaged, but their location will still be displayed on the app. George always rides faster than he walks, but considering that some bicycles are damaged, if George tries one by one, it may take a long time! In this regard, he has made some modeling, and hopes you can help him find the best strategy

The campus can be modeled as a graph of $$n$$ vertices and $$m$$ bidirected edges, where the $$i$$-th edge is $$w_i$$ meters long. George's dormitory is located at vertex $$1$$ and Guanghua Tower (the teaching building) is at vertex $$n$$, so George has to go from vertex $$1$$ to vertex $$n$$ to take classes. His walking speed is $$t$$ meters per second and his riding speed is $$r$$ meters per second. According to the bicycle sharing app, there are $$k$$ parked bicycles in the campus. The $$i$$-th bicycle is located at vertex $$a_i$$, and of probability $$\frac{p_i}{100}$$ to be damaged according to George's experience. However, only when George arrives at vertex $$a_i$$ and scans the QR code, can he determine whether the $$i$$-th bicycle is damaged or not. As soon as a bicycle is confirmed to be undamaged, George will get on it immediately and will not get off until he reaches vertex $$n$$

Now George wants to save time to get to the classroom. So you, George's roommate, should help him find an optimal strategy to minimize the mathematical expectation of the time cost on the way, and then output this value. Or you can let him continue sleeping if vertex $$n$$ is not reachable

In this problem, you should only consider the time of walking and cycling, and you can assume that the other actions(scanning QR code, getting on, getting off, $$\cdots$$) cost no time

### Input

The first line contains two integers $$t,r\,(1\le t\le r\le 10^4)$$ — the speed of walking and the speed of riding, respectively

The second line contains two integers $$n,m\,(1\le n,m\le 10^5)$$ — the number of vertices and the number of bidirected edges in the given graph

Following $$m$$ lines each contains three integers $$u_i,v_i,w_i\,(1\le u_i,v_i \le n, u_i \neq v_i, 1 \le w_i\le 10^4)$$, denoting that vertices $$u,v$$ are connected by a $$w_i$$-meter-long bidirected edge

The next line contains a single integer $$k\,(0\le k\le 18)$$, denoting the number of bicycles in campus

Following $$k$$ lines each contains two integers $$a_i,p_i\,(1\le a_i \le n, 0\le p_i \le 100)$$, denoting the locations of the bicycles and the percentages of damage probabilities respectively

It is guaranteed that no two bicycles are in the same vertex

### Output

If George cannot reach vertex $$n$$, output one line containing one integer -1, or output one line containing one real number, denoting the minimum expectation of the time cost on the way

As long as the relative or absolute error between your answer and the standard answer is within $10^{-6}$, your answer will be considered correct

### Note

For the first test case, one possible strategy is:

• Go along the route $$1\rightarrow 3$$ and try to ride the only bicycle in the campus
• If the bicycle is damaged, go along the route $$3 \rightarrow 1 \rightarrow 2 \rightarrow 4$$ on foot, or go by bicycle

Considering the time cost on the way:

• If the bicycle is damaged, George should go along the route $$1\rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$$ on foot, whose total length is 2100 meters. So the time cost is $$\frac{2100}{3} = 700$$ seconds
• If the bicycle is undamaged, George should go along the route $$1\rightarrow 3$$ on foot, whose total length is 300 meters, and then go along the route $$3 \rightarrow 1 \rightarrow 2 \rightarrow 4$$ by bicycle, whose total length is 1800 meters. So the time cost is $$\frac{300}{3} + \frac{1800}{15} = 220$$ seconds

As given in the input, the only bicycle has $$\frac{50}{100}$$ probability to be damaged. So the expectation time cost is $$\frac{50}{100}\times 700 + (1 - \frac{50}{100})\times 220 = 460$$

DP 不会写，写的记搜

### 复杂度

$$O(m+kn\log n+k^22^k)$$

Show code

## 拆方块 (CF573B, 51NOD1550)

1 s, 1024 MB

$$n$$ 堆方块，第 $$i$$ 堆方块由 $$h_i$$ 个方块堆积而成。具体可以看样例

### 解题思路

DP

$$f(x)$$ 为第 $$x$$ 堆方块最少需要多少次才能清空，则

$$f(1)=f(n)=1$$

\begin{align} f(x)&=\min\{f(x-1)+1,f(x+1)-1,h(x)\}\\ &=\min\{\min\{f(x-1)+1,h(x)\},\min\{f(x+1)+1,h(x)\}\} \end{align}

### 复杂度

$$O(n)$$

Show code