NC50439 题意 有n个士兵，每个士兵战斗力为v[i]，添加这个士兵则上场的总士兵数量要小于s[i]，求最高战斗力？ n(1≤n≤10^5) v,s(1≤v≤10^9,1≤s≤n) 思路 贪心+优先队列或multiset 一开始想到01背包变形，如果按照这个思路去解，会发现随着s[i]的变化（即背包的容量变化）。 如果有会dp解的大佬麻烦发我一下代码，我学一下。 这道题如果人数k是已知的，直接贪心取s[i]>=k中的最大的k个人的战斗力即可。 问题在于k是不确定的，那我们考虑优化，枚举k(从s[i]中枚举，并非连续）。 现在考虑从大到小枚举还是从小到大枚举方便。 我们从大到小枚举，优...

NC13230 题意 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。 需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可。 T(T ≤ 50) A,B(|A|,|B| ≤ 50) 思路 数据范围感觉区间DP 区间DP切忌枚举的是区间的长度，而不能直接枚...

C. Game with Chips 题意 给你一个n,m的棋盘，再给你k个棋子的坐标，让你移动经过接下来对应的k个位置。 可以所有棋子到一个格子。 当移动到边界的时候再往边界走则原地不动。 求所有棋子走的路线能够满足题意的，步数不超过2nm次。 LRUD对应移动的方向，输出构造的路径。 思路 构造题 当时打的时候一直在想如何构造最优路径，是BFS呢还是啥。 现在想想当时真的蠢，打一个EDU第C题没那么麻烦。 其实这道题的关键在于读题，步数不超过2nm，仔细想想所有格子移动到某个角落然后再S形遍历全图，这样的步数也不可能超过2nm。 读题很重要，注意一下数据的范围，有利于构造合理的算法。 #i...

NC15553 题意 给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？ 思路 前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。 扫一遍要选的第一个区间，扫的过程如果左右还有可以选的区间，则取他们的最大值和选的区间相加，记录最大值即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int>P; const double e...

C 操作集锦 题意 由小写英文字母组成的长度为n的一个字符串，求不相同的长度为k的子串的数量对1e9+7取模。      1   ≤   n   ≤   1   e   3   0   ≤   k   ≤   n    1≤n≤1e3 \quad 0 \leq k \leq n   1≤n≤1e30≤k≤n 思路      D   P    DP   DP 正难则反 正难则反，我们求所有不同的子串，不如把所有子串的数量求出来再减掉所以相同的子串数量。 若不去重求所有长度为k的子串的数量，则可由     f   [   i   ]   [   j   ]   =   f   [   i   − ...

ABC160 D - Line++ 题意 输入N,X,Y。     i   (   1   ≤   N   ≤   2   e   3   )    i(1\leq N \leq 2e3)   i(1≤N≤2e3) 给你一个由N个结点组成的图，连接 第     i    i   i 和第      i   +   1    i+1   i+1个点，一共构成了N-1条边。 连接X，Y，输出两节点间最短距离长度为      i   (   1   ≤   i   ≤   N   −   1   )    i(1\leq i \leq N-1)   i(1≤i≤N−1) 的边一共有多少条。 思路 再...

D. Carousel 题意 给你一个长度为     n   (   n   >   3   )    n(n>3)   n(n>3)的数组，首尾相连形成一个环。对每个位置进行涂色，要求相邻但不相同数字的填涂颜色不同，相邻且相同的位置颜色可以相同也可以不相同。要求所用颜色的最大数字最小，颜色由数字来表示。 思路 分类讨论 构造  全部为同一种颜色，则全为1即可。 至少有一个位置与其相邻的数字相同，则我们可以从这个相同的位置剖开这个环，形成一条线，再从头到尾1,2交替的填入即可。 n为偶数，交替填入1,2即可，首尾必不相同。 全部不相同且为奇数，第一个填入3，后面交替填入1,2...

NC50528 题意 给你一个长度为n的数组，依次求长度为k的区间中的最小值，最大值为多少。 思路 单调队列（双端队列） 时间复杂度     O   (   N   )    O(N)   O(N) 单调队列性质：   队列中的元素其对应在原来的列表中的顺序必须是单调递增的。  队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)  求最小值的做法：维护一个单调队列，头部元素的下标为     s    s   s，尾部元素的后一位下标为     t    t   t，其中的值为      x   i     x_i   xi​（存     a    a   a数组中的下标）使得    ...

NC82B 题意 给你一个长为n的序列a和一个常数k 有m次询问，每次查询一个区间     [   l   ,   r   ]    [l,r]   [l,r]内所有数最少分成多少个连续段，使得每段的和都 <= k 如果这一次查询无解，输出"     C   h   t   h   o   l   l   y    Chtholly   Chtholly"      1   <   =   n   ,   m   <   =   1   e   6   ,   1   <   =    a   i    ,   k   <   =   1   ...

NC22598 题意 （题目数据范围M=N-1可知这是一棵树，一个边数为结点数-1的连通图一定为一棵树） 给你一颗N个结点的树和对应边的权值，求以S结点为根节点去掉一些边使得不与叶子结点直接相连的最小代价为多少？ 思路      树   形   D   P    树形DP   树形DP      f   [   i   ]   =   ∑   m   i   n   (   f   [   s   o   n   ]   ,   c   o   s    t    i   →   s   o   n     )    f[i]=\sum min(f[son],cost_{i→son})   f...

NC23053 题意 给你一个字符串s，给你T组数据，每组数据输入一个字符串t，对该字符串判断是否为s的子串，若为子串则输出"YES"否则输出"NO"。      1   ≤   s   ≤   1   e   6   1   ≤   T   ≤   1   e   6   1   ≤   ∑   ∣   t   ∣   ≤   1   e   6    1\leq s \leq 1e6 \quad 1\leq T \leq 1e6 \quad 1\leq \sum |t| \leq 1e6   1≤s≤1e61≤T≤1e61≤∑∣t∣≤1e6 思路 预...

CF1331F Elementary! 题意 给你字符串     s   (   1   ≤   s   ≤   10   )    s(1\leq s \leq 10)   s(1≤s≤10)，判断是否为元素周期表里的大写元素。 思路 由Elementary 结合题目中样例HOMELES DOCTOR WASTON先把题意得出。 然后再打一张化学元素的表。（dbqwsdd） 这篇博客主要是让自己知道这样的匹配有两种做法，一个是DP，一个是DFS。  初始化     f   [   0   ]   =   t   r   u   e    f[0]=true   f[0]=true DP递推式...

NC13886 题意 给你一颗n(偶数）结点的树，将其分为n/2对，求所有对数相连的路径之和最小为多少？ 思路 DFS 数据结构 既然是图论那就先画图吧 左图由于以2号结点为根节点的子树结点数(包括其自身)为3（奇数），那么显然这棵树上一定有个节点要从树外找一个节点相连，那么必须要经过2号结点与其父节点的这条路(2->1)。 右图告诉我们如果能偶数配对的子树则不需要相连。 叶子节点为子树的结点数一定为1显然一定会加上。 DFS求子树的结点数，若结点数为奇数则需要该节点与其父节点相连的这一条边，若为偶数则不需要。 注意：多组数据要每次清空vector数组，然后置于cnt数组不需要memse...

CF1332 D. Walk on Matrix 题意  给你一个     k   (   0   ≤   k   ≤   105   )    k (0≤k≤105)   k(0≤k≤105) 要求你构造一个     n   ×   m    n \times m   n×m的矩阵满足下列条件       1   ≤   n   ,   m   ≤   500    1≤n,m≤500   1≤n,m≤500      0   ≤    a    i   ,   j     ≤   3   ⋅   1    0   5     0≤a_{i,j}≤3⋅10^5   0≤ai,j​≤3⋅105...