玉树营销网站建设哪家好,手机wap 网站,免费做链接的网站,网站怎么防黑客考试考到自闭#xff0c;每天被吊打。 还有几天可能就要AFO了呢。。。 Luogu3602#xff1a;Koishi Loves Segments 从左向右#xff0c;每次删除右端点最大的即可。 [HEOI2014]南园满地堆轻絮 答案一定是 \(\lceil \frac{max_{1\le i j \le n}(a_i-a_j)}{2} \rceil\)。…考试考到自闭每天被吊打。 还有几天可能就要AFO了呢。。。 Luogu3602Koishi Loves Segments 从左向右每次删除右端点最大的即可。 [HEOI2014]南园满地堆轻絮 答案一定是 \(\lceil \frac{max_{1\le i j \le n}(a_i-a_j)}{2} \rceil\)。 可以考虑一个二分答案 \(mid\)那么每个数 \(x\) 都是一个 \([x-mid,xmid]\) 的范围。 当前面有一个 \(y\) 使得 \(y-midxmid\) 时不合法。 然后答案就是最开始的东西了。 UOJ244【UER #7】短路 可以发现路径一定对称枚举在哪个绕半圈之前一定每个都走过两次每次肯定会多走前缀最小值所以直接加上即可。 Atcoder ???D Four Coloring 为了方便转成切比雪夫距离。 每个 \(d\times d\) 的矩阵染同样的颜色每次换颜色即可。 Codeforces 734FAnton and School \((a|b)(a\ b)ab\)全部加起来就可以手动解方程了。 注意还要代回去验证。 Atcoder ???J Farm Village 模拟费用流。正确性匹配不会交叉所以匹配过的不会同时返悔向后匹配。 [JXOI2017]加法 二分答案之后从前往后贪心每次选择右端点最大的区间加入。 BZOJ3709: [PA2014]Bohater 当 \(a-d0\) 的时候肯定是按照 \(d\) 从小到大打。 否则因为最后的血量是一定的那么直接倒过来向上面一样打即可。 Codeforces 720AClosing ceremony 把左边每个人按照体力值排序。 把每个空位按照到左边的距离排序。 左边人依次选择肯定选到右边距离最大的空位置。 然后右边随便贪心即可。 [AHOI2014/JSOI2014]宅男计划 三分最后要买的外卖数量。 然后考虑每次外卖怎么买首先肯定是先买便宜的买到保质期个。 那么从小到大考虑每个食物如果能使所有次外卖的存活天数增大就买到最多能增大的天数个。 买不了了就能买则买。 BZOJ3716: [PA2014]Muzeum 可以通过倍长坐标轴使得角度变成 \(\frac{\pi}{2}\)。 然后旋转使得变成一个向右下的矩阵。 这个东西就是一个最大权闭合子图。 考虑模拟网络流(?)按照 \(y\) 从小到大加入每一个手办和警卫插入警卫 \((x_0,y_0)\) 的时候按照 \(x,x\le x_0\) 从小到大依次流流量流满了就删除。 BZOJ2034: [2009国家集训队]最大收益 模拟二分图最大权匹配(?)。 首先可以缩小位置的规模每个区间(左端点小到大)向右找到第一个没有染色的点染色这样染色过的点才有可能匹配。 然后按照权值从大到小增广尝试每个位置如果没有匹配就成功如果这个位置匹配的区间右端点小于等于当前的点那么寻找下一个否则用这个位置的匹配去寻找(这样才更有可能找到)。 牛客Wannafly挑战赛27E 黄魔法师 考虑用 \(2,98,14\) 这些数字构造答案。 这些数字中 \(14216,1498112\)那么 \(1498\) 不是完全平方数。 所以可以找到一个最小的数 \(m\)使得 \(\frac{m(m-1)}{2}\ge k\)。 全部填 \(2\)多的用 \(98\) 换最后换个 \(14\) 即可。 UOJ143【UER #5】万圣节的数列 首先两个位置的和相同的等差子序列无论如何都消不掉不用管这些。 剩下的等差子序列是可以构造成没有的。 考虑对其奇偶分成两组那么剩下的等差子序列只可能出现在每个组内。 而每个数除掉 \(2\) 后等差子序列仍然等差所以递归处理即可。 [CEOI2011]Hotel 考虑将订单按价格从高到低排序然后按顺序安排最便宜房间并求出收益。取出前 \(o\) 大就是答案。 安排最便宜房间可以二分并查集维护删除。 因为如果房间有冲突显然会满足价格最高的如果 \(2\) 个订单对 \(2\) 个房间可以任意分配那么不会影响答案。 注意安排的时候要求收益大于 \(0\)。 BZOJ2124: 等差子序列 考虑枚举等差子序列 \((a,x,2\times x - a)\) 中间的 \(x\)。 如果长度不能大于 \(2\)那么就必须满足 \(a\) 和 \(2\times x-a\) 在 \(x\) 之前或之后出现。 也就是说把前面小于 \(x\) 的数的存在性写成一个 \(0/1\) 序列 \(a\)和大于 \(x\) 的数写成一个 \(0/1\) 序列 \(b\)。 那么满足 \(b\) 倒过来和 \(a\) 相等时就不会出现长度大于 \(2\) 的。 所以直接树状数组维护 \(hash\) 即可。 BZOJ 2907: 拜访神犇 枚举最后的终点可以确定最开始的方向分成三段除了起点到终点的这一段以外其它段的答案确定。 所以把间隔拿出来排序取出前 \(k\) 小即可用线段树或者优先队列即可。 Luogu5273【模板】多项式幂函数 (加强版) 可以把前面的 \(0\) 项先去掉最后补 \(m\) 倍 \(0\)。 注意到求 \(ln\) 要求常数项为 \(1\)那么可以先乘个逆元最后乘回来即可。 Codeforces 1111DDestroy the Colony 可以设计一个背包 \(f_i\) 表示选了 \(i\) 个字符的方案数每次枚举一个字符加入这个字符的个数。 答案就是强制不选 \(x,y\) 两种字符的方案数之后乘上可重组合即可。 可以预处理答案枚举 \(x,y\)做逆 \(dp\) 即可。 Codeforces 1111ETree 按照剧本先建立虚树然后从 \(r\) 开始 \(dfs\)。 设 \(f_{i,j}\) 表示到了点 \(i\) 分成了 \(j\) 个组的方案数。 从子树向上合并考虑非常麻烦考虑按照 \(dfs\) 序做。 那么这个点要么新建一个组 要么选一个组加入而选择的组不能包含之前已经插入过了的祖先而祖先们显然也不在一个组所以直接减去这些组即可。 Educational Codeforces Round 57 (Rated for Div. 2)E/F/G E 枚举分数枚举相同的人数容斥计算出把 \(n\) 分给 \(m\) 个人每个人不超过 \(lim\) 的方案数。F 期望的线性性求出每个逆序对的贡献即可。G 多项式快速幂模板题。 Codeforces Hello 2019D/E/F/G D 可以把操作看成是对每个质数的指数操作那么就可以质数分开独立计算(积性函数)。 每个质数分别暴力 \(dp\) 即可。E 可以发现 \(f(n) k − 1\),其中 \(k min\){\(x|\frac{x(x1)}{2} n\)}。 考虑证明同时构造答案。 对于长度为 \(n\) 的序列,设其 \(LIS\) 长度为 \(len\)。 若 \(len \le K\), 则 \(n − len \frac{K(K1)}{2}-K\frac{K(K-1)}{2}\) 若 \(len K\), 根据 \(Dilworth\) 定理,可以用 \( K\) 个下降序列覆盖, 只需要把以 \(i\) 相同的长度的点分成一组即可F 除了操作 \(3\) 都可以 \(bitset\) 现在要维护\[C_i\sum_{gcd(j,k)i}A_jB_k\] 类比 \(FWT\)只要求出 \(A_i\sum_{i|d}A_d\) 就可以直接按位相乘了 求答案就是莫比乌斯反演\(A_i\sum_{i|d}\mu(\frac{d}{i})A_i\) 把每个数字的 \(\mu\) 的 \(bitset\) 预处理出来乘法就是 \(and\) 最后用 \(count\) 统计答案G 对于 \(x^k\)。 二项式定理展开一般需要 \(k^2\) 卷积合并。 而斯特林展开后只需要求 \(\binom{x}{i}\) 之类的东西一般可以进行 \(O(k)\) 递推。 这题就是\(\sum_{i1}^{k}\binom{f(X)}{i}i!\begin{Bmatrix}k\\i\end{Bmatrix}\)。 考虑计算 \(\binom{f(X)}{i}\) 即可。 这个东西就是在一棵虚树上选出 \(i\) 条边的方案数。 可以树 \(dp\)设 \(f_{u,i}\) 表示当前到了 \(u\)虚数内选择了 \(i\) 条边的方案数。 合并儿子的时候注意一些子树内必须选点才能构成虚树要减去空集的方案。 计算的时候考虑清楚即可。 不难证明复杂度为 \(O(nk)\)。 LOJ2396「JOISC 2017 Day 3」长途巴士 对于所有的东西按照 \(mod~T\) 排序。 考虑 \(i\) 次和 \(i1\) 次饮水如果中间有一个站点那么一个以 \(i\) 结尾的后缀都是可以下车的。 可以设计一个 \(dp\)\(f_i\) 表示前 \(i\) 次饮水把每一个 \(T\) 的事情一次做完转移可以斜率优化。 TopCoder SRM720 Div 1ExtremeSpanningTrees 不难发现就是给定了一些形如 \(D_i\le D_j\) 的限制。 求 \(\sum_{i1}^{m} |D_i - w_i|\) 显然 \(D\) 只可能是出现过的 \(w\)。 首先考虑 \(1\le w_i\le 2\)只有两种取值最小割 \(S\) 表示 \(1\)\(T\) 表示 \(0\)建图即可。 对于 \(1\le w_i\le 10^9\) 首先答案肯定是关于 \(D_i\) 的一次函数加起来考虑整体二分。 对于所有小于等于 \(mid\) 的 \(w\) 看成是 \(1\)大于的为 \(2\)用上面的建图即可。 和 \(S\) 在同一集合的显然大于 \(mid\) 不优秀不在的同理分治即可。 TopCoder TCO2018 Algo Onsite FinalDiv1BalancingTrees 最优策略下可以只改变叶子只需要把父亲的改变均分给儿子即可。 那么每个叶子都是一个关于总和的一次函数。 总的代价肯定也是一个分段一次函数并且是凸的。 三分即可。 upd貌似不用三分直接排序枚举答案即可类似中位数。 [NOI2018]冒泡排序 自己yy了一个复杂的一批的方法QwQ 可以发现与一个位置 \(i\) 有关的逆序对的个数 \(\ge |p_i-i|\)。 显然一个排列合法就要要求与每个位置有关的逆序对的个数 \( |p_i-i|\)。 也就是说对于 \(p_ii\) 的要求 \(i\) 后面的 \(p\) 都大于 \(p_i\)对于 \(p_ii\) 的要求前面的 \(p\) 都小于 \(p_i\)。 那么就是不存在一个不以 \(i\) 为开头或结尾的的递减子序列也就是递减子序列长度不超过 \(2\)。 考虑没有字典序限制怎么计算。 可以考虑从小到大依次加入数字可以发现会形成很多空位。其中有一个前缀的空位置如果加入了当前的数字会使下降序列长度变成 \(2\)不妨认为这种位置是特殊的。 那么显然如果要放在这些特殊的位置就只能在第一个否则可以放在一个其它位置并把这个位置之前的位置变成特殊的。 那么可以设计状态 \(f_{i,j}\) 表示从小到大前 \(i\) 个数放完有 \(j\) 个特殊位置的方案数。 转移显然是 \(f_{i,j}f_{i-1,j1}\sum_{k0}^{j}f_{i-1,k}\) 设 \(g_{i,j}\sum_{k0}^{j}f_{i,k}\)。 那么 \(g_{i,j}g_{i,j-1}g_{i-1,j1}\) 可以看成是网格图上一个点 \((x,y)\) 每次可以使得 \(y1\) 或者 \(x1,y-1\)从 \((0,0)\) 最后到 \((n,0)\) 的方案数。 也就是 \((x,xy)\) 每次可以走到 \((x,xy1)\) 或者 \((x1,xy)\)从 \((0,0)\) 到 \((n,n)\) 的方案数要求 \((a,b)\) 满足 \(b\ge a\)即不经过 \(yx-1\)。 这是个经典组合问题对称相减即可。 考虑利用上面的东西计算最终答案。 枚举排列 \(p\) 的前 \(i-1\) 位和给定的排列 \(q\) 相同并且 \(p_iq_i\)。 分情况 如果前 \(i-1\) 位已经不合法就结束了。 如果前 \(i-1\) 位存在一个逆序对 \((x,y)\)使得 \(y\) 的还有数没有出现在前面同样也结束了。 否则那些小于 \(max\{max_{k1}^{i-1}\{q_k\},q_i1\}\) 的没有在前面出现的数显然只能递增的排列设这样的数有 \(k\) 个。 考虑用之前的 \(dp\) 计算也就是给之前的 \(f\) 赋值即 \(f_{k,i}\binom{k-i2}{i-1}\)也就是枚举强制 \(k\) 个递增后有多少特殊位置并且要求第一个位置必须为空。 这个东西就是网格图上 \((1,k1)\) 到 \((k,ki)\) 的格路数。 由于要求出 \(g\) 即 \(f\) 的前缀和\(g_{k,i}\) 也就是 \((0,k1)\) 到 \((k,ki)\) 的格路数。 那么答案就变成了 \((0,k1)\) 到 \((n-i1,n-i1)\)不经过 \(yx-1\) 的格路数直接组合数计算。 LOJ2834「JOISC 2018 Day 2」修行 神仙的一批。 相当于是要求有多少排列 \(P\) 满足 \(P_iP_{i1}\) 的位置数恰好为 \(k−1\)。 等价于求 \(n\) 个 \([0,1)\) 随机变量 \(v_i\)满足恰好 \(k-1\) 个满足 \(v_iv_{i1}\) 的概率 \(\times n!\)。 等价于 \(n\) 个 \([0,1)\) 随机变量 \(b_i\)\(a_i\) 对应 \(b_i\) 前缀和的小数部分满足 \(k-1 \le \sum b_i \ge k\)。 容斥有多少个 \(b_i\ge 1\)然后就变成了求 \(n\) 个 \([0,\infty)\) 随机变量之和 \(k\) 的概率这个概率等于 \(\frac{k^n}{n!}\)。 详见官方题解。 Codeforces 906EReverses 把 \(S\) 和 \(T\) 插空问题变成划分成长度为偶数的回文串的问题。 利用 \(PAM\) 上回文串长度不超过 \(log\) 进行 \(DP\)。 Codeforces 611HNew Year and Forgotten Tree 首先肯定要把相同的长度的边连成链缩起来设为关键点。 如果最终方案存在不同长度的非关键点之间连边那么显然可以更换连边方式使得这条边替换成关键点和非关键点的边。 所以现在只有两种边一个是关键点之间的边一个是非关键点和关键点之间的边。 可以枚举关键点之间的边(\(prufer\) 序列)然后对于非关键点和关键点之间的边一条边 \((a,b)\) 要么连 \(a\) 的关键点和 \(b\) 的非关键点要么连 \(b\) 的关键点和 \(a\) 的非关键点网络流解决。 [ZJOI2012]灾难 求 \(DAG\) 支配树的每个点子树大小 \(-1\) 每个点在支配树上的父亲为所有指向它的点的支配树的 \(lca\) 注意加超级源点有可能有某个点同时能吃多个生产者如果没有超级源点的话\(lca\) 就挂了。 Codeforces757FTeam Rocket Rises Again 在最短路径 \(DAG\) 上求个支配树即可。 [ZJOI2019]线段树 问题可以看成是每次有 \(\frac{1}{2}\) 的概率做修改求所有情况的权值总和。 设 \(f_i\) 表示 \(i\) 点有标记的概率那么答案就是求个和。 考虑一次修改的影响 a.对于树上不会打懒标记的并且会经过的点显然 \(f_x\frac{f_x}{2}\) b.对于会打懒标记的点显然 \(f_x\frac{f_x1}{2}\) c.关键是那些不会经过的但是会得到下放的标记的点\(f_x\frac{f_xv}{2}\)其中 \(v\) 表示 \(x\) 的祖先存在至少一个点有标记的概率。 可以发现这个 \(v\) 不好直接计算考虑再设 \(g_x\) 直接表示 \(x\) 的祖先存在至少一个点有标记的概率。 实际上在后面的过程中可以发现维护 \(x\) 的祖先不存在一个点有标记的概率更好操作。 所以就委会 \(x\) 的祖先存在不一个点有标记的概率。 对于 \(a\)显然 \(g_x\frac{g_x1}{2}\) 对于 \(b\)显然 \(g_x\frac{g_x}{2}\) 对于 \(c\)显然 \(g_x\frac{g_xg_x}{2}g_x\) 由于引入了 \(g\)所以需要考虑所有打上懒标记的点的子树显然 \(g_x\frac{g_x}{2}\)可以用懒标记维护。 Codeforces 1098EFedya the Potter 首先可以预处理每一种 \(gcd\) 的区间有多少可以 \(st\) 表倍增 \(log^2\) 处理。 然后二分中位数 \(mid\)。 考虑在预处理的东西上从小到大取出区间。 枚举左端点计算所有可能的右端点。如果这个区间的 $gcd\times $ 次数不超过 \(mid\) 则直接乘法原理。 否则就是一个类似求 \(\sum_{x1}^{n}\sum_{y1}^{m}axby\le c\) 的式子可以容斥之后直接做类欧几里得。 [HNOI2017]影魔 感觉还比较简单 以下是我这个垃圾想到的垃圾算法。\(ij\)分几种情况考虑贡献 首先是 \(p_1\) 的贡献 a. \(k_ik_j\)那么可以枚举 \(i\)显然只有一个 \(j\) 合法二分即可。 b. \(k_jk_i\)那么可以枚举 \(j\)显然也只有一个 \(i\) 合法还是可以二分。 这一部分的贡献就可以离线下来枚举右端点维护左端点的答案。 然后是 \(p_2\) 的贡献 a. \(k_imax_{pi1}^{j-1}\{k_p\}k_j\)可以枚举 \(i\)找到后面的第一个大于 \(k_i\) 的数然后这个位置之后的单调递增的位置都可以是 \(j\)。 b. \(k_jmax_{pi1}^{j-1}\{k_p\}k_i\)可以枚举 \(j\)找到前面的第一个大于 \(k_j\) 的数然后这个位置向前的单调递增的位置都可以是 \(i\)。 这一部分的贡献也可以离线下来从前到后和从后到前分别作一遍枚举右(左)端点维护左(右)端点的答案。 给单调递增的位置加贡献可以单调栈 \(lazy\) 实现每次弹出的时候在 \(bit\) 里面修改栈内的直接二分前缀和。 然后就可以在 \(O(nlogn)\) 的时间里面用单调栈\(bit\)二分解决这个题目。 [HNOI2017]大佬 首先可以认为怼大佬以及还嘴的操作看成是休息做完了之后再一次性怼个爽。 那么显然是留下的时间越多越好这个可以 \(O(n^2)\) 预处理。 假设最大时间为 \(d\)。 考虑枚举两次怼大佬的时间设嘲讽值为 \(f_1,f_2\)蓄力的时间为 \(d_1,d_2\)。 那么只要满足 \(f_1f_2-d_1-d_2d\ge c\) 且 \(f_1f_2\le c\) 即可。 可以把所有的 \(f,d\) 对爆搜出来据说不多 然后每次双端点即可。 [HNOI2016]大数 基本上是莫队模题特判一下 \(p\) 是 \(10\) 的约数的情况即可。 [HNOI2015]落忆枫音 记 \(d_i\) 表示 \(i\) 的入度那么不加边的答案显然是 \(\prod_{i2}^{n}d_i\)表示每个点选一个入边。 加边就只需要减去包含 \((x,y)\) 的环的贡献拓扑排序求出 \(y\) 到 \(x\) 的路径的贡献即可。 [HNOI2015]实验比较 可以发现把同样的缩起来之后就可以弄出一棵树。 设 \(f_{u,i}\) 表示点 \(u\) 的子树有 \(i\) 个不同的数的方案数。\(f_{u,ij-k}\sum_kf_{v,j}f_{u,i}\binom{ij-k}{i}\binom{i}{k}\) 枚举有多少变成相同\(\binom{ij-k}{i}\) 表示安排 \(i\) 的位置\(\binom{i}{k}\) 表示选出那些相同的数可以发现这些数确定了之后 \(v\) 的 \(j\) 个数的放法就确定了。 转载于:https://www.cnblogs.com/cjoieryl/p/10632843.html
