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篇）

【模板】离散化实现的两种方式

第一种：利用结构体实现离散化这种方法的弊端是无法辨别重复元素例如 1 2 2 3 3 离散化之后是 1 2 3 4 5 使用时应注意 #include <bits/stdc++.h> using namespace std; const int N=5e5+10; ...

2017-07-10

0 390

【HDU1423】【TYVJ1071】LCIS 最长公共上升子序列

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1423 题意：如题… 题解： LCS与LIS的合体显然用DP解，DP状态的定义比较巧妙先把暴力写出来然后考虑它的优化对于第二个状态转移方程，每次需要枚举f【i-1】【k】，其中有...

2017-07-10

0 444

【POJ2279】【杨氏矩阵/钩子公式】Mr. Young's Picture Permutations

题目链接：http://poj.org/problem?id=2279 题意：给出一个n行的矩阵，每一行有a[i]个数，总共有sum个数，要求每一个位置的数必须比上面的数和左面的数大，求总方案数题解：刚开始看到这道题，潜意识里是要爆搜（貌似我也只会这样做了）毕竟暴力出滑稽但貌似有D...

2017-07-10

0 748

【待填坑】sdfzchy的模板库

基础算法 1.三分 2.求逆序对 3.离散化字符串 1.KMP及EX_KMP 2.Manacher 3.Trie树 4.AC自动机 5.Hash 图论一.强连通分量 1.Tarjan 二.最短路 1.dijkstra的优先队列优化 2.SPFA判负权环三.网络流...

2017-06-26

0 377

【HDU1698】【模板】Just a Hook

线段树区间修改区间查询练习的模板题吧神奇的Pushdown #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace...

2017-05-29

0 361

【HDU 2795】Billboard

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：有一块尺寸为h*w的矩形长板，要在上面贴1*wi的海报n张，贴海报的要求是：所有能贴的位置中最靠上的一个，并且贴的时候尽量靠左贴题解：思路很明显，就是贪心了我们可以用线段树维护区间...

2017-05-29

0 367

【HDU1394】Minimum Inversion Number

题意：给出一个由0到n-1组成的序列，每次把队首的元素移到队尾，求形成的n个序列中逆序对数目的最小值（n<=5000）题解：首先可以对初始数组求一次逆序对（O（nlogn））很自然的想到，如果每次变幻数组后再求逆序对（O（n²logn）），显然会爆但我们可以做到O（1）的递...

2017-05-29

0 442

【HDU 1754】I Hate It

题意：单点修改求区间最小值题解：此处省略一万字线段树练练手就好了洛谷上的题目好像有点不一样（可怕的出题人）代码如下 #include<iostream> #include<cstdio> #include<cstring> #include&...

2017-05-29

0 407

【HDU 1166】【模板】敌兵布阵

感觉自己以前写的那个线段树并不是特别漂亮或者说又臭又长（手动@减维）于是改进一波代码风格稍微飘逸一点就看这个最简单的单点修改求区间和吧 #include<cstdio> #include<cstring> #include<iostream&g...

2017-05-29

0 428

【HDU1176】免费馅饼

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1176 题解： dp[i][j]表示第i秒时在位置j时包里的馅饼; 如果把每一刻能否得到馅饼画出来，大致就是这个样子第0秒 5 ...

2017-05-29

0 458