Ⅰ NOIP 適用范圍最廣的排序演算法 和求最短路的演算法
快排：
Procere Qsort(l,r:Longint);
var
a,b,mid,t : Longint;
begin
a:=l;b:=r;mid:=which[(l+r) shr 1];
Repeat
while which[a]<mid do inc(a);
while which[b]>mid do dec(b);
If a<=b then
begin
t:=which[a];which[a]:=which[b];which[b]:=t;
inc(a);dec(b);
end;
Until a>=b;
if a<r then Qsort(a,r);
if l<b then Qsort(l,b);
end;
最短路：SPFA
見http://ke..com/view/682464.htm
Ⅱ noip2011准備
可以按照下表復習演算法，查漏補缺：
1、排序演算法（快排、選擇、冒泡、堆排序、二叉排序樹、桶排序）
2、DFS/BFS 也就是搜索演算法，剪枝務必要學！
學寬搜的時候再復習一下哈希表
3、樹
①遍歷
②二叉樹
③二叉排序樹（查找、生成、刪除）
④堆（二叉堆、左偏樹、堆排序）
⑤線段樹（與RMB、樹狀數組的比較）
6.Trie樹
4、圖（圖論建模）
①最小生成樹
②最短路徑
③計算圖的傳遞閉包
④連通分量（其中要掌握並查集技術）
強連通分量
⑤拓撲排序、關鍵路徑
⑥哈密爾頓環
⑦歐拉迴路
⑧Bell-man Ford、SPFA（能解決負權迴路）
⑨二分圖（匈牙利演算法）
5、動態規劃（背包問題只是其中一種）
①線性動規
②區間動規
③樹形動規
④圖形動規
6、分治（掌握了動規分治就好學了）
7、貪心
8、位運算（可以用來進行優化）
9、網路流
Ⅲ noip初賽選擇題會考些什麼內容
NOIP初賽考的知識點，大綱上有3塊：計算機基本常識、計算機基本操作、程序設計基本知識。具體來說：選擇題考查的是計算機基本常識、基本操作和程序設計中的一些基本數據結構與基本演算法；而填空題更加重視能力（尤其是隊列、棧、二叉樹等數據結構、數學問題、歸納法、數列和邏輯推理等）的考查；讀程序寫運行結果考察的是對程序的理解和跟蹤，重在分析推理能力。讀程序的4條題目往往有一定的層次，試卷中給出程序的並不復雜，語句的含義容易明白，但是悟性好的選手總是很快就能體會到程序的設計思路並得出正確的答案，機械模仿計算機手工逐步算出結果的同學往往做的很慢，造成時間不夠，而且容易失誤；完善程序更是考察程序設計能力，尤其是在明確演算法和數據結構的條件下，如何編程。讀程序和完善程序，需要在平時的學習中提高，經常閱讀、討論和研究別人的優秀程序，提高自己的理解力和速度。
Ⅳ noip要用到哪些演算法
前言
離NOIP還有一個星期，匆忙的把寒假整理的演算法補充完善，看著當時的整理覺得那時還年少。第二頁貼了幾張從貼吧里找來的圖片，看著就很熱血
的。旁邊的同學都勸我不要再放PASCAL啊什麼的了，畢竟我們的下一級直接學C++。即便我本人對C++也是贊賞有加，不過PASCAL作為夢的開始終
究不能忘記。不像機房中其餘的OIERS，我以後並不想學計算機類的專業。當年來學這個競賽就是為了興趣，感受計算機之美的。經過時遷，計劃趕不上變化，
現在尚處於迷茫之中，也很難說當時做的決定是對是錯。然而我一直堅信迷茫的時候選擇難走的路會看見更好的風景。
這篇文章簡單的說了一下NOIP考試中會常用的演算法，可能難度掌握的不是太好，有一部分內容不是NOIP考查范圍，然而隨著難度的增加，看一些更高級的演算法也沒有壞處。還有一些非常非常基礎的比如鏈表啊什麼的就直接沒有寫上（別問我為什麼整理了那麼多的排序演算法）。
最後祝大家在NOIP中取得理想的成績！
搜索
DFS
框架
procere dfs(x);
var
begin
if 達到目標狀態 then 輸出結果並退出過程;
if 滿足剪枝條件 then exit;
for i:=1 to 搜索寬度 do
begin
備份現場；（注意如果現場使用了全局變數，則需要使用局部變數備份）
dfs(參數+增量)；
恢復現場；
end;
優化
（1） 最優化剪枝：求最優值時，當前的狀態無論如何不可能比最優值更優，則退出，可與展望結合剪枝
（2） 可行性剪枝：提前判斷該狀態是否能得到可行解，如不能則退出
（3） 記憶化搜索：對於已經搜索過的狀態直接退出
（4） 改變搜索順序：對於看起來希望更大的決策先進行搜索
（5） 優化搜索策略
（6） 預處理找到大體搜索翻譯
（7） 改寫成IDA*演算法
（8） 卡時（注意現在聯賽中禁止使用meml掐時）
BFS
框架
初始化；把初始布局存入
設首指針head=0； 尾指針tail:=1；
repeat
inc(head)，取出隊列首記錄為當前被擴展結點；
for i：=1 to 規則數 do {r是規則編號}
begin
if 新空格位置合法 then
begin
if 新布局與隊列中原有記錄不重復
tail增1，並把新布局存入隊尾；
if 達到目標 then 輸出並退出；
end；
end；
until head>=tail； {隊列空}
優化
判重的優化：hash，二叉排序樹
雙向廣搜或啟發式搜索
改寫成A*演算法
二分優化
排序
冒泡排序
var a:array[1..100] of longint;t,n,i,j:longint;
procere sort;
begin
for i:=1 to n-1 do{與每個數都進行比較}
for j:=1 to n-i do
if a[j]>a[j+1] then
begin
t:=a[j];
a[j]:=a[j+1];
a[j+1]:=t;
end;
end;
選擇排序
var a:array[1..100] of longint;t,n,i,j:longint;
procere sort;
begin
for i:=1 to n-1 do
for j:=1+i to n do{大數沉小數浮}
if a[j]>a[i] then
begin
t:=a[j];
a[j]:=a[i];
a[i]:=t;
end;
end;
插入排序
var a:array[0..100] of longint;n,i,j,t:longint;
procere sort;
begin
for i:=2 to n do
for j:=1 to (i-1) do
begin
if (a[i]<a[j]) then
begin
t:=a[j];
a[j]:=a[i];
a[i]:=t;
end;
end;
end;
桶排序
var a,b:array[0..100] of longint;r,i,j,t,k,n:longint;
procere sort;
begin
for i:=0 to 100 do b[i]:=0;{為B數組清零，小桶內容清零}
for i:=1 to n do b[a[i]]:=b[a[i]]+1;
{桶的序號就是那個要排序的東西；出現一次，桶里得旗數加一}
for i:=0 to 100 do{掃描所有的桶}
begin
if b[i]<>0 then{桶里有旗}
for j:=1 to b[i] do write(i,' ');{桶的序號就是那個數}
end;
end;
快速排序
var a:array[1..100] of longint;
n,i,h,g:longint;
procere kp(l,r:longint);{變數不能與全局變數相同，否則會被抹去}
var b,m,i,j,t:longint;
begin
i:=l;
j:=r;
m:=a[(l+r) div 2];{基準數最好從中間取}
repeat
while a[j]>m do dec(j);
while a[i]<m do inc(i);{兩側的哨兵移動}
if i<=j then
{哨兵未碰面}{「=」利用repeat循環的性質，使repeat循環得以結束}
begin
t:=a[j];
a[j]:=a[i
a[i]:=t;{交換兩個哨兵的值}
inc(j);
dec(j);{哨兵繼續運動}
end;
until i>j;
if j>l then kp(l,j);
if i<r then kp(i,r);{都是循環不結束後進行的動作}
end;
begin
read(n);
for i:=1 to n do read(a[i]);
kp(1,n); {「一」位置與「N」位置}
for i:=1 to n-1 do write(a[i],' ');
write(a[n]);{防止多輸出空格使程序結果出錯}
end.
堆排序
var a:array[1..100] of longint;
n,i,b:longint;
procere jianshu(i:longint);
begin
while ((a[i]>a[i*2])or(a[i]>a[i*2+1]))and(i<=n div 2) do
{當父親數大於子女數時並且他有孩子時進行}
begin
if a[i*2]<=a[i*2+1]{左兒子小於右兒子}
then
begin
b:=a[i*2]; a[i*2]:=a[i];a[i]:=b;{左右兒子的值互換}
jianshu(i*2);{繼續為左兒子建樹}
end
else
begin
b:=a[i*2+1];a[i*2+1]:=a[i];a[i]:=b;
jianshu(i*2+1);{上同，不過是為右兒子建樹}
end;
end;
end;
procere tiao;
begin
while n<>0 do
begin
write(a[1]);
a[1]:=a[n];
n:=n-1;
for i:=(n div 2) downto 1 do
jianshu(i);
end;
end;
begin
read(n);
for i:=1 to n do
read(a[i]);
for i:=(n div 2) downto 1 do
jianshu(i);
tiao;
end.
數學定理
中國剩餘定理
若有一些兩兩互質的整數m1, m2,… mn，則對任意的整數： a
1, a
2,... an
，以下聯立同餘方程組對模數m1, m2,… mn 有公解：
康托展開
a[i]為當前未出現的元素中是排在第幾個（從0開始）
把一個整數X展開成如下形式：
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
其中a[i]為當前未出現的元素中是排在第幾個（從0開始），並且0<=a[i]<i(1<=i<=n)
錯排通項
考慮一個有n個元素的排列，若一個排列中所有的元素都不在自己原來的位置上，那麼這樣的排列就稱為原排列的一個錯排。
f[1]=0;f[2]=1;
f[n] =(n-1)(f[n-2) + f[n-1])
f[n]:=n![1-1/1!+1/2!-1/3!……+(-1)^n*1/n!]
f[n] = (n!/e+0.5)，其中e是自然對數的底，[x]為x的整數部分。
費馬大定理
費馬大定理，又被稱為「費馬最後的定理」，由法國數學家費馬提出。它斷言當整數n >2時，關於x, y, z的方程 xn + yn = zn 沒有正整數解。
被提出後，經歷多人猜想辯證，歷經三百多年的歷史，最終在1995年被英國數學家安德魯·懷爾斯證明。
費馬小定理
假如a是一個整數，p是一個素數，那麼 ap ≡a (mod p)。
如果a不是p的倍數，這個定理也可以寫成ap-1 ≡1 (mod p)。----這個更加常用
逆元
由費馬小定理：假如p是質數，且gcd(a,p)=1，那麼ap-1≡1（mod p）
逆元：如果ab≡1（mod p），那麼在模p意義下，a、b互為逆元。
所以，假如p是質數，且gcd(a,p)=1，那麼a的逆元是ap-2
逆元的作用：在模意義下進行除法。乘a的逆元等同於除以a。
歐拉函數
在數論中，對正整數n，歐拉函數是小於或等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為φ函數、歐拉商數等。
若m,a為正整數，且m,a互素，(gcd(a,m) = 1)，則aφ(m)≡1，其中為φ(m)歐拉函數，mod m為同餘關系。
歐拉定理實際上是費馬小定理的推廣。
Stirling數
第一類s(p,k)的一個的組合學解釋是：將p個物體排成k個非空循環排列的方法數。
s(p,k)的遞推公式： s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1) ,1<=k<=p-1
邊界條件：s(p,0)=0 ,p>=1 s(p,p)=1 ,p>=0
遞推關系的說明：
考慮第p個物品，p可以單獨構成一個非空循環排列，這樣前p-1種物品構成k-1個非空循環排列，方法數為s(p-1,k-1)；
也可以前p-1種物品構成k個非空循環排列，而第p個物品插入第i個物品的左邊，這有(p-1)*s(p-1,k)種方法。
第二類S(p,k)的一個組合學解釋是：將p個物體劃分成k個非空的不可辨別的（可以理解為盒子沒有編號）集合的方法數。
k!S(p,k)是把p個人分進k間有差別(如：被標有房號）的房間(無空房）的方法數。
S(p,k)的遞推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1
邊界條件：S(p,p)=1 ,p>=0 S(p,0)=0 ,p>=1
遞推關系的說明：
考慮第p個物品，p可以單獨構成一個非空集合，此時前p-1個物品構成k-1個非空的不可辨別的集合，方法數為S(p-1,k-1)；
也可以前p-1種物品構成k個非空的不可辨別的集合，第p個物品放入任意一個中，這樣有k*S(p-1,k)種方法。
PS：第一類斯特林數和第二類斯特林數有相同的初始條件，但遞推關系不同。
Stirling's approximation
快速求階乘，不推薦用於競賽。
數論
GCD&LCM
//GCD
function gcd(a,b:longint):longint;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
//LCM
function lcm(a,b:longint):longint;
begin
if a<b then swap(a,b);
lcm:=a;
while lcm mod b>0 do inc(lcm,a);
end;
素數
//單個判斷
function prime (n: longint): boolean;
var i longint;
begin
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then exit(false)
exit(true);
end;
//篩法打表
procere main;
var i,j:longint;
begin
fillchar(f,sizeof(f),true);
f[0]:=false;f[1]:=false;
for i:=2 to trunc(sqrt(maxn)) do
if f[i] then
begin
j:=2*i;
while j<= maxn do
begin
f[j]:=false;
inc(j,i);
end;
end;
end;
快速冪
{a^b mod n}
function f(a,b,n:int64):int64;
var t,y:int64;
begin
t:=1;
y:=a;
while b<>0 do
begin
if(b and 1)=1 then t:=t*y mod n;
y:=y*y mod n;
{這里用了一個很強大的技巧,y*y即求出了a^(2^(i-1))不知道這是什麼的看原理}
b:=b shr 1;{去掉已經處理過的一位}
end;
exit(t);
end;
模運演算法則
(A+B) mod C = (A mod C + B mod C) mod C
(A-B) mod C = (A mod C - B mod C) mod C
(A * B) mod C = (A mod C) * (B mod C) mod C
(A / B) mod C = ???
Ⅳ Noip主要是考什麼普及組的C++，主要考什麼
一、試題形式
每次NOIP的試題分四組：普及組初賽題A1、普及組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中，A1和B1類型基本相同，A2和B2類型基本相同，但題目不完全相同，提高組難度高於普及組。
（一）初賽
初賽全部為筆試，2小時，滿分100分。試題由四部分組成：1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），後10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。普及組20個都是單選題。
2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的演算法，並推算出問題的解。考生給出的答案與標准答案相同，則得分；否則不得分。
3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關於程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。輸出與標准答案一致，則得分；否則不得分。
4、程序完善題：共2題，每題14分，共計28分。題目給出一段關於程序功能的文字說明，然後給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分並在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。
（二）復賽
復賽的題型和考試形式與NOI類似，全部為上機編程題，但難度比NOI低。每天3.5小時。普及組考一天，共4題，每題100分，共計400分；提高組考兩天，每天3題，共6題，每題100分，共計600分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時，測試程序為每道題提供了5-10組測試數據，考生程序每答對一組得10－20分，累計分即為該道題的得分。
五、試題的知識范圍
（一）初賽內容與要求：
計 基 算 本 機 常 的 識
1．計算機和信息社會（信息社會的主要特徵、計算機的主要特徵、數字通信網路的主要特徵、數字化）
2．信息輸入輸出基本原理（信息交換環境、文字圖形多媒體信息的輸入輸出方式）
3．信息的表示與處理（信息編碼、微處理部件MPU、內存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構）
4．信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、資料庫管理）
5．信息系統組成及互連網的基本知識（計算機構成原理、槽和埠的部件間可擴展互連方式、層次式的互連結構、互聯網路、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）
6．人機交互界面的基本概念（窗口系統、人和計算機交流信息的途徑（文本及交互操作））
7．信息技術的新發展、新特點、新應用等。
計 基 算 本 機 操 的 作
1. Windows和LINUX的基本操作知識
2. 互聯網的基本使用常識 （網上瀏覽、搜索和查詢等）
3. 常用的工具軟體使用（文字編輯、電子郵件收發等）
程序設計的基本知識數據結構
1．程序語言中基本數據類型(字元、整數、長整、浮點)
2. 浮點運算中的精度和數值比較
3．一維數組（串）與線性表
4．記錄類型（PASCAL）/ 結構類型（C）
程序設計
1．結構化程序設計的基本概念
2．閱讀理解程序的基本能力
3．具有將簡單問題抽象成適合計算機解決的模型的基本能力
4．具有針對模型設計簡單演算法的基本能力
5．程序流程描述（自然語言/偽碼/NS圖/其他）
6．程序設計語言（PASCAL/C/C++）
基本 演算法 處理
1．初等演算法（計數、統計、數學運算等）
2．排序演算法（冒泡法、插入排序、合並排序、快速排序）
3．查找（順序查找、二分法）
4．回溯演算法
（二）復賽內容與要求：
在初賽內容的基礎上增加以下內容：
數據結構
1．指針類型
2．多維數組
3．單鏈表及循環鏈表
4．二叉樹
5．文件操作（從文本文件中讀入數據，並輸出到文本文件中）
程序設計
1．演算法的實現能力
2．程序調試基本能力
3．設計測試數據的基本能力
4．程序的時間復雜度和空間復雜度的估計
演算法處理
1．離散數學知識的應用（如排列組合、簡單圖論、數理邏輯）
2．分治思想
3．模擬法
4．貪心法
5．簡單搜索演算法（深度優先 廣度優先）搜索中的剪枝
6．動態規劃的思想及基本演算法
Ⅵ 極高分求 noip 常用演算法 c++源碼
什麼？是C++……無奈，我手頭的程序都是PASCAL的……
1、初等演算法
2、高精度的四則運算
3、查找演算法（順序查找、二分法、哈希查找等等）
這三個較簡單，在網路上搜索即可
4、排序演算法
其實只需要背快排、堆排即可，其他的速度比較慢不推薦
5、分枝限界法
網路搜索
6、圖的演算法
floodfill：
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
int main(void)
{
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
int maxx, maxy;
/* initialize graphics, local variables */
initgraph(&gdriver, &gmode, "");
/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk)
/* an error occurred */
{
printf("Graphics error: %s\n",
grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1);
/* terminate with an error code */
}
maxx = getmaxx();
maxy = getmaxy();
/* select drawing color */
setcolor(getmaxcolor());
/* select fill color */
setfillstyle(SOLID_FILL, getmaxcolor());
/* draw a border around the screen */
rectangle(0, 0, maxx, maxy);
/* draw some circles */
circle(maxx / 3, maxy /2, 50);
circle(maxx / 2, 20, 100);
circle(maxx-20, maxy-50, 75);
circle(20, maxy-20, 25);
/* wait for a key */
getch();
/* fill in bounded region */
floodfill(2, 2, getmaxcolor());
/* clean up */
getch();
closegraph();
return 0;
}
7、其他：
KMP:
#include<iostream>
#include<time.h>
#include<string>
using namespace std;
void init(string ,string);
void show(char [],int);
int kmp(string ,string,int pos);
void get_next(char*,int *);
string s1,t1;
int m,n;
char *s;
char *t;
int *next;
/*************************MAIN**************************************/
int main(int argc[],char*args[])
{
double t=clock();
cout<<"找到位置為："<<kmp("acbsabcaacabaabaabcacaabc","abaabca",1)<<endl;
delete[] s;
delete[] next;
cout<<"耗時："<<(clock()-t)/1000<<"毫秒！"<<endl;
return 0;
}
/**********************++++NEXT++++********************************/
void get_next(char s[],int ne[])
{
ne =new int[n+1];
next=new int[n+1];
ne[0]=9999;
int i(1),j(0);
ne[1]=0;
while(i<=(int)(t[0]))//數組是字元型的，要轉化為整數
{
if(j==0||t[i]==t[j]){++i;++j;ne[i]=j;}
else j=ne[j];
}
for( i=1;i<=n;i++)
{
cout<<"next["<<i<<"]="<<ne[i]<<endl;
next[i]=ne[i];
}
}
/********************++++KMP+++**********************************/
int kmp(string s0,string t0,int pos)
{
init(s0,t0);
int i=pos,j=1;
while(i<=((int)(s[0]))&&(j<=((int)(t[0]))))
{
if((j==0)||(s[i]==t[j])){++i;++j;}
else j=next[j];
}
if(j>(int)(t[0])) return i-((int)(t[0]));
else return 0;
}
/**********************************************************/
void init(string ss,string tt)
{ s1=ss;
t1=tt;
m=s1.length();
n=t1.length();
//if((s=(char*)malloc((m+1)*sizeof(char)))<0){cout<<"failed\n";return;}
s=new char[m+1];
s[0]=m;
//if((t=(char*) malloc((n+1)*sizeof(char)))<0) {cout<<"failed\n";return;}
t=new char[n+1];
t[0]=n;
for(int i=1;i<=m;i++)
s[i]=s1.at(i-1);
for( i=1;i<=n;i++)
t[i]=t1.at(i-1);
cout<<"原字元串"; show(s,m);
cout<<"模式字元串： "; show(t,n);
get_next(t,next);
}
/*******************++++SHOW+++**************************************/
void show(char s[],int n )
{
for(int i=1;i<=n;i++)
cout<<s[i]<<" ";
cout<<endl;
cout<<"length： "<<int(s[0])<<"\n";
}
prim:
#include <stdio.h>
#define INFINITY 32767
#define MAX 4
typedef struct{
int vexnum;
int arcs[MAX][MAX];
}Graph;//圖的結構體
//*****************創建圖的鄰接矩陣 *****************
void Creat_Graph(Graph *g)
{
int i,j,v1,v2,w,num;
printf("please input vertex number:\n");
scanf("%d",&num);
g->vexnum=num;
for(i=0;i<num;i++)
for(j=0;j<num;j++)
if(i==j)
g->arcs[i][j]=0; //無環，對角線為0
else
g->arcs[i][j]=INFINITY;
printf("please input vertex ,vertex ,weight :(end with -1,-1)\n");
do
{ printf("<vertex1,vertex2,weight>:");
scanf("%d,%d,%d",&v1,&v2,&w);
if(v1>=0&&v1<num&&v2>=0&&v2<num)
{
g->arcs[v1][v2]=w;
g->arcs[v2][v1]=w;
}
}while(!(v1==-1&&v2==-1));//循環的條件
}
Kruskal:
#include<iostream>
#include<vector>
#include<algorithm>
#define max 100
using namespace std;
struct Edge{
int vi,vj,w;
};
bool lequal(Edge const* t1, Edge const* t2){
return (t1->w<t2->w);
}
int V,E;
vector <Edge*>edges;
vector <Edge*>mst;
int cicles[max];
int main(){
int i,W,number,c;
Edge *e;
c=1;
while(true){
edges.clear();
mst.clear();
cin>>V>>E;
if(!V && !E) break;
for(i=0;i<E;i++){
e = new Edge;
cin>>e->vi>>e->vj>>e->w;
edges.push_back(e);
}
sort(edges.begin(),edges.end(),lequal);
for(i=0;i<V;i++) cicles[i] = i;
while(mst.size()<(V-1) && edges.size()){
if(cicles[edges[0]->vi]!=cicles[edges[0]->vj]){
number = cicles[edges[0]->vj];
for(i=0;i<V;i++) {
if(cicles[i]==number)
cicles[i] = cicles[edges[0]->vi];
}
mst.push_back(edges[0]);
}
edges.erase(edges.begin(),edges.begin()+1);
}
W = 0;
for(i=0;i<mst.size();i++) {
W+=mst[i]->w;
}
cout<<"Case "<<c++<<":"<<endl;
cout<<"The Minimun Spanning Tree has cost: "<<W<<endl;
}
return 0;
}
floyd:
program floyd;
var st,en,f:integer;
n,i,j,x:integer;
a:array[1..10,1..10]of integer;
path,map1,map2:array[1..10,1..10]of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(a[i,j]);
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
writeln;
f:=st;
while f<> en do
begin
write(f);
write('=>');
f:=path[f,en];
end;
write(en);
end.
完畢
Ⅶ 關於初中的NOIP問題
這是我從
中華信息學競賽網http://www.100xinxi.com/上
復制過來的NOIP大綱,你自己看看吧,還什麼不懂的,你直接去那看吧``(中華信息學競賽網)
由中國計算機學會負責組織的全國青少年信息學奧林匹克聯賽（National Olympiad in Informatics in Provinces, 簡稱NOIP）是全國信息學奧林匹克競賽（NOI）系列活動中的一個重要組成部分，旨在向中學生普及計算機基礎知識，培養計算機科學和工程領域的後備人才。普及的重點是根據中學生的特點，培養學生學習計算機的興趣，使得他們對信息技術的一些核心內容有更多的了解，提高他們創造性地運用程序設計知識解決實際問題的能力。對學生的能力培養將注重以下的幾個方面：
1.想像力與創造力；
2.對問題的理解和分析能力；
3.數學能力和邏輯思維能力；
4.對客觀問題和主觀思維的口頭和書面表達能力；
5.人文精神：包括與人的溝通能力，團隊精神與合作能力，恆心和毅力，審美能力等。
二、命題程序和組織機構
命題是考核和選拔過程中的重要一環，對計算機的普及的內容具有導向性作用。命題應注重趣味性、新穎性、知識性、應用性和中學生的心智特點，不直接從大學專業教材中選題。
在命題和審題工作中，堅持開放和規范的原則。在NOI科學委員會主持下成立的NOIP命題委員會負責命題工作，命題委員會成員主要來自參加NOIP的省（ 包括直轄市、自治區，下同。每個省最多派一名委員），也可來自社會計算機界。NOIP命題委員會的主要職責是提供NOIP的備選題目，並承擔對所提供的題目保密的責任。
1. NOIP命題委員會委員應具備如下資格：
從事一線計算機教學或信息學奧賽輔導工作兩年（含）以上；
有精力和時間從事該項工作；
對此項工作有興趣並願意作為志願者從事NOIP命題及其相關工作。
2. NOIP命題委員會委員的產生過程：
本人提出申請（填寫表格）；
中學教師需得到所在單位同意或省奧賽主管部門同意；
科學委員會批准，由中國計算機學會頒發聘書（每一聘期為兩年）。
3. NOIP命題委員會委員的職責：
每年為NOIP提供備選題題目若干，在9月1日之前提交科學委員會；
備選試題的保密期為2年，在該段時間內不得泄密或另作他用；
搜集本省信息學奧賽的有關信息並向科學委員會通報；
4. 題目一經提交，即表明同意授權中國計算機學會科學委員會全權處理，包括使用、修改和出版。試題原型被科學委員會採用後，中國計算機學會將為命題者頒發試題錄用證書，並頒發酬金。無論是委員提交的題目還是科學委員會直接提交的題目，試題版權均歸中國計算機學會所有。NOIP所用試題由科學委員會確定，這些試題可能從備選題庫中選取並做適當修改後成型，也可能直接命題。
三、競賽形式和成績評定
NOIP分兩個等級組：普及組和提高組。每組競賽分兩輪：初試和復試。
初試形式為筆試，側重考察學生的計算機基礎知識和編程的基本能力，並對知識面的廣度進行測試。初試為資格測試，獲本省初試成績在本賽區前
15%的學生進入復賽。
復試形式為上機編程，著重考察學生對問題的分析理解能力，數學抽象能力，編程語言的能力和編程技巧、想像力和創造性等。各省NOIP的等第獎在復試的優勝者中產生。
比賽中使用的程序設計語言是：
初賽：PASCAL或C/C++：
復賽：PASCAL或C/C++。
每年復賽結束後，各省必須在指定時間內將本省一等獎候選人的有關情況、源程序和可執行程序報送科學委員會。經復審和評測後，由中國計算機學會報送中國科協和教育部備案。中國計算機學會對各省獲NOIP二等獎和三等獎的分數線或比例提出指導性意見，各省可按照成績確定獲獎名單。
四、試題形式
每次NOIP的試題分四組：普及組初賽題A1、普及組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中，A1和B1類型基本相同，A2和B2類型基本相同，但題目不完全相同，提高組難度高於普及組。
（一）初賽
初賽全部為筆試，滿分100分。試題由四部分組成：
1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），後10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。普及組20個都是單選題。
2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的演算法，並推算出問題的解。考生給出的答案與標准答案相同，則得分；否則不得分。
3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關於程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。輸出與標准答案一致，則得分；否則不得分。
4、程序完善題：共2題，每題14分，共計28分。題目給出一段關於程序功能的文字說明，然後給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分並在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。
（二）復賽
復賽的題型和考試形式與NOI類似，全部為上機編程題，但難度比NOI低。題目包括4道題，每題100分，共計400分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時，測試程序為每道題提供了5-10組測試數據，考生程序每答對一組得10－20分，累計分即為該道題的得分。
五、試題的知識范圍
（一）初賽內容與要求：
計基
算本
機常
的識 1．計算機和信息社會（信息社會的主要特徵、計算機的主要特徵、數字通信網路的主要特徵、數字化）
2．信息輸入輸出基本原理（信息交換環境、文字圖形多媒體信息的輸入輸出方式）
3．信息的表示與處理（信息編碼、微處理部件MPU、內存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構）
4．信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、資料庫管理）
5．信息系統組成及互連網的基本知識（計算機構成原理、槽和埠的部件間可擴展互連方式、層次式的互連結構、互聯網路、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）
6．人機交互界面的基本概念（窗口系統、人和計算機交流信息的途徑（文本及交互操作））
7．信息技術的新發展、新特點、新應用等。
計基
算本
機操
的作 1. Windows和LINUX的基本操作知識
2. 互聯網的基本使用常識 （網上瀏覽、搜索和查詢等）
3. 常用的工具軟體使用（文字編輯、電子郵件收發等）
程
序
設
計
的
基
本
知
識
數
據
結
構 1．程序語言中基本數據類型(字元、整數、長整、浮點)
2. 浮點運算中的精度和數值比較
3．一維數組（串）與線性表
4．記錄類型（PASCAL）/ 結構類型（C）
程
序
設
計 1．結構化程序設計的基本概念
2．閱讀理解程序的基本能力
3．具有將簡單問題抽象成適合計算機解決的模型的基本能力
4．具有針對模型設計簡單演算法的基本能力
5．程序流程描述（自然語言/偽碼/NS圖/其他）
6．程序設計語言（PASCAL/C/C++）- 2003仍允許BASIC
基本
演算法
處 理 1．初等演算法（計數、統計、數學運算等）
2．排序演算法（冒泡法、插入排序、合並排序、快速排序）
3．查找（順序查找、二分法）
4．回溯演算法
（二）復賽內容與要求：
在初賽內容的基礎上增加以下內容：
數
據
結
構 1．指針類型
2．多維數組
3．單鏈表及循環鏈表
4．二叉樹
5．文件操作（從文本文件中讀入數據，並輸出到文本文件中）
程
序
設
計 1．演算法的實現能力
2．程序調試基本能力
3．設計測試數據的基本能力
4．程序的時間復雜度和空間復雜度的估計
算
法
處
理 1．離散數學知識的應用（如排列組合、簡單圖論、數理邏輯）
2．分治思想
3．模擬法
4．貪心法
5．簡單搜索演算法（深度優先 廣度優先）搜索中的剪枝
6．動態規劃的思想及基本演算法
六、試題保密紀律
關於保密以及考試的紀律見NOI條例。NOIP主辦單位中國計算機學會負責NOIP的紀律監察工作並接受投訴，加強過程監管，防止賽題泄漏、考場舞弊、弄虛作假等現象的發生。一旦查實命題委員會委員泄密備選試題，考場泄題或舞弊，或篡改試卷和考試成績者，主辦單位將根據NOI條例及其有關規則予以懲罰。
Ⅷ 關於NOIP
NOIP級別中，普及組和提高組的要求不同。
但是這幾類動規的題目掌握了，基本也就可以了：
1、背包問題：01背包、完全背包、需要構造的多維01背包
詳見背包九講
2、最大降序：例如打導彈
3、矩陣相乘：例如能量珠子
4、買股票
5、方格取數：單向的、雙向的
6、三角取數
這些都是簡單的動規的應用，必須掌握，背也要背出來，還要會套用。
至於排序，本人認為基本的選擇排序大家都會，快速排序是一定要會的，當數據規模<500時用選擇排序，當數據規模在500和100000之間是用快速排序，但是NOIP中經常考到基數排序，例如劃分數線等，數據規模會達到1000000，用其他的排序法可能會超時一兩個測試點。
至於搜索，那是必須掌握的深搜、廣搜都要會，主要是深搜，當提高組碰到一下子想不出動規的狀態轉移方程式，深搜窮舉也是可行的，一般都能拿到不少的分數。個人之間廣搜的用處不大，程序復雜而且爆機率很高。當然n個for的窮舉法在不得已的時候也能得不少分，只要if剪枝的好，對付八後問題等問題時，時間效率比很高。
另外就是圖的遍歷，有關圖的最小生成樹、圖的單源最短路徑，也是需要很好地掌握，一直會考。當然，深搜的本事高的人可以用深搜搞定。
總結如下：要得一等，必須對模擬法和窮舉法有深刻的體會，並知道很多變通的手段；對快排要背的滾瓜爛熟；對深搜要做到不管是貪心還是動規的題，都能用深搜實現，只不過少量點超時而已；動規要記住六大模型，然後背包要理解透徹；數學很重要，數學分析的題要做對，例如排組合、凸包、計算幾何近幾年常考。有了這些，一等可以穩拿。
Ⅸ 學C語言的NOIP問題
一．選擇一個正確答案代碼（A/B/C/D/E）,填入每題的括弧內 (每題1.5分, 共30分)
1. 美籍匈牙利數學家馮·諾依曼對計算機科學發展所做出的貢獻是（ ）。
A. 提出理想計算機的數學模型，成為計算機科學的理論基礎。
B. 是世界上第一個編寫計算機程序的人。
C. 提出存儲程序工作原理，並設計出第一台具有存儲程序功能的計算機EDVAC。
D. 採用集成電路作為計算機的主要功能部件。
E. 指出計算機性能將以每兩年翻一番的速度向前發展。
2. 下列哪個不是CPU（中央處理單元）（ ）。
A. Intel Itanium B. DDR SDRAM C. AMD Athlon64
D. AMD Opteron E. IBM Power 5
3. 下列網路上常用的名字縮寫對應的中文解釋錯誤的是（ ）。
A. WWW（World Wide Web）：萬維網。
B. URL（Uniform Resource Locator）：統一資源定位器。
C. HTTP（Hypertext Transfer Protocol）：超文本傳輸協議。
D. FTP（File Transfer Protocol）：快速傳輸協議。
E. TCP（Transfer Control Protocol）：傳輸控制協議。
4. 下面哪個部件對於個人桌面電腦的正常運行不是必需的（ ）。
A. CPU B. 圖形卡（顯卡） C. 光碟機 D. 主板 E. 內存
5. 下列哪個軟體屬於操作系統軟體（ ）。
A. Microsoft Word B. 金山詞霸 C. Foxmail D. WinRAR E. Red Hat Linux
6. 下列哪個不是計算機的存儲設備（ ）。
A. 文件管理器 B. 內存 C. 高速緩存 D. 硬碟 E. U盤
7. 下列說法中錯誤的是（ ）。
A. CPU的基本功能就是執行指令。
B. CPU訪問內存的速度快於訪問高速緩存的速度。
C. CPU的主頻是指CPU在1秒內完成的指令周期數。
D. 在一台計算機內部，一個內存地址編碼對應唯一的一個內存單元。
E. 數據匯流排的寬度決定了一次傳遞數據量的大小，是影響計算機性能的因素之一。
8. 彩色顯示器所顯示的五彩斑斕的色彩，是由紅色、藍色和（ ）色混合而成的。
A. 紫 B. 白 C. 黑 D. 綠 E. 橙
9. 用靜電吸附墨粉後轉移到紙張上，是哪種輸出設備的工作方式（ ）。
A. 針式列印機 B. 噴墨列印機 C. 激光列印機 D. 筆式繪圖儀 E. 噴墨繪圖儀
10. 一台計算機如果要利用電話線上網，就必須配置能夠對數字信號和模擬信號進行相互轉換的設備，這種設備是（ ）。
A. 數據機 B. 路由器 C. 網卡 D. 網關 E. 網橋
11. 下列哪個不是資料庫軟體的名稱（ ）。
A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro
12. 下列哪個程序設計語言不支持面向對象程序設計方法（ ）。
A. C++ B. Object Pascal C. C D. Smalltalk E. Java
13. 由3個a，1個b和2個c構成的所有字元串中，包含子串「abc」的共有（ ）個。
A. 20 B. 8 C. 16 D. 12 E. 24
14. 某個車站呈狹長形，寬度只能容下一台車，並且只有一個出入口。已知某時刻該車站狀態為空，從這一時刻開始的出入記錄為：「進，出，進，進，出，進，進，進，出，出，進，出」。假設車輛入站的順序為1，2，3，……，則車輛出站的順序為（ ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7
15. 二叉樹T，已知其前序遍歷序列為1 2 4 3 5 7 6，中序遍歷序列為4 2 1 5 7 3 6，則其後序遍歷序列為（ ）。
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1
16. 滿二叉樹的葉結點個數為N，則它的結點總數為（ ）。
A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
17. 十進制數2004等值於八進制數（ ）。
A. 3077 B. 3724 C. 2766 D. 4002 E. 3755
18. (2004)10 + (32)16的結果是（ ）。
A. (2036)10 B. (2054)16 C. (4006)10 D. (100000000110)2 E. (2036)16
19. 在下圖中，從頂點（ ）出發存在一條路徑可以遍歷圖中的每條邊一次，而且僅遍歷一次。
A. A點 B. B點 C. C點 D. D點 E. E點
20. 某大學計算機專業的必修課及其先修課程如下表所示：
課程代號 C0 C1 C2 C3 C4 C5 C6 C7
課程名稱 高等數學 程序設計語言 離散數學 數據結構 編譯技術 操作系統 普通物理 計算機原理
先修課程 C0, C1 C1, C2 C3 C3, C7 C0 C6
請你判斷下列課程安排方案哪個是不合理的（ ）。
A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5
C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4
E. C0, C1, C2, C3, C6, C7, C5, C4
二．問題求解 （每題5分，共10分）
1. 一個傢具公司生產桌子和椅子。現在有113個單位的木材。每張桌子要使用20個單位的木材，售價是30元；每張椅子要使用16個單位的木材，售價是20元。使用已有的木材生產桌椅（不一定要把木材用光），最多可以賣 元錢。
2. 75名兒童到游樂場去玩。他們可以騎旋轉木馬，坐滑行鐵道，乘宇宙飛船。已知其中20人這三種東西都玩過，55人至少玩過其中的兩種。若每樣乘坐一次的費用是5元，游樂場總共收入700，可知有 名兒童沒有玩過其中任何一種。
三．閱讀程序 （每題8分，共32分）
1．#include <stdio.h>
int main(){
int a = 79, b = 34, c = 57, d = 0, e = -1;
if (a < c || b > c) d = d + e;
else if (d + 10 < e) d = e + 10;
else d = e - a;
printf("%d\n", d);
return 0;
}
輸出： 。
2．#include <stdio.h>
int main(){
int i, j;
char str1[] = "pig-is-stupid";
char str2[] = "clever";
str1[0] = 'd'; str1[1] = 'o';
for (i = 7, j = 0; j < 6; i++, j++)
str1[i] = str2[j];
printf("%s\n", str1);
return 0;
}
輸出： 。
3．#include <stdio.h>
int main(){
int u[4], a, b, c, x, y, z;
scanf("%d %d %d %d",&(u[0]), &(u[1]), &(u[2]), &(u[3]));
a = u[0] + u[1] + u[2] + u[3] - 5;
b = u[0] * (u[1] - u[2] / u[3] + 8);
c = u[0] * u[1] / u[2] * u[3];
x = (a + b + 2) * 3 - u[(c + 3) % 4];
y = (c * 100 - 13) / a / (u[b % 3] * 5);
if ((x + y) % 2 == 0) z = (a + b + c + x + y) / 2;
z = (a + b + c – x - y) * 2;
printf("%d\n", x + y - z);
return 0;
}
輸入：2 5 7 4
輸出： 。
4．#include <stdio.h>
char c[3][200];
int s[10], m, n;
void numara(){
int i, j, cod, nr;
for (j = 0; j < n; j++){
nr = 0; cod = 1;
for (i = 0; i < m; i++){
if (c[i][j] == '1'){
if (!cod){cod = 1; s[nr]++; nr = 0;}
}
else{
if (cod){nr = 1; cod = 0;}
else nr++;
}
}
if (!cod) s[nr]++;
}
}
int main(){
int i;
scanf("%d %d\n", &m, &n);
for (i = 0; i < m; i++) gets(c[i]);
numara();
for (i = 1; i <= m; i++)
if (s[i] != 0) printf("%d %d ", i, s[i]);
return 0;
}
輸入：
3 10
1110000111
1100001111
1000000011
輸出： 。
四、完善程序 (前4空，每空2分，後5空，每空4分，共28分)
1．三角形內切圓的面積
題目描述:
給出三角形三邊的邊長，求此三角形內切圓（如下圖所示，三角形的內切圓是和三角形三邊都相切的圓）的面積。
輸入:
三個正實數a、b、c（滿足a+b>c，b+c>a，c+a>b）, 表示三角形三邊的邊長。
輸出:
三角形內切圓的面積，結果四捨五入到小數點後面2位。
輸入樣例:
3 4 5
輸出樣例:
3.14
程序：
#include <stdio.h>
#include <math.h>
int main(){
float a, b, c, r, s, t;
scanf("%f %f %f", &a, &b, &c);
s = ( ① ) / 2;
t = ② (s * (s - a) * (s - b) * (s - c));
r = t / s;
printf(" ③ \n", 3.1415927 * r * ④ );
return 0;
}
2．Joseph
題目描述:
原始的Joseph問題的描述如下：有n個人圍坐在一個圓桌周圍，把這n個人依次編號為1，…，n。從編號是1的人開始報數，數到第m個人出列，然後從出列的下一個人重新開始報數，數到第m個人又出列，…，如此反復直到所有的人全部出列為止。比如當n=6，m=5的時候，出列的順序依次是5，4，6，2，3，1。
現在的問題是：假設有k個好人和k個壞人。好人的編號的1到k，壞人的編號是k+1到2k。我們希望求出m的最小值，使得最先出列的k個人都是壞人。
輸入:
僅有的一個數字是k（0 < k <14）。
輸出:
使得最先出列的k個人都是壞人的m的最小值。
輸入樣例:
4
輸出樣例:
30
程序：
#include <stdio.h>
long k, m, begin;
int check(long remain){
long result = ( ① ) % remain;
if ( ② ){
begin = result; return 1;
}
else return 0;
}
int main(){
long i, find = 0;
scanf("%ld", &k);
m = k;
while( ③ ) {
find = 1; begin = 0;
for (i = 0; i < k; i++)
if (!check( ④ )){
find = 0; break;
}
m++;
}
printf("%ld\n", ⑤ );
return 0;
}
賽區 市 學校 姓名
========================== 密 封 線 =======================
第九屆全國青少年信息學奧林匹克聯賽初賽試題
普及組答卷紙
閱 卷 記 錄
總閱卷人 總 得 分
第 一 大 題 得 分 第二大題得分
題號 1 2 3 4 5 6 7 8 9 10 第三大題得分
得分 1) 2) 3) 4)
題號 11 12 13 14 15 16 17 18 19 20 第四大題得分
得分 (1) (2)
============================ 以下由考生填寫 ==============================
答卷部分
一. 選擇一個正確答案代碼（A/B/C/D）,填入每題的括弧內 (每題1.5分,多選無分, 共30 分)
題號 1 2 3 4 5 6 7 8 9 10
選擇
題號 11 12 13 14 15 16 17 18 19 20
選擇
二．問題解答 （每題5分，共10分）
1. 答：
2. 答：
三. 閱讀程序，並寫出程序的正確運行結果：（每題8分，共32分）
（1） 程序的運行結果是:
(2) 程序的運行結果是:
賽區 市 學校 姓名
========================== 密 封 線 =======================
（3） 程序的運行結果是:
（4）程序的運行結果是:
四.根據題意, 將程序補充完整 (前4空，每空2分，後5空，每空4分，共28分)
C 語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
①
②
③
④
2.
①
②
③
④
⑤
第九屆全國青少年信息學奧林匹克聯賽初賽試題
普及組參考答案
一. 選擇一個正確答案代碼（A/B/C/D/E）,填入每題的括弧內 (每題1.5分,多選無分, 共30 分)
題號 1 2 3 4 5 6 7 8 9 10
選擇 C B D C E A B D C A
題號 11 12 13 14 15 16 17 18 19 20
選擇 D C D E B C B D E D
二．問題解答 （每題5分，共10分）
1. 答： 160
2. 答： 10
三. 閱讀程序，並寫出程序的正確運行結果：（每題8分，共32分）
（1）程序的運行結果是: -80
(2) 程序的運行結果是: dog-is-clever
（3）程序的運行結果是: 263
（4）程序的運行結果是: 1 4 2 1 3 3
四.根據題意, 將程序補充完整 (前4空，每空2分，後5空，每空4分，共28分)
C 語言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
① a+b+c
② sqrt
③ %.2f
④ r
2.
① begin+m-1
② result>=k (或者k<=result)
③ !find (或者 find==0)
④ 2*k-i
⑤ m-1
參考資料：www.noi.cn