BlabaDouble's Blog

1.Majority 好题啊。 首先发现操作比较复杂，但是有递归性，我们可以只研究最后一次操作。 然后令 fif_ifi​ 表示长度为 iii 的合法串的方案数，转移的时候枚举两段和中间，前缀和优化一下。 然后发现会算重，因为 101011010110101 这样的串，最后一步可以是 111011110111101 或者 101111011110111 变化而来。 我们想要去重，就可以让操作唯一。 操作唯一可以在从左往右扫的时候，能合并就合并。 这样的话，dpdpdp 其实不太好设计状态，在一个合并过程中的串是比较复杂的。 总之我们想多记录一维，因为还是考虑最后一次合并，最后一次合并形如 111000000111111000000111111000000111 合并成全是 111。 因此考虑记录一维，代表前缀 111 的个数，并且能遵循能合并就合并。 具体来说 dpi,jdp_{i,j}dpi,j​ 表示长度为 iii，合并后前缀 111 的个数是 jjj 的方案数。 然后考虑转移。 dpi,jdp_{i,j}dpi,j​ 从 i−1i-1i−1 或者 j−1j-1j−1 转移过来都 ...

7f83a7f3b2fd436072e0afa92b37bd64402c6f9bd815d81ec941538d01be63af650c571e662f7ebf96de9c651f6d837cacfd9a3311fb933e6a0b0324815ff49329a449693dfe017d36202492410fcbcb32129b857dfde279673e7e38015b81c9380c790add55af8c423817542a73071080734f07a0098f4f8a8436e234b7ab971de9c2bb48667de0fd40b0669abd5ffb81a46367013d2d64dca3318949815c71428661900143f378ff3302b3773d7d38ff593a5847e6369d28c3be1edf102ab7a4d1552df3735eecff74209be1f2b363e206947aea4fc9d3c7e380235f6be416844ff4c0fddccb7789ca22bdf668598fad4e442175b2f9886 ...

58979c36671e84846473c93fcbc42571489b4ff9f7a04a5e26fd75da654172dbbe8f1079dcf7b4e599fdb8c5d01cc914cf4f824b2496ba58721ddd24801235bc9e68d4e10ef9c98d6536e1cceb4160201681e601eddacfe6b49d7f6a1cfa21f193caa96f7b755647fd64219597f07c1138039f4bb1aff058a35d4da6515abdecb8dc163404641840c915f6994d12b05ff0ac39f03de77afec0a3b588a693ff780ca08f7291d80200e26765ce3b51020799d242b3ca27ccb3bacdde6d4f96a980c87fc00ed57e5500f4a9d749b909cf86f9681922d3aec547ba5ee433af24419a330460ee63f1fd299c8dc85608261bd3ede4bc2427b2a877f ...

a4fa0460f971bf1b68e73fb090360d6a2eb80f9c82da0c7cbe681eaddb08daf6d889ebb08c0c83287fc924c92e360ccc20aea427fd24e9cf6f58bc0bb9795d4c00a6a97338c753aa6f1d360e24532dea70eb4c86e1beca8c29f4e7c58be7c48ff0879d37be2e315e741aaf327ea9543dc32a18e322a083797f26ee7a071e58f5b2506f558440e6263347a82adea4d3052bd4f49939f5f0b77965fa57150fc358fd70ee4b291e3db8a9afcfd7170f705f2622bd21cc1740db82dc4639efe0639671c5b2925c188f37b90ceb084077a7177af553970d1867218b84465672a2ccab729894d828f55e2c68279d31dd7d859c50d8e7ee6c6d9e7ae ...

