与人无语

题解

acm学习(3) 未归档(2)

/ 注册

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

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

这是一道区间dp的题我们设置这样一个数组 dp[l1][r1][l2][r2] 来代表字符串 s1 s2 选择的范围那么递推方程怎么来对于这样一个方程它只能由这四种情况得来dp[l1+1][r1][l2][r2-1] dp[l1+1][r1-1][l2][r2]dp[l1][r1][l2...

题解

2020-05-05

4 1032

每日一题 3.25 tokitsukaze and Soldier 来自专栏

这是一个贪心题按容纳人数排序当新加入的人的容纳人数小于总人时去除人数差个战力最小的人每次加入人都会记录一下最大值最后就求出了军团战力的最大值 #include <bits/stdc++.h> #define ll long long ll const N=1e5+5; using...

题解

2020-05-03

7 892

每日一题 5.1 [SCOI2012]滑雪与时间胶囊来自专栏

这题我一看就感觉是最小生成树的板子题然后开心的复制板子改一下输出过了样例提交然后就是ac0% why？在仔细看题貌似点的高度没用好像只能从高点滑到低点。。。我最小生成树只会kruscal算法貌似不能解决开始学习prim算法最后掏出了这个优先队列优化的prim算法（最小生成树板子并且...

题解

2020-05-03

1 684

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

看题目后不会呀数据结构 (巨佬队友说是主席树的板子题果断向他学习了一下下面是我的学习理解主席树相当于线段树1-1,1-2,1-n的前缀和于是这样就可以用来维护区间信息将 l-r变为 1-l 1-r的减法套上板子这题维护的信息是区间的名次 #include <bits/stdc+...

题解

2020-05-03

0 607

每日一题 4.29 Symmetric Matrix 来自专栏

看题不会疯狂自闭看完雨巨和其他大佬的题解后写出了这道题写些自己的理解1、将矩阵的构造转化成图的构造（图的邻接矩阵表示法）边权值即表示点与点有几条边于是由条件可知每个点有且只有两条边（后面的关键）这个图由几个简单环组成每个环至少2个点2、如何由dp[n-1]推出dp[n] 相当于n-1个的...

题解

2020-04-30

0 911

每日一题 4.28 美味菜肴来自专栏

这是一道带点变化的01背包题首先对要做的 x y 两道菜怎么确定他们的先后关系？先做x后做y的美味值和为：a[x]-(\sum +t[x])b[x] + a[y] - (\sum + t[x] + t[y]) * b[y]a[x]−(\sum+t[x])∗b[x]+a[y]−(\sum+t[x]+t...

题解

2020-04-30

0 663

每日一题 4.27 Removal 来自专栏

这是一道二维dp题我们用 dp[i][j] 来表示前i个元素中删除j个如果不考虑重复的话 dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 分别是删不删除当前数考虑到重复重复的诞生是这一序列的第i个元素与前面的x位置相同那么就是以 a[x] 结尾的序列都能通过删除[x,i-1]...

题解

2020-04-29

0 627

4.24 子序列来自专栏

这是一道类似导弹拦截的dp题首先式子可化为 log(a[j])/j<log(a[i])/i然后用dp[i] 来表示以i位为结尾的子序列的个数 #include <bits/stdc++.h> #define ll long long int const N=110; int co...

题解

2020-04-28

2 598

4.23 边的染色来自专栏

这题没看题解前是不会的在看完雨姐的题解后知道了这题的几个关键1、我们直接来分析边的染色是比较复杂的那么我们就把边的权值当做边的两点的异或值那么题目要求的条件环的异或和为0就已经达到了（相当于把每个点异或了两次）2、如果题目不给边值而是全部由我们来标的话点有2^n次标法但装换成边值...

题解

2020-04-28

2 725

每日一题 4.21 糖糖别胡说，我真的不是签到题目来自专栏

这题注意两点就行了1、用后缀和处理发功的问题然后在把能力值加上这发功的2、反方向跑一遍能力值当前的糖糖不被消灭的要求是后面同组的最大值小于他详细看代码理解 #include <bits/stdc++.h> #define ll long long int const N=5e4+5;...

题解

2020-04-28

1 598