A.Donut Shops

题意：

现有两种购物方式

花单价 $a$ 元购买单个物品
花 $c$ 元购买 $b$ 个物品

询问购买多少个物品可以使得用方式1的花费严格小于方式2和购买多少个物品可以使得用方式2的花费严格小于方式1

题解：

分别判断购买 $1$ 个和 $b$ 个物品， $a$ 和 $c$ ， $a*b$ 和 $c$ 的大小即可

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

B.01 Game

题意：

给定一个 $01$ 串，两人开始删串，每次可以删除 $01$ 或者 $10$ ，最后不能删的人输。

题解：

如果序列中存在 $0$ 和 $1$ ，那么最终总能删到只剩其中一种或者为空，那么只需要计算出较小者，判断奇偶性即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
char s[105];
void solve()
{
    scanf("%s", s);
    int n1 = 0, n2 = 0;
    for (int i = 0; i < strlen(s); i++)
    {
        if (s[i] == '1')
            n1++;
        else
            n2++;
    }
    puts((min(n1, n2) & 1) ? "DA" : "NET");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Pluses and Minuses

题意：

图片说明
给定一个序列 $s$ ，只有 $+$ 和 $-$ ， $+$ 算 $1$ ， $-$ 算 $-1$ ，给定一个 $cur$ , $cur$ 从 $1$ 到无穷大，每次遍历一遍序列，当 $cur$ 小于 $0$ 时，就退出进入下一轮，询问当 $cur$ 完整遍历完序列值还 $\geq 0$ 时，一共遍历的长度

题解：；

简单模拟即可，遍历序列，每次计算下当前 $cur$ 值与最小值比较，如果小于最小值，则更新最小值，同时答案加上当前长度，遍历完序列，最终答案再加上序列长度即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
map<int, int> mp;
void solve()
{
    string s;
    cin >> s;
    int cnt = 0, last = 0;
    ll ans = s.length();
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '+')
            cnt++;
        else
            cnt--;
        if (cnt < last)
        {
            ans += i + 1;
            last = cnt;
        }
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Maximum Sum on Even Positions(最大字段和)

题意：

给定一个长度为 $n$ 的序列 $a_n$ ，有一次操作可以对任意的区间进行翻转，询问偶数位之和的最大值 $(a_0+a_2+\dots)$

题解：

可以发现如果要改变结果那么只会是选取一段 $l、r$ 奇偶性不同的区间，也就说将区间内的所有数进行奇偶交换，那么就是在原偶数位之和的基础上再加上一个连续的奇数减偶数之差的最大值，也就是将相邻的奇数-偶数看成一个整体，就一个最大字段和

#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;
ll a[maxn];
void solve()
{
    int n;
    ll ans = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
        if (!(i & 1))
            ans += a[i];
    }
    ll cur = 0, mx = 0;
    for (int i = 1; i < n; i += 2)
    {
        cur += a[i] - a[i - 1];
        cur = max(cur, 0ll);
        mx = max(mx, cur);
    }
    cur = 0;
    for (int i = 2; i < n; i += 2)
    {
        cur += a[i - 1] - a[i];
        cur = max(cur, 0ll);
        mx = max(mx, cur);
    }
    printf("%lld\n", ans + mx);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Sum of Digits(模拟)

题意：

$f(x)$ 为 $x$ 的各位数之和，给定 $n,k(1 \leq 150, 0 \leq k)$ 求最小的 $x$ ，使得 $f(x)+f(x+)+ \dots + f(x+k)=n$

题解：

首先先有个结论， $x$ 和 $x+k$ 的数量级是相同的，如果 $f(99)+f(100)=19$ ，那么一定能找到 $f(18)+f(19)=19$ 。
因此可以枚举最后一位，中间的数字尽可能大，首位数字尽可能小，求出 $x+k$ ，那么 $-k$ 即为 $x$ ,具体操作见代码
这题 $n$ 和 $k$ 均不大，打表也可以

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
int p[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9};
ll solve(int st, int n, int k)
{
    int i, sum = 0;
    ll ret = 0, pow = 10;
    for (i = st; i <= st + k; i++)
        sum += p[i];
    n -= sum;
    if (n < 0 || n % (k + 1))
        return INF;
    n /= (k + 1);
    if (st + k >= 10)
        n++;
    while (n > 0)
    {
        int tmp = min(9, n);
        ret += tmp * pow;
        pow *= 10;
        n -= 9;
    }
    ret += p[st + k];
    if (st + k >= 10)
        ret--;
    if (ret >= k)
        return ret - k;
    else
        return INF;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        ll ans = INF;
        for (int i = 0; i <= 9; i++)
            ans = min(ans, solve(i, n, k));
        if (ans == INF)
            printf("-1\n");
        else
            printf("%lld\n", ans);
    }
    return 0;
}

