house_cat

ACM

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

/ 注册

全部文章 / ACM （共110篇）

[动态规划+贪心]XXOR

题目描述 You are given N non-negative integers A1,A2,...,AN and another non-negative integer K. For a integer X between 0 and K (inclusive), let f(X)=(X ...

动态规划贪心

2020-03-11

0 563

[学习笔记]树套树

引言树套树，顾名思义，就是要将两种或多种树形数据结构结合起来，解决一些单独无法解决的问题。如果说要解决区间上的问题，如最大值，区间修改等，肯定会想到线段树。但是线段树不能查询第k大，不能查询一个数在区间的排名，自然也不能查询前驱和后继。平衡树可以解决查询排名、前驱、后继等问题，但其不...

线段树树查找二叉树 Splay 学习笔记树套树

2020-03-07

0 537

[平衡树-Splay]营业额统计

题目 https://loj.ac/problem/10143 题解一眼就能看出这题就是找Splay的前驱和后继通过这题可以体会到为什么要加入一个无穷小的点和一个无穷大的点，加入可以防止出坑代码 #pragma GCC optimize(2) #pragma GCC o...

树查找二叉树 Splay

2020-03-05

0 688

[学习笔记] 平衡树-Splay

简介 Splay是一种平衡二叉树。它通过不断地将某个节点旋转到根节点，使整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化成链。 Splay的时间复杂度是按总复杂度来算的，具体来说，即是：从空树开始，做插入、删除、访问操作共M次，树中最多同时存在N个点，则总时间复杂度不超过\(O(Ml...

学习笔记

2020-03-04

0 694

[CF百场计划]#3 Educational Codeforces Round 82 (Rated for Div. 2)

A. Erasing Zeroes Description You are given a string \(s\). Each character is either 0 or 1. You want all 1's in the string to form a contiguous sub...

训练记录

2020-02-20

0 485

[CF百场计划]Codeforces Round #617 (Div. 3)

A. Array with Odd Sum Description You are given an array \(a\) consisting of \(n\) integers. In one move, you can choose two indices $1 \le i, j \le...

训练记录

2020-02-12

0 478

[CF百场计划]#2 Codeforces Round #618 (Div. 2)

A. Non-zero Description: Guy-Manuel and Thomas have an array \(a\) of \(n\) integers [\(a_1, a_2, \dots, a_n\)]. In one step they can add \(1\) to a...

训练记录

2020-02-10

0 577

[贪心]邻项交换

引言训练赛遇到一个小学生的题，然后完全没思路．赛后才发现就是简单的邻项交换．初学的时候一直对一种题很迷茫，就是排序一下就可以做的贪心，感觉这个简直就是瞎搞．其实也是可以简单证明的．题目:得分题目描述现在zql手上有 N 道题，他总共有 T 的时间来完成他们中的...

贪心

2020-02-06

0 616

KMP算法复杂度证明

引言 KMP算法应该是看了一次又一次，比赛的时候字符串不是我负责，所以学到的东西又还给网上的博客了…… 退役后再翻开看，看到模板，心想这不是\(O(n^2)\)的复杂度吗？有两个循环也不能看做是\(O(n^2)\)的，这要用到摊还分析．模板这里用到的模板是算竞上的 calc...

字符串 KMP

2020-02-03

0 699

[AC自动机]玄武密码

题目描述一个长度为\(N\)的母串，有四个元素分别是:N,S,W,N．有M个长度为100的模式串．现在要求每个模式串的前缀与母串匹配最长长度．输入样例 7 3 SNNSSNS NNSS NNN WSEE 输出样例 4 2 0 题解这是AC自动机的模板题...

字符串 AC自动机

2020-01-29

1 459