TitanZhang

题解

算法浅谈(1)

/ 注册

全部文章 / 题解（共48篇）

2020牛客暑期多校训练营（第五场）I-'Hard' Math Problem 来自专栏

题目大意有一个无穷大的二维网格，每个格子可以是1、2或者3，每个1旁边要有一个2和3，要使机器的占比最大。解题思路这道题当时卡住了我们好久，打表，枚举，玄学都用过了，结果解题方法居然这么简单。交错2和3，使每个1旁边恰好有一个2和3，而任意两个2和3不相邻。所以答案是2/3。 AC代码言简意...

简单数学

2020-07-25

1 687

2020牛客暑期多校训练营（第五场）E-Bogo Sort 来自专栏

题目大意给定置换，求有多少个排列可以通过若干次这个置换，变成1到n的排列。解题思路如果一个置换中没有环，如{1,2,3}，只能找出一个符合条件的原排列：{1,2,3}。如果有一个环，如{3,1,2}，由于环的长度为3（不同元素的数量），所以可以找出三种原排列：{1,2,3},[2,3,1}...

置换群大数乘法

2020-07-25

4 1041

2020牛客暑期多校训练营（第五场）D-Drop Voicing 来自专栏

题目大意给定一个1~n(2<=n<=500)的排列，有两种操作： 1.将倒数第二个数放到开头； 2.将第一个数放到最后；连续的操作1（包括1次）称为一段。现在要将排列变成1~n，要使得段数尽可能少，输出这个最小值。解题思路我们可以想象出一...

LIS 思维

2020-07-25

2 760

2020牛客暑期多校训练营（第三场）J Operating on the Tree 来自专栏

题目大意这道题从G题（Operating on a Graph ）延伸而来，附上G题大意：给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的...

树形dp 组合数学

2020-07-23

1 791

2020牛客暑期多校训练营（第四场）A Ancient Distance 来自专栏

题目大意给定N个点构成的有根树，顶点编号从1-N，根节点为1号点。你可以选最多K个点（根必须选），使得所有点的最大“祖先距离”尽可能的小。点x的“祖先距离”是在点x到根节点上的路径上，点x与第一个关键点的距离。若没有关键点，则距离为正无穷大。（例如1-2-3树上，关键点为2，则三个点...

线段树 DFS序

2020-07-23

1 741

2020牛客暑期多校训练营（第四场）D-Dividing Strings 来自专栏

题目大意把一个长为n(n<=105)的数划成若干段，使得划分出的数最大值和最小值的差尽量的小。（新数不能有前导 0）解题思路首先，要使最大差值尽可能小，脑袋一拍想到：如果把这个数每一位都划一段，不是最大值能控制在9以内了？有了这个性质，再往里思考，因为最大是9，...

贪心分类讨论

2020-07-21

1 783

2020牛客暑期多校训练营（第四场） H-Harder Gcd Problem 来自专栏

题目大意给出一个集合的大小n，构造两个一样的集合A和B，分别包含{1,2,...,n}。对两个集合中的不同数两两组合，每一对gcd(Api,Bqi)>1，求最多有多少对。解题思路思路一：首先应该考虑有那些数不能参与匹配。显而易见1和大于n/2的素...

数学

2020-07-21

4 716

2020牛客暑期多校训练营（第四场） B-Basic Gcd Problem 来自专栏

题目大意已知函数：给定一些正整数对(ni, ci)，输出fci(ni)对1e9+7取余的值。解题思路官方题解已经简洁地叙述了：观察公式，fc (x) 其实是 c 的若干次方，且指数要尽量大。最好的情况下，每次只消掉一个质因子。所以 fci(ni)就是...

数论快速幂

2020-07-21

2 705

2020牛客暑期多校训练营（第三场） G-Operating on a Graph 来自专栏

题目大意其实这道题原题直译着实难理解，但是可以用一些形象的方式来理解：给一个 n 个点的 Graph，第 i 个点一刚开始是第 I 种颜色，接着有 k 次操作，第 i 次操作有个参数 oi 代表颜色 oi 会侵略所有和自己相邻的颜色，于是所有和 oi 相邻的颜色全都变成 oi (若已...

并查集启发式合并

2020-07-21

2 699

2020牛客暑期多校训练营（第三场） E-Two Matchings 来自专栏

题目大意长度为n的排列是一个数组p = [p1,p2,...,pn] ，其中每个整数为1到n中的一个数，且每个数恰好出现一次。本题对于任意i，。（排列中的数两两对应）给定一个数组a （0≤a≤10^9，并且n是偶数且大于等于4）。输出排列的最小和次小成本。（每对数之差的总和）解题思路显然最小...

构造 dp

2020-07-21

1 597