平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共47篇）

【每日一题】Symmetric Matrix 来自专栏

戳我传送题意：题目描述：计算一个满足下列条件的，n x n的矩阵的数量（答案对mod取余）输入描述：多组输入，每行输入两个整数，n和mod 1 ≤ n ≤ 105 1 ≤ mod ≤ 109 The sum of n does not exceed 107. 输出描述：输出一个整数...

数学 dp

2020-05-05

1 740

【每日一题】美味佳肴来自专栏

戳我传送题意：题目描述：小明是个大厨。他所在的餐厅每天早上都会买好n件食材（每种食材的数量可以视为无限），小明从到达餐厅开始就连续工作T时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第i道菜肴有三个属性ai，bi，ci，ai是该菜肴的美味值...

0/1背包 dp

2020-05-05

1 585

【每日一题】Removeal 来自专栏

戳我传送题意：题目描述：Bobo有整数s1，s2，...，sn，其中1 ≤ si ≤ k。删除m个后问有多少种序列,然后对（1e9 + 7）取模。输入描述：输入包含多个测试用例，并以文件结尾终止。每个测试用例的第一行包含三个整数n，m和k。第二行包含n个整数s1，s2，...，sn。...

计数dp

2020-05-05

0 710

【每日一题】合并回文子串来自专栏

戳我传送题意：思路：区间dp，表示a串的第i个字符到第j个个字符和b串第k个字符到第l个字符组成的串能否构成回文串，求法通过分解代码的形式分析，因为这个思路对我来说有点难。 for(int len1=0;len1<=n;++len1) for(int len2=0;len2<=m;++...

区间dp

2020-05-04

2 789

【每日一题】换个角度思考来自专栏

戳我传送题意：思路：离线+值域树状数组，保存每个点和每次询问的编号，每个点按照值的大小升序排序，每次询问按照k值大小升序排序。原理：1.处理k1的答案时（k最小的询问），树状数组中小于k1的位置都会被1标记，k1的答案就是树状数组 [l,r] 中1的个数。2.处理k2时（k2>=k1），之前被...

树状数组离线算法值域树状数组

2020-05-04

1 644

【每日一题】Rinne Loves Edges 来自专栏

戳我传送题意：这个题意是关键，首先n个点n-1条无向边边，接触过树的同学应该都知道这是一颗树，而度就是与这个点相连的边的数量，度为1就是叶子结点了，现在问题就变成了：在以S为根的树上删掉权值之和尽量小的一些边使得根和每一个叶子节点都不连通。思路：这是一个典型的树型dp，而树型dp本质上可以说是个搜索...

树状dp

2020-05-04

1 651

【每日一题】城市网络来自专栏

戳我传送题意：给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询（此时v是u的父亲），问你从u->v的最长上升子序列长度。思路：倍增+dfs题目表明v一定在u去网1的最短路径上，如果从u一直...

ST表树上倍增倍增

2020-05-03

1 626

【每日一题】tokitsukaze and Soldier 来自专栏

戳我传送题意：在一个游戏中，tokitsukaze需要在n个士兵中选出一些士兵组成一个团去打副本。第i个士兵的战力为v[i]，团的战力是团内所有士兵的战力之和。但是这些士兵有特殊的要求：如果选了第i个士兵，这个士兵希望团的人数不超过s[i]。(如果不选第i个士兵，就没有这个限制。)tokitsuka...

优先队列

2020-05-03

1 627

【每日一题】3月27日数学考试来自专栏

戳我传送题意：思路求两个不连续的区间的最大和，很容易想到前缀和，[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点，另一个指针枚举右区间的起点，两层循环复杂度（n^2）,应该会超时。枚举右区间的起点时，可以发现左区间的起点不需要从1开始找，此时的...

前缀和

2020-05-03

2 839

【每日一题】3月30日滑动窗口来自专栏

戳我传送题意：给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。思路：就和邓老师说的那样，每次滑动一个区间，区间从[l,r]到[l+1,r+1]，只是增加了a[r+1]减少了a[l]，...

单调队列

2020-05-02

2 676