998244353

分类

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

/ 注册

全部文章（共148篇）

计数dp

给一个数n（n <= 1000），问将这个n分解成n1，n2，n3...nk的解法有多少（k >= 1 且 n1 >= n2 >= n3 ...>= nk >= 1）由于答案可能过大，因此答案对1e9+7取模 1. 背包问题解决，这里可看作，结果恰好为n的...

2020-05-08

0 673

数位dp（计算区间个数问题）

给你一个区间[a, b] (0 < a, b < )，让你求出区间内[0~9]每个数字出现的总次数思想：实现一个count(n, x)代表1~n中x出现的次数然后用前缀和解决[a,b]中x出现的次数即 ans = count(b, x) - count(a, x); 对...

2020-05-08

0 492

HDU6669（贪心

刚开始看错题，一通乱搞发现了按输入顺序遍历。参考了下大佬的博客，发现了如果区间有交集那么就不断取他们共同的区间，如果没有交集那么就计算区间到区间之间的最小距离。乱搞一通会发现要么全走2，要么n-1次2加一次1，所以我们需要纠结的就是这最后一次到底怎么走。首先如果我们到这个区间的最短距离是奇数...

2020-05-08

0 568

Codeforces Round #589 (Div. 2) C Primes and Multiplication

这题刚开始着重看到了g和f函数上去了，后来看到了1e18知道了应该是个分解质因数的问题对g和f函数的参数简单理解下，f(x,y) 、g(y,p)只需要预处理出x的质因子即可，然后求解1~n中质因子的各幂次倍数有多少个即可不过有个玄学问题，先预处理出每个质因子及其幂次的倍数的总数再跑快速...

2020-05-08

0 444

UVA11235 RMQ模板

先占坑，日后来补贴个代码 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N ...

2020-05-08

0 487

最长公共前缀LCP

需要预先知道的： sa数组，其中按照数组的顺序存放着按照字符串后缀排好序的该后缀的首字符位置 rank数组，其中rank[i] = i在sa中的排名因此sa和rank是两个互逆的数组，即sa[rank[i]] = i; 此外也可以直观表示为sa[排名] = 首字符位置，rank[位置] = ...

2020-05-08

0 723

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 490

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

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

2020-05-08

0 530

kmp的模板理解

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

2020-05-08

0 470

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 503