T1：DTJO3636. IIIDX（iiidx）

题意

给定一颗$n$个点的树，要求在上面填上$a_1\dots \dots a_n$，要求父亲的值不能大于儿子的值，求字典序最大的方案。 $n\le 500000$

题解

有一个比较直观的贪心是从小到大填数，从根开始每次往编号大的儿子填，但这样只能保证在$a_i$互不相同时是对的。因为这并不是严格的字典序最大，在一些$a_i$相同时，可以先填到编号较小的点，以让后面的数填到这个点，使字典序更大。 考虑严格的贪心，按编号从小到大考虑每一个点，每个点填上能填的数的最大值，即在剩下的数中，第$sz[u]$（它的子树大小）大的值，而若有若干相同值，应取最前面的。 该过程当时是用一个比较玄学的做法调了半天，现在想想好像离散后用值域线段树直接做即可。

T2：DTOJ2652. 背单词（word）

题意

给定n个字符串，按一定顺序将其填入，每填入一个字符串的花费为它与它最后一个填入的后缀的时间差，求最小花费和。 $n\le 100000$，字符总长$\le 500000$

题解

把字符串建一个$trie$树，再把关键点拎出来建一颗树（如果直接在$trie$树上做会有一些问题），问题转化为遍历所有点，每个点的代价为与上一个点的时间差，求最小花费。 注意到每个点的贡献为：$t[u]$（被访问到的时间）$\times$ ($1-sn[u]$($u$的儿子个数)）。直观地猜想$dfs$是否最优，发现对于两颗子树，若一颗访问到一半就去另一颗，那一定不会更优，再通过列式发现先走大的子树一定是最优的。

T3:「JOISC 2016 Day 2」女装大佬

题目译自 JOISC 2016 Day2 T3 「トイレ」

题面魔改原因：原题是男选手太多所以要借用女厕所 →_→ 译者表示无法接受

IOI 的队服有两种，一种男装，一种是女装。然而很遗憾，所有参赛队伍中并没有女生，只有女装大佬。现在 IOI 设置了两个发放点，一个点只发放男装，另一个点只发放女装。

现在，所有队伍总共 $2N$ 个参赛队员，他们排成一列来领取队服，领取队服的规则如下：

当前队首是女装大佬，如果领取女装的地方是空的，那么他就会领取女装，否则如果领取男装的地方是空的，他会去领取男装；当前队首是正常男生，如果领取男装的地方是空的，那么他会领取男装，否则如果女装位空着，他就发挥绅♂士精神，给身后的最前面的女装大佬让位，让他先领取女装。

已知任意一个人领取队服都需要一分钟的时间，现在你需要重排所有人的顺序，使他们在 $N$ 分钟内领完队服 。

定义一个人的 Dark 值为：在重排队伍之前在他后面，且重排队伍之后在他前面的人的数量。 你现在需要找出重排后整个队伍最大的 Dark 值至少为多少。

对于全部的数据，$1\le N\le 10^{18}$,$1\le M\le 10^5$，给出的字符串总长小于等于 $2\times 10^5$。

具体子任务限制及得分情况如下表：

Subtask限制分数$1$$1\le N\le 10$，且字符串只有一个且只出现一次$14$$2$$1\le N\le 10^5$，且字符串只有一个且只出现一次$22$$3$无追加限制$64$

题解

发现限制相当于对于任意后面$2i$个都至少要有$i$个女装大佬。 于是有贪心的想法:从后往前把第i个女装大佬移到第2i个位置(如果本来在它之前的话)，于是答案为$max(0,pi-2i)$。 对于复读，因为是线性变化的，故判断第一个和最后一个即可。

T4

codeforces 1203 F2

题意

有n项任务，每项任务有一个经验值的要求$b_i$，以及做完后能增加的经验值$a_i$，求初始经验值为r的情况下，最多能完成的任务数。

题解

对于$a_i>0$的任务，显然先按$b_i$从小往大做，然后考虑对于剩下的任务，如果已经确定了一个最优的考虑顺序，那么按顺序DP即可，对于顺序，应该要使任意两个数交换顺序后都不会更优，即原本选了i后不能选j，而交换i,j顺序后就都能选的情况不会出现，列出不等式即可。

T5

XJOI round14 T3

题意

给定一颗n个点的树，每个点有权值$a_i,b_i$，取一个点时，s先减去$a_i$,再加上$b_i$，要求从1号点开始取，取完父亲才能取儿子，把所有点取完。求该过程s最小值的最大值。

题解

和T4的思路类似，先把$b-a>0$的取完，然后对于$b-a<0$的按贪心的原则列不等式，发现是按b从大到小排序。但还有父亲的限制，考虑从当前的堆中取出一个最大值，若它的父亲还没选该如何处置。这个点暂时不能选，但它的父亲选完之后，它就可以选，且是最优的，故它的父亲被选完后，一定会立刻选它，那就等价于把它的权值加到它的父亲上，再把这个点删掉，该过程用并查集维护即可。

T6

BZOJ 2288: 【POJ Challenge】生日礼物

题意

ftiasch $18$岁生日的时候，lqp18_31给她看了一个神奇的序列 $A_1,A_2,...,A_N$. 她被允许选择不超过 $M$ 个连续的部分作为自己的生日礼物。

自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？ $n\le 100000$

题解

先把原序列连续的正数和负数合并成一段段正负交替的数，如果m大于正数的段数就直接取所有整数，否则在全取整数的基础上，考虑如何用最小的代价把段数变为m。发现操作无非有两种，把一段正的舍掉，或取一段负的，把两段正的合并，该过程用链表+堆维护即可。

T7

BZOJ 2151: 种树 & DTOJ 1020. 编译优化 （compile）

题意

众所周知，衡量一个编译器是否优秀的标准，除了它的编译速度和正确性以外，编译出的代码的质量也很重要。最近，作为 XCC 系列编译器作者的 Dr. X 发明了一种跨时代的优化算法：“NanGe不等式优化”。一个程序可以看成是由若干个连续的函数构成的，NanGe 不等式算法能针对某一个函数进行优化，得到一个优化效果值, 不同的函数的效果值可能是不同的。但这个算法还有一个很大的 Bug：

该算法不能同时优化相邻的两个函数，否则就会直接 Compile Error ，值得注意的是，一个程序的第一个函数和最后一个函数也算是相邻的。

现在给你一个程序从头到尾每个函数的优化效果值，Dr. X 想用NanGe不等式对该程序的** $M$ 个函数进行优化**，他该怎么选择才能使总的优化效果值最大（前提是不能出现错误）？如果错误不能避免，请输出Error! 对于全部数据：$m\le n,-1000\le A_i\le 1000$

$N$ 的大小对于不同数据有所不同：

数据编号$N$的大小数据编号$N$的大小$1$$40$$11$$2013$$2$$45$$12$$5000$$3$$50$$13$$10000$$4$$55$$14$$49999$$5$$200$$15$$111111$$6$$200$$16$$148888$$7$$1000$$17$$188888$$8$$2010$$18$$199999$$9$$2011$$19$$199999$$10$$2012$$20$$200000$

题解

对于物品选取关系之间有一定限制的求最大价值和的问题，考虑用堆维护可撤销的贪心。先把每个物品扔进堆内，每次取出最大值，代表选了这个物品，然后它相邻的两个都不能选，再把相邻两个的价值和减去这个物品的价值扔进堆，代表放弃选这个物品而选择相邻的两个。每次找标记不能选取的和找到相邻的用链表维护即可。

T8

BZOJ 4240: 有趣的家庭菜园

题意

对家庭菜园有兴趣的JOI君每年在自家的田地中种植一种叫做IOI草的植物。JOI君的田地沿东西方向被划分为$N$个区域，由西到东标号为$1-N$。IOI草一共有N株，每个区域种植着一株。在第i个区域种植的IOI草，在春天的时候高度会生长至$h_i$，此后便不再生长。 为了观察春天的样子而出行的JOI君注意到了IOI草的配置与预定的不太一样。IOI草是一种非常依靠阳光的植物，如果某个区域的IOI草的东侧和西侧都有比它高的IOI草存在，那么这株IOI草就会在夏天之前枯萎。换句话说，为了不让任何一株IOI草枯萎，需要满足以下条件： 对于任意$2\le i\le N-1$，以下两个条件至少满足一个：

对于任意$1\le j\le i-1，h_j\le h_i$对于任意$i+1\le j\le N，h_k\le h_i$ IOI草是非常昂贵的，为了不让IOI草枯萎，JOI君需要调换IOI草的顺序。IOI草非常非常的高大且纤细的植物，因此JOI君每次只能交换相邻两株IOI草。也就是说，JOI君每次需要选择一个整数$i(1\le i\le N-1)$，然后交换第$i$株IOI草和第$i+1$株IOI草。随着夏天临近，IOI草枯萎的可能性越来越大，因此JOI君想知道让所有IOI草都不会枯萎的最少操作次数。 现在给出田地的区域数，以及每株IOI草的高度，请你求出让所有IOI草的不会枯萎的最少操作次数。 $3\le N\le 3\ast 10^5$ $1\le h_i\le 10^9$

题解

首先orzxjq。 直接贪心好像很难做，先考虑把原序列变换成一个排列的最小代价，不难发现最小代价即为逆序对对数，于是问题转化为把原序列排成单峰，对应排列逆序对数的最小值。从小到大考虑每个数，发现只能从两端往中间放，只需判断这个数放在左边或右边时产生的贡献，而该贡献可直接算出，用树状数组维护，取最小的即可。