1
树状数组1

树状数组1 基操: void in(int x,int val) { for(int i=x;i<=n;i+=(i&(-i))) tr1[i]+=val; } int ask(int x) { int ans=0; for(int i=x;i;i-=(i&(-i))) ans+=tr[i]; ret ...

嘛…… @ 2020/07/30

3
CF 1368C Even Picture

传送门 题目: ①所有块之间能够相互到达,即使一个连通图 ②所有块有偶数个邻居 ③规定有n个块有4个邻居 每组测试给定一个n,问你怎么构造一个图。 思路:水题。我们先构造好一个边长为2的矩形,然后我们给该矩形右下角添加三个块就能表达一个“有四个邻居”的块。 1 #include <iostream> ...

SummerMingQAQ @ 2020/07/29

4
CF 1368B Codeforces Subsequences

传送门 题目:给定一个串“codeforces”,给定一个n,让你在原串上任意位置添加任意个数的字符构造出一个字符串s,使得至少有n组子序列能够组成“codeforces”,需要构造出的串长度最短,再输出构造出的s 思路:根据排列组合的性质,我们尽量平均“codeforces”上每位的个数即可。 1 ...

SummerMingQAQ @ 2020/07/29

5
CF 1367D Task On The Board

传送门 题目: Polycarp wrote on the board a string s containing only lowercase Latin letters ('a'-'z'). This string is known for you and given in the input. ...

SummerMingQAQ @ 2020/07/29

7
交换排序算法之快速排序

八种排序算法可以按照如图分类,本文主要介绍快速排序。 交换排序 所谓交换,就是序列中任意两个元素进行比较,根据比较结果来交换各自在序列中的位置,以此达到排序的目的。 快速排序 快速排序的思想很简单,就是先把待排序的数组拆成左右两个区间,左边都比中间的基准数小,右边都比基准数大。接着左右两边各自再做同 ...

低吟不作语 @ 2020/07/29

10
交换排序算法之冒泡排序

八种排序算法可以按照如图分类,本文主要介绍冒泡排序。 交换排序 所谓交换,就是序列中任意两个元素进行比较,根据比较结果来交换各自在序列中的位置,以此达到排序的目的。 冒泡排序 冒泡排序是一种简单的交换排序算法,以升序排序为例,其核心思想是: 从第一个元素开始,比较相邻的两个元素。如果第一个比第二个大 ...

低吟不作语 @ 2020/07/27

12
Codeforces Round #655 (Div. 2)

Codeforces Round #655 (Div. 2) 1. 题目分析 A: 思维题,构造性题目 B: 打表发现规律 C: 思维 D: 思维+dp E: F: 2. 题解 A. Omkar and Completion 题意: 给定t个测试样例,每个测试样例给定一个n,要求构造一个长度为n的数 ...

spcia @ 2020/07/27

13
Educational Codeforces Round 91 (Rated for Div. 2)

Educational Codeforces Round 91 (Rated for Div. 2) 待补 E F G 1. 题目分析 A:思维 B: 思维 C: 贪心 D: 思维+分类讨论 2. 题解 A. Three Indices 题意: 给定t个样例,每个样例给定一个n,而后给出n个数字,要 ...

spcia @ 2020/07/27

14
Codeforces Round #656 (Div. 3)

Codeforces Round #656 (Div. 3) 待补 G 1. 题目分析 A: 思维 B: 思维 C: 思维 D: 思维+dfs E: 拓扑排序性质 F: 模拟 2. 题解 A. Three Pairwise Maximums 题意: 给定t个测试样例,每个测试样例给定x,y,z,需要 ...

spcia @ 2020/07/27

15
包含min函数的栈

目标:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。 设计思路: 我们要做的是在我们每次数据入栈的时候,记录当前数据栈中最小值,并且在pop()出栈之后依然能找到最小值; 方案①,如果只用一个 mi ...

不忘初心dbsdxq @ 2020/07/27

16
CF 1368D AND, OR and square sum

传送门 题目: Gottfried learned about binary number representation. He then came up with this task and presented it to you. You are given a collection of nn ...

SummerMingQAQ @ 2020/07/27

17
二维数组中的查找

######此题为LeetCode分类“剑指Offer”中第二题,本人仅使用了最简单的暴力法,在没有思路的情况下,毫不犹豫的去查看了官方答案,所以以下的两种方式均为官方解题 #####题目: 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请 ...

Schieber @ 2020/07/27

18
【算法】排序02——归并排序介绍及其在分治算法思想上与快排的区别(含归并代码)

归并排序是一种效率较高的排序方法。本文将先介绍归并排序,然后再简单盘点一下其与快排的一些区别。 ...

469の一方爬行 @ 2020/07/27

19
区间dp

区间dp 1.算法分析 算法思想 使用f[l][r]表示对[l, r]这段区间的处理答案,那么f[l, r]可以划分为对f[l, k]和f[k, r]两段区间的处理答案之和 算法时间复杂度 O(n3) 可以处理的问题分类 合并线性区间问题 合并环型区间问题 多边形划分三角形问题 子树划分问题 二维分 ...

spcia @ 2020/07/27

20
树形dp

树形dp 1.算法分析 在树上统计一些信息,可以使用树形dp来处理,一般的写法有递归和递推,递归写法最为常见。 常见的问题有: 求树的直径、树的重心、树的中心 树形背包dp 二次扫描与换根法 2. 典型例题 2.1 统计树上信息:树的直径、树的中心、树的重心 2.1.1 母题 acwing285 没 ...

spcia @ 2020/07/27