与人无语

题解

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

/ 注册

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

每日一题 5.15 储物点的距离来自专栏

这是一道前缀和的问题a[i]表示距离的前缀和 s[i]表示物品移动到1的价值的前缀和 b[i]表示物品数量的前缀和在对于l-r移动到x 有三种情况x<=l: 先全部移到1 对于每个储存点多移动了a[x]的距离即 ans=s[r]-s[l-1]-(b[r]-b[l-1])a[x]x>...

题解

2020-05-22

1 796

每日一题 5.14 maze 来自专栏

这是一篇学习题解（别人的bfs简洁明了我的一坨糊1、字符串处理提前记录起点终点用结构体数组记录传送坐标并且使用完初始化2、提前用数组模拟行走这样每次用循环即可省略一部分代码3、用数组记录当前地点当前的最低步数好比较并且确保正确4、要重复使用的都做到了每次都有初始化（确保正确 #inc...

题解

2020-05-21

1 674

每日一题 5.13 加分二叉树来自专栏

唉天天摸鱼导致一感冒好点后再写题解都超时了虽然没牛币可以白嫖但还是写写自己的理解吧这题我们要抓住中序遍历的特点以根节点划分左子树右子树这样就可以不断递归下去求解法就出来了区间dp dp[i][j]表示i-j区间二叉树划分的分数最大前序遍历就是每次求最大时记录下根节点即可 #includ...

题解

2020-05-21

1 639

每日一题 5.12 模拟战役来自专栏

一道简单的贪心+搜索题我们可以让齐齐每次以最小的炮数换掉司机最大的炮数首先对齐齐和司机的阵地进行搜索看可以分成多少块每块内的炮一炸一起炸块外的的炮不受影响题目就相当于每次用齐齐的最小连通块换司机的最大连通块代码有详细注释 #include <bits/stdc++.h>...

题解

2020-05-17

1 664

每日一题 5.11 Moovie Mooving 来自专栏

在看完谷歌翻译后本英语菜鸡大概弄懂了这题的题意 n部电影每部电影有多个不同放映时间同一部电影只看一次看完 n和l 的范围这一看就是状压dp 但dp方程表达什么？？这里我表达的是最长放映时长我们用二进制枚举选了哪几部电影放映时间选择最近的小于放映时长的（使用二分寻找）这样就出来了 ...

题解

2020-05-17

1 0

每日一题 5.9 过河来自专栏

这一看是一个简简单单的dp 转移方程一下子就推出来了但是一写就发现范围怎么这么大（憨批如我还真开了一次1e9的数组)这题击中了我的盲区 but 我的巨佬队友说这题太基础了（在洛谷有三万多提交这题主要是离散化（名词真熟悉不会在翻阅了十几篇题解过后我终于明白了离散化就是在一个大范围内目...

题解

2020-05-16

8 1092

每日一题 5.8 codeJan与旅行来自专栏

一开始看错了题目以为一个城市只能算一次（瞎子视力然后得出一个结论最多折返一次然后计算然后wawa只会看样例才发现一个城市能多次到达那么m够大的话最后一定变成了在i到i+1之间来回那么我们就枚举每个区间是否正确？错了然后苦思然后看题解（后面的情况没想到啊啊啊因为还有个问题没有考虑 ...

题解

2020-05-13

2 714

每日一题 5.7 「火」皇家烈焰来自专栏

一看就知道是dp 但就不知道怎么写啊啊啊啊看到设方程为dp[N][2][2] 时瞬间就知道了有了这个方程在按着条件写就行了具体情况看注释 #include <bits/stdc++.h> #define ll long long ll const N=1e6+5; ll const m...

题解

2020-05-13

2 931

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