Mrhanice

分类

codeforces(2) DP基础(3) POJ(8) UVA(14) 云服务器(1) 区间DP(4) 图论(2) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4) 背包问题(3)

/ 注册

全部文章（共50篇）

华为云上安装宝塔面板

1、设置安全组，开放端口浏览器到华为云界面，在控制台–弹性云服务器–安全组–配置规则-入方向规则-快速添加规则自己选择常用的端口，或者不用快速添加规则，自己单独指定端口，下面开放8888；888；443；20；80；21端口。在此处我把一些数据库的端口也开了。 2、进入华为云...

2019-11-07

0 898

珂朵莉的数列

树状数组题目描述：给你一串数字序列，求所有区间的逆序对。解题分析：对于每一个逆序对，计算它的贡献，也就是所有包含这个逆序对的区间。用树状数组来维护，不过得先离散化。数据太大，longlong无法表示，上的java 代码如下： import java.math....

2017-12-02

0 525

Coloring Brackets CodeForces - 149D

区间DP 题目描述：输入一串保证合法的括号序列，要求给这个括号序列串染色，满足三个要求：（1·）染色要不为红，要么为蓝，要么不染色（2）每队匹配的括号，只能有一个染色（3）相邻的染色的括号不能染一个颜色。解题分析：定义dp[l][r][x][y]为左边界为l，染色为x,右边界为r，...

2017-11-24

0 768

The Morning after Halloween UVA - 1601

状态空间搜索题目描述：把图中的小写字母，移动到对应的大写字母处，这些小写字母可以同时移动，而且只能通过空白处移动，两个字母之间不可以互换位置，也不可以在同一个位置。解题分析：直接暴力bfs的话，状态数目是256*256*256，状态数目不是很多，但是每一个状态的转移需要5*5*5...

状态空间搜索

2017-11-19

0 550

Matrix Processing ZOJ - 3284

线段树题目描述：看题吧，题目说的很清晰。解题分析：这个题同学用标记瞎搞的方法就过了，网上有人用二维树状数组做的，在这写一个线段树的写法。具体是定义两个线段树，一个只管行更新，一个只管列更新，每次更新的时候是一段线性的区间。查询就是两个线段树的查询和再加上矩阵元素本身。代码如...

2017-11-03

0 449

POJ 1651 Multiplication Puzzle

题目描述：给你n个数，拿走一个数，会获得一个值，该值是这个数*它左边的数*它右边的数，最后的结果是取走中间n-2个数所获得的值的和。因为选取的顺序不一样，所获得的值也不一样，求取走中间n-2个值，最小的结果。解题分析：其实就是类似矩阵连乘的思想，矩阵连乘中选取k作为最后一次乘法的中间矩阵，...

2017-10-13

0 583

Brackets sequence UVA - 1626

区间DP 题目描述：输出最短的满足括号匹配的字符串，该字符串满足，输入时该字符串的子串。解题分析：先做的POJ 2955-Brackets，两道题虽然不一样，但是该题的想法可以应用到本题上，定义dp[i][j]为以第i个字符开头，以第j个字符结尾的，最长匹配子串的长度。因为对于输入...

2017-10-11

0 492

POJ 2955-Brackets

区间 DP 题目描述：求一个字符串的最长括号匹配子串（非连续）解题分析：状态转移方程全在题目里，定义了两种括号匹配的子串： 1若s是匹配的字符串，则（s）,[s]也是，那么状态转移方程是if(s[i] == '(' && s[j] ==')' || s[i]...

2017-10-11

0 496

HDU 4553 约会安排

线段树区间合并+标记优先级题目描述：小明需要安排和基友开黑和和女神约会的时间。这两个时间总是一段连续的时间，小明总是会找最早的时间来开始这些事。当有基友找他开黑的时候，他会先在时间表里找最早的连续时间，如果有，就开黑，没有就不开黑。当有女神和他约会，他先在时间表里找最早的连续时间，如果有就...

2017-10-06

0 568

HDU 4614 Vases and Flowers

选段树区间更新题目描述:插花，每个花瓶只允许插入一枝花。插花操作是从第A个花瓶开始插花，如果第A个花瓶空着，就插入一枝花，否则判断第Ａ＋１个花瓶，知道插完全部的Ｆ只花，或者是没有花瓶可插，把剩余的花弃掉，操作终止。输出插花的第一个花瓶和最后一个花瓶，如果一枝花都无法插入，那输出Can no...

2017-10-05

0 460