目錄

模擬的概念

例1：開關燈

算法思路：

代碼如下：

輸入輸出：

例2：序列操作和查詢

算法思路：

代碼如下：

輸入輸出：

例3：數組折疊

算法思路：

代碼如下：

例4：數字消除

算法思路

代碼如下：

作業1：角谷猜想

作業2：校門外的樹

作業3：乒乓球

---

模擬的概念

模擬算法就是模擬題目給的操作，用代碼一步一步的描述出來即可。在過程中使用的都是我們已知的各種方法，如數組元素調用、排序、枚舉等等，只是這些過程一般比較復雜。本次課程主要針對一維數組的模擬。

在各類算法競賽中，包括CSP-J/S，NOIP等競賽，經常會出現各類“模擬題目”，遇到這種題大家不需要害怕，甚至可以將其作為“送分題”，因為你只需要按照題目敘述的方式來寫程序就能得到最終答案。模擬不是一種算法，而是一種技巧，要想掌握模擬題目，就需要多讀題、多整理細節問題。

例1：開關燈

【描述】有n盞燈，從1到N按順序依次編號，初始時所有燈都處于開啟狀態；有m個人，從1到m依次編號。第一個人將燈全部關閉，第二個人將編號為2的倍數的燈打開，第三個人將編號為3的倍數的燈做相反處理（即將打開的燈關閉，將關閉的燈打開）。依照編號遞增順序，以后的人都一樣，將凡是自己編號倍數的燈做相反處理。請問：當第m個人操作之后，哪幾盞燈是關閉的，按從小到大輸出其編號，用逗號間隔。

【輸入】一行，n和m，空格隔開

【輸出】順次輸出關閉的燈的編號,用逗號隔開

【輸入樣例】10 1010

【輸出樣例】1,4,9

算法思路：

這個問題是一個經典的編程問題，通常被稱為“燈泡問題”或“約瑟夫環問題”的變體。問題的核心在于模擬每個人對燈的操作，并跟蹤每盞燈的狀態。以下是解決這個問題的詳細思路：

?1. 初始化

- 創建一個數組 `lights`，長度為 `n+1`（因為燈的編號從1到n），初始時所有燈都設置為開啟狀態（例如，可以用 `true` 表示開啟）。

?2. 模擬操作

? - 對于每個人（從1到m），執行以下操作：
? - 遍歷所有燈，找到編號是當前人編號的倍數的燈。
? - 切換這些燈的狀態（如果燈是開啟的，則關閉；如果燈是關閉的，則開啟）。

3. 狀態切換

? - 燈的狀態切換可以通過簡單地取反數組中對應位置的值來實現。例如，如果 `lights[j]` 是? `true`，則將其設置為 `false`，反之亦然。

?4. 收集結果

? - 在所有人操作完成后，遍歷 `lights` 數組，收集所有關閉的燈的編號。

?5. 輸出結果

? - 將收集到的關閉的燈的編號按從小到大的順序輸出，編號之間用逗號隔開。

代碼如下：

