GenmCai

题解

ACM(1) C++(2) C\C++(1) Git(1) Linux(1) Python(2) shell(3) 算法和数据结构(6)

/ 注册

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

题解 | 《算法竞赛进阶指南》蒙德里安的梦想

【题目】 Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where ...

状压dp

2019-08-26

0 802

题解 | 《算法竞赛进阶指南》最大子序和

【题目】输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。例如 1,-3,5,1,-2,3当m=4时，S=5+1-2+3=7当m=2或m=3时，S=5+1=6 【题解】一开始没有想到可以用单调队列，以为能用dp之类的过过掉，但是莫得成功，寻思之后再想想。而单调队...

单调队列

2019-08-26

0 677

题解 | 《算法竞赛进阶指南》前缀统计

【题目】给定N个字符串，接下来进行M次询问，每次询问给定一个字符串T，求中有多少个字符串是T的前缀。输入字符串的总长度不超过，仅包含小写字母。【题解】 Trie的裸题，用C++11(clang++ 3.9)疯狂出现段错误，结果C++14(g++ 5.4)提交就A了，莫得找到原因在哪。这道题的Tr...

trie

2019-08-26

0 528

题解 | 《算法竞赛进阶指南》一个简单的整数问题

【题目】 You have N integers,.You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given i...

线段树

2019-08-26

0 682

题解 | 《算法竞赛进阶指南》64位整数乘法

【题目】求 a 乘 b 对 p 取模的值，其中【题解】普通的，在这个数据范围肯定是超出的，就算可以取余，但最坏的情况下，精度还是会溢出，在这种情况下我们就会想到快速幂。做法跟快速幂差不多，也是使用类似的反复翻倍法，即，,时间复杂度为，网上很戏谑的称这种做法是龟速乘，跟快速幂成鲜明对比。听说还...

龟速乘

2019-08-26

0 766

题解 | 《算法竞赛进阶指南》a^b

【题目】求 a 的 b 次方对 p 取模的值，其中【题解】因为数字过大，不管是精度还是时间都不够，所以得用快速幂。即利用,例:,。来简化的过程，要注意的是p=0的情况。时间复杂度： #include<iostream> #include<cstring> #inc...

快速幂

2019-08-26

0 731

题解 | 《算法竞赛进阶指南》棋盘覆盖

【题目】给出一张n×n(n≤100)的国际象棋棋盘，其中被删除了一些点，问可以使用多少1*2的多米诺骨牌进行掩盖。【题意】题意简单，不做多说明，多米诺骨牌可以理解为长方形的方块。【题解】仔细一想，可以发现能用二分图来做。即可以把每个位置的点进行重新编号，相邻的两点具有不同的性质。比如说在2...

二分图

2019-08-26

1 642

题解 | 《算法竞赛进阶指南》银河英雄传说

【题目】公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。杨威...

带权并查集

2019-08-23

0 1008

题解 | 《算法竞赛进阶指南》程序自动分析

【题目】在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设 𝑥1, 𝑥2, 𝑥3, ⋯ 代表程序中出现的变量，给定 𝑛 个形如 𝑥𝑖 = 𝑥𝑗 或 𝑥𝑖 ≠ 𝑥𝑗 的变量相等/不等的约束条件，请判定是否可以分别为每一个...

并查集离散化

2019-08-23

2 645

题解 | 《算法竞赛进阶指南》闇の連鎖

闇の連鎖【题目】传说中的暗之连锁被人们称为 Dark。Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。经过研究，你发现 Dark 呈现无向图的结构，图中有 N 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。Dark 有 N – 1 条主要边，并且 Dark 的任...

LCA 树上差分

2019-08-19

0 668