字符串：P4391[BOI2009]RadioTransmission无线传输https://www.luogu.com.cn/problem/P4391kmp的next数组如果next[x]=len（0<len<x）,那么就有s[len]=s[x];那么去掉s[x]后得到的[1,x-1]依旧是原串的循环子串，因为x为最短长度，所以可得next[x]一定为0;所以我们可以推论得到n

背包问题背包，即询问一个背包装最大价值的物品总价值。01背包例题：P1048采药想到使用DP。\[f_{i,j}=\left\{\begin{matrix}\maxf_{i-1,j-c_i},f_{i-1,j}&j\gec_i\\f_{i-1,j}&j<c_i\end{matrix}\right.\]（公式中，\(f_{i,j}\)表示使用前\(i\)个物品，重量小

达到今日更新量题目让我们求所有简单路径上最大值减去最小值的总和实际上就是所有简单路径的最大值总和减去所有简单路径上最小值总和然后分别求所以简单路径的极值，下面以最大值为例：我刚开始想到了非常SB的做法：枚举最大值x，设比x大的数为y，实际上有很多y，如果y是x的祖先，那么点对

7.3一直想挑个好日子开始写做题纪要，防止自己太颓，但是咕了很久。今天也并不是什么好日子，只是不想再咕了。不是怎么突然就高二了啊啊啊啊啊。CF1552HGuessthePerimeter以为只有\(4\)次询问次数会有什么逆天不平凡做法，结果还是二分，不过还是比较牛。将原本一个格点看做一个

首先根据\(\operatorname{xor}\)，就想到拆成二进制的\(a_{i,w},b_{i,w}\)来处理。类似竖式加法，考虑把得到的结果\(c_{w}\)分为\(a_{i,w}+b_{j,w}+x\)，其中\(x\)就是上一位的进位。进一步的，发现对于总的\(c_{w}\)，\(a_{i,w},b_{j,w}\)肯定都在这个位置加了\(

先说线段数做法发现一个区间连续有一个性质：这个区间\([l,r]\)存在相邻两个数的对数是\(r-l\)考虑离线下来，线段数维护每个区间存在相邻数的对数，当前是\(i\)，每次扫描新的一个\(a[i]\)进来，因为我扫描线是钦定了以\(i\)位右端点，所以若\(a[i]-1\)的位置在\(a[i]\)前面，我就将\([1,a[i]

首先考虑这个\(S,T\)肯定需要固定一个算另一个的方案数。如果固定\(S\)，会发现非常不好给\(T\)下限制。于是考虑固定\(T\)，对\(S\)计数。首先考虑如果\(T\)只有\(2\)个点\(x,y\)，该怎么对\(S\)计数。考虑到这个简单路径的定义是不经过重点，考虑找到点双。然后能

考虑找一下走掉的条件:若\(x\)第\(1\)天走掉，那么就说明\(x\)没有知道任何咒语。若\(x\)第\(2\)天走掉，那么就说明应该存在一个\(y\)，按照\(x\)已知的信息，\(y\)应该没有掌握咒语，但是\(y\)第一天没走。若\(x\)第\(3\)天走掉，那么就说明应该存在一个\((y,z)\)

连接：https://codeforces.com/problemset/problem/1976/C题目：思路：我们可以想象这个是两个队列，采用两个前缀和数组：suma和sumb记录前几个完全按照大小分配成程序员/测试员的个数（指不考虑每个种类人数限制的情况），然后二分查找到最小满足的种类。这里采用ra和rb表示，然后哪个更小取哪

CF1987E题解题意给定一棵大小为\(n\)的有根树，各点各有一点权\(a_i\)。每次操作可以选定一节点使其点权加一，求最小的操作数，使得任一节点满足其点权不大于其所有儿子的点权之和。\(n\le5000,0\lea_i\le10^9\)题解麻了，赛后十五分钟调出来，可惜为时已晚。读懂题之后

牛逼贪心题假设都是将总和正的变成负的，所以如果总和是负的，val取相反数对于二进制操作，我们一位一位考虑，想让其二进制下1的个数最好变成奇数，只能选一个数保留哪些1，所以我们保留一个1就能乘上-1，改变了奇偶性。贪心满足无后效性，最优子结构，局部最优解为全局最优解，我们尝试将一个数二

1187：统计字符数时间限制:1000ms内存限制:65536KB提交数:31962通过数:18310【题目描述】给定一个由a-z这26个字符组成的字符串，统计其中哪个字符出现的次数最多。【输入】输入包含一行，一个字符串，长度不超过1000。【输出】输出一行，包括出现次数最多的字符

题目信息题目链接LuoguCF1907G思路分析如果我们把每一个关系都转化为一条无向边，则\(n\)个点会有\(n\)条边，并且每一个点的度数至少是\(1\)，所以是一颗基环树森林。我们分别看看每一个数。一棵树一定会有一个环，首先环外树的决策方案是一定的，一定是将每一个权值为\(1\)的

题目描述给你一棵\(n\)个节点的树，每个节点有一种颜色，有\(m\)次查询操作。查询操作给定参数\(l\r\x\)，需输出：将树中编号在\([l,r]\)内的所有节点保留，\(x\)所在连通块中颜色种类数。每次查询操作独立。对于\(100\%\)的数据，所有出现过的数在\([1,10^5]\)之间，保证每

题意：有\(n\)个行星，编号为\(0\simn-1\)。有\(m\)辆星际列车，第\(i\)辆列车在时刻\(a_i\)从行星\(x_i\)出发，在时刻\(b_i\)到达行星\(y_i\)，代价为\(c_i\)。换乘条件为上一辆车的终点和下一辆车的起点相同，且上一辆车到达时刻\(\le\)下一辆车出发时刻。你需要吃

LIS问题LIS，即最长上升子序列。1.朴素的求法使用动态规划，\(dp_i\)代表以第\(i\)位结尾的最长上升子序列长度。得动态转移方程：\[dp_i=\max_{j<i\text{且}a_i>a_j}dp_j+1\]Code1#include<iostream>usingnamespacestd;#defineMAXN100005inta[MAXN],f

LCS问题LCS，即最长公共子序列。1.朴素的求法使用动态规划，\(dp_{i,j}\)代表以序列\(a\)第\(i\)个字母结尾，序列\(b\)第\(j\)个字母结尾的LCS长度。得动态转移方程：\[dp_{i,j}=\left\{\begin{matrix}\max(dp_{i-1,j},dp_{i,j-1})&a_i\neb_j\\dp_{i-1,j-1}

前缀和前缀和是什么可以说，前缀和是一种优化程序运行时间的一种方法，一般用于求一个序列中的区间和。前缀和的原理顾名思义，前缀和数组，即一个序列中前\(i\)个数据之和。\[b_i=\sum_{j=0}^{i}a_j\]所以\(a_l\)到\(a_r\)的和是：\[\sum_{j=l}^{r}a_j=b_r-b_{l-

重温Tarjan,网上看了许多博客感觉都讲的不清楚.故传上来自己的笔记,希望帮到大家.提到的一些概念可以参考oiwiki,代码也是oiwiki的,因为我不认为我能写出比大佬更好的代码了.强连通分量:有向图的最大强连通子图(有向图中任意两点可达)Tarjan对每个结点维护

 目录 A:子串个数B.模式串C.主对角线上的数据和D.顺时针排螺旋阵E:汉诺塔游戏中的移动F.树的先根遍历G.树的后根遍历A:子串个数本题未考虑重复的情况，直接使用公式既可考虑重复的情况：不同子串个数-洛谷#include<bits/stdc++.h>usingnamespacestd;i

题意公司要升级一个产品的K种属性，每种的初始值为0。有N种升级计划，第i种花费c[i]的代价给编号为j=1,2,...,K的属性分别增加a[i][j]，求把所有属性提升到大于等于P的最小代价题解显然多维费用背包，定义dp[t][i][j][k][s][r]为前t个物品，让这几种属性为i,j,k,s,r的时候的最小费用。在

CF1515GPhoenixandOdometers首先进行缩点，对于一个点，与它不在同一连通分量的点无法形成回路，所以对每个连通分量分别计算。假设一个点\(u\)，有两个长度为\(a\)和\(b\)的环，那么就相当于找两个非负整数\(x\)和\(y\)，使得\(ax+by=w\)，其中\(w\)为题中的路径长，根据裴蜀定理

题意在坐标轴上给定N个点，坐标依次为x1,x2,...,xn,你需要从原点前往xn并且实现往返，其中从第一个点到第N-1个点上有加油站，其中第i个加油站可以花费p[i]购买f[i]升汽油，汽油的上限为H升，每行驶一单位距离需要花费一升汽油。在全部过程中每个加油站最多使用一次，判断是否可以完成行程并

题意：给定一颗树，构造一个排列\(p\)使得对于每一对\((x,y),dis(x,y)=3\)，有\(3\midp_x+p_y\)或\(3\midp_x\timesp_y\)。首先我们先将所有\(p_i\)都模上\(3\)。条件等价于每一对距离为\(3\)的\((x,y)\)，\(p_x\)和\(p_y\)不同时为\(1\)或\(2\)。那先考虑如

P3267JLOI2016/SHOI2016侦察守卫互相赋值的双dp思路设\(f[u][i]\)表示包括\(u\)子树内所有关键点都被覆盖（包括\(u\)），且至少还可以向\(u\)的父亲方向覆盖\(i\)层的最小代价。设\(g[u][i]\)表示向下距离大于等于\(i\)的点全部被覆盖，剩下距离小于\(i\)的点随意