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

二分图染色

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

2020-05-09

0 562

更高效的字符串匹配算法——shift-and

在接触这个算法之前，一直觉得kmp巧夺天工，利用next数组的递推，实现对于模式串任一子串最大相同前后缀的找寻，继而在匹配目标串的过程中，一旦遇到失配情况，可以令匹配起始下标进行合理范围内最大的跳跃，从而将匹配整体复杂度从O(nm)降为O(m+n)。 a b c a b c ........ ...

2020-05-09

0 1198

莫队—优雅的暴力算法

例题牛客暑期训练营 J 题意描述：输入一串整数（n<=1e5），对于每个询问（i，j），输出a[1]…a[i]以及a[j]…a[n]里数字的种类数，询问一共q个（<=n）思路分析：暴力解法，即对于每个询问均通过遍历寻找答案，会令复杂度高达O(n^2)，考虑对其进行优化。...

2020-05-09

0 645

组合数学（1）

poj3252 题意：给出两个数n，m，求出其区间中round number的个数，round number即满足在二进制写法中，0的个数大于等于1的个数的正整数。利用前缀和思想，求出（1，n），（1，m）中round number的个数，相减即可。求法：对于数字21，它的二进制写法为...

2020-05-09

0 534

强连通分量分解

知识背景：首先明确强连通分量(strongly connected component)的概念，从任一顶点能够到达任一其他顶点的有向图的顶点子集，而任意有向图均可以分解成若干不相交的scc。把每个scc视作一个顶点，可得到一个DAG。实现算法：两次dfs，第一次 dfs 遍历将顶点后序(pos...

2020-05-09

0 559

并查集在实际问题中的应用

并查集：用以将元素高效分组以及区分。题目来源：codeforces 1012B 原问题如下，在一个（n*m）的table上，element会做出一种增值行为，如果有三个物质处于某个矩形的三个顶点上，那么在第四个顶点上会自动增值出一个element。现在table上已经存在了一些物质，求出最少仍...

2020-05-09

0 543

单调栈的运用

题目来源：poj3250 题目链接题目大意：有一群列队，面朝右站立的牛，输入每头牛的身高，如果视线前方有一头高于自己的牛，则看不到它之后的牛；求出所有牛能看到头顶的个数。 n方算法超时，故考虑优化，首先能想到的是，在计算左边的牛能看到多少牛时，可以利用右边的结果。栈优化的思路即是，从右向左遍历...

2020-05-09

0 538

全排列生成方法汇总

递归法按字典序生成整体思路：首先原序列已经按照字典序排好，继而通过逐个添加新字符生成新序列，字符添加所遵守的规则即是，按照字典序贪心地添加，（遇到未与已确定序列重复的字符，就添加在后面；遇到重复的就跳过这个字符），第一个由于不存在会重复的情况，所以生成序列即为原table，之后逐个回溯，由于是...

2020-05-09

0 585

MFC项目一：基于逆波兰表达式的计算器

知识基础：我们平时所见到的，类似于（2+9）*6的计算式，都可称之为中缀表达式，其双目运算符位于两个操作数之间；而逆波兰表达式又可称为后缀表达式，其操作符位于两个操作数之后，例如 1+1 -> 11+，（2+9）*6 -> 29+6*。在进行计算时，从左到右遍历算式遇到操作数即压入数...

2020-05-09

0 813

约瑟夫环

问题原型：n个人围坐一圈依次报数（1~n），第m个人离席；之后从第（m+1）个人开始继续报数，报至第m个人时同样离席，求最后剩下的人的最初编号。 1.递归法考虑将问题拆分，对于刚去掉m的环： 1，2，，m-1，m+1，，，n，可以视作环（通过平移得到，前面原本有m个元素）： m+1，，...

2020-05-09

0 752