2017年

9月

11日

非考试

ID	题目	状态	思路	注意
1	【bzoj2243】[SDOI2011]染色	TLE&WA/AC	树链剖分，线段树维护相同连续段数	链合并时减去重复时是一条重链左端点颜色与另一条重链左端点颜色判断是否相等，而不是左与右，右与左

考试

ID	题目	状态	思路	注意
2	【09-11】卫星连接	100/100(AC)	将点权变为每个点与同一新建点相连边的边权，跑kruskal	不要每个点都新建一个点，不然会炸掉
3	【09-11】奇袭西欧	0/100	二分答案（max）+bfs	不要交错代码&&判-1&&不要把点数当做边数
4	【09-11】叹息之墙	0/100	tarjan裸题	找对模板，建对边

12日

考试

ID	题目	状态	思路	注意
5	[APIO2009]抢劫计划	100/100(AC)	Tarjan+缩点+SPFA最长路	分清缩点前后
6	[bzoj2081]项链	0/100	简单hash	base不要取太大??
7	[rqnoj86]智捅马蜂窝	100/100(AC)	最短路	分清什么时候建双向边，什么时候建单向边
8	[rqnoj84]逛公园	0/100	状压dp	用short

13日

非考试

ID	题目	状态	思路	注意
9	[poj2186]Popular Cows	RE/WA/AC	Tarjan缩点，统计出度为0的点，若有多个，则ans为Zer0，若只有一个，ans为该点缩点前环上点个数	模板测试，保证模板正确性
10	[bzoj1529]ska Piggy banks	MLE/WA/AC	并查集判连通块个数	不要用Tarjan+出度为0判断
11	[poj2479]Maximum sum	WA/AC	两段不相交连续子区间最大和（dp）	注意更新顺序
12	[openjudge162]post office	AC	dp,用f[i][j]表示前i个村庄修j个邮局的最小距离，sum[i][j]表示第i个村庄到第j个村庄修1个邮局的最小距离，方程为$f[i][j]=min(f[i][j],$f[k][j-1]+sum[k+1][i])$(边界f[i][1]=sum[1][i])$和$sum[i][j]$$=sum[i][j-1]+pos[j]-pos[i+j>>1]$	注意初始化的值&&i,j内外层位置
13	[openjudge1759]最长上升子序列	WA/AC	就是最长上升子序列，f[i]表示前i个数的最长上升子序列长度，$f[i]=max(f[j]+1)$ $(if \ a[i] > a[j] \& j < i)$	最后输出ans，不是f[n]
14	[openjudge1768]最大子矩阵	AC	转化一下，记录每行的前缀和，列举列的子区间和，并对每行做最大连续和，取最大	注意转化

14日

非考试

ID	题目	状态	思路	注意
15	[openjudge1775]采药	AC	基础01背包$f[j]=max(f[j],f[j-c[i]]+w[i])$	最外层i的遍历顺序不影响ans
16	[openjudge1808]公共子序列	AC	公共子序列, $f[i][j]=$$ \begin{cases}max(f[i][j],f[i-1][j-1]+1)&a[i]==b[j]\\max(f[i-1][j],f[i][j-1])&a[i]!=b[j] \end{cases} $	a[i]==b[j]对答案的影响是f[i-1][j-1],不是f[i][j]
17	[openjudge1944]吃糖果	AC	简单递推$f[i]=f[i-1]+f[i-2]$	f[1]=1,f[2]=2
21	[hdu1423]Greatest Common Increasing Subsequence	WA/PE/AC	$f[j]=max(f[k])+1$ $(if\ 1<=k<=j-1 \& a[i]==b[j])$	每层记录的最大值必须清零
22	[poj2155]Matrix	PE/AC	二维树状数组+差分 修改$(x1,y1,1)(x1,y2+1,-1)$$(x2+1,y1,-1)(x2+1,y2+1,1)$	注意容斥的正负

考试

