《CF632D Longest Subsequence》
题目描述
给定有 n 个元素的数组 a 和数字 m。记 LCM 为 l 。找出使 l≤m 的 a 的最长子序列。
定义 a 的子序列为通过删除 a 中的一些元素得到的数组。允许删除 0 个元素或所有元素。
空数组的 LCM 等于 1。
输入格式
第一行包含两个整数 n 和 m ( 1≤n,m≤106 ) — 数组 a 的大小和题目描述中的参数。
第二行包含 n 个整数 ai ( 1≤ai≤109 ) — a 的元素。
输出格式
第一行打印两个整数 l 和 kmax ( 1≤l≤m,0≤kmax≤n ) — LCM 的值和最优子序列中的元素数量。
第二行打印 kmax 个整数 — 按升序排序输出元素。
请注意，您可以找到并打印任何具有最大长度的子序列。
显示翻译
题意翻译
输入输出样例
输入 #1复制
7 8 6 2 9 2 7 2 3
输出 #1复制
6 5 1 2 4 6 7
输入 #2复制
6 4 2 2 2 3 3 3
输出 #2复制
2 3 1 2 3
代码实现：
#include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; const int mx = 1000005; int ct[mx]; vector<int> vec[mx]; void writeln(int val) { cout << val << endl; } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) { int x; cin >> x; if (x <= m) vec[x].push_back(i); } for (int i = 1; i <= m; ++i) for (int j = 1; i * j <= m; ++j) ct[i * j] += vec[i].size(); int p = max(int(max_element(ct + 1, ct + m + 1) - ct), 1); set<int> res; // 替换auto为vector迭代器 for (int i = 1; i <= p; ++i) { if (p % i == 0) { for (vector<int>::iterator it = vec[i].begin(); it != vec[i].end(); ++it) { res.insert(*it); } } } cout << p << " "; writeln(res.size()); bool f = true; // 替换auto为set迭代器 for (set<int>::iterator it = res.begin(); it != res.end(); ++it) { if (!f) cout << " "; f = false; cout << *it; } if (!res.empty()) cout << endl; return 0; }