题意：
$给定一个N\le 10^5次多项式P(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$现2个人轮流随意填P(x)的系数，填过的不能再填$$现有一个多项式Q(x)=x-k，如果最终多项式P(x)可以整除Q(x)，那么后手赢$$有一部分系数数已经被2个人填了，?表示还没填$$现2个人最优操作的情况下，问后手是否能赢$
Read more
Ⅰ. 背包问题认知
$物品：不可拆分，具有三种属性(体积w_i, 价值v_i, 个数c_i)$
$背包问题：将物品装入V大小的背包获得最优价值的问题$
$c_i=1时，称为01背包$
$c_i=\infty 时，称为完全背包$
$c_i=不定值时，称为多重背包$
Read more
TaoSama
May 18, 2016
题意：
$将N\le 2\times 10^5个关卡划分成M\le min(50, n)个组，组内关卡连续，t_i\le 10^5$$定义游戏规则，每次选择第一个未全部完成的组，假设组处于关卡区间[l, r]$$选择到组内第一个未完成的关卡的概率p_i=\frac{t_i}{\sum_{i=l}^i t_i}$$求怎样划分组使得通过所有组的期望打关卡次数最小，求这个次数，误差小于10^{-4}$
Read more
题意：
$N\le 1000个点，点权c_i \le 100，划分成0\le M<N个连续段$$每段的权值w(x, y)=\sum_{i=x}^{y-1}\sum_{j=i+1}^y c_i\cdot c_j$$求一个划分使得段权值和最小，输出这个权值和$
Read more
Ⅰ. 斜率优化认知
这东西英文名叫$Convex Hull Trick (CHT)$
主要优化形如$f_i = min\{ f_j + cost(j+1, i) \}的这种dp$
由于等号右边的式子并不能$O(1)$计算，所以我们需要一些技巧来优化
Read more
TaoSama
May 11, 2016
题意：
$N\le 2\times 10^5长度的二进制数，由0、1、?组成，?代表01都可$$每位有个权值，w_i\le 1000$$如果将这个二进制数转化成格雷码，1获得这个权值，0不获得$$求怎样确定这个二进制数才能获得最大权值，输出这个权值$
Read more
题意：
$N\le 2\times 10^5次操作$$0 l:如果是第i次添加操作，那么加入一条长度为i的线段，即[l, l+i]$$1 i:删除第i次添加操作添加的线段$$输出每个添加操作的线段所完全包含的线段个数$
Read more
题意：
$N\le 10^5个点，M\le 10^6个操作$$U a b:合并a，b$$D a:移除a所在的集合关系$$S a:询问a所在的集合大小$$F a b:询问a和b是否在同一集合$
Read more
题意：
$N\le 10^5个序列，A_i\le 10^5，定义任意2个相邻数都不互质的序列为Angela序列$$求最长Angela子序列的长度$
Read more
TaoSama
May 09, 2016