ID	题目	状态	思路	注意
18	最近公共祖先	0/100	分块or树剖&卡空间	3 char -> int
19	无题	0/100	树剖+segtree	维护标记需注意
20	游走	0/100	树形dp，$f[u]=max(\sum_{v \in u} f[v],g[u])$ $g[u]=\sum_{v \in u }max(g[v],0) + val[u]$	很迷

15日

考试

ID	题目	状态	思路	注意
23	磁力阵	0/100	貌似是启发式合并搜索	向std的码风致以崇高的敬意
24	虫洞	0/100(RE)	建建边,去去重,跑跑最短路	注意离散
25	电路维修	100/100(AC)	当成网格图,对每个网格对角线建双向边,如原状态有边,则现边权为0,否则为1,跑个SLF的SPFA或堆优的dijkstra即可	双向边是必须的

非考试

ID	题目	状态	思路	注意
26	[bzoj1503]郁闷的出纳员	WA/AC	由于对所有员工都要增减工资，若对每个员工都修改，复杂度高达O(n)，这时候，我们可以记录一个基准值now，每次对它修改，用一个Treap维护相对工资，加时直接加，减时del掉工资小于min-now的员工。至于查询第k大，也就是查询排名为t[root].sz-k+1的树。	insert时应插入x-now，因为之前工资的增减对才插入的值没影响。

16日

非考试

ID	题目	状态	思路	注意
27	[hdu 3625]Posters	WA/AC	只需稍微转化的矩形面积并，把一个矩形拆成4个就行了	若小孔在边缘，拆后面积为0的也对答案无贡献，不用特殊讨论，而坐标为整数，范围也不大，不用离散化。
28	[APIO 2012]派遣	WA/AC	由于并且每一个忍者的老板的编号一定小于自己的编号 Bi < i，那么我们可以由n到1，(表从属的树从下至上)，维护多颗左偏树(大根)，并且依次合并，一旦某点所在左偏树sum大于m，一直pop直到其左偏树sum<=m，每次算出的num*L[i]与ans取max，最后ans即为答案。	1.long long必开。2.合并时，将该点所在左偏树root节点与儿子节点所在左偏树root节点合并，并非它们本身。3.区分原树与左偏树。

17日

非考试

ID	题目	状态	思路	注意
29	[bzoj1452][JSOI2009]Count	WA/AC	开100个树状数组维护即可	输入数据的顺序

18日

考试

ID	题目	状态	思路	注意
30	count	0/100	根据题意($∀i ∈ [1, 2m], x _i ∈ Z ^+ , x _i \	n$)，可以推出满足条件$\prod_{i=1}^{2m} x_i< n^{2m}$,必有另一个满足$\prod_{i=1}^{2m} x_i> n^{2m}$与之对应，所以根据容斥原理，我们只需计算满足$\prod_{i=1}^{2m} x_i = n^{2m} $的解的个数,最后算出$\prod_{i=1}^{2m} x_i< n^{2m}$加上，对n分解质因数后，对每个质因数dp,$f[i][j]=\sum_{k=0}^w f[i-1]j-k$,还可以用滚动数组优化	需要求逆元
31	delete	0/100	根据Dilworth TH，对于一个长度为n的序列至多用$\sqrt n$个上升序列覆盖，所以只需每次贪心删去最长上升或下降子序列，就OK了	由于数据范围，求最长上升或下降子序列必须用$O(nlogn)$时间，并求出序列(方法有些偏门，忘了最后stack中不是满足题意的最长上升或下降子序列，最后hehe)
32	floor	15/100	看x就想起了斐波拉契数列通项公式,构造共扼根$y=\frac{\sqrt{5}-1}{2}$,构造递推数列$f_i=f_{i-1}+f_{i-2}(f[1]=2,f[2]=1)$,可用矩阵快速幂,当i为偶数时，对于近似解有影响(需减1)	用py跑对近似解有影响的i时，由于精度原因，n>34时偶数似乎就没影响了，然后特判写挂

