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

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

展开阅读

CF1370E Binary Subsequence Rotation题目大意给你两个 01 串，求最少的操作次数，使这个串相等。一次操作：任选几个不同位置上的数，然后讲这些数顺时针旋转（就是将第一个挪到最后，其它的往前）。思路很显然，两串相同的是不影响答案的。而且不需要选择连续的位置，如果有一个 01 交替的子串，那么只需要 1 次操作，就可以将它们变为一样的。所谓 01 交替串，举个例子，A 串为0101010，B串则为1010101。这样就有了一个很裸的想法：每次找到最长的 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)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1- 剩余部分藏起来了(￣∇￣) -

展开阅读

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

展开阅读

XTUOJ-1223 Repeat One题目描述求由最小的一个N，N个数码1组成的数能被M整除？ 比如M=3时，111能被3整除。M=2时，则不存在这样的N。输入第一行是一个整数K(K≤1,000),表示样例的个数。 以后每行一个整数M(1≤M≤1,000,000)输出每行输出一个样例的结果，如果不存在这样的N，输出0。样例输入5 1 2 3 4 999989样例输出1 0 3 0 473670思路题目十分良心地给出了 M = 999989 时的答案，告诉我们哪怕时限有三秒，我们也无法通过高精度直接暴力，但我没试过高精行不行。然后先思考 M 的取值，显然 N- 剩余部分藏起来了(￣∇￣) -

展开阅读

XTUOJ-1270 Unique Digit Number数位不同的数题目描述数位不同的数是指所有数位上的数码都不一样的数，比如“123”三个数码1,2,3，都不一样，所以是数位不同的数；但是“1232”中有两个相同的数码2，所以不是。请写一个程序，计算第几个符合条件的数是什么？输入每行输入一个整数n(1≤n≤8877691)。输出每行输出一个整数，为对应样例的结果。样例输入1 10 100 8877691样例输出0 9 120 9876543210思路我就一蒟蒻，只能搞搞暴搜了，希望有位大佬能教我递推。每位数字不同，自然而然地想到了全排列，然后保存答案即可- 剩余部分藏起来了(￣∇￣) -

展开阅读

XTUOJ-1908071097 排序偷懒，用了STL里的sort()1103 日期纯净水，注意输出格式注意闰年就好1098 素数个数筛法求素数1090 组合数纯净水，注意输出格式组合数公式搞一搞1266 RGB矿泉水第一眼看成交换相邻两个数，这样子是寻找逆序对第二眼觉得不对，可以交换任意两个数，然后我就懵逼了，难过头了吧，正铺开草稿本验算时看了第三眼，就三个数，总数也才 10000 ，不如暴力。1230 Score纯净水，注意输出格式

展开阅读

  1. 1
  2. 2