#include <iostream>
using namespace std;
int main(){bool lights[1000];int n,m;cin>>n>>m;for(int i=1;i<=n;i++){lights[i]=true;}for(int i=1;i<=m;i++){for(int j=i;j<=n;j=j+i)lights[j]=!lights[j];}int cnt=0;for(int i=1;i<=n;i++){if(!lights[i]){cnt++;if(cnt==1) cout<<i;else cout<<","<<i;}	}

輸入輸出：

例2：序列操作和查詢

【描述】現有一個長度為n的數組，對這個數組進行m次操作，可以對數組進行的操作分為以下三類：

輸入1 i： 表示輸出數組中第i個元素的值；

輸入2 i v：表示在數組中第i個元素前加入新的元素v；

輸入3 i：表示刪除數組中的第i個元素。

注意：三類操作都要滿足 i <= n。經過m輪操作后，輸出的是哪些數字，每行一個數字。

【輸入】第1行一個整數n，表示數組的初始長度；第2行是n個用空格間隔的數，表示原始的數組；第3行是整數m，表示操作次數。接下來m行是m次操作指令，每個指令一行（題目描述中的三類操作中的一種）。

【輸出】對于第一種操作輸出對應的答案，一行輸出一個數。

算法思路：

對題目的要求一步一步的實行，先保證數組的輸入以后，需要對三種情況進行分類處理。第一種處理里面有輸出，后面兩種都是在操作。操作的要點是數組的插入和刪除。

插入的話，就要求插入位置后面所有數字向后移動一步，實現a[i+1]=a[i]的操作；

而刪除則需要當前位置后面所有的數字向前移動一步，實現a[i]=a[i+1]。這里需要注意移動的方向，要從頭移動。

代碼如下：

using namespace std;
int main(){int a[1000];int n,m,p,q,v;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cin>>m;for(int i=1;i<=m;i++){cin>>p;if(p==1){cin>>q;cout<<a[q]<<endl;}else if(p==2){cin>>q>>v;for(int j=n;j>=q;j--)a[j+1]=a[j];a[q]=v;n++;}else{//p=3cin>>q;for(int j=q;j<n;j++)a[j]=a[j+1];n--;}}
}

輸入輸出：

例3：數組折疊

【描述】李雷和韓梅梅在玩數組折疊游戲，游戲規則是，給出n個整數，按照從左到右的順序排列，現在需要將這列整數從中間折疊m次，右邊的疊加到左邊，每次折疊后，重合的兩個數字會相加變成一個新的數字。請你輸出折疊m次后的s數組。
【輸入】第1行是整數n和m；第2行是數組中的n個整數

【輸出】1行。折疊m次后的數組元素

算法思路：

數組對折，需要把后半部分移動到前半部分對應位置進行數組相加，所以移動次數為n/2（即循環次數），然后需要進行的就是數組加法，最后要對數組長度也做n/2的操作，但是這里需要注意的是，如果長度是奇數不能只是簡單的n/2哦，對稱位置怎么找？

如果數組下標從1開始，那么第個元素的對稱元素位置是誰？ 找找規律：1對n；2對n-1；3對n-2；i對什么?

代碼如下：

#include <iostream>
using namespace std;int main() {int a[1000]; // 假設數組最大長度為 1000int n, m;cin >> n >> m; // 輸入數組長度和操作次數 for (int i = 0; i < n; i++) { // 輸入數組元素cin >> a[i];}for (int j = 0; j < m; j++) { // 進行 m 次操作for (int i = 0; i < n / 2; i++) { // 遍歷前半部分a[i] = a[i] + a[n - 1 - i]; // 將前半部分和后半部分對應元素相加}if (n % 2 == 1) {// 如果數組長度是奇數，中間元素保持不變n = n / 2 + 1;} else {n = n / 2;}}for (int i = 0; i < n; i++) { // 輸出最終結果cout << a[i] << " ";}return 0;
}

例4：數字消除

【描述】李雷喜歡玩游戲，有一天他在電腦上發現 了一個叫“數字消消消”的游戲，其規則如下： 給定一個長度為n的整型數組，指定一個數a，如果該數組中有3個及3個以上的a連續出現，則該數字將會從數組中消除。

【輸入】第1行是整數n和a；第2行是數組中的n個整數

【輸出】1行。輸出消除后的數組

【樣例輸入】 6? 1

? ? ? ? ? ? ? ? ? ? ? 1 1 1 2 2 3

【樣例輸出】 2 2 3

算法思路

1、輸入處理：

• 首先讀取兩個整數 n 和 a，分別表示數組的長度和需要移除的數字。
• 然后讀取數組中的 n 個整數到數組 arr 中。

2、雙重循環檢測：

• 使用一個外層循環 for(int i=0; i<n; i++) 遍歷數組的每個元素。

• 對于每個元素，使用一個內層循環 for(int j=i; j<n; j++) 檢查從當前元素開始的連續相同數字的數量。

• 如果當前元素 arr[j] 等于 a，則增加計數器 num；如果不等于 a，則跳出內層循環。

3、移除連續相同數字：

• 如果計數器 num 大于等于 3，說明從索引 i 開始有連續三個或更多的 a，需要跳過這些元素。

• 使用 i=i+num-1 將外層循環的索引跳過這些連續的 a。

• 如果 num 小于 3，說明當前元素不是連續三個或更多的 a，需要輸出該元素。

4、重置計數器：

• 每次完成一次內層循環后，重置計數器 num 為 0，以便下一次檢測。

5、輸出結果：

• 在外層循環中，對于不滿足連續三個或更多 a 的元素，輸出該元素。

代碼如下：

#include <iostream>
using namespace std;
int main(){int n,a;int arr[1000];cin>>n>>a;for(int i=0;i<n;i++)cin>>arr[i];int num=0;for(int i=0;i<n;i++) {for(int j=i;j<n;j++){if(arr[j]==a)num++;elsebreak;}if(num>=3)i=i+num-1;elsecout<<arr[i]<<" ";num=0;}
}

作業1：角谷猜想

【描述】 所謂角谷猜想，是指對于任意一個正整數，如果是奇數，則乘3加1，如果是偶數，則除以2，得到的結果再按照上述規則重復處理，最終總能夠得到1。如，假定初始整數為5，計算過程分別為16、8、4、2、1。 程序要求輸入一個整數，將經過處理得到1的過程輸出來。

【輸入 】一個正整數N(N <= 2,000,000)

【輸出】從輸入整數到1的步驟，每一步為一行，每一部中描述計算過程。最后一行輸出"End"。如果輸入為1，直接輸出"End"。

【樣例輸入】 5

【樣例輸出】 5*3+1=16

? ? ? ? ? ? ? ? ? ? ? 16/2=8

? ? ? ? ? ? ? ? ? ? ? ?8/2=4

? ? ? ? ? ? ? ? ? ? ? ?4/2=2

? ? ? ? ? ? ? ? ? ? ? ?2/2=1

? ? ? ? ? ? ? ? ? ? ? ?End

【提示】注意計算過程中中間值可能會超過int范圍。

作業2：校門外的樹

【描述】某校大門外長度為L的馬路上有一排樹，每兩棵相鄰的樹之間的間隔都是1米。我們可以把馬路看成一個數軸，馬路的一端在數軸0的位置，另一端在L的位置；數軸上的每個整數點，即0，1，2，……，L，都種有一棵樹。

由于馬路上有一些區域要用來建地鐵。這些區域用它們在數軸上的起始點和終止點表示。已知任一區域的起始點和終止點的坐標都是整數，區域之間可能有重合的部分。現在要把這些區域中的樹（包括區域端點處的兩棵樹）移走。你的任務是計算將這些樹都移走后，馬路上還有多少棵樹。

【輸入】第一行有兩個整數L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表馬路的長度，M代表區域的數目，L和M之間用一個空格隔開。接下來的M行每行包含兩個不同的整數，用一個空格隔開，表示一個區域的起始點和終止點的坐標。
? ? ? ? 對于20%的數據，區域之間沒有重合的部分；
? ? ? ? 對于其它的數據，區域之間有重合的情況。

【輸出】包括一行，這一行只包含一個整數，表示馬路上剩余的樹的數目。

【樣例輸入】 500? 3

? ? ? ? ? ? ? ? ? ? ? 150? 300

? ? ? ? ? ? ? ? ? ? ? 100? 200

? ? ? ? ? ? ? ? ? ? ? 470? 471

【樣例輸出】 298

作業3：乒乓球

【題目背景】國際乒聯現在主席沙拉拉自從上任以來就立志于推行一系列改革，以推動乒乓球運動在全球的普及。其中?11?分制改革引起了很大的爭議，有一部分球員因為無法適應新規則只能選擇退役。華華就是其中一位，他退役之后走上了乒乓球研究工作，意圖弄明白?11?分制和?21?分制對選手的不同影響。在開展他的研究之前，他首先需要對他多年比賽的統計數據進行一些分析，所以需要你的幫忙。

【題目描述】 華華通過以下方式進行分析，首先將比賽每個球的勝負列成一張表，然后分別計算在 11 分制和 21 分制下，雙方的比賽結果（截至記錄末尾）。 比如現在有這么一份記錄，（其中 W 表示華華獲得一分，L 表示華華對手獲得一分）：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? WWWWWWWWWWWWWWWWWWWWWWLW

在 11 分制下，此時比賽的結果是華華第一局 11 比 0 獲勝，第二局 11 比 0 獲勝，正在進行第三局，當前比分 1 比 1。而在 21 分制下，此時比賽結果是華華第一局 21 比 0 獲勝，正在進行第二局，比分 2 比 1。如果一局比賽剛開始，則此時比分為 0 比 0。直到分差大于或者等于 2，才一局結束。 注意：當一局比賽結束后，下一局立刻開始。 你的程序就是要對于一系列比賽信息的輸入（WL 形式），輸出正確的結果。

【輸入格式】 每個輸入文件包含若干行字符串，字符串由大寫的 W 、 L 和 E 組成。其中 E 表示比賽信息結束，程序應該忽略 E 之后的所有內容。

【輸出格式】 輸出由兩部分組成，每部分有若干行，每一行對應一局比賽的比分（按比賽信息輸入順序）。其中第一部分是 11 分制下的結果，第二部分是 21 分制下的結果，兩部分之間由一個空行分隔。