ArabellaCPC 2019（补题）

• D. Meeting Bahosain

• • 题目大意
• • 解题思路
• • 代码

• I. Bashar and Hamada

• • 题目大意
• • 解题思路
• • 代码

---

D. Meeting Bahosain

---

题目大意

a，b两个数组，其中b数组里面的元素都是不同的，问我们是不是可以在a里面选一个元素，用b里面的元素对其进行无限次的加减，最后让a数组元素相同。比赛时根本不懂题目意思，裂开。

---

解题思路

要让所有元素相同，那么a[i] - a[j] （i, j 为任意的数）就要等于x1 * b1 + x2 * b2 + x3 * b3 + … + xn * bn。这里就要引入一个定理：a * x + b * y = gcd(a, b) 一定有解。代入进去我们可以得出 x1 * b1 + x2 * b2 + x3 * b3 + … + xn * bn = gcd(b1, b2, b3, …, bn)一定有解，这里因为乘数是自己取得，所以可得出 a[ i ] - a[ j ] = x * (gcd(b1, b2, …, bn))，x是任意常数。

最后就得出结论了，只要所有的a[ i ] - a[ j ]整除gcd(b1, b2, …, bn)就可以了。

---

代码

#include <bits/stdc++.h>

using namespace std;

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
//#define For(i, k, n) for (int i = k; i < n; i ++)
//#define FOR(i, k, n) for (int i = k; i <= n; i ++)
#define P acos(-1);
typedef long long LL;
typedef unsigned long long ULL;
#define PII pair<int, int>
#define PDD pair<double, double>
#define Pll pair<LL, LL>
typedef unsigned long long Uint;
const double eps = 1e-7;
const int M = 1e6 + 10, mod = 1000000007;
const int inf = 0x3f3f3f3f;
int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
int lowbit(int x) { return (x & -x); };

//  以上可忽略

const int N = 1e6 + 10;

int a[N], b[N];

void solve()
{
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i ++)
        cin >> a[i];
    
    int res = 0;
    for (int i = 0; i < n; i ++)
        cin >> b[i], res = (res == 0) ? b[i] : __gcd(res, b[i]);
    
    for (int i = 1; i < n; i ++)
    {
        if ((a[i] - a[i - 1]) % res != 0)
        {
            puts("No");
            return;
        }
    }

    puts("Yes");
}

int main()
{
    IOS 
    int T = 1;
    //cin >> T;
    //scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    return 0;
}

---

I. Bashar and Hamada

---

题目大意

k（2 <= k <= n) 长度的数字问相互之间的差值的绝对值的最大值是多少。

---

解题思路

首先我们应该明白顺序是不影响大小的。然后再找一个规律：

假定一组数据 {1,2,3,4,5,7}，开始ans=0;

开始：ans+= |1-7|

插入5: ans+=|5-1|+|5-7|=|1-7|

插入2: ans+=|2-1|+|2-7|+|2-5|==|1-7|+|2-5|

插入4: ans+=|4-1|+|4-7|+|4-5|+|4-2|==|1-7|+|2-5|

插入3: ans+=|3-1|+|3-7|+|3-5|+|3-2|+|3-4|==|1-7|+|2-5|+|3-4|

这样列出来就很明显了。奇数次插入，要加的数保存不变。

可以看到每插入2个就增加一个组合，只要每次加入的组合为最大，就能保证答案最大。

每次组合都选差最大的，排序后，就是左右各一个。

思路转载自这个博客：

https://www.cnblogs.com/studyshare777/p/12766707.html

---

代码

#include <bits/stdc++.h>

using namespace std;

#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
//#define For(i, k, n) for (int i = k; i < n; i ++)
//#define FOR(i, k, n) for (int i = k; i <= n; i ++)
#define P acos(-1);
typedef long long LL;
typedef unsigned long long ULL;
#define PII pair<int, int>
#define PDD pair<double, double>
#define Pll pair<LL, LL>
typedef unsigned long long Uint;
const double eps = 1e-7;
const int N = 3e5 + 10, M = 1e6 + 10, mod = 1000000007;
const int inf = 0x3f3f3f3f;
int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};
int lowbit(int x) { return (x & -x); };

LL f[N];

void solve()
{
    LL n;
    cin >> n;

    for (int i = 1; i <= n; i ++)
        cin >> f[i];
    
    sort(f + 1, f + 1 + n);

    LL ans = 0, tot = 0;
    ans = f[n] - f[1];
    tot = ans;

    cout << ans << ' ';

    int r = n - 1, l = 2;
    for (int i = 1; i < n - 1; i ++)
    {
        if (!(i & 1))
            tot += f[r --] - f[l ++];
        
        ans += tot;
        cout << ans << ' ';
    }
}

int main()
{
    IOS 
    int T = 1;
    //cin >> T;
    //scanf("%d", &T);
    while (T--)
    {
        solve();
    }
    return 0;
}