F.Network Coverage(二分)

题意：

$n$ 个城市围城一圈，每个城市有 $a_i$ 的需求，又能提供 $b_i$ 的需求，但是每个城市提供的需求只能给它和它后一个城市使用，询问是否存在一种分配方案能满足所有城市的需求

题解：

可以确定当一个城市提供给自身的需求确定了以后，所有的城市满足自身所有的需求和能提供给下一个城市的需求就都确定了，那么只需要对 $1$ 号城市提供给自身的需求进行二分，那么就可以找到是否存在一种策略满足条件了。唯一要注意的是当上一个城市提供的需求给这个城市还有剩余时，这个需求并不能再转移到下下个城市

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int a[maxn], b[maxn], n;
int check(int x)
{
    int pre = b[1] - x;
    for (int i = 2; i <= n; i++)
    {
        pre = min(pre, a[i]);
        pre += b[i];
        pre -= a[i];
        if (pre < 0)
            return -1;
    }
    return pre;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &b[i]);
        int l = 0, r = b[1];
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid) >= 0)
                l = mid;
            else
                r = mid - 1;
        }
        if (r >= 0 && r + check(r) >= a[1])
            puts("YES");
        else
            puts("NO");
    }
}

G.Pawns(线段树)

题意：

给定一个 $n \times n$ 的棋盘，其中第 $k$ 列为特殊列，有 $m$ 次操作，每次操作给定 $(x,y)$ ，表示第 $x$ 列第 $y$ 行，如果该位置有士兵就把这个士兵去掉，否则在这个位置放上士兵，对于 $(x,y)$ 可以向 $(x,y+1),(x+1,y+1),(x-1,y+1)$ 三个方向移动，现在每次操作过后要求将所有士兵移动到第 $k$ 列，并且要求每个士兵均不相同，询问最少需要对第 $k$ 列扩展多少行

题解：

可以发现不论哪种操作士兵每次都会行坐标都会 $+1$ ，所以在一个兵最少移动次数到达第 $k$ 列之后，如果当前坐标已经有兵了，那么就不断递增行坐标直到找到第一个空的位置。因此首先想到把所有的兵移动到离它最近的第 $k$ 列的位置，并统计第 $k$ 列上所有位置的兵的个数，再求出最大的位置即可。而考虑到这时一道在线操作的题目，不可能每次都重新计算，因此可以用线段树来维护每个区间的值，线段树初始化为每个下标位置 $-1$ ，当这个区间出现士兵时值刚好对应下标，因此每次对 $1,i$ 的位置 $+1$ 或 $-1$ ，最终只需要求出 $1$ 到最远那个士兵所移动距离的最大值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
int T[maxn << 3], lazy[maxn << 3], cnt[maxn << 1];

void build(int l, int r, int rt)
{
    if (l == r)
    {
        T[rt] = l - 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    T[rt] = max(T[rt << 1], T[rt << 1 | 1]);
}

void pushdown(int rt)
{
    if (lazy[rt])
    {
        T[rt << 1] += lazy[rt];
        T[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void update(int l, int r, int L, int R, int rt, int x)
{
    if (L <= l && r <= R)
    {
        T[rt] += x;
        lazy[rt] += x;
        return;
    }
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        update(l, mid, L, R, rt << 1, x);
    if (R > mid)
        update(mid + 1, r, L, R, rt << 1 | 1, x);
    T[rt] = max(T[rt << 1], T[rt << 1 | 1]);
}

int query(int rt, int l, int r, int L, int R)
{
    if (L <= l && r <= R)
        return T[rt];
    pushdown(rt);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (L <= mid)
        ans = max(ans, query(rt << 1, l, mid, L, R));
    if (R > mid)
        ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
    return ans;
}

int main()
{
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    build(1, n + n, 1);
    set<pii> s;
    set<int> S;
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        int pos = y + (int)abs(x - k);
        pii p = pii(x, y);
        if (s.count(p))
        {
            if (--cnt[pos] == 0)
                S.erase(pos);
            update(1, n + n, 1, pos, 1, -1);
            s.erase(p);
        }
        else
        {
            if (++cnt[pos] == 1)
                S.insert(pos);
            update(1, n + n, 1, pos, 1, 1);
            s.insert(p);
        }
        if (S.empty())
            puts("0");
        else
            printf("%d\n", max(0, query(1, 1, n + n, 1, *S.rbegin()) - n));
    }
    return 0;
}

Educational Codeforces Round 90 (Rated for Div. 2)