19日

考试

ID	题目	状态	思路	注意
33	coin	0/100	概率dp，由于每个点被选中的概率是一定的，我们可以预处理出每个点被选中的概率，f[i][j]表示长度为i的数列第j个点被选中的概率，由于选中某点的概率=1-上一次取的人取到这个数的概率，即$f[i][j]=1-0.5\times (f[i-1][j-1])$$(取第一个，所有编号-1)+f[i-1]j)$，最后将每个点的权值乘上再求和即可	想错了，以为有O(1)算法，然后……
34	triangle	0/100	对于原图的每一条边，枚举两个端点中度数较少的端点的邻接点，判断是否构成三元环,判断时用HashMap判，至于补图，很方便计算它们的和，用和-原图的三元环个数即可	别想复杂，其实就是暴力优化
35	aqnum	0/100	暴力dfs，并剪枝，若now*prime[dep]^2>n,则在prime[dep]~maxprime中二分出最大质数prime[k],再给答案加上k-dep+1	别脑抽取对数，精度爽爽的(oj上却过啦，无语)

20日

非考试

ID	题目	状态	思路	注意
36	[bzoj1430]小猴打架	WA/AC	打架的过程可以抽象为对n个点连边形成无根树，由prufer数列得出共有$n^{n-2}$种本质不同的树，而连边的顺序共有$(n-1)!$种情况，相乘即可。	中途相乘时先转成long long，不然爆int会WA
37	[luogu1060]开心的金明	AC	稍微转化一下的01背包	背包就是背包，没什么可说的
38	[luogu1164]小A点菜	WA/AC	再转化一下的01背包，变成了求方案数，$f[j]+=f[j-c[i]]$	再次看清数据
39	[luogu1064]金明的预算方案	AC	有依附关系的背包，由于最多只有两个附件，列举四种情况，跑01背包（只对主件）	至今不知通过有没有附件判是否为主件与父亲为0有什么区别
40	[luogu1049]装箱问题	AC	01背包，把体积当作消耗，箱子当作背包	注意转化
41	[luogu1616]疯狂的采药	AC	完全背包，把01背包的内层循环倒着跑遍即可	倒着跑

21日

考试

ID	题目	状态	思路	注意
42	sum	20/100	n,k都很大，而m很小，显然对m搞事情，线性筛(因为它是积性的)跑一遍，1～m的k次方就得出了，$(m+i)^k \equiv i^k (mod \ m)$,然后……	考场上想到对m搞事情，却没想到后面的
43	light	100/100	二分高度，与每个灯求交点，得到一堆线段，搞搞线段覆盖即可	注意精度问题
44	sequence	0/100	dp,f[i]表示前i个的最小合并次数，g[i]表示在f[i]下最后一组的和，由于f单调不减，直接找到最大的j满足$sum[i]-sum[j]>=g[j]$,用$f[i]=f[j]+i-j-1$,$g[i]=sum[i]-sum[j]$更新f[i],g[i],然后break;	贪心写挂

非考试

ID	题目	状态	思路	注意
45	[luogu1880]石子合并	AC	区间dp，f[i][j]表示从第i堆石子到第j堆石子合并的最大(小)积分,sum[i][j]表示第i堆石子到第j堆石子的总数	sum[i][j]计算跨n时需注意

22日

考试

ID	题目	状态	思路	注意
46	overflow	100/100	高精乱搞，反正位数很小，像我直接上FFT	读入数据有毒，判断数据类型时不要用长度判断，没改数据前我读入炸掉，所以说，请考虑程序的鲁棒性
47	func	100/100	由于k很小，而且经过实验，最大数据最多跑30次，直接爆搜(求phi用$O(\sqrt n)$的方法)	不要线性筛phi，看看数据范围，空间要炸
48	jumpcut	0/100	暴力枚举a的倍数，然后暴力匹配	由于第一题读入有毒，所以说第三题没时间调了，时间的把握需注意

