题意给你\(n\)个串\(s_i\)，你需要选出\(k\)个串并按照某个顺序拼接起来形成的字符串字典序最小。\(n,k,|s|\le50\)。分析由于顺序不固定，所以我们无法直接DP。而状压的复杂度也太高了，怎么办呢？考虑钦定一个顺序，使得按照这个顺序排列字符串一定最优。一个经典的错误想法

题意给定一个图，每次修改一条边的边权，每次修改后输出该图的最小生成树边权和，询问间不独立。思路在线不好做，考虑离线下来，可以使用线段树分治。我们称在当前区间\(\left[l,r\right]\)的边为动态边，不在的边为静态边。但这样每次遍历到叶子节点的时候静态边的数量都是\(m\)的

CodeforcesRound975(Div.2)A~F题解（Div.1A~D)也是补完整场了。A.MaxPlusSize枚举最大值的位置，使长度最长，更新答案。B.AllPairsSegments每个线段内部的点的答案都是一样的，在处理一下线段两边边界的点。被包含次数就是左边\(\times\)右边。用\(map\)记录答案

这里从DBImpl::MaybeScheduleFlushOrCompaction开始讲起。DBImpl::MaybeScheduleFlushOrCompaction可能会scheduleDBImpl::BGWorkFlush和DBImpl::BGWorkCompaction。这里主要看Flush。Compaction部分见：{%post_linkStorage/'RocksDB代码分析——Compaction流程'%}DBImpl::BGWo

【20联赛集训day10】排列一个长度为\(n\)的排列，每次操作删除所有存在相邻的数字比它更大的数字，问执行\(k\)次操作后剩下恰好一个数的排列方案数。首先因为每次删除至少删一半的数字，所以最多删\(\log\)次。对于一个排列，我们可以发现把序列按最大值劈开，左右两边互不干扰，成

link：https://codeforces.com/contest/1592/problem/F2题意：给定一个\(n\)行\(m\)列的目标矩阵，矩阵元素只有W或B，并且你有一个初始矩阵，元素全为W。现在你可以矩阵实施以下操作：使用一块钱，选定一个包含\((1,1)\)的子矩阵，把矩阵中的元素全部反转（W变B，B变W）。使用

