题面题面下载算法转化题意说白了就是给了你一堆点，让你数这种折线有多少个(严格向下走，并且横坐标之间的差越来越小)看着像一种在y轴方向排序的dp但是由于是折线,所以需要加一维来判断转向dp设计状态设计\(dp_{i,0/1}\)表示第i个点,是向左下还是右上状态转移

题面题目下载算法考虑当\(k\)确定的时候如何求答案,显然对于所有形如\([ak,(a+1)k)\)的值域区间,最大值一定是最优的似乎怎么都是\(O(n^2)\)的算法观察到\(a_i\)的值域比较小,所以考虑桶显然对于一段区间\([L,R]\)我们可以推出其\(modk\)的最大值方法

题目链接题目分析听说是很典的一道题，很明显难点在于除法下取整的操作。类似花神那一道题，但是由于有区间加，所以无法进行暴力修改。很明显暴力复杂度爆炸，考虑下取整带来的性质：对于一对相邻的数，很明显有\(\lfloor\frac{x-1}{k}\rfloor\le\lfloor\frac{x}{k}\rfloor-1\)。

雅礼2023.12.27习题课记录前言这一场罚时多，都是一些低级错误。好吧全都是水题。水题（只放代码）莫诺卡普参加了一场编程比赛，其中包括\(26\)个问题，从A到Z命名。问题按难度排序。此外，已知莫诺卡普可以在\(1\)分钟内解决问题A，在\(2\)分钟内解决问题B，\(\dots\)，在\(2

雅礼\(2023.12.20\)习题课记录（讲解版）前言AlwaysCF，NeverAT。又双是CF题，只能说“水”，AK了。水题（只放代码）B-TwoVessels（CF1872A)有分别装有\(a,b\)单位水的两个杯子，容量无限大。现在有一个勺子，容量为\(c\)，每次可以从一个杯子里舀一勺不超过\(c\)单位的水（\(c\)

LOJ传送门显然枚举物品做背包没有前途，于是我们把体积相等的物品捆绑在一起。设\(f_{i,j}\)为考虑完体积\(\in[1,i]\)的物品，背包容量为\(j\)的最大值。可以贪心求出\(g_{i,j}\)为选\(j\)个体积为\(i\)的物品的价值最大值。分\(j\bmodi\)的余数转移，发现可以

总结100+0+100+30=230分对于昨天来说好多了，但是第二题忘去重了（本来去重了，但是对拍写错了，然后就把去重删掉了

总结100+0+0+0=100分考的很垃圾（第二题调试删了但没完全删这一场感觉是纯数学呀T1枚举时间复杂度：\(O(1)\)空间复杂度：\(O(1)\)code:#include<bits/stdc++.h>usingnamespacestd;constintN=15;longdoublea[N];intmain(){a[0]=1.0;for(inti

给定\(n\)个物品，第\(i\)个物品有体积\(c_i\)，价值\(v_i\)。给定\(K\)，对\(1\simK\)的所有\(i\)求大小为\(i\)的背包的最大价值。\(n\leq10^6\)，\(K\leq5\times10^4\)，\(c_i\leq300\)，\(0\leqv_i\leq10^9\)，时限\(\text{2.0s}\)。注意到\(c_i\)范

这道题恶心之处在于区间向下取整。这里给出两种思路：区间覆盖做法如果最大值和最小值向下取整后相等，则对此区间进行区间覆盖。我考场写的是这个，但是码错了，加上习惯不好,\(100\to64\),再加上烦了弱智错误，\(64\to9\)，不给出代码。差值相等做法注意到相邻两数的向下取整的差值不

做到这题，发现自己对\(SAM\)的一些性质还不知道，特此记录。题目要求01字符串区间内前缀的最长公共后缀由SAMparenttree性质可知，2个前缀的最长公共后缀就是它们在parenttree上lca的len值如何去感性理解我们知道，在parenttree上每个节点都代表了一个endpos等价类，由后缀链接将他

题目大意有\(n\)个物品，第\(i\)个费用为\(w_i\)，价值为\(v_i\)，对于\(k\in[1,m]\)求费用为\(m\)时能获得的最大价值。\(1\leqn\leq10^6,1\leqm\leq5\times10^4,1\leqw_i\leq300,1\leqv_i\leq10^9\)思路\(n\)很大，但\(w_i\)很小，于是我们考虑以其为突破口

题目前言这个贪心有点妙，考试的时候没有想出来，一看题解恍然大悟。分析首先对于洗衣服，显而易见我们可以用堆来处理，可以得出每件衣服洗完的时间\(t_i\)，其中\(t_i\)表示

题目链接U161009[雅礼集训2017Day1]市场题目背景从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落

「雅礼集训2018Day1」树首先发现这个期望是诈骗，我们只需要求出\(g_i\)表示深度为\(i\)的树的个数然后带权除以总方案数即可。树的题目容易想到一个子树一个子树抠出来，

雅礼NOIP2018集训day5联题面由于出题人懒所以没有背景。一个无限长的01序列，初始全为0，每次选择一个区间[l,r]进行操作，有三种操作：•1lr将[l,r]中所有元素变

雅礼NOIP2018集训day5赛题面由于出题人思维枯竭所以想不出好玩的背景。有n个物品，第i个物品的价格是vi，有两个人，每个人都喜欢n个物品中的一些物品。要求选出正

雅礼NOIP2018集训day3u题面考虑一个\(n*n\)的矩阵\(A\)，初始所有元素均为\(0\)。执行\(q\)次如下形式的操作：给定\(4\)个整数\(r,c,l,s\)，对于每个满足\(x\in[r,r+l),y\in

雅礼NOIP2018集训day3w题面有一棵n个节点的树，每条边长度为1，颜色为黑或白。可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。对于某些边，要求在操作结