非考试

ID	题目	状态	思路	注意
49	N皇后	WA/AC	dfs	数组开大些(听说启发式修补可以解决千皇后)

23日

非考试

ID	题目	状态	思路	注意
50	[poj1655]Balancing Act	RE/AC	求树编号最小的重心，dfs记录sz数组等，一直取max更新即可	每次清空tot,sz,pre,vis
51	[poj3107]Godfather	AC	求树所有的重心	size初值
52	[cf27E]Number With The Given Amount Of Divisors	AC	给定n，求最小正整数满足它的因数等于n，枚举质数的n次方，每个质数的n次方作为dfs树的每一层，剪枝为若当前now×prime[dep]>ans则退出该层枚举	熟练背记100以内质数
53	[zoj2562]More Divisors	TLE	求n以内的因子最多的那个数。和上题差不多	看清n的取值范围

25日

考试

ID	题目	状态	思路	注意
54	sort	10/100	对于一个数，若它的右边有比它小的数，必然选择它，而移动不会影响其它数的相对位置，直接倒着$O(n)$扫一遍即可	考试脑抽，直接上逆序对，hehe
55	graph	0/100	若蓝图中存在$$,则红图中不存在$$或$$,又由于原图为竞赛图,任意两点有边，所以只需判断原图是否为DAG，以及将蓝边反向后的图是否为DAG，两次拓扑排序	考试似乎理解错题了
56	or	30/100	数位dp

26日

考试

ID	题目	状态	思路	注意
57	gene	70/100	后缀数组，从h[rank[1]]往分别前后扫，不断更新最小值并加上，最后加上原长即可	打个da,T了，还是写dc3
58	shield	0/100	将每个点当作向量，分解到两基底方向，按其中一个排序，再上$O(nlogn)$的最长上升子序列	考试时上了一大堆反三角函数，精度被卡死
59	chronophere	0/100	先建立超级源汇点S，T，最长链变成最长路，按拓扑序dp得到fi,g[i]，x->y建立f[x]+g[y]的边，拿堆维护并枚举更新答案即可	时间的把握需注意

非考试

ID	题目	状态	思路	注意
60	[bzoj1053]反素数ant	WA/AC	dfs枚举即可	注意反素数的因子个数必须严格大于小于它的数，所以一遇到因子个数相同并小于它的数，必须更新答案

27日

考试

ID	题目	状态	思路	注意
61	guard	20/100	若无精灵，则贪心取大于等于$B_i$的第一个$A_j$，有精灵，首先考虑秒杀，但秒杀集合中原威力最小的$A_k$也大于大于等于$B_i$的第一个$A_j$或无秒杀集合才考虑贪心取大于等于$B_i$的第一个$A_j$	STL写残了
62	phase	100/100	链询问+子树修改+满足区间可加性的异或，这不是裸的树剖吗？直接上树链剖分(虽然比dfs序慢)	终于在考场上完全写对树剖了
63	refuse	0/100	设$P_i$为进行i次操作后没有到达最终状态的概率，则$ans=\sum\limits_{i=0}^\infty P_i$,对于$P_i$,需要容斥计算，$$P_i=\sum_{\	S\	\&1}(1-p(S))^i- \sum_{!(\	S\	\&1)}(1-p(S))^i$->$ans=\sum\limits_{i=0}^\infty(\sum_{\	S\	\&1}(1-p(S))^i- \sum_{!(\	S\	\&1)}(1-p(S))^i)$,$ans=\sum_{\	S\	\&1}\sum\limits_{i=0}^\infty(1-p(S))^i- \sum_{!(\	S\	\&1)}\sum\limits_{i=0}^\infty(1-p(S))^i$,$ans=\sum_{\	S\	\&1}\frac{1}{p(S)}- \sum_{!(\	S\	\&1)}\frac{1}{p(S)}$,设sum(S)表示组成行列状态S的1的个数,$ans=\sum_{\	S\	\&1}\frac{tot}{sum(S)}- \sum_{!(\	S\	\&1)}\frac{tot}{sum(S)}$$,枚举$sum(S)$,可以用背包，$f[i][j][k]$表示确定了前i列的状态，$\	S\	$的奇偶性为j，元素个数为k的方案数，并把n,m中较小的作行，跑的快些	推式子大法好