题面稍微有一点不一样。Statement给\(n\)个物品，每个物品有价值\(v_i\)、体积\(w_i\)。\(q\)次询问，问考虑\([L..R]\)区间的物品，用容量为\(m\)的背包最多能装多少价值的物品，有多少种方案，每个物品只能被装一次。\(n\le2\cdot10^4,q\le10^5,w_i,m_i\le500,v_i\le

Solution先离散化，记\(f(l,r,p)\)为覆盖了\([l,r]\)区间内纵坐标\(\gep\)的点最少矩形个数。则：\[f(l,r,p)=\min(f(l,r,p),f(l,mid,p)+f(mid+1,r,p))\]\[f(l,r,p)=\min(f(l,r,p),f(l,r,res)+1)\]令\(h\)为用面积为\(S\)的矩形去覆盖\([l,r]\)区间的高度，即\(S/(r

Statement给出\(k,p,L\)，数序列\(a\)，满足如下条件：\(1\lea_i\lek\)\(\sum_ia_i=L\)\(\nexistsi,a_i\gep\landa_{i+1}\gep\)答案对\(20201114\)取模，\(p\lek\le1000,L\le10^{18}\).Solution30pts注意到可以dp，记\(f(i,0/1)\)为凑出\(i\)的方案

StatementQ7.1.2.4，时限4s给一个串，定义\(\mathrm{LCS}\)为最长公共子串长度，\(q\)次询问，每次给出\(l,r\)，求\[\operatorname{xor}_{i=1}^{r-l+1}\{i+\mathrm{LCS}(S[l,l+i-1],S[l+i-1,r])\}\]\(n\le10^5,q\le30\)Solutiontag：SA，线段树维护分治结构，orzhunction题目就是

Statement给 \(n\) 个串，问每个串有多少子串是所有 \(n\) 个串中至少 \(k\) 个串的子串。Solution1%%注意到\(\text{LCP}\)在后缀排序后一定是连续的一段，包含一个串的区间是连续的先预处理出对于所有左端点\(l\)，最左的\(r\)满足\([l..r]\)中出现了至少\(k\)个

Statement把\(S\)分成不超过\(k\)段，使每段的最大子串中的最大串最小。输出这个串。Solution按排名二分这个串，check中从右往左贪心地划分，需要实现\(O(1)\)比较两个子串大小。#include<bits/stdc++.h>usingnamespacestd;#definerep(i,j,k)for(inti=(j);i<

对于一个固定的右端点\(r\)，左端点\(l\)合法当且仅当\(\max(d_l,d_{l+1},\dotsd_r)\ler-l+1\le\min(c_l,c_{l+1},\dots,c_r)\)。容易得到一个很朴素的dp：记\(f_i\)表示前\(i\)个位置可以分成的组的数目的最大值，\(g_i\)表示有多少种分组方案能达到最大值，直接枚举左端点

前言：在之前已经学习过矩阵快速幂的用法，那些只是基础。在ICPC中大多数难度较高，且并不是简单的只需要常数的矩阵或者简单的图上问题，而是结合dp方程去推导出来转移矩阵。trick：例题：链接：https://ac.nowcoder.com/acm/contest/88880/E来源：牛客网给出两个整数\(n,k\)，有一个正整数

K-HaitangandAva怎么还有人签到题wa啊/kk定义以下的字符串是合法的：空字符串若\(S\)是合法的，那么\(S\)+ava和ava+\(S\)都是合法的若\(S\)是合法的，那么\(S\)+avava和avava+\(S\)都是合法的给定一个字符串，判断是否合法。以v为分隔计数a，容易发现计数数组中除了开头和末

SS240914A.神灵庙(desire)问一棵有\(n\)个叶子的任意形态的二叉树，左儿子边权是\(1\)，右儿子边权是\(2\)，给叶子任意顺序附上\(a_i\)的权值，问\(\sumdep_ia_i\)最小。首先如果树的形态确定了，显然是深度大的叶子选小的\(a_i\)。（注：这里的深度都是只带权到根的距离）因为是树

感觉每一步都挺自然的。首先连续加减让我们不难想到差分，每次给\(d_i\)加一或减一，每次给\(d_{i+l}\)减一或加一。然后要求单调不降就是要求每个\(d_i\)大于等于\(0\)。然后注意到我们每次操作相当于是\(i\)向\(i+l\)贡献\(1\)或者\(i+l\)向\(i\)贡献\(1\)，结合

B.【20省选十联测day2】bitrev求\(\sum_{i-1}^Rpopcount(i+g(i))\)，其中\(g(i)\)表示把\(i\)的二进制（不含前导\(0\)）reverse得到的数。\(R\le10^{14}\)。显然这种东西我们会想到数位DP。于是正解是一个很恶心的数位DP。首先我们要按枚举有效位数\(x\)，显然\(x=1\)

感觉是一个比较厉害的trick，并且从来没见过，记录一下。题意给定\(n\)个数和\(q\)次操作：1lrx：区间\([l,r]\)加\(x\)。2xv：查询在询问之前有多少时刻\(a_x\gev\)。一次操作定义为一个时刻，初始为\(0\)时刻。\(n,q\le10^5\)分析如果\(x\ge0\)，那么\(a_i\)的

【五一省选集训day4】Permutation每次操作把数分成两组，每组内的顺序不变，把第\(0\)组放到第\(1\)组前面。发现这很像基于二进制的基数排序。假设我们进行\(k\)次这样的操作，就相当于给每个数赋一个值\((x,y)\)，其中\(0\lex\le2^k-1,y=\texttt{数的下标}\)。然后对第一维

link：https://codeforces.com/contest/1715/problem/E有\(n\)座城市，城市间有\(m\)条双向道路，通过第\(i\)条道路需要花费\(w_i\)的时间，任意两个城市之间都有航班，乘坐城市\(u\)和\(v\)之间的航班需要花费\((u-v)^2\)的时间。现在请对于任意城市\(i(1\lei\len)\)

题解题意：题面很臭很长。大意是，有一个大小为N的环，给出M，K，D，以及N个数。我们进行K次操作，每次操作把距离当前点不超过D的累加到当前点，结果模M。思路：因为要进行K次，每次的原则是一样的，我们可以想到用矩阵来优化，如果i能到达j，把么base[i][j]=1；则结果ans=A(base^K)。但是需要优化，时间复杂

题解题意：题面很臭很长。大意是，有一个大小为N的环，给出M，K，D，以及N个数。我们进行K次操作，每次操作把距离当前点不超过D的累加到当前点，结果模M。思路：因为要进行K次，每次的原则是一样的，我们可以想到用矩阵来优化，如果i能到达j，把么base[i][j]=1；则结果ans=A(base^K)。但是需要优化，时间复杂

问题在学习到Linux内核input子系统时，产生了一个疑惑。可以看到，我们改造按键中断驱动程序（请见keyinputdriver.c（内核驱动代码）），通过检测按键的上升沿和下降沿，在中断处理函数（上半部内）通过mod_timer(&dev->timer,jiffies+msecs_to_jiffies(20))函数启动定时器。在定时器处理函数中上

简要题意可以去看其他题解。前置知识：LGV引理。看到这道题我们先考虑该怎么判定\(f(l,r)\)是否等于\(x\)。看完题面后很难不让人想到LGV引理（不相交路径，起点集\(S\)和终点集\(T\)）。但是LGV引理是用于计数的，放在这里似乎并不好用。但是我们可以注意到，只要没有合法情况，