A.Fast Food Restaurant

题意：一共有3种物品，每种物品每次只能取一个或零个，问一共能组成多少种组合

题解：取一个、两个、三个，一共就7种情况讨论一下即可

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

B.Different Rules

题意：一个人参加两场比赛，一共n个人，第一次第x名，第二次y名，询问他两场的名次相加最高能取得第几名以及最低能取得第几名

题解：对于最低的名次，只要将第一次的第1名与第二次的第x+y-1名、第一次的第2名与第二次的第x+y-2名...这样就能构造出x+y-1个x+y分的人，他的最低名次就是x+y-1。对于最高名次，如果x+y<=n，那么就可以通过第一次的第1名与第二次的第n名、第一次的第2名与第二次的第n-1名...将剩下的构造成n+1分，使他成为第1名；如果x+y>n，那么将两次比赛的第一名组合一起、第二名组合一起...设组合了t组，使得x-t+y-t<=n-t，就满足了新的x+y<=n，可以算出t=x+y-n，所以他最高就是第x+y-n+1名

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, x, y;
int get_min()
{
    if (x + y <= n)
        return 1;
    return min(n, x + y - n + 1);
}
int get_max()
{
    return min(n, x + y - 1);
}
void solve()
{
    scanf("%d%d%d", &n, &x, &y);
    if (x > y)
        swap(x, y);
    printf("%d %d\n", get_min(), get_max());
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

C.Skyscrapers（单调栈/分治+线段树）

题意：要建建筑，要求对于任意一个不能同时存在左、右都有比它高的建筑，同时对于每个i都有给定的mi，每个i不能超过mi。询问这些建筑高度和最大能是多少。

题解：显然满足题意的一定是一个单峰序列，于是可以考虑第i个当最高点的时候，左边的最大总和，而这个是可以递推的，因为当mi>=mi-1的时候第i个可以直接取mi加上去，而当mi<mi-1的时候，要把之前所有大于mi的都变成mi，而之前的部分是单增的，于是可以开个单调栈来维护，复杂度O(n)，同理右边的最大总和也可以这么算。还有一种方法：找出区间里的最小值mi，分治，比较左边都取mi+solve右边与左边solve+右边都取mi的大小。用线段树来维护区间。

单调栈：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
typedef long long ll;
ll a[maxn], pre[maxn], nex[maxn], l[maxn], r[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    a[0] = a[n + 1] = 0ll;
    stack<int> s;
    s.push(0);
    for (int i = 1; i <= n; i++)
    {
        while (a[s.top()] >= a[i])
            s.pop();
        pre[i] = s.top();
        s.push(i);
        l[i] = l[pre[i]] + a[i] * (i - pre[i]);
    }
    while (!s.empty())
        s.pop();
    s.push(n + 1);
    for (int i = n; i >= 1; i--)
    {
        while (a[s.top()] >= a[i])
            s.pop();
        nex[i] = s.top();
        s.push(i);
        r[i] = r[nex[i]] + a[i] * (nex[i] - i);
    }
    ll mx = 0;
    int id = 0;
    for (int i = 1; i <= n; i++)
        if (mx < l[i] + r[i] - a[i])
            mx = l[i] + r[i] - a[i], id = i;
    for (int i = id - 1; i >= 1; i--)
        a[i] = min(a[i], a[i + 1]);
    for (int i = id + 1; i <= n; i++)
        a[i] = min(a[i], a[i - 1]);
    for (int i = 1; i <= n; i++)
        printf("%lld ", a[i]);
    puts("");
    return 0;
}

分治+线段树

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7;
int n;
long long a[maxn], b[maxn];
typedef pair<long long, int> SgTreeDataType;
struct treenode
{
    int L, R;
    SgTreeDataType mi, lazy;
} tree[maxn * 4];
inline void push_up(int o)
{
    if (tree[2 * o].mi.first == 0)
        tree[2 * o].mi = {1e9 + 7, 1e9};
    if (tree[2 * o + 1].mi.first == 0)
        tree[2 * o + 1].mi = {1e9 + 7, 1e9};
    if (tree[2 * o].mi.first > tree[2 * o + 1].mi.first)
        tree[o].mi = tree[2 * o + 1].mi;
    else
        tree[o].mi = tree[2 * o].mi;
}

inline void build_tree(int L, int R, int o)
{
    tree[o].L = L, tree[o].R = R;
    if (L == R)
        tree[o].mi = {a[L], L};
    if (R > L)
    {
        int mid = (L + R) >> 1;
        build_tree(L, mid, o * 2);
        build_tree(mid + 1, R, o * 2 + 1);
        push_up(o);
    }
}
inline SgTreeDataType query(int QL, int QR, int o)
{
    int L = tree[o].L, R = tree[o].R;
    if (QL <= L && R <= QR)
        return tree[o].mi;
    else
    {
        int mid = (L + R) >> 1;
        SgTreeDataType mi = {1e9 + 7, 1};
        if (QL <= mid)
        {
            SgTreeDataType res = query(QL, QR, 2 * o);
            if (res.first < mi.first)
                mi = res;
        }
        if (QR > mid)
        {
            SgTreeDataType res = query(QL, QR, 2 * o + 1);
            if (res.first < mi.first)
                mi = res;
        }
        push_up(o);
        return mi;
    }
}

long long solve(int l, int r)
{
    if (l > r)
        return 0L;
    if (l == r)
    {
        b[l] = a[l];
        return 1ll * a[l];
    }
    pair<long long, int> mi = query(l, r, 1);
    long long sum1 = solve(l, mi.second - 1);
    long long sum2 = solve(mi.second + 1, r);
    if (1ll * ((r - mi.second - 1) + 1) * mi.first + mi.first + sum1 >
        1ll * ((mi.second - 1 - l) + 1) * mi.first + mi.first + sum2)
    {
        for (int i = mi.second; i <= r; i++)
            b[i] = mi.first;
        return 1ll * ((r - mi.second - 1) + 1) * mi.first + mi.first + sum1;
    }
    else
    {
        for (int i = l; i <= mi.second; i++)
            b[i] = mi.first;
        return 1ll * ((mi.second - 1 - l) + 1) * mi.first + mi.first + sum2;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build_tree(1, n, 1);
    solve(1, n);
    for (int i = 1; i <= n; i++)
        cout << b[i] << " ";
    cout << endl;
}