28日

非考试

ID	题目	状态	思路	注意
64	[luogu2352]队爷的新书	WA/AC	q将左右端点离散化，在整个区间从左往右扫描，遇左端点cnt++,遇右端点更新答案并cnt—	读入优化读空数据会TLE
65	[luogu1955$\	$bzoj4195]NOI2015程序自动分析	TLE&RE&WA/AC	i，j很大，必须离散化，离散后先用并查集维护相等的，如在不相等中找出祖先相同的，输出NO，否则为YES	1.set的迭代器不能相减，vector可以 2.对祖先数组初始化时必须到二倍n，因为有n个条件，最多有2n个点
66	[luogu2062]分队问题	AC	排序，cnt记录当前队人数，如cnt==a[i],cnt清零，ans++	就是道水题
67	[bzoj1800][Ahoi2009]fly 飞行棋	WA/AC	矩形的对角线为直径，转化为求直径数量 若直径数量为x，则答案为$C_n^2=\frac{(n-1)\times n}{2}$	水题做1个小时，竟然想偏了

28日

考试

ID	题目	状态	思路	注意
68	number	100/100	找出小于等于n的所有数组成的质因数指数数组，只需n不断除以某个质数，并累加每次的商，即为此质数的指数，再用快速幂（指数为奇需减一）	脑袋短路想了1个半小时，才发现是水题
69	game	30/100	先用前缀和，然后是求$L \leq \frac{sum[r]-sum[l-1]}{r-l+1} \leq R $,化为整式，拆为两个不等式$ 0< sum[r]-sum[l-1] < L \times (r-l+1)$和$ 0 < sum[r]-sum[l-1] \leq R \times (r-l+1)$将使a[i]先减去L或R，得到新的$sum’[]$,变为求$sum’[r]\leq sum’[l-1]$,即为求逆序对，上BIT即可	多多推式子，又忘推式子了
70	fence	10/100	直接dfs，并对每只羊判断是加入以前的还是自成一家	dfs还是打少了

29日

考试

ID	题目	状态	思路	注意
71	fruit	80/100	直接二分即可	判断是否超过m在最后判断，不要中间return，20分不翼而飞
72	process	50/100	贪心，按一个的t×另一个的s是否小于一个的s×另一个的t排序，然后累乘即可	注意用快速乘
73	tree	50/100	贪心，按右端点排序，将树尽量放在右边	注意用BIT等数据结构维护区间信息

10月

2日

非考试

ID	题目	状态	思路	注意
74	[poj3321]Apple Tree	AC	树剖+BIT或dfs序

3日

考试

ID	题目	状态	思路	注意
75	clique	0/100	将$(x_i,w_i)$拆为$(x_i-w_i,x_i+w_i)$,用$x_i-w_i$与stack[top]比较，插入时用$x_i+w_i$，类似最长上升子序列$O(nlogn)$	stack[0]赋值为-INF
76	mod	40/100	线段树维护MAX和SUM，取模时对单点递归，若MAX < MOD,则return
77	number	0/100	f[i][k]表示1～i中有多少数在二进制下有k个1，f(i,k)单调递增(打表可知)，二分满足f[l][k]==f[r][k]==m的l，r，FirstAns=$\forall x \in [l,r]$,SecondAns=$r-l+1$	注意特判k==1

非考试

