【题解】牛客练习赛3

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 反蝴蝶效应
GeneralJoke
SPOJNPC2014D
定位：NOIPDay2T1

T2 贝伦卡斯泰露
把问题转化为将序列中的每个元素选择一个和它数值相同的元素匹配。

T3 形态形成场
串的构成是递归定义的。
考虑合并两个串时的更新答案，相当于把两个串的答案相加，再统计两个串交汇处的贡献。

T4 生物课程
合法的情况一定是树，即m=n−1。
通过统计每种度数的点的出现次数判断。

T5 绝对半径2051
考虑最短路模型中的一条边u→v，权值为c

T6 监视任务
考虑最短路模型中的一条边u→v，权值为c。
一定满足distu+c≥distv，形式与转化过的约束条件相同。
由于主要影响为sumr→suml−1权值为−k的边。这个模型为sumn→sum0的最短路，最后答案要取相反数。最长路版本的算法也可以用类似的方法对应得到。

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305