TitanZhang

题解

算法浅谈(1)

/ 注册

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

2020牛客暑期多校训练营（第七场）H Dividing 来自专栏

题目大意定义传奇元组：● (1,k)始终是传奇元组。● 如果(n,k)是传奇元组，(n+k,k)与(nk,k)也是传奇元组。我们想知道1≤n≤N,1≤k≤K时传奇元组(n,k)的数目。答案取模10^9+7。解题思路官方题解的思路写的很清晰（出题人宁太棒了）通过题目条件，可以发现：一旦通过(n...

分段数学

2020-08-01

6 837

2020牛客暑期多校训练营（第七场）B Mask Allocation 来自专栏

题目大意将n∗m个口罩分成k份分给医院，使得从中挑出n组，每组口罩数量一样多，也可以从中挑出m组，每组一样多，最后输出字典序最大的。解题思路我们可以先将n,m互换（如果m<n），使得n<m。由于要求字典序最大，装口罩最多的盒子不超过n。医院数量为n的时候，需要给每个医院安排m个口...

欧几里得算法

2020-08-01

7 728

2020牛客暑期多校训练营（第一场）B-Infinite Tree 来自专栏

题目大意定义为n的最小质因子，构造一棵无限的树，树上每个n(n>1)与相连。定义为到间的边的数量（距离），给出与数组，求出。解题思路一本题因为树上节点过多，用虚树来优化树形dp是一种方法。所以，我们可以虚树二次扫描换根，求解树的带权重心来得到答案。带权重心介绍：https://b...

虚树树形DP 换根

2020-07-30

1 980

2020牛客暑期多校训练营（第六场）K K-Bag 来自专栏

题目大意若一个数列是由一些1∼k的排列组成，那么就被称作一个k-bag。例如，数列1,2,3,2,3,1,1,3,2是一个3−bag（由1,2,3 2,3,1 1,3,2三个排列组成）。判断一个数列是不是一个k−bag的一部分。解题思路以样例2,3,2,1,3,3,2,1为例，可以发现，在前面...

集合交离散化前缀和

2020-07-28

2 861

2020牛客暑期多校训练营（第六场）G-Grid Coloring 来自专栏

题目大意给定一个n×n的正方形（如下图），有k种不同颜色，给每条边染色，使其满足以下条件，输出一种方案：(1) 所有颜色的边数应该相同；(2) 不存在一个单色环；(3) 一行或一列至少存在两种颜色。解题思路图片转载自：https://www.cnblogs.com/st1vdy/p/1338...

构造

2020-07-28

4 701

2020牛客暑期多校训练营（第六场）H Harmony Pairs 来自专栏

题目大意定义S(x)为x数位和，给出N,满足的A,B组数。解题思路阅读题面，很容易想到这是一道数位DP能做的题。我们先决定dp数组几个参数。可以列出dp[x][a][b][u][v]；其中x是现在搜到的位置，ab分别表示当前的A与B，u表示当前位之前B是否等于N(B<=N)，而v表示当...

数位DP

2020-07-28

3 1218

2020牛客暑期多校训练营（第六场）B-Binary Vector 来自专栏

题目大意设A={0,1}，每天Roundgod从（即维度为n，每一位由01组成的所有向量的集合）中随机选择一个二进制向量。现在他想知道n天中选取n个线性独立向量的概率。设表示n的答案，最后输出，表示异或。线性独立是什么？（其实就是任意一个向量不能通过其他两个的“加减”运算得到）https:...

数学

2020-07-27

13 1140

2020牛客暑期多校训练营（第六场）E-Easy Construction 来自专栏

题目大意给定n,k，构造一个1-n的排列P，使得对于1-n中的每个i，P都存在一个长为i的子序列，而每个子序列的和模n都余k。有解则输出任意P，无解输出-1。解题思路（做题的时候我和队友花了好久，试图凑出一种看起来靠谱的通用方案，没想到还真能歪打正着）因为长度为n的子区间只有P本身，而所有的子...

EASY

2020-07-27

6 631

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

题目大意给一棵树，每条边有边权。可以任意加边和删边，但要满足任何时刻图连通，而且任何一个环的边权异或和为0。求操作后最小权值和。解题思路任意两个点之间连边的权值都是固定的，由于图需要始终联通，所以两点间始终存在至少一条路径，如果存在多条，根据环的异或和为0，两点间的路径的异或和应该相等，且始终...

字典树 Boruvka 异或最小生成树

2020-07-26

4 760

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

题目大意从点1出发，你要按顺序完成k个任务，每个任务有要求的起点终点。途中你可以在所在的位置建立一个传送门，而同时只能用两个传送门存在，如果超过两个，则必须（远程）关闭任意一个传送门。解题思路一首先可以想到，所谓的k个任务有起点终点，就是按顺序走过2k个点，a->b,c->d这样...

最短路动态规划

2020-07-26

5 831