ID	题目	状态	思路	注意
78	[bzoj1221][HNOI2001]软件开发	RE/AC	费用流，把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。1、从S向每个Xi连一条容量为ri，费用为0的有向边。2、从每个Yi向T连一条容量为ri，费用为0的有向边。3、从S向每个Yi连一条容量为无穷大，费用为f的有向边。4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。5、从每个Xi向Yi+A+1(i+A+1<=N)连一条容量为无穷大，费用为fa的有向边。6、从每个Xi向Yi+B+1(i+B+1<=N)连一条容量为无穷大，费用为fb的有向边。

4日

考试

ID	题目	状态	思路	注意
79	mine	60/100	dp,f[i][j]表示第i位(是雷，不缺雷，缺雷)，ans为f[len][0(不缺雷)]+f[len][2(是雷)]
80	water	0/100	外围与超级源点S建立边，每个点与四周点建立边，把高度与当前dis的max当新dis更新最短路，跑SPFA或Dijkstra，最后每个点的积水高度为max(dis[i]-height[i],0)
81	gcd	0/100	容斥，用莫比乌斯函数即可

5日

非考试

ID	题目	状态	思路	注意
82	[luogu1429]平面最近点对（加强版）	WA/AC	分治，先按x为第一关键字，y为第二关键字从小到大排序，每次计算$[l,r]$区间MinDis，l>=r直接return INF;l+1==r返回dis(p[l],p[r]),若有更小的点，必在x轴$[p[mid].x-d,p[mid].x+d]$,取出这些点，按y排序，若有更小的点，必在y轴$[p[mid].y-d,p[mid].y+d]$,枚举dis比较即可	第二次排序关键字为y坐标
83	[hdu3932]Groundhog Build Home	WA/AC	最小覆盖圆,先随机化序列，圆O是前i-1个点得最小覆盖圆，加入第i个点，如果在圆内或边上则什么也不做。否则新得到的最小覆盖圆肯定经过第i个点。然后以第i个点为基础（半径为0），重复以上过程依次加入第j个点，若第j个点在圆外，则最小覆盖圆必经过第j个点。重复以上步骤（因为最多需要三个点来确定这个最小覆盖圆，所以重复三次）。遍历完所有点之后，所得到的圆就是覆盖所有点得最小圆。

6日

考试

ID	题目	状态	思路	注意
84	[cf558E]string	0/100	基数排序+线段树+卡常 或 线段树合并 或 LZW压缩+二分Code1 或 Splay	本题的数据最好用二分，写线段树基本都TLE，cf的数据最好用Splay
85	matrix	0/100	dp
86	big	0/100	Trie贪心

7日

考试

ID	题目	状态	思路	注意
85	mayuri	100/100	约瑟夫环的O(logn)解法	空间O(1)的
86	kurisu	0/100	经过一堆推式子后，得到 $$\sum \limits_{l \leq i < j \leq r } \	V_i \times V_j\	^2 = (\sum \limits_{i=l}^{r} X_i^2)(\sum \limits_{i=l}^{r} Y_i^2) - (\sum \limits_{i=l}^{r} X_i\times Y_i)^2$$ ,树状数组维护即可
87	okarin	100/100	最长公共上升子序列+路径打印

8日

非考试

ID	题目	状态	思路	注意
88	loj6029[雅礼集训2017Day1]市场	WA/AC	线段树维护区间加，除+查询和，min；用减法模拟除法（通过维护min和max,判断min==max时区间一起减）	开long long！！

9日

考试

ID	题目	状态	思路	注意
89	Matrix	100/100	记录每行到某点的最长1子区间长度，枚举每列按从大到小排序，取最长1子区间长度的min，ans取$i*最长1子区间长度的min$	排序不要直接对原二维数组排序，否则会TLE，建一个指针数组辅助
90	Present	30/100	设Pmin为p中最小值，对于模Pmin余x的a[i]，如存在其他物品能得到模Pmin余x的最小价值不大于a[i],则该a[i]可以满足，再模Pmin的剩余系跑最短路即可	Sk->Knowledge
91	Mahjong	0/100	“简单”的dfs??，枚举34块牌先判断国士无双和七对，然后先确定对子，直接dfs（字牌只能凑连子）	对细节的处理++

