hnust_yangyanjun

分类

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

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

和与或来自专栏

题意：有一个长度为N的数组R，求有多少满足条件的序列A使得0 ≤ A[i] ≤ R[i]A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]输出答案对1e9+9取模思路：由于A的N个数和与或结果相等，所以每一位最多存在于这n个数中的其中一个数中。所以可以从高...

数位dp 状压dp

2021-02-02

1 825

[HNOI2012]矿场搭建来自专栏

题意：给出n条边，求该图至少需要设置多少个逃生点才能使无论哪一个点失去，其余点都能至少到达一个逃生点，并求出方案数。思路：考虑点双连通分量：如果该点双连通分量只有一个割点，则需要设一个逃生点，且该点不能是割点（防止唯一的割点失去时其余点无法到达逃生点）。如果该点双连通分量有大于一个割点，则无需设置...

割点点双联通分量

2021-01-29

2 658

魔改森林来自专栏

题意：有一个n行m列的网格图，起点在格点(n+1，1), 终点在(1,m+1),有k个格点是不能走的障碍点。求从起点到终点的路线有多少种？（只能向上或向右）思路：从数据范围看当n,m<=1000时我们可以用动态规划解决：dp[n+1][1]=1;dp[i][j]=dp[i+1][j]+dp[...

容斥组合数

2021-01-26

1 680

[HAOI2006]均分数据来自专栏

题意：将n个数分成m组，求最小均方差？思路：随机打乱数组，然后贪心求结果，取最小值。(double)clock()/CLOCKS_PER_SEC得出程序运行的时间，单位为S。random_shuffle(a+1,a+n+1);打乱数组。贪心策略：前m个数每个数单独为一组，然后将剩余数分给当前最小数...

贪心

2021-01-26

1 632

质数与合数来自专栏

题意：有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 814

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