A.Park Lighting

题意：

给定一个的方格，要求用或者的方块填充，询问所需的最少方块数

题解：

向上取整即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    printf("%lld\n", (n * m + 1) / 2);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Maria Breaks the Self-isolation

题意：

原先操场上只有一个人，现在给定个人，每个人都有一个，表示此时操场上有个人时(包括自身，但不包括一开始那个人)她才能够成功到达操场。询问最终能有多少人在操场上

题解：

将从小到大进行排序，从后往前遍历，找到一个最大的数使得此时的,此时答案就是，如果没有找到一个，答案就为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a + n);
    for (int i = n - 1; i >= 0; i--)
    {
        if (a[i] <= i + 1)
        {
            printf("%d\n", i + 2);
            return;
        }
    }
    puts("1");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Celex Update

题意：

给定一个无限长的棋盘(见下图),要求从走到，并且只能往下或者往右走，求走过的路径上所有格子和的不同情况有多少种

题解：

可以发现先一直往右走最后往下走得到的和最小，记为，先一直往下走最后往右走得到的和最大，记为，而且中的每一个值都是能得到的，因此答案就为

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll x1, x2, y1, y2;
    scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
    printf("%lld\n", (x2 - x1) * (y2 - y1) + 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.The Best Vacation

题意：

一年有个月，每个月有天，现在要求找出连续天，使其日期的总和最大，可以跨年

题解：

首先可以明确一个月的最后几天之和肯定比月初的大，因此只需要找出一段月末加上几个月的总和即可。因此可以用两个前缀和分别维护月数和日期总和，再枚举以每一个月为末尾能往前取的最大值更新即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 5;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
ll n, x, d[maxn], c[maxn], ans;
int main()
{
    scanf("%lld%lld", &n, &x);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &d[i]), d[i + n] = d[i];
    n *= 2;
    for (int i = 1; i <= n; i++)
    {
        c[i] = c[i - 1] + (d[i] + 1) * d[i] / 2;
        d[i] += d[i - 1];
    }
    ans = x;
    for (int i = 1, j = 0; i <= n; i++)
    {
        while (d[i] - d[j] > x)
            j++;
        ll y = d[j] - d[j - 1], t = min(y, x - (d[i] - d[j]));
        ans = max(ans, c[i] - c[j] + (y + y - t + 1) * t / 2);
    }
    printf("%lld\n", ans);
    return 0;
}