动态维护，加权点重心。

决策单调性

题目描述：给定一个序列 $a$，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。

$(k\leq 20)$

给你一个字符串$S$，然后$q$个询问，每次给出$S$的一个子串$T$。对于每个询问的子串$T$，Calabash可以在$Ｓ$中选择任意个以T作为后缀的子串，然后生成子串对应数目个石子堆，每堆的石子数量等于$w[对应子串在S中出现的次数]$。然后Rounddog可以从这么多堆石子中选择任意堆的石子（至少选一堆），两人开始玩Nim游戏，Calabash先手。现在问Calabash是否存在必胜策略，如果有输出Calabash在必胜策略下，能够选出来的最多的石子数目。

给定$n$个格子

• 对于前M1个约束，区间$[L,R]$内取的数量必须严格不少于K

• 对于后M2个约束，区间$[L,R]$外取的数量必须严格不少于K

• 满足所有M1+M2个约束的前提下使得取的个数最少，输出最少取的个数

  阅读全文 »

给出$n$个点，再给出$m$个询问，每次询问给出一个点 $x$，我们需要回答包括点 $x$ 的直角三角形有多少个

简单题意，不说。

有 $A,B$ 两种金券，它们每天的价值都不同，在第 $i$ 天时分别为 $A_i,B_i$你可以用手中的金券换取相应价值的钱，或用钱兑换相同价值的金券，但兑换到的两种金券的数量之比是一个定值，这个定值在第 $i$ 天为 $R_i$
现给出 $n$天中两种金券的价值$R$，以及你初始时拥有的资金 $S$，求 $n$ 天后你最多能有多少钱。

注：一定存在一种最优方案，满足：每次兑换金券花光所有的钱，每次换钱时花掉所有的金券。

一共有$n$对情侣。
共有多少种不同的就坐方案满足恰好有 $k$ 对情侣是和睦的。

给定$d_i$山丘的位置，以及每个小猫在$i$个山丘$t_i$结束游玩。等待铲屎官接送。

安排每个铲屎官出发的时间，最小化猫子们等待的时间之和。