Codeforces Round 286(Codeforces Round 286)

Codeforces Round 286

https://codeforces.com/contest/505

A

给出一个长度为n的字符串。

询问是否可以插入一个小写英文字母使其成为回文

n<10

直接暴力

B

给出一个n个点m条边的无向图。

每条边有一个颜色ci。

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

求满足以下条件的颜色个数,该颜色的边直接或间接连接ui和vi

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

做法:

暴力枚举颜色,用并查集维护一下连通性。

C

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

一共30000个岛。

一开始我在0号岛。

首先,我从0号岛跳到d号岛。

之后,设L为上次跳跃的距离,下一次可以跳L-1,L或L+1,但不能不跳。

询问可以收集的最大数量的宝石。

n,d<=30000

做法:

一个很妙的DP Trick。

定义方程\(dp[i][j]\)表示到第\(i\)步,步伐长度变化j的能收集到的最大宝石数量。

然后根据\(dp[i][j]\)这个值去往后更新。

根据等差数列求和的性质,这个j不会太大,大概是-300到300。

D

n个城市。

有m对城市是重要的。

我计划建造单向边,使得对于每一对城市(ai,bi),都可以通过单向边从ai到bi。

找出需要建造的最少数量的单向边方案,打印最少数量即可。

n,m<=100000

做法:

结论:

不同连通块之间显然不需要边,所以单独考虑每个连通块。

一个连通块内如果没有环,可以根据拓扑序重构成一条链满足题目要求。

一个连通块内如果有环,不管有几个环,都可以通过一个大环来满足要求。

所以答案是n-连通块数量+含环连通块数量。

E

我有n根竹子。

第i根竹子高度位hi米,每天生长ai米。

我每天可以使用魔力k次,每次可以将一根竹子变低p米。不会变成负数,变成0,但不会消失。

现在我有m天,我要最小化m天后最高竹子的高度。

询问m天后最高竹子的最低可能高度。

n<=100000

m<=5000

k<=10

p<=1e9

做法:

二分,m天后最高的竹子为H是否可行。

然后反过来做。

先统一在第m天把所有竹子变成H。

然后每天,所有竹子高度变矮ai,你必须保证所有竹子高度>=0,且m天结束后竹子高度>=hi。

用一个堆维护,当前状态下继续减少高度而不拔高,第m天结束后竹子高度会<hi的竹子,一直减少高度,多少天后的高度会<0。

每次取出剩余天数最少的竹子,拔高即可。

如果无论怎么拔高还是会<0的竹子,直接返回错误。

————————

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.