藍橋杯2022省A題C-創(chuàng)新互聯(lián)

題目鏈接：https://www.luogu.com.cn/problem/P8772

目前創(chuàng)新互聯(lián)建站已為1000多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站托管運營、企業(yè)網(wǎng)站設(shè)計、屏邊網(wǎng)站維護等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

我是在洛谷里做到這題的。

因為剛接觸算法在練習(xí)前綴和，我直接再洛谷上搜索了關(guān)于前綴和的題看到這個題。

由于我一開始就知道這題要用前綴和做，所以我做起來就不難了，關(guān)鍵是怎么找到里面運用了前綴和的地方。

題目只給了一個式子，我們首先看不到任何破解之法，就可以帶入特定的值，就像題中的案例帶入的是4，將4帶入后寫出完整的式子是

s?=?a1*a2?+?a1*a3?+?a1*a4

+?a2*a3?+?a2*?a4

+a3*a4

將公因式提取出來就是

s = a1*（a2 + a3 + a4）

+ a2*（a3 + a4）

+a3*a4

可以看到括號內(nèi)就是一個前綴和的形式，這樣就和前綴和聯(lián)系起來了。

但是說實話，我還是不清楚怎么一看到題目就知道要運用到前綴和，如果有網(wǎng)友知道的話可以在評論區(qū)告知一聲嗎？提前說聲謝謝啦。

我用的是java寫的，代碼如下

import java.util.*;

public class Main{
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int[] a = new int[n + 10];
  long[] s = new long[n + 10];
  long sum = 0;
  for(int i = 1; i<= n; i++){
   a[i] = sc.nextInt();
   s[i] = s[i - 1] + a[i];
  }
  for(int i = 1; i<= n; i++){
    sum += a[i] * (s[n] - s[i]);
  }
  System.out.println(sum);
 }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前題目：藍橋杯2022省A題C-創(chuàng)新互聯(lián)
本文來源：http://m.jiaotiyi.com/article/csohhh.html