1. 项目背景与题目解析这道P6390 [COCI 2007/2008 #4] POKLON题目来自克罗地亚信息学竞赛COCI是典型的信奥赛中级难度题目。题目大意是给定一个数字序列要求统计满足特定条件的数对数量。这类题目在信奥初赛和复赛中经常出现主要考察选手对基础算法的掌握程度和代码实现能力。我在洛谷刷题时发现很多同学在处理这类问题时容易陷入暴力枚举的误区导致时间复杂度不达标。实际上通过合理分析题目条件可以找到O(n)或O(nlogn)的优化解法。下面我将详细讲解如何用C高效解决这个问题。2. 题目分析与算法选择2.1 题目条件拆解首先我们需要明确题目要求给定一个长度为n的整数序列a统计满足a[i] a[j]且i j的数对(i,j)的数量。换句话说就是统计数组中所有相等元素的两两组合数。例如对于序列[1,2,1,1]符合条件的数对有(1,3)、(1,4)和(3,4)共3对。2.2 算法复杂度分析最直观的解法是双重循环暴力枚举int count 0; for(int i0; in; i){ for(int ji1; jn; j){ if(a[i] a[j]) count; } }这种方法时间复杂度为O(n²)当n达到1e5时会超时。我们需要更高效的算法。2.3 优化思路观察到题目本质是统计每个数值出现的次数然后对每个数值计算组合数C(m,2)m*(m-1)/2其中m是该数值出现的次数。这样可以将时间复杂度降到O(n)。3. C实现详解3.1 数据结构选择使用unordered_map来记录每个数字出现的次数是最佳选择#include unordered_map using namespace std; unordered_mapint, int freq;unordered_map的平均时间复杂度为O(1)比map的O(logn)更高效特别适合这种计数场景。3.2 完整代码实现#include iostream #include unordered_map using namespace std; int main() { int n; cin n; unordered_mapint, int freq; long long result 0; // 使用long long防止溢出 for(int i0; in; i){ int num; cin num; result freq[num]; // 当前数字之前出现的次数就是新增的数对 freq[num]; } cout result endl; return 0; }3.3 代码解析输入处理使用cin读取输入数据哈希表记录使用unordered_map记录每个数字出现的频率实时计算每次遇到一个数字时该数字之前出现的次数就是新增的有效数对输出结果最终累加的结果即为答案这种实现方式只需要一次遍历时间复杂度O(n)空间复杂度O(n)完全满足题目要求。4. 常见问题与优化技巧4.1 数据范围与溢出问题原题中n的范围是1≤n≤1e6每个a[i]的范围是1≤a[i]≤1e9。最坏情况下所有数字都相同结果会是n*(n-1)/2对于n1e6这会达到约5e11远超int范围(约2e9)。因此必须使用long long存储结果。4.2 输入输出优化对于大规模数据(1e6级别)使用cin/cout可能会超时。可以加入以下优化ios::sync_with_stdio(false); cin.tie(0);或者使用更快的scanf/printfscanf(%d, n); printf(%lld\n, result);4.3 哈希表性能比较在极端情况下unordered_map可能因为哈希冲突退化为O(n)。如果遇到超时可以尝试以下优化预分配足够空间freq.reserve(n);使用自定义哈希函数如果数字范围不大(如≤1e6)直接用数组代替哈希表5. 同类题目拓展掌握这个问题的解法后可以解决许多类似问题统计三元组(i,j,k)满足a[i]a[j]a[k]且ijk的数量统计满足a[i]a[j]且j-ik的数对数量(滑动窗口变种)统计满足a[i]a[j]k的数对数量(两数之和问题)这类问题在力扣(LeetCode)和洛谷上都很常见是算法竞赛的基础题型。6. 刷题建议与学习路径对于信奥初学者我建议按照以下顺序刷题先掌握基础语法和STL容器使用练习简单模拟题和枚举题学习基础算法排序、二分、前缀和掌握简单DP和贪心学习图论和树的基础算法这道POKLON题目属于第二阶段的练习题适合已经掌握基础语法开始学习算法优化的同学。在洛谷上类似的题目还有很多建议每天保持3-5题的练习量逐步提升算法思维和编码能力。提示刷题时一定要自己先思考写出代码并提交测试不要直接看题解。只有经过自己的思考和实践才能真正掌握算法思想。
