3.藍橋速算【算法賽】 - 藍橋云課

---

問題描述

藍橋杯大賽最近新增了一項娛樂比賽——口算大賽，目的是測試選手的口算能力。

比賽規則如下：

• 初始給定一個長度為?N?的數組?A，其中第?i?個數字為?Ai?。
• 隨后數組會被隱藏，并進行?Q?次值域變換操作。
• 每次操作給出兩個數字?L,R?(1≤L≤R≤N)，表示對子數組?[L,R]?進行如下變換：
  • AL??增加?L。
  • AL+1??減少?L+1。
  • AL+2??增加?L+2。
  • AL+3??減少?L+3。
  • 以此類推，直到?R。

在所有操作完成后，選手需要快速計算出最終的數組之和，最快回答出正確答案的選手將會獲得獎勵，請你嘗試解決這個問題。

輸入格式

第一行輸入兩個整數?N,Q?(1≤N,Q≤105) 表示數組長度和值域變換操作次數。

第二行輸入?N?個整數?A1?,A2?,A3?,…,AN??(1≤Ai?≤105) 表示數組的初始值。

接下來?Q?行，每行兩個整數?L,R?(1≤L≤R≤N) 表示一次值域變換操作。

輸出格式

輸出一個整數，表示值域變換操作完畢后數組之和。

輸入樣例

5 2
1 2 3 4 5
1 3
4 5

輸出樣例

16

思路：

暴力
代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll L = 1e5+10;
ll N,Q;
ll a[L];
int main(void)
{cin >> N >> Q;for(ll i = 1 ; i <= N ; i++)cin >> a[i];while(Q--){ll l,r,cnt = 1;cin >> l >> r;for(ll i = l ; i <= r ; i++){if(cnt % 2 != 0){cnt++;a[i] += i;}else if(cnt % 2 == 0){cnt++;a[i] -= i;}}}ll sum = 0;for(ll i = 1 ; i <= N ; i++)sum += a[i];cout << sum;return 0;
}

思路：

數學問題，注釋寫的清楚

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll L = 1e5+10;
ll N,Q;
ll a[L];
int main(void)
{ll sum = 0;cin >> N >> Q;for(ll i = 1 ; i <= N ; i++){cin >> a[i];sum += a[i];}while(Q--){ll l,r,cnt = 1;cin >> l >> r;ll s = r-l+1;if(s % 2 == 0)//長度為偶數，會出現s/2個-1 {sum -= s/2; }else if(s % 2 != 0)//長度為奇數，會出現(1+s/2)個1 {sum += (l + s/2);}}cout << sum;return 0;
}