非考试

ID	题目	状态	思路	注意
92	[bzoj3211]花神游历各国	RE/AC	线段树维护区间和+更新区间sqrt，有数据范围可知，对于一个数，最多开6次就会变成1，记录每个开方次数，大于等于6，return，小于6暴力修改单点

10日

考试

ID	题目	状态	思路	注意
93	adore	20/100	状压dp，按方案数奇偶性分类	ps:先预处理出0~(1<< k)的数二进制中1的个数
94	confess	70/100	任选2个集合判断，期望O(n)得出答案
95	repulsed	50/100	g[x][k]表示x下面距离为k的需要灭火器的房间数，f[x][k]表示x下面距离为k的多余灭火器数,对于房间与灭火器的匹配在lca处进行，对于根节点特殊处理

11日

非考试

ID	题目	状态	思路	注意
96	[bzoj1087]互不侵犯King	AC	状压dp，f[i][j][k]表示前i行在状态为j时放k个国王的方案数$\begin{cases}f[0][1][0]=1 \\ f[i][j][k]=\sum{f[i-1][p][k-c[j]]}\end{cases}\$(c[j]为该状态该行国王数量，p为与j不冲突的上一行状态),p可以在dfs预处理j时得出。	!运算符优先级高于&
97	[vijos1424][NOI2001]炮兵阵地	WA/AC	状压dp，f[i][j][k]表示前i行在第i行状态为j时且第i-1行状态为k的方案数$f[i][j][k]=\max({f[i-1][k][l])+c[j]}$(c[j]为该状态该行炮兵数量，且j,k,l不冲突，j,k,l都满足不与该行地形状态冲突)。	j,k,l与该行地形状态一一对应，不要搞错
98	[poj2411]Mondriaan’s Dream	AC	状压dp，f[i][j]表示前i行在状态为j时的方案数$f[i][j]=\sum f[i-1][p]$(p为与j不冲突的上一行状态)$f[1][0]=1$

13日

非考试

ID	题目	状态	思路	注意
102	[luogu1280]尼克的任务	WA/AC	f[i]表示i~n时间能获得的最大空闲时间，倒着跑$f[i]=f[i+1]+1(g[i]==0)$$f[i]=max(f[i],f[i+max(t[j].T)])(g[i]!=0)$	自己重定义max，用三目运算符，如用++cnt会执行两次
103	[luogu1108]低价购买	AC	求最长下降子序列和不重复的方案数，f[i]表示前i个最长下降子序列，g[i]表示前i个最长下降子序列的方案数$边界(g[i]=f[i]==1)\\ g[i]+=gj\\ g[j]=0 ( a[i]==a[j] \&\& f[i]==f[j] ) $
104	[luogu1282]多米诺骨牌	WA/AC	f[i][j]表示前i个牌得到j需要的最小次数（由于j可能为负，所以加上n6）, 初值为INF，f[0][n6]=0,$f[i][j]=min(f[i-1][j+a[i]-b[i]],\\f[i-1][j-a[i]+b[i]]+1)$	由于每次只用到上次的值，可以用滚动数组优化
105	[luogu1508]Likecloud-吃、吃、吃	AC	f[i][j]表示第i行第j列能获得的最大价值，$f[i][j]=a[i][j]+max(a[i-1][j],$$a[i-1][j-1],a[i-1][j+1])$,ans为$max(f[n][m/2],f[n][m/2+1],f[n][m/2+2])$
106	[luogu1006]传纸条	AC	f[i][j][k][l]表示第一个走到(i,j),第二个走到(k,l)的最优解$f[i][j][k][l]=a[i][j]+a[k][l]+\\Max(f[i-1][j][k-1][l],f[i-1][j][k][l-1],\\f[i][j-1][k-1][l],f[i][j-1][k][l-1])$如出现相交，则一定不是最优解，但须减去重复计算的a[i][j]。而且两个必定同时进行，步数相同(i+j==k+l),则四层循环可减掉一层，l由l=i+j-k(i+j-k>0)推出
107	[luogu1387]最大正方形	AC	f[i][j]表示以(i,j)为右下角的最大正方形的边长，$f[i][j]=Min(f[i-1][j],f[i-1][j-1],\\f[i][j-1])+1(a[i][j]==1)$
108	[luogu1417]烹调方案	WA/AC	贪心的可以知道满足c[y]b[x]>c[x]b[y]，前者更优，所以排个序，跑一遍0/1背包即可

