hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

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

质数与合数来自专栏

题意：有n个石头，FFF和GGG轮流对这堆石头进行操作，每一次可以取[1,k]个石头，但FFF取完后石头数为质数，GGG取完后石头数为合数，如果FFF赢了，则输出回合数，如果GGG赢了，则输出回合数的相反数。注意：1既不是质数，也不是合数。胜利者会尽可能的快点赢，输者会尽可能的慢点输。思路：快点...

思维

2021-01-23

1 760

兔子的排列来自专栏

题意：给你一个长度为n的目标数列，源数列为0，1，2.....,n-1。有编号为0到n-2的操作数，你可以使用编号为i的操作数交换源数列第i个和第i+1个数，请你计算源数列变成目标数列操作数的排列方式有多少种？思路：分治+记忆化搜索在[l,r]区间使用编号为i的操作数时数列将分为[l,i]和[i+...

记忆化搜索前缀和分治

2021-01-20

2 819

小阳的贝壳来自专栏

题意：有n个有颜色的贝壳，每一个的颜色值为col[i],小阳能进行以下三种操作：1 l r x：给 [l,r]区间里所有贝壳的颜色值加上x。 2 l r：询问 [l,r]区间里所有相邻贝壳颜色值的差（取绝对值）的最大值（若l=r输出0）。 3 l r ：询问 [l,r]区间里所有贝壳颜色值的最大公约...

线段树差分 gcd

2020-12-25

0 650

Necklace 来自专栏

题意：给你n种珠子，每种珠子ai颗，用全部珠子组成一条项链，项链最多有多少个切点为美丽的，美丽的为切完后为回文串，并输出其中的一种方案。思路：由于我们需要的是回文串，如果有两种珠子个数为奇数则一定不能构成回文串，否则一定存在回文串，切点个数等于ai的最大公约数，具体构造参考代码。代码： #inc...

构造题

2020-12-18

1 815

Superhero Battle 来自专栏

题意：有一个初始血量为h的怪物，有n个回合，每回合怪物的血量加di，如果怪物血量小于等于0，则怪物死亡，如果怪物不是，则n个回合循环运行，如果怪物无法死亡，则输出-1，否则输出怪物死的回合. 思路：记录n个回合中对怪物伤害最大的一个回合,即d数组的最小前缀和，记录值mi.如果mi+h<=0,则...

2020-12-17

0 759

函数的魔法来自专栏

题意：你可以进行二种操作: 操作一：可以将x变成F(x),F(x)=(x * x * x+x * x)%233;操作二：可以将x变成G(x),G(x)=(x * x * x-x * x)%233; 求最少多少次可以使a变成b，如果无解则输出-1；思路：先对233以内的数到233以内的数进行预处理：...

预处理 Floyd

2020-12-16

1 793

A and B and Lecture Rooms 来自专栏

题意：有一颗n个节点的树，有m个询问，每个询问给出x和y两个节点，让你求树上节点到这两个节点距离相等的数目。思路：①：如果x和y深度相同，则他们的最近公共祖先lca（x,y)的非这二个节点方向的节点以外的节点到x和y的距离相等.②：如果x和深度不同，则他们的路径为奇数时无解，为偶数时中点在深度大的...

倍增

2020-11-29

4 647

疫情控制来自专栏

题意：给你一个有n个城市的国家，n-1道路将城市连接（即为树），首都为节点1，有m支军队，每支军队可以在一个城市设立一个检查点，问使从首都到任意一个边境节点都会碰到检查点军队移动最少时间为多少，军队可以同时移动。思路：如果军队数少于与首都直接相连的节点数则输出-1，否则一定有解。我们可以发现时间越...

倍增

2020-11-28

3 886

[AHOI2008]MEET 紧急集合来自专栏

题意：有一颗n个节点的树，现在有m个询问，每个询问给与三个节点，求这三个节点在哪个节点集合时总距离最小？输出集合节点和总距离。思路：我们知道在树上求任意两个节点可以用lca求取，求三个节点怎么转换成求两个节点呢，我们画一颗树然后任找三个点可以发现两两之间的lca的值要么三个相等，此时该点为集合点，...

LCA

2020-11-26

3 801

Tree with Small Distances 来自专栏

题意：给你一颗有n个节点的无向树，你可以往树中加无向边，求你形成1节点到任意一个节点距离小于等于2的图加边的最小次数？思路：你可以认为是求一个变形的最小支配集，即求以1节点为根节点时第0，1，2层无需考虑的最小支配集，所以可以用动态规划和贪心算法解决。代码： #include<bits/s...

最小支配集树状dp

2020-11-19

3 840