expect2004

分类

Codeforces Round(2) Contests(11) review(2) 其他(1) 动态规划(19) 动态规划 - 区间DP(3) 动态规划 - 期望与概率DP(1) 动态规划 - 树形DP(4) 动态规划 - 状压DP(1) 动态规划 - 线性DP(1) 动态规划 - 背包(2) 图论 - Tarjan(4) 图论 - 二分图判定(2) 图论 - 拓扑排序(1) 图论 - 最短路(1) 图论 - 生成树(3) 字符串 - AC自动机(2) 字符串 - KMP(2) 字符串 - 后缀数组（SA）(3) 字符串 - 字典树（Trie）(1) 数学 - 其他(2) 数学 - 多项式(3) 数学 - 组合计数(1) 数学 - 莫比乌斯反演(2) 数学 - 高斯消元(2) 数据结构 - 分块(1) 数据结构 - 平衡树(1) 数据结构 - 树状数组(1) 数据结构 - 树链剖分(2) 数据结构 - 珂朵莉树(2) 数据结构 - 线段树(6) 数据结构 - 虚树(1) 未归档(6) 模板(5) 游记(3) 算法 - 2-SAT(2) 算法 - CDQ分治(1) 算法 - 搜索(2) 算法 - 树分治(2) 算法 - 矩阵树定理(1) 网络流(7) 网络流 - 二分图相关(1) 网络流 - 最大流(1) 网络流 - 最小割(6) 题解(22)

/ 注册

全部文章（共149篇）

LG2598/BZOJ1412 「ZJOI2009」狼和羊的故事最小割

问题描述 LG2598 BZOJ1412 题解看到要把狼和羊两个物种分开自然想到最小割。发现\((x,y)\)可以向上下左右走以获得贡献，所以建边：\((x,y),(x-1,y)\),\((x,y),(x,y-1)\),\((x,y),(x,y+1)\),\((x,y),(x+...

2019-09-13

0 421

LG2766 最长不下降子序列问题最大流网络流24题

问题描述 LG2766 题解 \(\mathrm{Subtask 1}\) 一个求最长不下降子序列的问题，发现\(n \le 500\)，直接\(O(n^2)\)暴力DP即可。 \(\mathrm{Subtask 2}\) 设\(opt_i\)代表区间\([1,i]\)，且以\(i\...

2019-09-13

0 498

LG1983 「NOIP2013」车站分级拓扑排序

问题描述 LG1983 题解考虑建立有向边\((a,b)\)，代表\(a\)比\(b\)低级。于是枚举每一辆车次经过的车站\(x \in [l,r]\)，如果不是车辆停靠的车站，则从\(x\)向每个停靠了的车站连边。拓扑排序，建立分层图，搞出最大的层数即可。 \(\math...

2019-09-13

0 776

LG4171/BZOJ1823 「JSOI2010」满汉全席 2-SAT

问题描述 LG4171 BZOJ1823 题解显然，每个评委对每个材料的满式/汉式要求是对\(n\)个元素的\(0,1\)取值限制。显然想到\(\mathrm{2-SAT}\) 于是就可以切掉了。 \(\mathrm{Code}\) #include<bits/st...

2019-09-13

0 412

LG4782 「模板」2-SAT问题 2-SAT

问题描述 LG4782 题解对于一个限制条件，建边如下：如果\(x,-x\)在同一个强联通分量里，则不行，否则可以构造方案：输出\(bel_i<bel_{i+n}\) \(\mathrm{Code}\) #include<bits/stdc++.h>...

2019-09-12

0 437

CF1076D Edge Deletion 最短路树

问题描述 Codeforces 洛谷（有翻译）题解最短路树，是一棵在最短路过程中构建的树。在\(\mathrm{Dijkstra}\)过程中，如果最终点\(y\)是由点\(x\)转移得到的，则在最短路树上\(x\)是\(y\)的父节点，\(x\)到\(y\)的最短路树上长度等于原...

2019-09-11

0 405

LG1155 「NOIP2008」双栈排序二分图判定

问题描述 LG1155 题解 \(i,j\)如果不能进入一个栈，要满足存在\(k\)，使得\(i<j<k\)且\(a_k<a_i<a_j\) 如果\(i,j\)不能进入一个栈，在\(i,j\)之间连边。判定这个图是不是二分图。如果是二分图，则可以，否则不行...

2019-09-10

0 464

LG4819/BZOJ2438 「中山市选2011」杀人游戏 Tarjan缩点+概率

问题描述 LG4819 BZOJ2438 题解发现如果有一些人之间认识关系形成环，只需要问一个人就能把控整个环。 \(\mathrm{Tarjan}\)缩点。缩点之后所有入度为\(0\)的点，必须询问。注意特判有没有孤身一人的。 \(\mathrm{Code}\) #...

2019-09-10

0 507

LG2272/BZOJ1093 「ZJOI2007」最大半连通子图 Tarjan缩点+DAG求最长链

问题描述 LG2272 BZOJ1093 题解观察半联通的定义，发现图中的一些结点，构成的链一定是一个半联通子图。此时存在的环可能会干扰求解，于是\(\mathrm{Tarjan}\)缩点。于是求最长链，过程中计数即可。 \(\mathrm{Code}\) #inclu...

2019-09-09

0 573

LG2463/BZOJ4698 「SDOI2008」Sandy的卡片后缀数组

问题描述 LG2463 BZOJ4698 题解看到\(n\)个数串，一开始不太好处理，可以很容易想到把这\(n\)个数串连到一起，形成一个大串，但是每个串之间不容易处理。经过思考，想到在每个串中间加一个不可能出现在原数串中的数，取\(2333\)。对大串做后缀数组，求\(\ma...

2019-09-08

0 435