与人无语

分类

acm学习(3) 未归档(2) 题解(68)

/ 注册

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

每日一题题解

57篇文章 1428人学习

全部文章（共73篇）

每日一题 5.6 [SCOI2009]粉刷匠来自专栏

这题一看不会在看了半天像dp 想半天推不出转移方程不知道怎么写经过对大佬们的博客的学习终于弄懂了一种解决方法（大佬怎么写都是对的渣渣怎么写都是错的QAQ三个数组：dp[i][j][k] 第i个木板k个格子粉刷j次正确格子数 sum[i][j] 第i个木板j个格子1的...

题解

2020-05-13

1 714

3.27 数学考试来自专栏

在这题我们要选择两个区间首先我们知道右区间一定在左区间右边于是我们枚举i作为分界线 i左边最大的长度为k的的区间 i右边最大的长度为k的的区间解题的思路出来了那么该如何用程序表达用cnt数组表示前缀和那么i左边的最大区间和表达为 dp1[i]=max(dp1[i-1],cnt[i]-c...

题解

2020-05-05

3 969

每日一题 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 1019

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

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

题解

2020-05-03

7 877

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

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

题解

2020-05-03

1 680

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

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

题解

2020-05-03

0 599

每日一题 4.29 Symmetric Matrix 来自专栏

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

题解

2020-04-30

0 903

每日一题 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 654

每日一题 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 618

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 594