AtCoder Beginner Contest 178 个人题解（C组合问题 快速幂，D规律，E数学公式变形）

补题链接：Here

A - Not Editorial

给出 则输出 0；给出 则输出 1

利用 x ^ 1 可以快速实现 的转换

B - Product Max

比较端点乘积的大小即可

C - Ubiquity

题解：输入一个N，，所以一共 种情况，序列中元素个数为 ，序列中一定存在 0 和 9，要得到至少有一个0和一个9的所有情况，思路使用总共的情况减去只有一个 0 、只有 一个 9 、或者 0 和 9 都没有的情况。

ans = (ans + mod) % mod;

因为取余后，各数的大小发生变化，这里防止 ans 减为负数！！！

typedef long long ll;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b) {
    ll ans = 1;
    a %= mod;
    for (; b; a = a * a % mod, b >>= 1)
        if (b & 1) ans = ans * a % mod;
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll n;
    cin >> n;
    ll ans = qpow(10, n) - qpow(9, n) - qpow(9, n) + qpow(8, n);
    ans %= mod;
    cout << (ans + mod) % mod;
    return 0;
}

D - Redistribution

PS：先是看了半天，然后写几组样例，就找到规律了

最后别忘记取模即可

E - Dist Max

题意：二维平面上有N个点 #card=math&code=%28x_i%2Cy_i%29)。 找到其中两个点的最大曼哈顿距离。

思路：两点之间的位置关系可以有以下两种模式。

考虑两个最远点之间的位置关系…

• 的最大值 和最小值 之间的差异，当两个最远的点是右侧图形时；
• 的最大值，当两个最远的点是右侧图形时，与最小值之间的差异值

因此，从直觉上讲，最 #card=math&code=max%28M_1-m_1%EF%BC%8CM_2-m_2%29) 似乎是答案。 让我们在公式转换的基础上进一步说明这一点。

公式变形：

关于绝对值问题前提：#card=math&code=%7Cx%7C%20%3D%20max%28x%2C-x%29)

通常情况下，前景会更好。 对于每对（i，j），即使xi <xj，它也不会失去通用性（反之亦然，交换）。

)%5C%5C%0A%3Dmax((x_j%20%2B%20y_j)%20-%20(x_i%20%2B%20y_i)%2C(x_j%20-%20y_j)-(x_i%2Cy_i))%0A#card=math&code=%7Cx_i%20-%20x_j%7C%20%2B%20%7Cy_i%20-%20y_j%7C%20%5C%5C%0A%3D%28x_j%20-%20x_i%20%2Bmax%28y_j-y_i%2Cy_i-y_j%29%29%5C%5C%0A%3Dmax%28%28x_j%20%2B%20y_j%29%20-%20%28x_i%20%2B%20y_i%29%2C%28x_j%20-%20y_j%29-%28x_i%2Cy_i%29%29%0A)

由上面的变形

• 求各个 #card=math&code=%28i%2Cj%29) 的 %20-%20(x_i%20%2B%20y_i)#card=math&code=%28x_j%20%2B%20y_j%29%20-%20%28x_i%20%2B%20y_i%29) 的最大值
• 求各个 #card=math&code=%28i%2Cj%29) 的 %20-%20(x_i%20-%20y_i)#card=math&code=%28x_j%20-%20y_j%29%20-%20%28x_i%20-%20y_i%29) 的最大值

所以再回到上面：#card=math&code=max%28M_1-m_1%EF%BC%8CM_2-m_2%29) 正是答案

• #card=math&code=%5Cmathcal%7BO%7D%28N%29)，但由于用了 sort 时间复杂度为 #card=math&code=%5Cmathcal%7BO%7D%28NlogN%29)

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    vector<int> a, b;
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        a.emplace_back(x + y);
        b.emplace_back(x - y);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    cout << max(a[n - 1] - a[0], b[n - 1] - b[0]);
    return 0;
}