## ACM 介绍 ### ACM的输入和输出 ACM竞赛题目的输入数据和输出数据一般有多组（不定），并且格式多种多样，所以，如何处理题目的输入输出也很重要 输入_第一类： 输入不说明有多少个Input Block，以EOF为结束标志。 核心： ```C while(scanf("%d %d",&a,&b)!=EOF) ``` scanf返回的是正确读取值的个数 文件结束读到的是-1,即EOF 或者 ```c while(scanf("%d %d",&a,&b)==2) ``` ```C++ while(cin>>a>>b) ``` 输入第二类 输入一开始会有N个Input Block，下面接着是N个block ```c scanf("%d",&n) for (int i=0;i>n &&n!=0) { } ``` 输入第五类：输入字符串 ```C char buf[20]; gets(buf); ``` ```C++ 用string buf来存储 getline(cin,buf); 用buf[255]存储 cin.getline(buf,255); ``` 说明 > 1. scanf("%s %s",str1,str2),在多个字符串之间用一个或多个空格分隔。 > 2. 若使用gets函数，应为gets(str1);gets(str2);字符串之间用回车符作分隔。 > 3. 通常情况下，接收短字符串用scanf函数,接收长字符串用gets函数。 > 4. 而getchar函数每次只接受一个字符。 输出每个答案间有空格，判断第一次即可。 ## 基础数学题 You may assume the result will be in the range of 32-bit signed integer. (即int,2147483647,21亿多) 1. **累加器** ``` while(scanf("%d",&n)==1) { sum=0; for (i=1;i<=n;i++) sum+=i; printf("%d\n\n",sum); } ``` 当然可以用等差数列求和的方法,将O(n)降到O(1) 但是,会超过int.那你可以换成longlong,64位. 但是太大了 OJ评测原理.运行程序的时候会生成一个临时的输出, ![image-20251206101804094](https://chenalna.oss-cn-hangzhou.aliyuncs.com/img/image-20251206101804094.png) 2. **[电梯问题](http://acm.hdu.edu.cn/showproblem.php?pid=1008)** 3. **多项式相加** ```2 1 2.4 0 3.2 2 1 2.4 0 3.2 2 2 1.5 1 0.5 ``` 1. 结构体 2. 数组,用下标对应指数. 3. 二维数组,一个系数一个指数. 4. **最大公约数和最小公倍数** 1. 暴力算法,倍数来枚举 2. 辗转相除法,将LCM->GCD(最小公倍数转换求解最大公因数) ``` 思想: K1X=10; K2X=14; 因为14里面有个10,说明14÷10...4,4也是x的倍数 int gcd(int m,int n ) { int temp; while(n!=0) {temp=m%n; m=n; n=temp;} retrun (n); } 也可以用递归形式 int gcd(int m,int n) { if (n==0) return n; gcd (n,m%n); } return b == 0 ? a : gcd_recursive(b, a % b); ``` 递归: 1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。 3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 5. **[求解个位数](http://acm.hdu.edu.cn/showproblem.php?pid=2035)** 找循环节，循环节的证明和推导 求A^B的最后三位数表示的整数 **二分加速(快速幂运算).**拆分指数.但是奇数怎么办?只能拆出来个位数, 底数变平方指数减半的思想 ``` int power(int a,int n) { int ans; if (n==0) ans=1; else {ans=power(a*a,n/2);底数变平方.指数减半. if (n%2==1) ans*=a; } return ans; } 奇数的话(n-1)/2和n/2结果一致 ``` 递归首先要写特殊情况,写中止条件(即如果n=0,返回ans=1) ``` int power(int a,int n) { int ans=1; while (n) { if (n&1) ans*=a; //按位与，来判断是奇数 a*=a; //底数平方 n>>1;//指数减半 } return ans; } ``` 快速幂法两个问题：求余和乘法（小心溢出） 6. **[斐波那契数列](http://acm.hdu.edu.cn/showproblem.php?pid=1021)** ```` int Fibbo(int a) {if a==0 return a0; else if a==1 return a1; return (Fibbo(a-1)+Fibbo(a-2)); } ```` F(n)=F(n-1)+F(n-2) F(n)%3=(F(n-1)%3+F(n-2)%3)%3 但是，有循环 n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... mod3: 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 ... 对于标准斐波那契数列模 m，存在**皮萨诺周期**。对于模 3： - 标准斐波那契（F0=0,F1=1）模3的周期是8：0,1,1,2,0,2,2,1 - 本题数列是标准斐波那契的线性变换，周期相同或为其因数 可以通过计算状态机证明： 状态 (F(n-1)%3, F(n)%3) 只有 3×3=9 种可能（排除连续两个0的情况） 实际状态序列会形成循环，循环长度是8。 那么就是8个一循环，9个对一循环，即10个对，肯定有一对是重复的。 ``` { long n; scanf("%ld",&n); if (n%8==2 || n%8==6) printf("yes\n"); else printf("no\n");} } ``` 7. **[Problem - 1005](http://acm.hdu.edu.cn/showproblem.php?pid=1005)** 求前51项，有50对，那一定有重复的。因为A.B不一样，所以循环节不一样。 8. **[Problem - 1205](http://acm.hdu.edu.cn/showproblem.php?pid=1205)** 最大值如果比剩下的所有加起来的大于1，那么隔不开 1. 判断一个数是否为素数，或者求 1~n 范围内的所有素数， ```C++ // 判断单个数是否为素数 O(√n) bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } // 求 1~n 的所有素数 O(n√n) vector findPrimes(int n) { vector primes; for (int i = 2; i <= n; i++) { if (isPrime(i)) primes.push_back(i); } return primes; } ``` ### **1.3 埃拉托斯特尼筛法（埃氏筛）基本原理** **核心思想**：一个素数的倍数一定不是素数 **算法步骤**： 1. 假设所有数都是素数（标记为 true） 2. 从 2 开始，如果当前数是素数，则将其所有倍数标记为合数 3. 继续下一个未标记的数 ```C++ vector isPrime; vector primes; void eratosthenes(int n) { isPrime.resize(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i *i<= n; i++) {//从i*i开始标记 if (isPrime[i]) { primes.push_back(i); // 将 i 的倍数标记为合数 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } } 时间复杂度O(nloglogn) 欧拉筛（线性筛） 埃氏筛的问题：一个合数可能被多个素数重复标记（如 30 被 2、3、5 各标记一次） 欧拉筛核心思想：每个合数只被其最小质因子标记一次 void eulerSieve(int n) { isPrime.resize(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i*i <= n; i++) { if (isPrime[i]) { primes.push_back(i); } for (int j = 0; j < primes.size(); j++) {// 等同于or (int p : primes) { int p = primes[j]; if (i * p > n) break; isPrime[i * p] = false; if (i % p == 0) break; } } } 时间复杂度O(n) ``` **二、预处理优化思想** **2.1 什么是预处理** 预处理是指在程序正式处理输入数据之前，预先计算并存储一些可能多次使用的信息，以提高后续查询的效率。 **2.2 筛选法中的预处理思想** - **一次计算，多次使用**：筛法一次性生成所有素数，后续判断素数只需 O(1) 查表 - **空间换时间**：用 O(n) 的空间，将判断素数的时间从 O(√n) 降到 O(1) **2.3 预处理的常见应用场景** | 场景 | 预处理内容 | 查询复杂度 | | :--------- | :-------------- | :--------- | | 素数判断 | 素数表/标记数组 | O(1) | | 区间和查询 | 前缀和数组 | O(1) | | 最值查询 | ST 表 | O(1) | | 阶乘计算 | 阶乘表、逆元表 | O(1) | 败者树 ``` from typing import List, Tuple def find_min_and_second_min(A: List[int]) -> Tuple[int, int]: n = len(A) if n == 0: return None, None if n == 1: return A[0], None # 记录每个元素在比赛中被最小值击败的对手 losers = [[] for _ in range(n)] # 构建败者树，返回最小值的索引 def build_winner_tree(indices: List[int]) -> int: if len(indices) == 1: return indices[0] next_round = [] for i in range(0, len(indices), 2): if i + 1 < len(indices): a, b = indices[i], indices[i + 1] if A[a] > A[b]: losers[a].append(b) next_round.append(a) else: losers[b].append(a) next_round.append(b) else: next_round.append(indices[i]) return build_winner_tree(next_round) indices = list(range(n)) min_index = build_winner_tree(indices) min_val = A[min_index] # 收集所有与最小值直接比较过的败者 candidates = [] stack = losers[min_index][:] while stack: idx = stack.pop() candidates.append(A[idx]) stack.extend(losers[idx]) # 递归收集所有被最小值间接击败的败者 second_min =max(candidates) if candidates else None return min_val, second_min # 测试 A = [3, 1, 4, 2, 5] min_val, second_min = find_min_and_second_min(A) print(f"最小值: {min_val}, 次小值: {second_min}") ```