Absoler

搜索

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

/ 注册

全部文章 / 搜索（共7篇）

NC20265 计数+记忆化搜索来自专栏

https://ac.nowcoder.com/acm/problem/20265 补充数据范围：k<=15, c<=5我们尝试着模拟给砖块着色的过程，已经处理完[1,l]区间时，l+1位置可以安放除了color[l]之外任何一种颜色的砖块。这是一个很显然的状态转移的过程，接下来思考如...

每日一题

2020-07-17

0 665

NC20272 简单dfs 来自专栏

给一块矩形蛋糕，要求切成等面积的n个矩形，且长宽比的最大值最小。首先题目中的切n-1刀是很自然的，不需要去管，因为每一刀只能把一块切成两块，所以任何分割情况都是合法的。接下来看到n最大是10，那就很可能是指数级或阶乘级的算法，自然想到dfs。怎么搜呢？我们枚举每一刀的位置即可，对于当前矩形假如要把它...

每日一题

2020-07-14

0 867

二分图染色

出处：2016大连ICPC A 题意：有n个拳击手，其中一些人要进行m场拳击比赛。已知同场比赛的两名选手均可以分为高水平选手和低水平选手，并且有一些人的水平状况已经明确。需要根据选手之间的关系判断，这n个选手是否能分为高水平低水平两组。解读：能分为两组，并不需要指明具体是某一组，例如样例...

2020-05-09

0 562

树形dp入门——poj2378

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

2020-05-09

0 537

poj3140——树形搜索

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

2020-05-09

0 554

HDU1043&3567 搜索（八数码，康托展开+双向bfs+A*）

八数码问题，类似华容道，要求给出复位的操作序列。康托展开用于解决排列相关问题，实现了一个排列到整数双射。因此我们可以用一个整数表示当前排列，便于进行搜索。以下是康托展开和逆展开的模板。 int cantor(int* st){ int x=0; for(int i=0;i&l...

2020-05-09

0 641

舞蹈链（dancing links X）

舞蹈链算法，用于求解精确覆盖或者重复覆盖问题，目的是保证每一列的值最后为1或大于1，搜索中选用某一行后就将这一行以及它所解决的所有列删去，最后如果发现有列无法删去则失败，回溯并将之前删去的都恢复；如果最后发现所有列都被删去了，则说明问题解决。它首先可以用来解决数独问题：转化为每行，每列，每个宫都...

2020-05-09

0 557