house_cat

ACM

JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章 / ACM （共110篇）

[学习笔记]ST表

给狂妄自负以适当的绝望，这就是真理基本概念 RMQ问题：给定一个长度为N的区间，M个询问，每次询问Li到Ri这段区间元素的最大值/最小值。如果暴力找最大值，复杂度是\(o(n)\)。但如果查询多次，这个复杂度就很大了。解决这个问题的方法是离线ST表和支持在线修改的线段树。 ...

学习笔记 ST表

2018-09-02

0 420

Crowd Control

我的图论还是只会套模板嘤嘤嘤题目描述 The BAPC draws a large number of visitors to Amsterdam. Many of these people arrive at the train station, then walk from inte...

图论并查集

2018-08-26

0 388

EXAM-2018-08-21

EXAM-2018-08-21 自己真的是菜的恐怖 D:Fence Building 欧拉公式：V-E+F=2 在平面中：V为顶点个数，E为边数，F为区域数在简单几何体中：V为顶点个数，E为边数，F为面数考虑到区域最多，每个交点最多由两条线构成。顶点数为C(n,4)...

训练记录矩阵生成树

2018-08-26

0 515

NAIPC2018

NAIPC2018 参考：http://www.cnblogs.com/LQLlulu/p/9513669.html?tdsourcetag=s_pctim_aiomsg https://www.cnblogs.com/clrs97/p/8730429.html?tdsourcetag=s_...

训练记录 tire树字符串

2018-08-26

0 510

[学习笔记]网络流

基本概念网络流用来解决流量的问题：所有弧上流量的集合\(f={f(u,v)}\),称为该容量网络的一个网络流带权的有向图\(G=(V,E)\) 满足以下几点，则称为网络流图有一个入度为0的顶点\(s\)，称\(s\)为源点。有一个出度为0的顶点\(t\)，称...

学习笔记图论网络流

2018-08-21

0 573

Rikka with Prefix Sum

Rikka with Prefix Sum 题目 https://www.nowcoder.com/acm/contest/148/D 题目有三个操作 l到r都添加一个数取一次前缀和查询区间和这三个操作实际上都跟求前缀和有关。如果把操作...

数学组合数学

2018-08-20

0 537

Traffic Network in Numazu

Traffic Network in Numazu 题目描述 Chika is elected mayor of Numazu. She needs to manage the traffic in this city. To manage the traffic is too hard for...

图论 LCA 树状数组

2018-08-18

0 357

EXAM-2018-8-10

EXAM-2018-8-10 F 突然卡了一会的水题 M 这题有点坑考虑到一个数列的第一个数肯定会有我们可以贪心的认为最优的方案是一个数列的第一个与另一个数列所有数的和。但是很容易找到反例 1 2 4 5 1 2 4 5 1先跟1 然后与2 然后1与4 而实际上这时的最佳是2与2...

训练记录

2018-08-18

0 392

EXAM-2018-8-9

EXAM-2018-8-9 B 水题注意理解题意有坑 G 博弈观察发现总是会进行到最后两个，或者先手取完全部，再特判一下只有一张牌的情况 H 九连环通过找规律我们可以得出递推式： F[n]=F[n-1]+2*F[n-2]+1 而这个递推式可以通过构造矩阵，然后矩...

训练记录

2018-08-09

0 369

EXAM-2018-8-3

EXAM-2018-8-3 D H 喜闻乐见的水题 J lower_bound + upper_bound 一个可以查找第一个大于，另一个可查找第一个不小于。 F 找规律+奇偶分析偶数好找，就是奇数的问题。然后我们可以发现，只有当总数是偶数时会与中间发生偏差。 C 显而易见最短路？...

训练记录

2018-08-06

0 401