2023牛客寒假算法训练营2

A.Tokitsukaze and a+b=n (easy)

easy 与 medium 的唯一区别是输入的数据范围，直接见medium

B.Tokitsukaze and a+b=n (medium)

题意：

给你一个 n ，两个区间 [l1,r1],[l2,r2] ,分别从两个区间内任选两个数 a,b，使得 a + b = n

数据范围

T :测试数据组数

两个区间的范围一致

$$1\leq T \leq 5, 1 \leq n \leq 2\cdot10^5,1\leq L \leq R\leq 10^5$$

题解：结论，模拟，数学

根据 a + b = n 得出 b = n - a ，因此知道只需要找到 b 与 n - a 的区间交即可

代码：

void JiuCherish(){
    ll n;
    std::cin >> n;
    ll l1 = 0,r1 = 0;
    ll l2 = 0,r2 = 0;
    std::cin >> l1 >> r1 >> l2 >> r2;
    ll a = n - r1;
    ll b = n - l1;
    if(l2 > b || a > r2) {
        std::cout << 0 << endl;
        return;
    }
    if(a <= l2 && b >= r2) {
        std::cout << r2 - l2 + 1 << endl;
        return;
    }
    if(a >= l2 && b <= r2) {
        std::cout << b - a + 1 << endl;
        return;
    }
    if(a <= l2 && b <= r2) {
        std::cout << b - l2 + 1 << endl;
        return;
    }
    if(a >= l2 && b >= r2) {
        std::cout << r2 - a + 1 << endl;
        return;
    }
}

C.Tokitsukaze and a+b=n (hard)

D.Tokitsukaze and Energy Tree

E.Tokitsukaze and Function

F.Tokitsukaze and Gold Coins (easy)

G.Tokitsukaze and Gold Coins (hard)

H.Tokitsukaze and K-Sequence

I.Tokitsukaze and Musynx

J.Tokitsukaze and Sum of MxAb

题意：

给你一个长度为 n 的序列 a

同时定义

$$MxAb(i,j) = max(|a_i-a_j|,|a_i+a_j|)$$

问：

$$\displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{n} MxAb(i,j)$$

题解：模拟、数学

对待绝对值进行讨论：不难发现结果就是

$$|a_i|+|a_j|$$

因此最大值就是上面的式子

那么原式为：

$$\displaystyle \sum_{i = 1}^{n} \sum_{j = 1}^{n} MxAb(i,j)$$

$$\displaystyle = \sum_{i = 1}^{n} \sum_{j = 1}^{n} (|a_i|+|a_j|)$$

$$\displaystyle = \sum_{i = 1}^{n} (n * |a_i|+ \sum_{j = 1}^{n} |a_j|)$$

$$\displaystyle = \sum_{i = 1}^{n} n * |a_i|+ n * \sum_{j = 1}^{n} |a_j|$$

$$\displaystyle = n * \sum_{i = 1}^{n} |a_i|+ n * \sum_{i = 1}^{n} |a_i|$$

$$\displaystyle = 2 * n * \sum_{i = 1}^{n} |a_i|$$

代码：

void JiuCherish(){
   int n;
   std::cin >> n;
   for(int i=1;i<=n;i++) {
      std::cin >> a[i];
      pre[i] = pre[i - 1] + abs(a[i]);
   }
   std::cout << pre[n] * n * 2 << endl;
}

玖的数学&算法录