noip杂题选讲\(A\)CF1290CPrefixEnlightenment\(B\)CF1458DFlipandReverse\(C\)CF1389FBicoloredSegments\(D\)CF1580DSubsequence\(E\)CF1720D2Xor-Subsequence(hardversion)\(F\)CF1775ETheHumanEquation\(G\)CF1763CAnotherArray

“最大权值闭合图，即给定一张有向图，每个点都有一个权值（可以为正或负或0），你需要选择一个权值和最大的子图，使得子图中每个点的后继都在子图中。”这样的定义可以让你理解算法执行的逻辑，却难以在你赛场上遇到它时牵动你的思绪更符合你做题时真切感受的描述应该是：给你一些点，消耗一些

Description给定一个整数序列\(\left(X_1,\ldots,X_M\right)\)，其长度为\(M\)，元素取值为\(1,\ldots,K\)。要求找出长度为\(N\)的序列\((A_1,\ldots,A_N)\)的数量，元素取值为\(1,\ldots,K\)，并满足以下条件，结果取模\(998244353\)：在所有长度为\(M\)的序列中，唯

根据数据范围，不难想到DP状态应该是\(n^4\)级别的。先考虑当没有反转区间的操作时如何转移。设\(dp_{l,r,L,R}\)表示当前区间为\(l\simr\)，值域\(\in[L,R]\)时的答案。转移时枚举四个维度，可以从\(dp_{l,r,L,R-1},dp_{l,r,L+1,R},dp_{l+1,r,L,R},dp_{l,r-1,L,R}\)转移

SubsequenceandPrefixSum\(n\)才\(100\)，\(a_i\)才\(20\)，显然DP。设\(f_{i,j}\)表示第\(i\)个数，前\(i\)个数前缀和为\(j\)的方案数。显然，\(f_{0,0}=1\)。留意到如果\(j=0\)，那么加入和不加入第\(i\)个数，最终的答案序列是一样的，因此此时加入第\(i\)个数对答

Description给定一个长度为\(n\)的有\(k\)个空缺的序列。你有\(m\)个数可以用于填补空缺。要求最大化最长上升子序列的长度。\(n,m\le10^5\)，\(k\le10^3\)。Solution容易发现只需要先构造出LIS上的位置的值，对于其余未填位置随便填，所以构造LIS时就不需要考虑出

虽然比赛没打，但是想来水估值发表思路。题意给你一个\(1\simn\)的排列，让你从中找一段长为\(k\)的子序列，使得这个子序列中的元素排序后数值连续。分析题意转换一下，先用结构体存储每个元素的编号和数值，按照数值排序。于是这道题就成了：一个序列，让你求所有长\(k\)的子段中

CodeForces843AA.SortingbySubsequencestimelimitpertest:1secondmemorylimitpertest:256megabytesinputstandardinputoutputstandardoutputYouaregivenasequence\(a_1, a_2, ..., a_n\)consistingofdifferentintegers.Itisrequiredtos

原题链接题解1.如果没有不能表示出\(k\)的限制，那么数组由一众二次方构成2.对于小于\(k\)的数，考虑\(k\)的最高位\(i\)由于\([0,i-1]\)最多为\(2^i-1\)所以可以考虑添加一个\(k-2^i\)来表示完\([1,k-1]\)内所有的数（尽管有重复）同时删掉\(2^i\)3.对于大于\(k\)

