Codeforces Round 286(Codeforces Round 286)
Codeforces Round 286
n<=100 m<=100 q<=100
Codeforces Round 286
Give a string of length n.
Ask if you can insert a lowercase letter to make it a palindrome
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
Enumerate colors violently, and maintain connectivity with query set.
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
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.
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
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.
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
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.