hihoCoder 1518-最大集合

---

给定一个1~N的排列A，然后定义关于k的集合S[K] = {A[K], A[A[K]], A[A[A[K]]] … }，要求最大的S[K]的大小。 分析一下样例，当k=1时，S[1]={6,7,3,1,6…}，循环节是{6,7,3,1}，然后又从6开始循环，但是S是集合，所以|S[1]|=4。当k=2时，S[2]={5,2,5…}，循环节是{5,2}，所以|S[2]|=2。当k=3时，S[3]={1,6,7,3,1…}，发现规律了吗，根据集合的无序性，S[3]==S[1]的。 其实这有点像置换群，6开始的循环节中，对于{6,7,3,1}中的任意一个数K，都有S[K]=4。同理对于另一个循环节{2,5}中的任意一个数K，都有S[K]=2。所以其实我们不需要对A中的所有数都求S[K]，只需要求出一个循环节之后，其循环内的所有K的S[K]都相等，这样可以节省很多重复计算。 最后从多个不相交的循环中求最大的S[K]即可。 代码如下： [cpp] #include<iostream> #include<vector> #include<climits> #include<algorithm> #include<set> #include<unordered_set> #include<unordered_map> #include<cmath> using namespace std; unordered_map<int, int> result; void solve(vector<int>& A, int start) { unordered_set<int> si; si.insert(start); int last = start; while (si.find(A[last]) == si.end()) { si.insert(A[last]); last = A[last]; } int ans = si.size(); unordered_set<int>::iterator it = si.begin(); while (it != si.end()) { result[*it] = ans; // 循环内的所有S[K]都相等 ++it; } } int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d", &n); vector<int> A(n + 1, 0); for (int i = 1; i <= n; ++i)scanf("%d", &A[i]); for (int i = 1; i <= n; ++i) { if (result.find(A[i]) == result.end())solve(A, A[i]); } int ans = 0; for (unordered_map<int, int>::iterator it = result.begin(); it != result.end(); ++it)ans = max(ans, it->second); printf("%d\n", ans); return 0; } [/cpp] 本代码提交AC，用时271MS。]]>