[2022-51nod赛前模拟]csp-s 第6套-T1
题目描述
给出一个 n 个点 m 条边的有向图，顶点编号 1 到 n ，边的编号为 1 到 m。
你可以选择一些边进行反转（即从 u 到 v 的边反转后变为从 v 到 u 的边），将每条边反转都需要一定代价。最终使得整个图变成一个 Dag 图。
总的反转代价是由所有需要反转的边中，代价最高的那一条决定的，求达成目标的最小代价。
输入格式
第一行输入两个整数n,m，分别表示点数和边数；
之后m行，每行输入三个整数u,v,c，表示有一条u向v的边，其反转代价为c。
其中2≤n≤1e5,1≤m≤1e5。
输出格式
输出一行一个数，表示达成目标的最小代价。
样例 #1
样例输入 #1
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4
样例输出 #1
2
提示
对于20%的数据，
2≤n≤100,1≤m≤200
对于40%的数据，2≤n≤500,1≤m≤1000
对于70%的数据，2≤n≤5000,1≤m≤10000
对于100%的数据，2≤n≤1e5,1≤m≤1e5,1≤c≤1e9。
样例解释
最初图中有 2 个环： 1→5→2→1 和 2→3→4→5→2 .
反转 2→1 和 2→3 ，代价为 2 。
目标：20 实际：8
错误原因：找环的时候出错了。
考场分析：在考场上我没有想到用二分答案去判断，只打了暴力，但暴力写错了，最后没有拿到预计得分。这道题我主要暴露出来的问题是对于图中的环的处理有所欠缺，对于图论的基础题可以多见识一下。
反思与收获：对于这道题的思路，应该先看数据范围，我们最终解法的复杂度一定要小于或等于\(O(nlogn)\)。而且这道题是让我们求最大值的最小值，有二分性，考虑二分答案。顺着这个思路想下去，我们可以二分当前答案，再判断答案为mid时行不行。所以正解为二分边权K,如果边权大于K的边所组成的图中有环，则只修改边权小于K的边无法达到目的。如果边权大于K的边所组成的图中无环，则一定存在对应的方案，使得修改过的图是无环的。（ps:图中是否有环可以用拓扑序来做）
最大的收获是对于图中环的处理，和二分答案的使用判断，明确自身在图论上的问题。
[2022-51nod赛前模拟]csp-s 第6套-T2
题目描述
杭州有一棵 n 个点的歪脖子树（节点编号 1∼n），每个点有一个丑陋度 a[i]。它的长相过于奇怪以至于人们甚至不知道它的根在哪里，但大家初始时都假定节点 1 为根。为了验证，植物学家们做了 T 次实验，每次实验形如下列三者之一：
V x y：把点 x 的丑陋度改成 y ；
E x：将 x 设为新的树根；
Q x：查询 x 的子树中丑陋度的最小值；
输入格式
第一行两个整数 n,T，分别表示树的大小和实验数。（n,T≤1e5）
之后n行，每行两个整数f,v，其中第i+1行两个数表示点i的父亲编号和i的丑陋度。保证f[1]=0,f[i]<i。
输出格式
对于每个实验Q，输出一行一个数表示答案。
样例 #1
样例输入 #1
3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1
样例输出 #1
1
2
3
4
提示
对于40%的数据， n,T≤1e4；
对于100%的数据， 2≤n≤1e5,1≤T≤1e5,0≤v≤1e4。
[2022-51nod赛前模拟]csp-s 第6套-T3
题目描述
有 n 个水杯，水杯中分别有 a[i] 升水，你采用以下方式把所有水杯倒空。
设当前所有水杯中水量最多的一杯有 g 升，你可以把所有水量在 g/2 （下取整）以上的水杯都倒空。
然后继续这个操作，直到所有水杯被倒空为止。设总共倒了 h 次。
不过在干这个事情之前，你可以先选出至多 k 个水杯，预先将其中的水都倒空。你可以通过不同的选择，让最终的 h 尽可能小。问最小的 h 是多少，同时输出预先倒空的水杯数量（有可能小于 k）？
输入格式
第一行输入两个整数n,k，分别表示水杯总个数、预先倒空的水杯数上限。
第二行输入n个数a[i]，分别表示每个水杯中的水量。
其中1≤n≤2e5，0≤k≤n。
输出格式
输出一行两个数，最小的h和对应的倒空水杯数量，以空格隔开。若倒空水杯数量有多解，取最小。
样例 #1
样例输入 #1
4 1
2 3 4 9
样例输出 #1
2 1
样例 #2
样例输入 #2
4 2
2 2 2 2
样例输出 #2
1 0
提示
对于10%的数据，1≤n≤10
对于30%的数据，1≤n≤2×1e4
对于100%的数据，1≤n≤2×1e5,0≤k≤n,1≤a[i]≤1e9
期盼：30 实际：12
考场分析：我考场上打的暴力+单个二分判断，但写挂了，初步估计是算法有问题+二分写挂了。
方法：因为倒水次数是\(log(n)\)级别的,用贪心的思想肯定想把水量大的水倒掉更优。所以我们先对所有水杯按照水量排序。
然后考虑dp，用\(f_{i,j}\)表示将前i杯水用j次倒空，所需要提前移除的最少的水杯数量。
我对于怎么推出dp方程的还有点不了解，但最终状态转移为：\(f_{i,j}=min(f_{k,j-1},f_{i-1,j})\).