《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; }