16日

考试

ID	题目	状态	思路	注意
109	AddEdge Loves Working	25/100	用一个堆维护结束时间，如堆顶元素+m<当前块起始时间，一直弹出，然后如堆顶元素<=当前块起始时间,ans++，并弹出堆顶元素，最后将当前块结束时间插入堆	先对块按左端点从小到大排序
110	LargeDumpling Loves Graph	50/100	用倍增跑Floyed，得到某两点距离为$2^t$的最短路，再处理出距离为$e$的最短路
111	jvjhfhg Loves Sequence	25/100	将所有询问按右端点排序，用类似twopointer的方法，并用BIT

17日

考试

ID	题目	状态	思路	注意
112	斜率	100/100	可以证明，得到的最大斜率必由相邻点得出（画个三角形就行了）
113	最优路线	100/100	将点权排序，按点权从小到大枚举第三点跑Floyed
114	小G的线段树	0/100	因为没有修改，所以可以不用BIT，直接用差分维护每个点的期望，最后查询即可

18日

考试

ID	题目	状态	思路	注意
115	sum	100/100	可以发现，以$a_i$为右端点的答案可以由$a_{i-1}$的答案+1再乘以$a_i$得到，所以$O(n)$扫一遍即可	由于乘时可能会爆unsigned long long，所以要用快速乘
116	road	0/100
117	shopping	10/100	用线段树维护

19日

非考试

ID	题目	状态	思路	注意
118

20日

考试

ID	题目	状态	思路	注意
119
120
121

非考试

ID	题目	状态	思路	注意
122	[luogu1967][NOIP2013]货车运输	WA/AC	对答案有贡献的边，一定在最大生成树上，再在最大生成树上倍增求lca计算ans,用并查集维护不相通的	1.建双向边！2.dis <- INF. 3.每个点都要尝试dfs，因为可能不相通
123	[bzoj2134] 单选错位	AC	每道题的期望是独立的，当$a_i > a_{i+1}$时，有 $\frac{a_{i+1}}{a_i}$ 的概率选中$1,2……,a_{i+1}$中的一个，这一个正确的概率为$\frac{1}{a_{i+1}}$，选对的概率为$\frac{1}{a_i}$，每道题贡献为1， 每道题期望做对的题目个数为$\frac{1}{a_i}$，当$a_i < a_{i+1}$时同理可得为$\frac{1}{a_{i+1}}$，所以每道题期望做对的题目个数为$\frac{1}{max(a_i,a_{i+1})}$。

21日

考试

ID	题目	状态	思路	注意
124
125
126

22日

非考试

ID	题目	状态	思路	注意
127

23日

考试

ID	题目	状态	思路	注意
128

25日

考试

ID	题目	状态	思路	注意
129
130
131
132
133

26日

考试

ID	题目	状态	思路	注意
134
135
136

27日

非考试

ID	题目	状态	思路	注意
137

28日

考试

ID	题目	状态	思路	注意
138	抄代码	100/100	字符串签到题	注意对末尾’\n’的处理
139	做运动	100/100	两遍SPFA，第一遍得出最高温度最小值，第二遍得到最低热量	第二遍dis注意开long long
140	大逃杀	0/100	树形dp……

^Code1. github上的代码仓库 ↩