本文为PAT甲级分类汇编系列文章。
集合、散列、数学、算法，这几类的题目都比较少，放到一起讲。
| 题号 | 标题 | 分数 | 大意 | 类型 |
| 1063 | Set Similarity | 25 | 集合相似度 | 集合 |
| 1067 | Sort with Swap(0, i) | 25 | 通过与0号元素交换来排序 | 数学 |
| 1068 | Find More Coins | 30 | 子集和问题 | 算法 |
| 1070 | Mooncake | 25 | 背包问题 | 算法 |
| 1078 | Hashing | 25 | 散列 | 散列 |
| 1085 | Perfect Sequence | 25 | 符合约束的最大数列长度 | 集合 |
| 1092 | To Buy or Not to Buy | 20 | 判断子集 | 集合 |
| 1093 | Count PAT's | 25 | 数子串 | 数学 |
1063就是 std::set 的使用，1092更水，这两道不做了。
集合-1085：
集合，表示方法多种多样，简单的有用数组表示的并查集，复杂的有基于红黑树的 std::set 。
但我也不知道当时整理的时候怎么把这道题分到集合里来了，但还真挺难说这道题怎么分类的。题目要求从输入数据中找出最大的子列（不一定连续）满足最大值不超过最小值的给定倍数。
实现方法比较简单，先排序，然后对于每个数，找到第一个超过它的倍数的数，迭代器相减一下就是长度。查找要用二分不能用线性，会超时。
#include <iostream>
#include <vector>
#include <algorithm> int main()
{
long num, para;
std::cin >> num >> para;
std::vector<long> data(num);
for (auto& i : data)
std::cin >> i;
std::sort(data.begin(), data.end());
int max = ;
for (int i = ; i != num; ++i)
{
if (i == || data[i] != data[i - ])
{
auto left = data.begin() + i;
auto right = data.end();
while (left < right)
{
auto mid = left + (right - left) / ;
if (*mid > data[i] * para)
right = mid;
else
left = mid + ;
}
int length = right - data.begin() - i;
if (length > max)
max = length;
if (right == data.end())
break;
}
}
std::cout << max;
}
散列-1078：
纯理论地考察散列知识，用单向平方探测法处理冲突。没什么好说的，就是很标准的散列。数据结构那个题集中有一道hard version，那个真的难。
#include <iostream>
#include <vector>
#include <cmath> bool is_prime(int _num)
{
if (_num == )
return false;
if (_num > && _num % == )
return false;
int end = std::sqrt(_num);
for (int i = ; i <= end; i += )
if (_num % i == )
return false;
return true;
} int main(int argc, char const *argv[])
{
int m;
std::cin >> m;
while (!is_prime(m))
++m;
std::vector<bool> hash(m);
int n;
std::cin >> n;
for (int i = ; i != n; ++i)
{
try
{
int t;
std::cin >> t;
for (int j = ; j != m; ++j)
{
int h = (t + j * j) % m;
if (hash[h] == )
{
hash[h] = ;
if (i > )
std::cout << ' ';
std::cout << h;
throw ;
}
}
if (i > )
std::cout << ' ';
std::cout << '-';
}
catch (...)
{
;
}
}
return ;
}
数学-1067：
乍一看，完全没有思路。正常排序哪有这么玩的？显然，这道题不考排序，需要一点数学知识把问题转化一下。
对于一个序列，如果值与位置的集合相等，那么一定可以形成若干个环。这道题中需要考虑的是：一元环，即就在应该在的位置上的元素，以及0处于什么样的环中。
自己编几个数据试一下就会发现，需要交换的次数为：
当0处于0号位置时，序列长度+多元环个数-一元环个数（包括0）；
当0号位置不是0时，序列长度+多元环个数-一元环个数-2。
#include <iostream>
#include <utility> int main(int argc, char const *argv[])
{
int n;
std::cin >> n;
std::pair<int, bool> data[n];
int loop = ;
int single = ;
for (auto& i : data)
std::cin >> i.first;
for (int i = ; i != n; ++i)
{
if (data[i].second)
continue;
data[i].second = ;
if (data[i].first == i)
++single;
else
{
++loop;
int t = data[i].first;
while (!data[t].second)
data[t].second = , t = data[t].first;
}
}
if (data[].first == )
std::cout << n + loop - single;
else
std::cout << n + loop - single - ; return ;
}
数学-1093：
要求数“PAT”的个数。如果一个个数的话肯定超时，毕竟题目中都说了数量很大要取模。
正常的算法也不麻烦。先从左向右遍历，数‘P’的数量，在遇到'A'时记录下来；再从右向左遍历，数'T'的数量，也在遇到'A'时记录下来；最后遍历，对每个'A'计算刚才记录的数的乘积并累加。
#include <iostream>
#include <string>
#include <vector> int main()
{
std::string str;
std::cin >> str;
std::vector<int> count_p(str.size());
std::vector<int> count_t(str.size());
long count = ;
for (int i = ; i != str.size(); ++i)
if (str[i] == 'P')
++count;
else if (str[i] == 'A')
count_p[i] = count;
count = ;
for (int i = str.size() - ; i >= ; --i)
if (str[i] == 'T')
++count;
else if (str[i] == 'A')
count_t[i] = count;
count = ;
for (int i = ; i != str.size(); ++i)
if (str[i] == 'A')
count += count_p[i] * count_t[i];
count %= ;
std::cout << count;
}
算法-1070：
贪心算法，在数据结构的Dijkstra中提到过一句，没有系统讲过。但是，这道题的算法相当显然，对每种月饼的单价排序，从高到低选择即可。
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath> struct Mooncake
{
double weight;
double price;
}; int main()
{
int num;
double demand;
std::cin >> num >> demand;
std::vector<Mooncake> product(num);
for (auto& p : product)
std::cin >> p.weight;
for (auto& p : product)
std::cin >> p.price;
std::sort(product.begin(), product.end(), [](const Mooncake& lhs, const Mooncake& rhs) {
return lhs.price / lhs.weight > rhs.price / rhs.weight;
});
double total = ;
double profit = ;
for (const auto& p : product)
{
double weight = p.weight > demand - total ? demand - total : p.weight;
total += weight;
profit += weight / p.weight * p.price;
if (std::abs(total - demand) < 0.001)
break;
}
std::cout.setf(std::ios::fixed);
std::cout << std::setprecision() << profit;
}
算法-1068：
这道题压轴，因为我不会。
因为不会，所以瞎写。先写了个递归实现，对每种硬币的数量枚举，其中递归调用函数。遇到有符合要求的组合时，就抛出异常，将硬币组合作为异常参数。结果两个样例竟然都过了，然而提交的结果是4个accept、1个wrong、2个timeout。毕竟递归了，时间复杂度是指数量级的，不超时才怪呢。
想不出更好的算法，去查了答案。这道题是01背包问题，属于动态规划算法，我还没学到，难怪不会做。而且这道题是01背包问题的特殊版，子集和问题，重量和价值都是数的大小。类似的还有著名的两数和、三数和、四数和等。
核心算法是抄的，来自这篇博客。
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> int main()
{
int num, target;
std::cin >> num >> target;
std::vector<int> coin(num);
for (auto& i : coin)
std::cin >> i;
std::sort(coin.begin(), coin.end(), std::greater<int>());
std::vector<std::vector<bool>> select(num);
for (auto& v : select)
v.resize(target + );
std::vector<int> total(target + );
for (int i = ; i != num; ++i)
for (int j = target; j >= coin[i]; --j)
if (total[j] <= total[j - coin[i]] + coin[i])
{
select[i][j] = true;
total[j] = total[j - coin[i]] + coin[i];
}
if (total[target] != target)
{
std::cout << "No Solution";
return ;
}
int price = target;
int which = num - ;
std::vector<int> found;
while (price)
{
if (select[which][price])
{
found.push_back(coin[which]);
price -= coin[which];
}
--which;
}
int count = ;
for (int i : found)
{
if (count++)
std::cout << ' ';
std::cout << i;
}
}
最后还要说一句，Eva你已经是一个大孩子了，要学会自己解决问题，别总是让我写算法。关键问题是你还老给我出难题。