2017.1.12——寒假集训第一天

今天欲消化八道题：

T1：

题目：https://jzoj.net/senior/#contest/show/1889/0

题目大意：

求trunc(n/1)+trunc(n/2)+……+trunc(n/n)-n的值

分析：

通过对每个加式的值分析，易得出规律，即n在除以某个数时，可能有相同的值，那么我们可以对除以过后的值进行枚举，因数为i的个数即为n div i-n div (i+1)，那么易知商的值呈前后对称状，故可在O(sqrt(n))时间内求出答案

T2：

题目：https://jzoj.net/senior/#contest/show/1889/1

题目大意：

给定一个残缺矩形，中间有缺口（只可能是矩形某一部分的上面），求最少需要粉刷几次使得残缺矩形被全部刷过，刷的时候只能刷矩形，但不能刷有缺口的部分

分析：

贪心，可以用单调栈，对于当前i如果小于栈顶，则把大于i的所有部分都计算答案（依次粉刷，即判断大于i部分的不相同的个数），并把i加入栈。

这题还可用RMQ和线段树，都要做一下

T3：

题目：https://jzoj.net/senior/#contest/show/1889/2

题目大意：

在n*n的矩阵里放k个国王（国王能侵犯其周围的八个格），使得互不侵犯

分析：状压Dp，fi,j,k表示前i行，第i行的国王状态为j，一共放了k个国王的方案数

显然枚举第i-1行的状态，因为“互不侵犯”，所以状态数并不多，可预处理出

链接：https://jzoj.net/junior/#main/show/2081

（集训后一同理解一下）

T4

题目：https://jzoj.net/senior/#contest/show/1889/3

题目大意：

在n*n的矩阵里找出一个子矩阵使得此子矩阵和在[k..2k]之间

类似的，有关题目：https://jzoj.net/senior/#contest/show/1835/2

https://jzoj.net/junior/#main/show/1385

T5

题目：https://jzoj.net/senior/#contest/show/1891/0

题目大意：

给定两序列a,b，找出b序列的好数（当x为好数时即用x随意加或减a序列里的数，使得最后结果为0）

分析：

T6：

题目：https://jzoj.net/junior/#contest/show/1360/1

题目大意：

给定杨辉三角的“顶”和“底”的个数，求“底”

T7：

题目：https://jzoj.net/junior/#contest/show/1360/2

题目大意：

构造2*s的序列，使得总和为T，且前后相等

T8：

题目：https://jzoj.net/junior/#contest/show/1360/3

题目大意：前n个数分成k个集合，使得每个集合和的最大值最小