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的竹子，直接返回错误。