分类 算法与数据结构 下的文章

# 【扩域/佩尔方程】2017 ACM/ICPC 沈阳 F - Heron and His Triangle ## 大意 给你一个$$n$$,求$$t$$,满足$$t \ge n$$,使得边长为 $$t-1, t, t+1$$ 的三角形**面积**为整数。 ## 题解 因为数据过大,指数增长,记得开 `__int128` 。 ### 法一扩域: 比赛时搞了这种。 1. 由海伦公式得:$$ A={\sqrt {s(s-a)(s-b)(s-c)}}, {\displaystyle s={\frac {a+b+c}{2}}}- 剩余部分藏起来了( ̄∇ ̄) -

展开阅读

# CF1370E Binary Subsequence Rotation [题目](https://codeforces.com/contest/1370/problem/E) --- ## 大意 给你两个 01 串,求最少的操作次数,使这个串相等。 一次操作:任选几个不同位置上的数,然后讲这些数顺时针旋转(就是将第一个挪到最后,其它的往前)。 ## 思路 很显然,两串相同的是不影响答案的。而且不需要选择连续的位置,如果有一个 01 交替的子串,那么只需要 1 次操作,就可以将它们变为一样的。 所谓 01 交替- 剩余部分藏起来了( ̄∇ ̄) -

展开阅读

# 【拓扑排序+bitset】吉林大学ACM集训队选拔赛(重现赛)C Strange Bulbs ## 题目大意 一张图,开始灯1只有亮,每次开关当前灯,后面所有和它联通的灯的状态也变了;要求全暗的操作次数。 ## 思路 显而易见,我们对节点的操纵是按层来的,当前的会影响后面,后面的影响不了父节点,所以用拓扑排序。当前节点的变化也关联着它所有的子节点,而当前节点是否需要开关则是看它的所有开关过的父节点的数量的奇偶性,奇开偶不开。所以我们需要一个东西,来保存它的所有开关过的父节点的数量,且数量不能重复记录,这里就要用到 bitset 了。- 剩余部分藏起来了( ̄∇ ̄) -

展开阅读

# POJ题目分类推荐 (很好很有层次感) [TOC] ## 初期 ### 一. 基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) ### 二. 图算法: (1)图的深度优先遍历和广度优先遍- 剩余部分藏起来了( ̄∇ ̄) -

展开阅读

# HDU-2512 一卡通大冒险(集合划分) [TOC] ## Problem Description 因为长期钻研算法, 无暇顾及个人问题,BUAA ACM/ICPC 训练小组的帅哥们大部分都是单身。某天,他们在机房商量一个绝妙的计划"一卡通大冒险"。这个计划是由wf最先提出来的,计划的内容是,把自己的联系方式写在校园一卡通的背面,然后故意将自己的卡"遗失"在某处(如水房,TD,食堂,主M。。。。)他们希望能有MM看到他们遗失卡,能主动跟他们联系,这样就有机会请MM吃饭了。他们决定将自己的一卡通夹在基本相同的书里,然后再将书遗失到校园的各- 剩余部分藏起来了( ̄∇ ̄) -

展开阅读