yizimi远欣

题解

其他(14) 算法及模板(3) 课内(2)

/ 注册

全部文章 / 题解（共39篇）

【题解】PAT 1003 Emergency

主要思路：Dijkstra + DP 如果做过最短路计数，这道题就相当于双倍经验了。就是在跑Dijkstra时，另计一个 \(t_i\) 作为到第 \(i\) 个点时最短路的条数，一个 \(rs_i\) 作为到第 \(i\) 个点最短路点权和的最大值注意一下维护条数时要分类，是...

DP 最短路 Dijkstra

2019-12-10

0 613

SPOJ GSS1 ~ 8解题报告【完整版】

若转载请注明出处！！！ GSS1 —— GSS8 简述做法加代码。 GSS1 给出了序列\(A[1]\)，\(A[2]\)，…，\(A[N]\)。 \((a[i]≤15007,1≤N≤50000)\)。查询定义如下：查询\((x,y)=max\{a[i]+a[i+1]+...+a...

线段树平衡树树链剖分

2019-03-26

1 659

题解 UVA1659 【帮助小罗拉 Help Little Laura】

首先纠正：题目描述中应该是dx - y（这个式子本应该是从原题中证出来的）题目描述：给定一个平面上的一些有向边，每条边涂色费用为 \(dx-y\) ，其中 \(d\) 为边的长度（实数）， \(x,y\) 为题中给定参数。环路的涂色费用为其上各边涂色费用和。找出一些环路，这些环路没...

网络流最大费用循环流

2019-03-22

0 585

题解 UVA753 【UNIX插头 A Plug for UNIX】

题目简述有 n 个插座，m 个设备和 k (n, m, k ≤ 100) 种转换器，每种转换器有无限多。已知每个插座的类型，每个设备的插头类型，以及每种转换器的插座类型和插头类型。插头和插座类型都用不超过 2424 个字母表示，插座只能插到类型名称相同的插座中。例如，有 4 个插座，...

网络流 Dinic 最大流

2019-03-22

0 547

题解 P3740 【[HAOI2014]贴海报】

题目描述 Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。张贴规则如下： electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子； ...

珂朵莉树

2019-03-22

0 693

题解 UVA11992 【Fast Matrix Operations】

题目描述有一个r行c列的全0矩阵，有以下三种操作。 1 X1 Y1 X2 Y2 v 子矩阵（X1,Y1,X2,Y2）的元素加v 2 X1 Y1 X2 Y2 v 子矩阵（X1,Y1,X2,Y2）的元素变为v 3 X1 Y1...

线段树

2019-03-22

0 514

题解 UVA12299 【RMQ with Shifts】

题目简述：给出n个数q个询问。对于query（a，b），输出区间（a，b）的数的最小值；对于shift（a0，a1，a2，......，an），则将第a1个数的值赋给a0，第a2个数赋给a1......，第an个数赋给an-1，第a0个数赋给an 主要思路：三叉线段树（单点修改，区...

线段树

2019-03-22

0 581

题解 UVA12538 【自带版本控制功能的IDE Version Controlled IDE】

题目大意维护一种数据结构，资磁三种操作。 1.在p位置插入一个字符串s 2.从p位置开始删除长度为c的字符串 3.输出第v个历史版本中从p位置开始的长度为c的字符串1≤n≤50000，所有字符串总长度小于等于10^6，输出字符串总长度小于等于20000 强制在线，每次...

FHQ Treap STL 可持久化

2019-02-17

0 490

题解 P1020 【导弹拦截】

题目某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次...

DP 线段树

2019-02-12

0 668

题解 P2085 【最小函数值】

题目描述有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Aix^2+Bix+Ci (x∈N*)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。输入输出格式输入格式：输入数据：第一行输入两个正整数n和m。以下n行每...

2018-12-30

0 950