牛客练习赛56部分题解

传送门:https://ac.nowcoder.com/acm/contest/3566#question

题意:给一些特定的数，让你找出最长子串.

思路:求最长子串,水dp.

AC代码:

题意:

思路:读完题可知肯定找规律。

而且这是颗树,我们考虑在遍历的时候求答案.

考虑每条边对答案的贡献，对于某条边,由这条边分割把图看成两个部分.那么根据简单的计数原理,这条边的答案推个公式出来就可以O(1)求出了。

AC代码:

题意:

思路:

$\text{[math]}$

$状态转移方程列出来,对于一个点g,dp[g][k] = \sum_{i=1}^{g-1}dp[i][k-1](当A[g] > A[i] )$

观察到k很小，思考一下发现可以用树状数组维护k个状态，注意要离散化一下数据。

AC代码:

题意:

思路:

很显然用线段树很方便维护，就是区间修改，全局最大最小值而已。

但是选择的情况太多了，需要贪心去解决（这一部分待补）.

AC代码:

题意:

思路：

一眼看出用tarjin求割边，但是从没打过模板，也懒得去网上copy别人的板子.放到之后补吧。

应该是不在射程范围内了。。随缘补题吧。