# Codeforces Round 286(Codeforces Round 286)-其他

## Codeforces Round 286(Codeforces Round 286)

Codeforces Round 286

https://codeforces.com/contest/505

A

n<10

B

q次询问，每次询问两个数ui和vi

n<=100 m<=100 q<=100

C

n颗宝石，第i颗宝石位于pi岛上。

n,d<=30000

D

n个城市。

n,m<=100000

E

n<=100000

m<=5000

k<=10

p<=1e9

————————

Codeforces Round 286

https://codeforces.com/contest/505

A

Give a string of length n.

Ask if you can insert a lowercase letter to make it a palindrome

n<10

Direct violence

B

An undirected graph with n points and m edges is given.

Each edge has a color CI.

Q queries, two numbers UI and VI at a time

Find the number of colors that meet the following conditions. The edges of the color directly or indirectly connect UI and VI

n<= 100 m<= 100 q<= one hundred

Practice:

Enumerate colors violently, and maintain connectivity with query set.

C

N gemstones, the I gemstone is located on PI island.

A total of 30000 islands.

At first I was on island 0.

First, I jumped from island 0 to island D.

Then, set l as the distance of the last jump. You can jump L-1, l or L + 1 next time, but you can’t skip.

Ask about the maximum number of gems you can collect.

n,d<= thirty thousand

Practice:

A wonderful DP trick.

The definition equation \ (DP [i] [J] \) represents the maximum number of gemstones that can be collected when the step length changes j from step \ (I \).

Then update it later according to the value of \ (dp[i][j]\).

According to the summation property of the arithmetic sequence, this j will not be too large, about – 300 to 300.

D

N cities.

Having M is important to the city.

I plan to build a one-way edge so that for each pair of cities (AI, BI), we can go from AI to bi through the one-way edge.

Find out the minimum number of unidirectional edge schemes to be built, and print the minimum number.

n,m<= one hundred thousand

Practice:

Conclusion:

Obviously, there is no need for edges between different connected blocks, so each connected block is considered separately.

If there is no ring in a connected block, a chain can be reconstituted according to the topological order to meet the requirements of the problem.

If there are rings in a connected block, no matter how many rings there are, it can meet the requirements through a large ring.

So the answer is the number of n-connected blocks + the number of connected blocks with rings.

E

I have n bamboos.

The height of the ith bamboo is hi meters and grows AI meters every day.

I can use magic K times a day, reducing one bamboo to p meters each time. It doesn’t become negative, it becomes 0, but it doesn’t disappear.

Now I have m days. I want to minimize the height of the highest bamboo in M days.

Ask the lowest possible height of the highest bamboo in M days.

n<= one hundred thousand

m<= five thousand

k<= ten

p<=1e9

Practice:

Two points. Is it feasible that the highest bamboo after M days is h.

Then do the opposite.

First unify and turn all bamboos into H on day M.

Then every day, the height of all bamboos becomes shorter AI, and you must ensure the height of all bamboos & gt= 0, and bamboo height after M days & gt= hi。

Maintain with a pile. In the current state, continue to reduce the height without pulling up. After the end of day m, the bamboo height will be & lt; The height of hi bamboo has been reduced. How many days later will the height be & lt; 0

Take out the bamboo with the least remaining days each time and pull it up.

If no matter how high it is, it will & lt; 0, which directly returns an error.