2025年IOI信息學奧林匹克模擬試卷：算法競賽與深度學習挑戰(zhàn)一、算法競賽基礎題要求：本部分旨在考察學生對基礎算法和數(shù)據(jù)結構的掌握程度，包括排序算法、查找算法、圖論算法等。1.編寫一個程序，實現(xiàn)一個冒泡排序算法，對輸入的整數(shù)數(shù)組進行排序。輸入：538271輸出：123782.編寫一個程序，實現(xiàn)一個二分查找算法，在有序數(shù)組中查找一個特定的整數(shù)。輸入：10123456789105輸出：53.編寫一個程序，實現(xiàn)一個深度優(yōu)先搜索算法，用于遍歷一個無向圖的所有頂點。輸入：412233441輸出：1234二、遞歸與動態(tài)規(guī)劃題要求：本部分旨在考察學生對遞歸和動態(tài)規(guī)劃算法的理解和應用能力。1.編寫一個程序，實現(xiàn)一個遞歸算法，計算斐波那契數(shù)列的第n項。輸入：5輸出：52.編寫一個程序，實現(xiàn)一個動態(tài)規(guī)劃算法，計算一個字符串的最長公共子序列。輸入：abacac輸出：ac3.編寫一個程序，實現(xiàn)一個遞歸算法，計算一個整數(shù)數(shù)組中的最大子序列和。輸入：-21-34-121-54輸出：6三、圖論題要求：本部分旨在考察學生對圖論算法的理解和應用能力。1.編寫一個程序，實現(xiàn)一個廣度優(yōu)先搜索算法，用于遍歷一個無向圖的所有頂點。輸入：412233441輸出：12342.編寫一個程序，實現(xiàn)一個最小生成樹算法，計算一個無向圖的最小生成樹。輸入：4123234345416輸出：12343.編寫一個程序，實現(xiàn)一個最大流算法，計算一個有向圖的最大流。輸入：4123234345416123234345416345416345416234345416345416123234345416輸出：9四、字符串處理題要求：本部分旨在考察學生對字符串處理算法的理解和應用能力，包括字符串匹配、字符串編輯距離等。1.編寫一個程序，實現(xiàn)KMP算法，用于在一個文本字符串中查找一個模式字符串的所有出現(xiàn)位置。輸入：文本字符串:ABCABCDABABCDABCDABDE模式字符串:ABCDABD輸出：位置:0,10,182.編寫一個程序，實現(xiàn)一個算法來計算兩個字符串之間的編輯距離（Levenshtein距離）。輸入：字符串A:kitten字符串B:sitting輸出：編輯距離:33.編寫一個程序，實現(xiàn)一個算法來找出兩個字符串的最長公共前綴。輸入：字符串A:flower字符串B:flow輸出：最長公共前綴:flow五、數(shù)據(jù)結構應用題要求：本部分旨在考察學生對常見數(shù)據(jù)結構的應用能力，包括棧、隊列、鏈表等。1.編寫一個程序，實現(xiàn)一個棧，支持基本的棧操作：push、pop、peek和isEmpty。輸入：操作序列:push1,push2,peek,pop,isEmpty,push3,peek,pop,isEmpty輸出：當前棧頂元素:2棧是否為空:False2.編寫一個程序，實現(xiàn)一個隊列，支持基本的隊列操作：enqueue、dequeue、peek和isEmpty。輸入：操作序列:enqueue1,enqueue2,peek,dequeue,isEmpty,enqueue3,peek,dequeue,isEmpty輸出：隊列前元素:2隊列是否為空:False3.編寫一個程序，實現(xiàn)一個單鏈表，支持基本的鏈表操作：append、remove、search和isEmpty。輸入：操作序列:append1,append2,append3,search2,remove2,isEmpty輸出：鏈表元素:13鏈表是否為空:False六、深度學習基礎題要求：本部分旨在考察學生對深度學習基礎概念的理解和應用能力，包括神經(jīng)網(wǎng)絡、激活函數(shù)、損失函數(shù)等。1.編寫一個程序，實現(xiàn)一個簡單的全連接神經(jīng)網(wǎng)絡，包含輸入層、隱藏層和輸出層，使用Sigmoid激活函數(shù)。輸入：訓練數(shù)據(jù):(x1,y1),(x2,y2),...,(xn,yn)輸出：預測結果:y1_hat,y2_hat,...,yn_hat2.編寫一個程序，實現(xiàn)一個交叉熵損失函數(shù)，用于評估神經(jīng)網(wǎng)絡的預測結果。輸入：真實標簽:y預測概率:y_hat輸出：交叉熵損失:loss3.編寫一個程序，實現(xiàn)一個梯度下降算法，用于更新神經(jīng)網(wǎng)絡中的權重，以最小化損失函數(shù)。輸入：學習率:alpha損失函數(shù):loss權重:W輸出：更新后的權重:W'本次試卷答案如下：一、算法競賽基礎題1.冒泡排序算法實現(xiàn)：```pythondefbubble_sort(arr):n=len(arr)foriinrange(n):forjinrange(0,n-i-1):ifarr[j]>arr[j+1]:arr[j],arr[j+1]=arr[j+1],arr[j]returnarr#輸入處理n=int(input())arr=list(map(int,input().split()))#調用冒泡排序函數(shù)sorted_arr=bubble_sort(arr)#輸出排序后的數(shù)組print(''.join(map(str,sorted_arr)))```解析思路：通過雙層循環(huán)遍歷數(shù)組，每次循環(huán)將相鄰的元素進行比較，如果順序錯誤則交換位置，直到整個數(shù)組排序完成。2.二分查找算法實現(xiàn)：```pythondefbinary_search(arr,x):low=0high=len(arr)-1mid=0whilelow<=high:mid=(high+low)//2ifarr[mid]<x:low=mid+1elifarr[mid]>x:high=mid-1else:returnmidreturn-1#輸入處理n=int(input())arr=list(map(int,input().split()))x=int(input())#調用二分查找函數(shù)result=binary_search(arr,x)#輸出查找結果ifresult!=-1:print(result)else:print("Elementisnotpresentinarray")```解析思路：通過不斷將查找范圍縮小一半，直到找到目標值或者查找范圍為空。3.深度優(yōu)先搜索算法實現(xiàn)：```pythondefdfs(graph,start):visited=set()stack=[start]whilestack:vertex=stack.pop()ifvertexnotinvisited:visited.add(vertex)print(vertex,end='')stack.extend(graph[vertex]-visited)print()#輸入處理n=int(input())graph={i:set()foriinrange(1,n+1)}for_inrange(n-1):u,v=map(int,input().split())graph[u].add(v)graph[v].add(u)#調用深度優(yōu)先搜索函數(shù)dfs(graph,1)```解析思路：使用棧來存儲待訪問的頂點，每次從棧中取出一個頂點，訪問它并標記為已訪問，然后將它的所有未訪問的鄰居加入棧中。二、遞歸與動態(tài)規(guī)劃題1.斐波那契數(shù)列遞歸算法實現(xiàn)：```pythondeffibonacci(n):ifn<=1:returnnelse:returnfibonacci(n-1)+fibonacci(n-2)#輸入處理n=int(input())#輸出斐波那契數(shù)列的第n項print(fibonacci(n))```解析思路：遞歸地計算斐波那契數(shù)列的第n項，直到達到基本情況。2.最長公共子序列動態(tài)規(guī)劃算法實現(xiàn)：```pythondeflcs(X,Y):m=len(X)n=len(Y)L=[[None]*(n+1)foriinrange(m+1)]foriinrange(m+1):forjinrange(n+1):ifi==0orj==0:L[i][j]=0elifX[i-1]==Y[j-1]:L[i][j]=L[i-1][j-1]+1else:L[i][j]=max(L[i-1][j],L[i][j-1])returnL[m][n]#輸入處理X=input()Y=input()#輸出最長公共子序列print(lcs(X,Y))```解析思路：使用一個二維數(shù)組L來存儲子問題的解，通過比較字符來填充數(shù)組，最終得到最長公共子序列的長度。3.最大子序列和遞歸算法實現(xiàn)：```pythondefmax_subarray_sum(arr):iflen(arr)==1:returnarr[0]else:mid=len(arr)//2left_sum=max_subarray_sum(arr[:mid])right_sum=max_subarray_sum(arr[mid:])cross_sum=max_subarray_cross_sum(arr,mid)returnmax(left_sum,right_sum,cross_sum)defmax_subarray_cross_sum(arr,mid):left_sum=float('-inf')current_sum=0foriinrange(mid-1,-1,-1):current_sum+=arr[i]left_sum=max(left_sum,current_sum)right_sum=float('-inf')current_sum=0foriinrange(mid,len(arr)):current_sum+=arr[i]right_sum=max(right_sum,current_sum)returnleft_sum+right_sum#輸入處理arr=list(map(int,input().split()))#輸出最大子序列和print(max_subarray_sum(arr))```解析思路：將數(shù)組分成兩半，遞歸地計算左右兩半的最大子序列和，然后計算跨越中間點的最大子序列和，最終返回這三個值的最大值。三、圖論題1.廣度優(yōu)先搜索算法實現(xiàn)：```pythonfromcollectionsimportdequedefbfs(graph,start):visited=set()queue=deque([start])whilequeue:vertex=queue.popleft()ifvertexnotinvisited:visited.add(vertex)print(vertex,end='')queue.extend(graph[vertex]-visited)print()#輸入處理n=int(input())graph={i:set()foriinrange(1,n+1)}for_inrange(n-1):u,v=map(int,input().split())graph[u].add(v)graph[v].add(u)#調用廣度優(yōu)先搜索函數(shù)bfs(graph,1)```解析思路：使用隊列來存儲待訪問的頂點，每次從隊列中取出一個頂點，訪問它并標記為已訪問，然后將它的所有未訪問的鄰居加入隊列中。2.最小生成樹算法實現(xiàn)（克魯斯卡爾算法）：```pythonclassDisjointSet:def__init__(self,vertices):self.parent={v:vforvinvertices}self.rank={v:0forvinvertices}deffind(self,v):ifself.parent[v]!=v:self.parent[v]=self.find(self.parent[v])returnself.parent[v]defunion(self,u,v):root_u=self.find(u)root_v=self.find(v)ifroot_u!=root_v:ifself.rank[root_u]>self.rank[root_v]:self.parent[root_v]=root_uelifself.rank[root_u]<self.rank[root_v]:self.parent[root_u]=root_velse:self.parent[root_v]=root_uself.rank[root_u]+=1defkruskal(graph,vertices):mst=[]edges=sorted(graph.items(),key=lambdax:x[1])disjoint_set=DisjointSet(vertices)foredgeinedges:u,v=edge[0]ifdisjoint_set.find(u)!=disjoint_set.find(v):disjoint_set.union(u,v)mst.append(edge[1])returnmst#輸入處理n=int(input())graph={i:set()foriinrange(1,n+1)}for_inrange(n-1):u,v=map(int,input().split())graph[u].add(v)graph[v].add(u)#調用克魯斯卡爾算法mst=kruskal(graph,range(1,n+1))#輸出最小生成樹print(''.join(map(str,mst)))```解析思路：使用并查集來維護圖中的連通分量，按照邊的權重排序，每次選擇一條邊，如果這條邊連接的兩個頂點不在同一個連通分量中，則將它們合并，直到所有頂點都在同一個連通分量中。3.最大流算法實現(xiàn)（埃里克森算法）：```pythondefbfs(graph,source,sink,parent):visited=set()queue=[source]visited.add(source)whilequeue:u=queue.pop(0)forvingraph[u]:ifvnotinvisitedandgraph[u][v]>0:queue.append(v)visited.add(v)parent[v]=ureturnqueuedefedmonds_karp(graph,source,sink):parent={}max_flow=0whilebfs(graph,source,sink,parent):path_flow=float('inf')s=sinkwhiles!=source:path_flow=min(path_flow,graph[parent[s]][s])s=parent[s]max_flow+=path_flowv=sinkwhilev!=source:u=parent[v]graph[u][v]-=path_flowgraph[v][u]+=path_flowv=parent[v]returnmax_flow#輸入處理n=int(input())graph={i:{j:0forjinrange(1,n+1)}foriinrange(1,n+1)}for_inrange(n-1):u,v,w=map(int,input().split())graph[u][v]=w#調用埃里克森算法max_flow=edmonds_karp(graph,1,n)#輸出最大流print(max_flow)```解析思路：使用廣度優(yōu)先搜索找到從源點到匯點的增廣路徑，然后沿著路徑更新圖中的流量，直到?jīng)]有增廣路徑為止，最終返回最大流的值。四、字符串處理題1.KMP算法實現(xiàn)：```pythondefkmp_search(text,pattern):m=len(pattern)n=len(text)lps=[0]*mcompute_lps_array(pattern,m,lps)i=j=0whilei<n:ifpattern[j]==text[i]:i+=1j+=1ifj==m:print("Foundpatternatindex",i-j)j=lps[j-1]elifi<nandpattern[j]!=text[i]:ifj!=0:j=lps[j-1]else:i+=1defcompute_lps_array(pattern,m,lps):length=0i=1whilei<m:ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length-1]else:lps[i]=0i+=1#輸入處理text=input()pattern=input()#調用KMP算法kmp_search(text,pattern)```解析思路：KMP算法通過預處理模式字符串來創(chuàng)建一個部分匹配表（LPS），然后在搜索過程中使用這個表來避免不必要的比較。2.Levenshtein距離算法實現(xiàn)：```pythondeflevenshtein_distance(s1,s2):iflen(s1)<len(s2):returnlevenshtein_distance(s2,s1)iflen(s2)==0:returnlen(s1)previous_row=range(len(s2)+1)fori,c1inenumerate(s1):current_row=[i+1]forj,c2inenumerate(s2):insertions=previous_row[j+1]+1deletions=current_row[j]+1substitutions=previous_row[j]+(c1!=c2)current_row.append(min(insertions,deletions,substitutions))previous_row=current_rowreturnprevious_row[-1]#輸入處理s1=input()s2=input()#輸出Levenshtein距離print(levenshtein_distance(s1,s2))```解析思路：使用動態(tài)規(guī)劃來計算兩個字符串之間的編輯距離，即最小編輯次數(shù)將一個字符串轉換為另一個字符串。3.最長公共前綴算法實現(xiàn)：```pythondeflongest_common_prefix(strs):ifnotstrs:return""prefix=strs[0]forsinstrs[1:]:whilenots.startswith(prefix):prefix=prefix[:-1]ifnotprefix:return""returnprefix#輸入處理strs=[input()for_inrange(int(input()))]#輸出最長公共前綴print(longest_common_prefix(strs))```解析思路：通過比較字符串列表中的第一個字符串與其他字符串的前綴，逐步縮小公共前綴的范圍，直到找到最長的公共前綴。五、數(shù)據(jù)結構應用題1.棧實現(xiàn)：```pythonclassStack:def__init__(self):self.items=[]defis_empty(self):returnlen(self.items)==0defpush(self,item):self.items.append(item)defpop(self):ifnotself.is_empty():returnself.items.pop()returnNonedefpeek(self):ifnotself.is_empty():returnself.items[-1]returnNone#輸入處理operations=input().split()stack=Stack()foroperationinoperations:ifoperation=='push':stack.push(int(input()))elifoperation=='pop':print(stack.pop())elifoperation=='peek':print(stack.peek())elifoperation=='isEmpty':print(stack.is_empty())```解析思路：實現(xiàn)一個棧類，包含基本的棧操作：push、pop、peek和isEmpty。2.隊列實現(xiàn)：```pythonclassQueue:def__init__(self):self.items=[]defis_empty(self):returnlen(self.items)==0defenqueue(self,item):self.items.append(item)defdequeue(self):ifnotself.is_empty():returnself.items.pop(0)returnNonedefpeek(self):ifnotself.is_empty():returnself.items[0]returnNone#輸入處理operations=input().split()queue=Queue()foroperationinoperations:ifoperation=='enqueue':queue.enqueue(int(input()))elifoperation=='dequeue':print(queue.dequeue())elifoperation=='peek':print(queue.peek())elifoperation=='isEmpty':print(queue.is_empty())```解析思路：實現(xiàn)一個隊列類，包含基本的隊列操作：enqueue、dequeue、peek和isEmpty。3.單鏈表實現(xiàn)：```pythonclassListNode:def__init__(self,value=0,next=None):self.value=valueself.next=nextclassLinkedList:def__init__(self):self.head=Nonedefappend(self,value):ifnotself.head:self.head=ListNode(value)else:current=self.headwhilecurrent.next:current=current.nextcurrent.next=ListNode(value)defremove(self,value):ifself.headandself.head.value==value:self.head=self.head.nextreturncurrent=self.headwhilecurrentandcurrent.next:ifcurrent.next.value==value:current.next=current.next.nextreturncurrent=current.nextdefsearch(self,value):current=self.headwhilecurrent:ifcurrent.value==value:returnTruecurrent=current.nextreturnFalsedefis_empty(self):returnself.headisNone#輸入處理operations=input().split()linked_list=LinkedList()foroperationinoperations:ifoperation=='append':linked_list.append(int(input()))elifoperation=='remove':linked_list.remove(int(input()))elifoperation=='search':print(linked_list.search(int(input())))elifoperation=='isEmpty':print(linked_list.is_empty())```解析思路：實現(xiàn)一個單鏈表類，包含基本的鏈表操作：append、remove、search和isEm