998244353

基础知识

Atcoder(3) C/C++(21) Codeforces(6) study(2) 动态规划(2) 图论(1) 字符串(2) 思维(15) 技巧(1) 搜索(1) 搜索基础(1) 数论(5) 未归档(14) 简单题解(1) 线段树(8) 贪心(1) 题解(34)

/ 注册

全部文章 / 基础知识（共30篇）

Codeforces Round #593 (Div. 2) C. Labs

不得不说cf锻炼思维，基础题考思维，实现都很简单本题题意如下：给个数n，问你将1~这个数平均分布在n个组中，有两组比较，A组和B组，A组中的每个数和B组中的每个数比较，共有次，若A中某数大于B中某数，则sumAB++，否则sumBA++。然后组比较中min{sum} 现在问你所有分组情况中...

2020-05-08

0 481

Educational Codeforces Round 74 (Rated for Div. 2) C - Standard Free2play

本题是道阅读理解题，读懂题意了就可破。题意：就是h个平台，初始在h高度上，事先已经使n个平台已开，当你需要下降时，事先必须有now-1的状态为开且每次最多下降2格，当你无法满足条件来下降时，可花费一块水晶来调整平台状态，问你最少要多少水晶来到达地面注意下h <= 1e9 用数...

2020-05-08

0 520

kmp的模板理解

kmp是一个模式匹配串，主要作用即给出一个串t，一个串s，问s中是否有子串和串t相等的解法。暴力时间复杂度则是O(len(t) * len(s)) 那么kmp则是在暴力匹配的情况下记录了串的已匹配特征来减少回溯的范围。 1.首先求next数组. 这里预先知道s[1~n], t[1~m]为...

2020-05-08

0 463

HDU3336 Count the string（kmp）

题意：给一个字符串及其长度，问你该字符串的每个前缀在该字符串***有多少个题解： kmp的next数组含义：next[i]表示在1~i中前缀和后缀的最大长度。举例：ababab s : ababab next : 001234 a: 2 + 1 ab: 2 + 1 aba:...

2020-05-08

0 500

Codeforces Round #595 (Div. 3) C. Good Numbers

数学太差自闭了。题意：给一个数n，问你大于等于n的数中，可以拆分成3的幂之和的最小的数，其中每个幂最多出现一次题解：先将n分解成三进制，然后观察，当某位出现2的时候，我们需要从大于这位的幂开始寻找一位出现0次的幂，将其改成1，同时将小于这个幂出现次数被改成1的幂的出现次数全部改成0 ...

2020-05-08

0 592

最短哈密顿路径（位运算+dp）

原题链接：https://www.acwing.com/problem/content/description/93/ 题意：求从点0到点n-1的最短哈密顿路径，即0~n-1这n个点每个点必须且只能经过一次。起点为0，终点为n-1，问你最短路径长度题解：设f[i][j]表示从...

2020-05-08

0 551

归并排序

归并排序，简而言之就是将两个内部顺序已经确定的集合进行合并，使得合并后的集合仍然有序那么对于一个无序集合，就需将其递归到最底层从底开始回归上一层，这样不停地将每个集合内部归并而有序。那么对于一个集合的逆序对该如何求呢？比如集合{5,4,3,2,1}逆序对为4+3+2+1 = 10 ...

2020-05-08

0 467

字符串哈希

字符串哈希就是将一个字符串映射成一个P进制的数，然后用前缀记录下来，当你查询某个字符串的哈希值时，只要用前缀相减就可以了。通常P取131或者13331来尽可能减少冲突，同时用unsigned long long值过大自动溢出避免手动取模 eg：s[] = "ABACBDAB"，...

2020-05-08

0 579

最长上升子序列

一、O(n^2)暴力，对于第i个元素，找到前i-1个元素中小于第i个元素的当前最长上升子序列。二、O(nlogn)二分，维护一个递增序列，对于第i个元素，如果其大于这个递增序列的最大值，将其加入序列末尾否则用第i个元素置换掉递增序列中最小的大于第i个元素的元素最长上升子序列的输出：...

2020-05-08

0 630

最长上升/公共子序列

LCS的输出：一、对于 O ( n 2 ...

2020-05-08

0 340