子谦。

分类

入门教程(10) 未归档(52)

/ 注册

全部文章（共61篇）

数位DP入门详解+题目推荐

\(update:2019-9-6\) 博客里某些东西没有解释清楚，完善了对应的解释在开始之前，我们先来看一道题——题目链接题目要求，相邻两位的差大于等于2，那么我们先来构造一个试一试。比如说\(15246\)这个数，我们先取第一位为\(1\)，然后第二位是\(5...

入门教程数位DP 数据结构

2019-09-03

0 449

P3525 INS-Inspection

这道题的题面有点问题，如果按照题面做，应该是A不了的，下面引用一下评论里@REM_001的翻译一棵n个节点的树，行动中心S从1->N。从S出发前往任意一个未标记到的点(沿树上两点的唯一路径走)，标记该节点，然后返回S。相邻两次行动所经过的道路不允许有重复，最后一次标记后不需要返回，求...

2019-08-28

0 352

最小生成树

何为最小生成树？最小生成树就是对于一个连通图，保留若干条边，使图依然联通，且边权和最小。因为\(n\)个点的连通图（以下自动默认为连通图，），最少要有\(n-1\)条边。所以对于一个图的最小生成树，也一定只有\(n-1\)条边。反证一下（此证明仅限于非负边权）：如果这个图的最小生成树...

图论最小生成树入门教程

2019-08-16

0 307

负环详解

什么是负环？顾名思义，就是一个所有边的边权和为负数的环出现负环会怎么样？我们知道，一般情况下，图上的最短路都是确定的。但是一旦图上有一个负环，\(s\)到\(t\)的最短路就会不远千里的去覆盖上这个环（只要能够到达），并且不厌其烦的走上一遍又一遍。由于负环的边权和是负的，并且...

入门教程图论负环

2019-08-16

0 390

AFO?

\(update:2019-8-16\) AFO的我又回来了， \(NOIP2019\) 冲鸭！！！

2019-04-09

0 353

P2053 [SCOI2007]修车

题目链接这是一道很不错的费用流好题，建图的思想很是巧妙我们把每个工人拆成\(n\)个点，表示当前工人在\(n\)个不同的时间段，那么\(m\)个工人就是\(n*m\)个点，然后把这些点向汇点连一条费用为0边权为1的边，也就是同一时段一个工人只能维修一辆车。对于每辆车，我们先从汇点连出一条费用...

2019-03-31

0 364

P3254 圆桌问题

题目链接非常简单的一道网络流题我们发现每个单位的人要坐到不同餐桌上，那也就是说每张餐桌上不能有同一单位的人。这样的话，我们对于每个单位向每张餐桌连一条边权为1的边，表示同一餐桌不得有相同单位的人。从源点向每个单位连一条边权为人数的边，从餐桌向汇点连一条边权为餐桌容量的边，这样的话跑最大流，跑...

2019-03-31

0 381

P3114 [USACO15JAN]踩踏Stampede

题目链接我一开始看错题了，看成每秒走\(c_i\)个单位了，于是样例答案就变成了3。。害我调好久，还以为样例错了对于每头奶牛，我们求出它经过\(y\)轴的时间段，然后离散化一下，将奶牛按照从低到高的顺序排序，区间上记录最新经过的奶牛，如果当前奶牛的区间都已经被覆盖过了，那么说明完全被遮挡...

2019-03-12

0 348

SP1043 GSS1

题目链接简单说就是带修的查询区间最大子段和，用线段树维护即可对于每个区间，我们肯定要记录它的最大子段和\(v\)，但是怎么维护呢？我们可以记录下从区间左端点开始的最大子段和\(v1\)，从右端点开始的最大子段和\(v2\)以及区间和\(sum\) 那么\(t[p].sum=t[lc]....

2019-03-06

0 284

SP2713 GSS4

题目链接这是一道假题，表面上看起来，好像使用了什么奇妙的操作，其实就是一个无脑暴力我们会发现，即使是\(1e18\)，在开方\(6\)次之后也已经变成了\(1\)，而\(1\)再怎么开方还是\(1\)，也就是说，每个数最多被修改\(6\)次，那么我们记录区间内是否都是\(1\)，如果都是\(...

2019-03-06

0 310