Scorpioch

分类

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 未归档(72) 算法(1) 背包问题(1)

/ 注册

全部文章（共109篇）

【模板】二逼平衡树

题目链接：传送门题解：线段树套splay //by sdfzchy #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ls t[x]...

2017-11-28

0 439

【BZOJ1251】序列终结者

1251: 序列终结者 Time Limit: 20 Sec Memory Limit: 162 MB Submit: 3778 Solved: 1583 [Submit][Status][Discuss] Description 网上有许多题，就是给定一个序列，要你支持几种操作：A、B、...

2017-11-18

0 402

【模板】普通平衡树（splay）

题目链接：传送门注意splay和upd的位置就好了 //by sdfzchy #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using name...

2017-11-18

0 378

【ARC084D】Small Multiple

题目链接：传送门题解：问题可以转化成从任意一个数字转化为k的倍数的最小代价可以发现对于一个数字x，变为x+1的代价是1（最后一位不为0），变为10*x的代价是0 如果最后一位是9，那么+1后得到的数一定能由某个数*10转移得到所以按照上述步骤bfs即可，复杂度O(k) //by ...

2017-11-18

0 525

【BZOJ1060】[ZJOI2007]时态同步

题目链接：传送门题解：树形DP，用f[u]表示u及其子树中dis的最大值，发现选取的边越靠近根越优，所以对于一条边（u,v），如果f[u]>f[v]，那么显然这条边对于答案的贡献是f[u]-f[v] //by sdfzchy #include<iostream> #inc...

2017-10-31

0 407

【BZOJ1055】【HAOI2008】玩具取名

题目链接：传送门题解：用f[l][r][i]表示从l到r能否合成第i种字符，转移很好写 //by sdfzchy #include<iostream> #include<cstdio> #include<cstring> #include<algo...

2017-10-31

0 493

【数论】错排公式

定义：一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。推导：一.递推首先将第一个元素错排，假设将第一个元素放到第k位，那么对于第k位的元素，有两种情况 1.k放在第1位，此时相当于对处第1位与...

2017-10-24

0 571

【CF622F】The Sum of the k-th Powers （拉格朗日插值法）

题目链接：传送门题意：求 <nobr> ∑ni=1ik </nobr> 题解：找规律可以发现前n项k次幂的和一定能用一个k+1次多项式表示出来，所以可以暴力地求出前k+2所对应的值，再用拉格朗日插值法求解即可 <nobr> ...

2017-10-22

0 406

【WC2002】奶牛浴场

题目链接：传送门题解：方法一见【codevs1159】最大全0子矩阵枚举每一个障碍点作为左边界扩展极大子矩阵，复杂度 <nobr> O(S2) </nobr>，其中 <nobr> S </nobr>为障碍点数目...

2017-08-21

0 437

【codevs1159】最大全0子矩阵（悬线法）

题目链接：传送门题解：方法二见【WC2002】奶牛浴场悬线法求极大子矩阵，复杂度 <nobr> O(n2) </nobr> 讲解戳这里 //by sdfzchy #include<cstdio> #include<cstring...

2017-08-21

0 610