Absoler

分类

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

TA的专栏 9篇文章 0人订阅

9篇文章 1279人学习

全部文章（共83篇）

牛客网NOIP赛前集训营-普及组（第一场）

C 括号题目大意：对于输入的一串括号“()))(()()((”，可以删去若干位（删除位置不完全相同时均算作两种操作），若想最终得到合法括号串，求共有多少种操作方法可选。先说算法后解释： dp[i][j]表示，加入第i个元素后，能将前i个字符转化为有j个未配对左括号‘（’的方法数。 ...

2020-05-09

0 445

poj 1920 汉诺塔变种

思维题链接暂时没明白为啥好多poj的总结把它放在dp里题目大意：现有汉诺塔残局，也就是说盘子零散地插在三个钉子上，当然各自也都遵守“上小下大”的摆放规律。求将其全部整理至一个钉子上所需最少步数，输出最后所在钉子位置（1，2，3）以及最小步数。首先对于基础的汉诺塔问题，由数列递推式可得，...

2020-05-09

0 697

树形dp入门——poj2378

题目大意：给出一个大小为n的树，意欲破坏其中一个节点使得剩余残骸大小均不超过n/2，给出所有可行的节点编号（1~n）思路很直接，拆除一个节点后，剩余部分为其若干儿子的子树以及该节点上层所连其余部分（n-size[i]），只要这些连接块大小都不超过n/2，该节点就满足条件。因而我们可以先求出每个节...

2020-05-09

0 537

MFC学习笔记

记录一些零碎知识文本框需将Mutiline设置为true之后方可进行换行，滑块出现true选项；可通过在准备传入SetWindowTextw()的CString中加入\r\n实现换行更改对话框ID后，要去头文件中更改关联ID，这里IDE不会自动修改，需要手动完成，否则可能导...

2020-05-09

0 678

poj3140——树形搜索

题目大意：每个节点有一个权值，可从任一边将树一分为二，求两边权和之差的最小值附：题目链接建树过程和上一道题一样，同时求出每个节点管辖子树的规模size，然后在dfs函数中判断：把当前点及其以下从树上割开时，两者之差是否更小，ans初始值设为所有点权和即可。出现问题： 1.runt...

2020-05-09

0 554

SPFA算法简介

SPFA为Shortest Path Faster Algorithm的缩写，用来解决单源最短路问题，在效率上相比传统算法有一定优势。算法首先需要获取点点距离，不相通的点间距设为inf，准备一个vis数组用来判断点是否在队列中，一个dis数组记录每个点到起点的最短距离。算法核心：不断...

2020-05-09

0 744

最小生成树poj2253

样题：poj2253 题目链接题目大意：一只青蛙需从1号石头经由一系列石头跳跃至2号石头，每块石头相隔一定距离（任意两石头均可跳），求出在所有可能的跳跃路径中，单步跳跃距离最大值最小的一条路径中，该值的大小。向最小生成树算法方向分析，无论是prim还是kruskal算法，均是优先挑选短...

2020-05-09

0 382

一些数学知识补充

1 分数取模需要对一个分数 p q \fra...

2020-05-09

0 415

线段树RMQ(MAX)模板

const int MAX_N=300010; int dat[2*MAX_N-1]; int n; #define maxn 0x3f3f3f3f void init(int _n){ n=1; while(n<_n) n<<=1; fo...

2020-05-09

0 532

单调队列

单调队列是一种在直觉上很容易想到的数据结构。有一个经典例子是滑动窗口问题，对于一串数字（长为n），存在一个在其上滑动的矩形窗（长为k），要求线性时间内求出每个窗口中的最大值。我们可以想见在窗口的每次右移后，新的最大值与原最大值会具有很密切的关系。我们可以设置一个单调减队列q，添加元素时从队尾添加，遇...

2020-05-09

0 455