ProblemGiventwostringstext1andtext2,returnthelengthoftheirlongestcommonsubsequence.Ifthereisnocommonsubsequence,return0.Asubsequenceofastringisanewstringgeneratedfromtheoriginalstringwithsomecharacters(canbenone

算法合集这里是我的算法合集：博弈论Gametheory图论Graphtheory数论Numbertheory三角函数Trigonometricfunction字符串Strings计算几何Computationgeometry数据结构Structs动态规划DynamicprogrammingLIS问题LongestIncreasingSubsequenceproble

算法合集这里是我的算法合集：博弈论Gametheory图论Graphtheory数论Numbertheory三角函数Trigonometricfunction字符串Strings计算几何Computationgeometry数据结构Structs动态规划DynamicprogrammingLIS问题LongestIncreasingSubsequenceproble

题目链接：来自罗勇军《算法竞赛》书中的习题。题意：给长度为\(N\)的数组和一个整数\(S\)，求总和不小于\(S\)的连续子序列的最小长度。方法一：尺取法主要思想为：当\(a_1,a_2,a_3\)满足和\(\geqslantS\),得到一个区间长度\(3\),那么去掉开头\(a_1\)，剩下\(a_2,a_3\)

题意：给定\(n(n\le10^6)\)和\(k(k\len)\)。构造一个长度小于等于\(25\)的序列\(a\)满足：1.不存在一个子序列的和为\(k\)。2.对于\(1\lei\len,i\nek\)，存在一个子序列的和为\(i\)。看到长度为\(25\)，首先肯定会想到二进制。那么我们先构造出一个序列\([2^

SOSDP学习笔记Linkhere:代码：importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.math.BigInteger;importjava.util.*;publicclassMain{staticintn;staticlongm;staticlong[]a;

F-SubsequenceLCMProblemStatementYouaregivenasequenceofpositiveintegers$A=(A_1,A_2,\dots,A_N)$oflength$N$andapositiveinteger$M$.Findthenumber,modulo$998244353$,ofnon-emptyandnotnecessarilycontiguoussubsequencesof$A$suc

题面。2023.5.18修正关于前缀和数组的说法，与代码适配的思路。题意给定长度为\(n\)一个序列\(a\)以及\(q\)次询问，每次询问给出\(l\)和\(r\)，要求找出序列\(a\)在\([l,r]\)内最长的几乎递增子序列。对于几乎递增的定义：如果一个序列中不存在连续的三个数\(x\)，\(y\)

原题链接题解明确每个变量的意义code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lla[200005];intmain(){llt;cin>>t;while(t--){map<ll,ll>b;//b[x]代表数组b中x的使用情况，大于0代表还有剩余，等于0代表刚好借满

题目给定一个大小为\(n\)的序列，要求支持单点修改和查询区间内至多\(k\)个不交子区间之和的最大值（可以不取）分析考虑源点向每个点、每个点向汇点流流量1费用0的边，每个点向右边的点流流量1费用\(a_i\)的边，流量最大为\(k\)，这样构建出一个费用流的模型。很显然，退流相当于给区

求最长递增子序列是深度优先搜索(DFS)的一种应用，有两种比较好的方法可以解决。第一种是动态规划法，时间复杂度为O(n*n)，即设置边界条件和更新迭代公式求解最优解。第二种使用二分查找将时间复杂度降为O(nlogn)。本文给出两种方法的实现代码及说明。示例：图1最长递增子序列输入

First,let'sreviewsomedefinitions.Feelfreetoskipthispartifyouarefamiliarwiththem.Asequence aaaisanincreasing(decreasing)subsequenceofasequence bbbif aaacanbeobtainedfrom bbbbydeletionofseveral(possibly,zeroorall)

首先，我们对这个幸运数进行分析，发现：\(10^9\)以内只有\(1023\)个幸运数，即\(\sum\limits_{i=0}^92^i\)个。考虑对幸运数和非幸运数分类讨论。幸运数部分：01背包裸题，\(dp_{i,j}\)表示前\(i\)个幸运数里选了\(j\)个，转移方程为\(dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\tim

分析线段树模板题。一眼DP。定义状态函数\(\mathit{f}_i\)表示前\(i\)个数中，必选\(\mathit{A}_i\)时\(B\)的最大长度。则有转移方程：\(\mathit{f}_i=\max\{f_j|((1\lej\lei-1)\land(-k\leA_i-A_j\lek))\}+1\)。答案就是\(\max\limits_{i=1}^{n}\mathit{f}_i

DividingSubsequence这道题与最长公共子序列类似，可以先去水一水那道题。题意本题就是让你从\(p\)里面选出一个子序列\(b_i\)和\(q\)里面选出一个子序列\(a_i\)，我们要使\(b_i\)是\(a_i\)的倍数。解法本题直接用动态规划，是\(O(n^2)\)做法，会超时，因此我们用树状数

B-ArithmeticProgressionSubsequenceProblemStatementYouaregivenasequence$A$oflength$N$consistingofintegersbetween$1$and$\textbf{10}$,inclusive.Apairofintegers$(l,r)$satisfying$1\leql\leqr\leqN$iscalledagoodpairif