SXOI2016题解

上古时代的题啊。。都没地方交。。找到题面了，口胡一下：

T1

有一支n个人的队伍要过一座限重为W的桥，我们规定这支队伍过桥时只能分组过，即当一组全部过去后，下一组才能接着过。给定每个队员的重量wi和过桥时间ti，一组人的过桥时间为花费时间最多的人的时间。问如何分组使得总的过桥时间最短。 对于100%的数据，n≤16,100≤W≤400,1≤t≤50,10≤w≤100 题解：直接状压枚举子集就好了

T2

定义$g_n$为把$n$拆分为正整数$x_1,x_2,…$的和，每一种方案所有贡献的和，其中贡献为$\prod f_{x_i}$，$f$是斐波那契数列。$n \leq 10^{18}$ 题解：简单DP：$g_n=\sum f_i g_{n-i}$。就可以打个表，发现$g_n=g_{n-1}+2g_{n-2}$。为什么大约可以归纳证明吧。

T3

给定n个回文串，s1,s2,…,sn。求有多少有序整数对 (i,j) 使得sisj 仍为回文串。 对于100%的数据，n≤2000000,m≤2000000 题解： 因为输入就是回文，冷静分析一下可以发现就是要求$(a,b)=(b,a)$有多少对。考虑Hash，$h_ab+h_b=h_ba+h_a$，整理可以把$a,b$放到两边，开个map就可以了 或者用Trie，短的在长的上跑，前后匹配打标记

T4

一个$10^5$的数列，$ans$定义为前缀$\max$和。单点修改并回答新的值。 题解： 如果没有修改，单调栈就好了。有修改就用线段树维护单调栈。节点上不维护单调栈具体的样子，只维护一些必要信息。合并左右的时候，左边的$\max$会影响右边，利用已知信息在右边二分到影响的位置即可。$O(nlog^2n)$