<0x05> 逛画展
这道题我想的太抽象了，导致我在复杂的方向上花了很多时间
（因为那个思路确实不能说错吧，毕竟确实是能解决问题的）
洛谷的P1638
题目描述
博览馆正在展出由世上最佳的 $m$ 位画家所画的图画。
游客在购买门票时必须说明两个数字，$a$ 和 $b$
代表他要看展览中的第 $a$ 幅至第 $b$ 幅画（包含 $a,b$）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的 $a,b$，数据保证一定有解。
若存在多组解，输出 $a$ 最小的那组。
输入格式
第一行两个整数 $n,m$，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
第二行包含 $n$ 个整数 $a_i$，代表画第 $i$ 幅画的名师的编号。
输出格式
一行两个整数 $a,b$。
样例
样例输入
12 5
2 5 3 1 3 2 4 1 1 5 4 3
样例输出
2 7
数据规模与约定
- 对于 $30%$ 的数据，有 $n\le200$，$m\le20$。
- 对于 $60%$ 的数据，有 $n\le10^5$，$m\le10^3$。
- 对于 $100%$ 的数据，有 $1\leq n\le10^6$，$1 \leq a_i \leq m\le2\times10^3$。
分析
这里先讲正确的思路
首先先看看怎么求最小的区间
这个可以用贪心的方式
我们可以维护一个某大师的画最后出现位置的数组
那么，对于一个固定的end
最小区间的start一定小于等于所有最后出现位置并且尽可能大的
end可以从1开始遍历，然后计算start的值
后面就是看哪个短就取哪段了
代码
#include <iostream>
#include <vector>
int main()
{
int n, m;
int count = 0;
int ansLength = 1e7;
int ansStart = -1;
int ansEnd = -1;
// 读入
std::cin >> n >> m;
// 初始化
std::vector<int> nums;
nums.resize(n + 1);
std::vector<int> positions;
positions.resize(m + 1, -1);
int start = 1;
for (int end = 1; end <= n; end++)
{
int temp;
std::cin >> temp;
nums[end] = temp;
// 如果这个大师的画还没出现过
if (positions[temp] == -1)
{
count++;
}
positions[temp] = end;
// 计算当前位置为尾部的最小解
while (start < end && start < positions[nums[start]])
{
start++;
}
// 有新的最小解就更新
if (count == m && end - start < ansLength)
{
ansLength = end - start;
ansStart = start;
ansEnd = end;
}
}
std::cout << ansStart << " " << ansEnd << "\n";
return 0;
}
遇到的坑
一开始这个临时的start我是放在while里面的
这导致start每次都是从1开始遍历，浪费了很多时间
因为都是找新的解，start没必要从1开始，放while外面就行
我的神秘前缀和思路
因为最近也在看一些前缀和相关的东西，所以这道题就往前缀和的思路去想了
而且确实能想出来怎么用前缀和去解这道题
这里用样例的数据解释
12 5
2 5 3 1 3 2 4 1 1 5 4 3
对于每个数字，我们可以附加一个list表示前面不同的画出现了几次
对于这个输入，得到的list是这样的
index list num
1 0 1 0 0 0 2
2 0 1 0 0 1 5
3 0 1 1 0 1 3
4 1 1 1 0 1 1
5 1 1 2 0 1 3
6 1 2 2 0 1 2
7 1 2 2 1 1 4
8 2 2 2 1 1 1
9 3 2 2 1 1 1
10 3 2 2 1 2 5
11 3 2 2 2 2 4
12 3 2 3 2 2 3
然后就可以选取start和end，end的list减去start的list，如果没有0，那就是满足要求的
比如说2 7这对，对应选start = 1和end = 7，相减的结果就是1 1 2 1 1没有零
算法开始时，先从index = 1开始遍历，先去搜第一个解
搜到第一个解后，也得到了第一个解的长度length
后面只要直接检查某个index的list和index-length的list的差是否有0就行
没有0的话就求出这个最小解然后替换长度之类的
总的算下来时间复杂度大概是O(n)，我想是没问题的
（不考虑空间复杂度的后果）
然后就丢洛谷去跑了，发现爆内存了
经过优化变量类型之类的操作，能过的数据点多了几个但没AC
发现代码运行时间还行，就开始用时间换空间
原来是缓存全部的list，最后改成了每30个缓存一个，其他的靠现场计算
结果是只剩最后一个数据点没过，超时并且内存也差点超限(1.2s/127MB)
到这我才反应过来思路有点问题
主要也确实不甘心，鬼知道算法题原本的思路是什么，况且这样写的代码还真能过大部分数据点
我就以为是我优化没做好，不会是思路本身出了问题
最后没办法，看了看题解，发现完全是我想复杂了
代码如下，稍微有点长
#include <iostream>
#include <stdint.h>
#include <vector>
// 设置缓存频数
int bufferSlice = 30;
// 封装的画出现次数的类型
class SumInfo
{
std::vector<uint16_t> count;
public:
SumInfo(const SumInfo &c)
{
count.assign(c.count.begin(), c.count.end());
}
SumInfo(int length)
{
count.resize(length, 0);
}
SumInfo(const SumInfo &c, int index)
{
count.assign(c.count.begin(), c.count.end());
count[index]++;
}
// 判断开始结束位置是否满足要求
static bool Judge(const SumInfo &start, const SumInfo &end)
{
int length = end.count.size();
for (int i = 0; i < length; i++)
{
if (end.count[i] - start.count[i] < 1)
{
return false;
}
}
return true;
}
// 判断是否所有画都出现过
static bool Check(const SumInfo &sum)
{
for (auto &i : sum.count)
{
if (i < 1)
{
return false;
}
}
return true;
}
};
std::vector<SumInfo> frontSum;
std::vector<uint16_t> input;
// 获取缓存或计算的函数
SumInfo GetSumInfo(int index)
{
if (index % bufferSlice == 0)
{
return frontSum[index / bufferSlice];
}
else
{
return SumInfo(GetSumInfo(index - 1), input[index] - 1);
}
}
int main()
{
// 读入
int n, m;
std::cin >> n >> m;
SumInfo tempSum(m);
input.push_back(0);
frontSum.push_back(tempSum);
for (int i = 1; i <= n; i++)
{
uint16_t num;
std::cin >> num;
input.push_back(num);
tempSum = SumInfo(tempSum, num - 1);
// 做频数缓存
if (i % bufferSlice == 0)
{
frontSum.push_back(SumInfo(tempSum));
}
}
int index = 1;
int ansStart = -1;
int ansEnd = -1;
int ansLength = -1;
while (index < input.size())
{
// 搜索第一个解
if (ansEnd == -1)
{
// 找到首次所有大师的画都出现的情况
if (SumInfo::Check(GetSumInfo(index)))
{
ansEnd = index;
for (int i = 0; i < index; i++)
{
if (!SumInfo::Judge(GetSumInfo(i), GetSumInfo(ansEnd)))
{
ansStart = i;
break;
}
}
ansLength = ansEnd - ansStart;
}
}
// 遍历剩下的，看看有没有别的解
else
{
// 发现有长度更小的解
if (SumInfo::Judge(GetSumInfo(index - ansLength), GetSumInfo(index)))
{
// 求解
ansEnd = index;
int tempStart = index - ansLength;
for (int i = tempStart; i < index; i++)
{
if (!SumInfo::Judge(GetSumInfo(i), GetSumInfo(ansEnd)))
{
ansStart = i;
break;
}
}
ansLength = ansEnd - ansStart;
}
}
if (ansLength + 1 == m)
{
break;
}
index++;
}
std::cout << ansStart << " " << ansEnd;
return 0;
}
<0x06> 跳跳！
今天别的事情多，所以就挑一道简单的题写写
洛谷的P4995
题目描述
你是一只小跳蛙，你特别擅长在各种地方跳来跳去。
这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头
其中第 $i$ 块的石头高度为 $h_i$，地面的高度是 $h_0 = 0$
你估计着，从第 $i$ 块石头跳到第 $j$ 块石头上耗费的体力值为 $(h_i - h_j) ^ 2$，从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i) ^ 2$
为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次
并最终停在任意一块石头上，并且小跳蛙想耗费尽可能多的体力值
当然，你只是一只小跳蛙，你只会跳，不知道怎么跳才能让本领更充分地展现
不过你有救啦！小 F 给你递来了一个写着 AK 的电脑，你可以使用计算机程序帮你解决这个问题，万能的计算机会告诉你怎么跳。
那就请你——会写代码的小跳蛙——写下这个程序，为你 NOIp AK 踏出坚实的一步吧！
输入格式
输入一行一个正整数 $n$，表示石头个数。
输入第二行 $n$ 个正整数，表示第 $i$ 块石头的高度 $h_i$。
输出格式
输出一行一个正整数，表示你可以耗费的体力值的最大值。
样例 #1
样例输入 #1
2
2 1
样例输出 #1
5
样例 #2
样例输入 #2
3
6 3 5
样例输出 #2
49
提示
样例解释
两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。
数据规模与约定
对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。
对于 $10%$ 的数据，$n \leq 3$；
对于 $20%$ 的数据，$n \leq 10$；
对于 $50%$ 的数据，$n \leq 20$；
对于 $80%$ 的数据，$n \leq 50$；
对于 $100%$ 的数据，$n \leq 300$。
分析
既然是要求可消耗的体力最大值，那就是怎么麻烦怎么来
因为对于两块石头间的体力消耗，是用差的平方算的
所以高度相差越大越好
那最好的办法是从低跳到最高的，从高的跳到最低的
由于输入的石头高度序列是无序的，并且保证高度互不相同
所以采用计数排序的思路标flag，速度最快
代码
// 因为一遍过了，所以代码逻辑挺乱的
#include <iostream>
#include <vector>
// 保存是否有这个高度
std::vector<bool> isExist;
int max = 0;
int min = 0;
// 找下一个最大值
void FindNextMax()
{
max--;
while (!isExist[max])
{
max--;
}
}
// 找下一个最小值
void FindNextMin()
{
min++;
while (!isExist[min])
{
min++;
}
}
// 算平方
size_t Sqr(size_t n)
{
return n * n;
}
// 算差
size_t DiffSqr(size_t a, size_t b)
{
if (a > b)
{
return Sqr(a - b);
}
else
{
return Sqr(b - a);
}
}
// 解题
int main()
{
// 初始化
isExist.resize(10001, false);
// 从平地跳算高度0
isExist[0] = true;
// 读入
int n;
std::cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
std::cin >> temp;
isExist[temp] = true;
// 更新最大值
if (temp > max)
{
max = temp;
}
}
size_t ans = 0;
// 从高度0开始
int p = min;
bool isFindMin = false;
while (min <= max)
{
if (isFindMin)
{
ans += DiffSqr(p, min);
p = min;
FindNextMax();
isFindMin = false;
}
else
{
ans += DiffSqr(p, max);
p = max;
FindNextMin();
isFindMin = true;
}
}
std::cout << ans << "\n";
return 0;
}
<0x07> 采药
今天挑一道经典题目来学学动态规划
洛谷的P1048
题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师
为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题
医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
输入格式
第一行有 $2$ 个整数 $T$（$1 \le T \le 1000$）和 $M$（$1 \le M \le 100$）
用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目
接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数
分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
样例
样例输入
70 3
71 100
69 1
1 2
样例输出
3
数据规模与约定
- 对于 $30%$ 的数据，$M \le 10$；
- 对于全部的数据，$M \le 100$。
分析
背包DP的经典题目，关键在于理解什么是动态规划
如果采用暴力枚举的方式，那么时间复杂度是在$O(2^{T})$，这是完全不能接受的
如果采用贪心呢，貌似可以先选择单位价值高的，但由于草药不能无限细分，这样不能保证总体最优
而动态规划的思路可以保证总体最优解
动态规划有点像贪心，都是先将问题拆解，然后看子问题怎么解决
但贪心的思路通常是一条路顺下来的，通常不会判断会不会有更好的解法
而动态规划将一个个子问题视为一个个状态，将问题求解看作子问题之间的转移
所以一般动态规划的题关键是想出那个状态转移方程
这道题的话，我们令状态转移方程为$f(i,j)$
其中$i$表示已经处理了前$i$个草药数据，$j$表示背包还能装$j$重量的草药
那么，这个状态转移方程就是$f(i,j)=max(f(i-1,j),f(i-1,j-w)+v)$
$f(i-1,j)$表示不放进去，$f(i-1,j-w)+v$表示放进去，$w$表示加入草药的重量，$v$表示加入草药的价值
并且由于处理下一个草药数据时，完全不会用到之前状态的数据，所以可以把第一维省略
这时候状态转移方程就变成了$f(j)=max(f(j),f(j-w)+v)$
有这个方程之后只要写好遍历就可以了
代码
#include <iostream>
#include <vector>
// 定义草药的数据
class Herb
{
public:
int weight;
int value;
Herb(int weight, int value)
{
this->weight = weight;
this->value = value;
}
};
// 解题
int main()
{
// 解题
int t, m;
std::cin >> t >> m;
// 草药列表和dp表
std::vector<Herb> list;
std::vector<int> dp;
dp.resize(t + 1, 0);
for (int i = 0; i < m; i++)
{
int tw, tv;
std::cin >> tw >> tv;
list.push_back(Herb(tw, tv));
}
// 通过状态转移方程计算最佳解法
for (int index = 0; index < m; index++)
{
for (int l = t; l >= list[index].weight; l--)
{
dp[l] = std::max(dp[l], dp[l - list[index].weight] + list[index].value);
}
}
// 最后再遍历一遍取最大值
int ans = 0;
for (auto &i : dp)
{
ans = std::max(ans, i);
}
std::cout << ans << "\n";
return 0;
}
<0x08> 求区间和
急着看今晚OW比赛，所以就随便写个前缀和的题目
（OA猛）
洛谷的P8218
题目描述
给定 $n$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和
对于所有测试数据，$n,m\le10^5,a_i\le 10^4$
输入格式
第一行，为一个正整数 $n$
第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$
第三行，为一个正整数 $m$
接下来 $m$ 行，每行为两个正整数 $l_i,r_i$ ，满足$1\le l_i\le r_i\le n$
输出格式
共 $m$ 行
第 $i$ 行为第 $i$ 组答案的询问
样例
样例输入
4
4 3 2 1
2
1 4
2 3
样例输出
10
5
数据规模与约定
对于 $50 %$ 的数据：$n,m\le 1000$；
对于 $100 %$ 的数据：$1 \le n, m\le 10^5$，$1 \le a_i\le 10^4$
分析
数据输入后没有更改行为，所以可以直接维护一个到当前位置的和
相当于数组内容是$[0,i]$的总和
查询的话对应位置相减即可
代码
#include <iostream>
#include <vector>
int main()
{
// 读入数据数
int n;
std::cin >> n;
// 初始化与扩容
std::vector<size_t> list;
list.resize(n + 1, 0);
for (int i = 1; i <= n; i++)
{
int temp;
std::cin >> temp;
// 维护[0,i]得和
list[i] = list[i - 1] + temp;
}
// 读入查询数
int m;
std::cin >> m;
for (int i = 0; i < m; i++)
{
int a, b;
std::cin >> a >> b;
// 相减即可
std::cout << list[b] - list[a - 1] << "\n";
}
return 0;
}