2018 ACM-ICPC Jiaozuo Online Contest [Personal Summary]

My Status

A B C D E F G H I J K
O Ø Ø Ø Ø Ø Ø Ø O Ø Ø

Level

签到题:
A, I
简单题:

中等题:

难题:

Solution

A. Magic Mirror

solution: http://www.bofc.tech/index.php/archives/141/

B. Mathematical Curse

unsolved

C. Password

unsolved

D. Sequence

unsolved

E. Jiu Yuan Wants to Eat

unsolved

F. Modular Production Line

unsolved

G. Give Candies

unsolved

H. String and Times

unsolved

I. Save the Room

solution:

J. Participate in E-sports

unsolved

K. Transport Ship

unsolved

L. Poor God Water

unsolved

2017 CCPC China-Hunan Invitional [Personal Summary]

My Status

A B C D E F G H I J K
Ø Ø Ø Ø Ø O Ø Ø Ø Ø Ø

Level

签到题:A

简单题:F

中等题:

难题:

Solution

A. Easy hh-index

unsolved

B. Higher hh-index

unsolved

C. Just hh-index

unsolved

D. Circular Coloring

unsolved

E. From Tree to Graph

unsolved

F. Sorting

Solution: http://www.bofc.tech/index.php/archives/124/

G. String Transformation

unsolved

H. Infinity

unsolved

I. Longest Increasing Subsequence

unsolved

J. Vertex Cover

unsolved

K. 2018

unsolved

图算法简论(2) :图的存储结构

设有向图 G=(V,E)G=(V,E), 令 n=Vn=|V|, m=Em=|E|(x,y)(x,y)表示一条从 xxyy 的有向边,并记该条边的边权为w(x,y)w(x,y)

存储 GG时,我们一般使用两种存储结构:邻接矩阵和邻接表。如果GG 是无向图,我们可以把无向边看作两条方向相反的有向边,从而使用与有向图相同的方式存储。

阅读更多

动态规划系列(1): 线性DP

从斐波那契数列说起

可能你从来没有接触过动态规划,只是隐约听别人提起过DP是种特别厉害的算法;又或许你已经看过动态规划的相关定义和教程,能够做一些像LCS、数字三角形之类的简单DP题目。

但无论你对DP了解如何,阅读本文都会使你对动态规划有更为清晰的认识。不同于你可能看过的很多资料,本文将会以一种更为崭新的视角,从更为本质而数学化的角度出发,尽力发掘出隐藏在所谓的“状态转移方程”、“最优子结构”等重重迷雾下动态规划的真实一面。

阅读更多

卡特兰数与默慈金数

**默慈金数 (Motzkin Number)**是特殊计数序列中的一种。在中文互联网上比较难查到有关默慈金数的资料,能获得的信息基本局限于默慈金数的定义和(一种)应用,并且这两者之间没有什么比较明显的联系。事实上,作为一种特殊计数序列,想研究默慈金数就逃不开大名鼎鼎的卡特兰数。下面就让我们通过引入卡特兰数,逐步认识默慈金数,以及阐释51Nod 1556利用默慈金数的思路。

阅读更多

基本算法(3):回溯策略

回溯策略的基本思想

回溯策略是暴力搜索法中的一种。对于某些约束满足问题,要求给出问题全部或最优解时,尤其适合使用回溯策略。

回溯策略的基本思想是试错法,它尝试分步地去解决一个问题。在解决问题的过程中,当回溯策略发现现有的分步答案不能给出有效的解答时,它将向上回溯,取消前一步甚至是前几步的计算结果,然后再通过其他可能的分步解答再次尝试寻找问题的答案。通俗地说,就是选定一条路往前走,直到“撞了南墙”再回头换一条别的路。

阅读更多

基本算法(1):枚举策略

枚举策略的基本思想

  1. 在问题所有可能解之集合中一一枚举所有可能元素。
  2. 以问题所给检验条件判断每个元素的状态(符合或不符合检验条件),符合条件的元素构成问题的解集。
阅读更多

n!末尾0的个数之计算

本文通过数学分析给出了输出n!末尾0的个数之函数的递归形式,并同时给出了两种本问题的枚举解法。

问题描述

给定正整数n, 计算n!末尾0的个数。例:

5! = 120, 故 5! 结尾0的个数为1.
10! = 3628800, 故 10! 结尾0的个数为2.
25! = 15511210043330985984000000, 故 25! 结尾0的个数为6.

阅读更多