卷首语 非淡泊无以明志，非宁静无以致远。——诸葛亮《诫子书》 前言 致远DP是用来解决一类特定的动态规划问题的方式，其核心思想是在维护最小值信息时利用好题目的特殊性，让下标参与到最小值信息的维护中。 其最早被OI选手葛致远提出。 而且结合了贪心的思路设计dp，诠释了非宁静无以致远的重要内涵和深刻思想。 引入 在正式介绍致远DP之前，让我们先来看一道例题。 题意 有长度为 nnn 的序列 aaa，判断 aaa 是否可以拆成两个上升子序列。 每个 aia_iai​ 都得属于其中一个上升子序列。 n≤106n\leq10^6n≤106 做法 考虑从前往后扫碰到 aia_iai​ 的时候，aia_iai​ 一定会成为一个上升子序列的最后元素，因此，我们只需要让另一个上升子序列最后的元素最小，即可满足最优性。 设计dp。 dp(i)dp(i)dp(i) 表示前 iii 个数拆成两个上升子序列，aia_iai​ 不在的那个的末尾最小是多少。 转移的时候从 dp(i−1)dp(i-1)dp(i−1) 得来。 如果 aia_iai​ 两个都能接上，接在大的后面。 只能接一个，就接在它后面。 ...

arc138e Decreasing Subsequence 题意 定义一个长度为 nnn 的序列 aaa 为好序列，当且仅当满足以下两个条件。 0≤ai≤i(1≤i≤n)0\leq a_i\leq i(1\leq i\leq n)0≤ai​≤i(1≤i≤n) 对于每个 v∈[1,n]v\in[1,n]v∈[1,n]，序列 aaa 中最多只有一次 vvv 的出现。 对于每个好序列，统计长度为 kkk 的严格递减子序列的数量并求和，且子序列中不能出现 000。 n,k≤5000n,k\leq5000n,k≤5000 做法 我们先来转化一下好序列的形式。考虑如下这个转换。 在 iii 时获得一个写着 iii 的球，然后从你拥有的球中选择一个放在 aia_iai​ 或者不选。 考虑一组严格递减子序列的下标 i1,i2,...,iki_1,i_2,...,i_ki1​,i2​,...,ik​。 容易发现，所有的 aija_{i_j}aij​​ 都小于等于 i1i_1i1​。 这个好序列也可以理解为，把 i1i_1i1​ 前面的 kkk 个球留下来放到 i1i_1i1​ 后面的 ...

不能懒了。 记录一点做过的abc中的h。 abc219h 好久以前做的，记不清了，套路大概是多开一维记录还没跑到的地方。 不如贴个三维写的题解吧！ here upd：震惊了，以前竟然在学校在本子上写过这题题解。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<bits/stdc++.h>#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)#define rep(i,n)for(int i=0,_n=n;i<n;i++)#define ll long long#define pii pair<int,int>#define m_p make_pair#define pb push_back#define fi firs ...

网络流学习笔记 本文不会介绍网络流的基本概念和模板怎么写，因为我学了之后就再也没有想过是为什么，都背的板子。 大概就讲一些例题，和经常会用到的模型，建模方式。 后面可能还会涉及一些 Hall定理，拉格朗日对偶，线性规划等更厉害的事情。 Part1：模型 最大权闭合图 挖坑。 最大密度子图 挖坑。 二分图最大点独立集，最小点/边覆盖集 挖坑。 Part2：例题 挖坑。大概会填wll24题，毕竟这个系列很经典。然后再补一些lin题。 Part3：高端技巧 Hall定理

背包神奇小 trick 学习笔记 碎碎念 先占个坑，明天写。 本文基本都是复读某个 CF博客（可能会附带例题） CF博客链接：here Part1：背包的基本问题定义 01-背包 有 nnn 个物品，第 iii 个重量是 wiw_iwi​，价值是 viv_ivi​，找到一个集合 SSS，使得 ∑i∈Swi≤C\sum\limits_{i\in S}w_i\leq Ci∈S∑​wi​≤C，并且使得 ∑i∈Svi\sum\limits_{i\in S}v_ii∈S∑​vi​ 最大化。 多重背包 有 nnn 个物品，第 iii 种有 aia_iai​ 个，重量是 wiw_iwi​，价值是 viv_ivi​，找到一组序列 ttt，使得∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n] 有 ti≤ait_i\leq a_iti​≤ai​， ∑i∈Switi≤C\sum\limits_{i\in S}w_it_i\leq Ci∈S∑​wi​ti​≤C， ∑i∈Sviti\sum\limits_{i\in S}v_it_ii∈S∑​vi​ti​ 最大化。 子集和 有 nn ...