A.Dead Pixel

题意：给定一个a*b的矩阵，其中(x,y)坏掉了，求一个最大的不包含这个点的矩阵面积。

题解：一个点可以将矩形分成四个部分。通过算出边界点我们可以求出四个矩阵的面积图片说明 。

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int get(int x1, int y1, int x2, int y2, int a, int b)
{
    if (x1 = a || x2 = a || y1 = b || y2 = b)
        return 0;
    return (abs(x1 - x2) + 1) * (abs(y1 - y2) + 1);
}
void solve()
{
    int a, b, x, y;
    scanf("%d%d%d%d", &a, &b, &x, &y);
    int ans = 0;
    ans = max(ans, get(0, 0, x - 1, b - 1, a, b));
    ans = max(ans, get(0, 0, a - 1, y - 1, a, b));
    ans = max(ans, get(x + 1, 0, a - 1, b - 1, a, b));
    ans = max(ans, get(0, y + 1, a - 1, b - 1, a, b));
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

B.Homecoming

题意：给定一段地铁和巴士交替的道路，其中最后一站为家，A代表巴士，B代表地铁，若前后两个字节不同则代码后一个字节所在位置为一种交通工具的终点和另一种交通工具的起点。其中坐巴士a元，坐地铁b元，他一共有p元。他前面的路走路，后面的路都坐交通工具，询问最少要走多少步。

题解：题目要求最后的路都要坐交通工具，那么我们只需要倒着走即可，如果能坐交通工具则坐，否则就break输出结果。

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
void solve()
{
    int a, b, p;
    string s;
    cin >> a >> b >> p;
    cin >> s;
    int i;
    for (i = s.size() - 2; i >= 0; i--)
    {
        if (s[i] == 'A')
        {
            if (p < a)
                break;
            p -= a;
        }
        if (s[i] == 'B')
        {
            if (p < b)
                break;
            p -= b;
        }
        while (i > 0 && s[i] == s[i - 1])
            i--;
    }
    printf("%d\n", i + 2);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

C.Restoring Permutation

题意：给定一个序列b1 ~ bn，找出字典序最小的序列a1 ~ a2n，其中

题解：首先我们将b[i]放在a[2i-1]，这样肯定是最小的，然后我们对每一个i都找一个比a[2i-1]大的放在a[2i]。然后我们再进行一次排序考虑能不能交换a[2i]与a[2j]使得字典序变小。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int a[maxn], H[maxn], vis[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    memset(H, 0, sizeof(H));
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[2 * i + 1]);
        H[a[2 * i + 1]] = 2 * i + 1;
        vis[a[2 * i + 1]] = 1;
    }
    int now = 1;
    for (int i = 1; i <= 2 * n; i++)
    {
        if (H[i] == 0)
        {
            puts("-1");
            return;
        }
        if (!vis[i])
            continue;
        for (int j = i + 1; j <= 2 * n; j++)
        {
            if (H[j] == 0)
            {
                a[H[i] + 1] = j;
                H[j] = H[i] + 1;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i * 2] >= a[j * 2 - 1] && a[j * 2] >= a[i * 2 - 1] && a[i * 2] > a[j * 2])
                swap(a[i * 2], a[j * 2]);
    for (int i = 1; i <= 2 * n; i++)
        printf("%d ", a[i]);
    puts("");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

D.Recommendations（贪心）

题意：有n种书，一开始第i种书的数量是ai本，你可以花ti的时间使得第i种书的数量增加一本。询问最少需要花多少时间可以使得所有种类的书本数都不一样。

题解：先对a进行排序，用一个set来维护花费，每次将需要花费最大的留在当前数量，其他的书数量都增加一，这次的贡献可以通过sum-mx来算出，sum为当前set内贡献之和，mx为贡献最大的值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
multiset<ll> s;
pair<ll, ll> a[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i].first);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i].second);
    sort(a, a + n);
    ll now = -1;
    ll ans = 0, sum = 0;
    for (int i = 0; i < n; i++)
    {
        while (!s.empty() && now < a[i].first)
        {
            ll mx = *s.rbegin();
            ans += sum - mx;
            sum -= mx;
            s.erase(s.find(mx));
            now++;
        }
        s.insert(a[i].second);
        sum += a[i].second;
        now = a[i].first;
    }
    while (!s.empty())
    {
        ll mx = *s.rbegin();
        ans += sum - mx;
        sum -= mx;
        s.erase(s.find(mx));
    }
    printf("%lld\n", ans);
    return 0;
}