[Codeforces]#668 div2
本文最后更新于 132 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/cf1405/

前言

补题。

C

给定一个字符串和 $k$,要求每个长度为 $k$ 的子串都有 $\dfrac{k}{2}$ 个 $0$ 与 $\dfrac{k}{2}$ 个 $1$.
字符串中有部分 ?,可以决定 ? 为 $0$ 或 $1$,问是否能实现。
可以发现,给 ? 赋值并非完全自由。
例如从 $[1,k]$ 移动到 $[2,k+1]$ 时,若 $s_{k+1}$ 为确定值,则 $s_1$ 也可以被确定。
因为公共部分 $[2,k]$ 且 $[1,k]$ 满足条件,则减少一个 $1$ 一定要补充一个 $1$,反之同理。
另外,若某个区间内已确定的值有过半的,则一定不行。

#include <cstdio>
const int maxn = 3e5 + 100;
int T,n,k;
char s[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&k);
        scanf("%s", s + 1);
        int one = 0,zero = 0;
        for (int i = 1; i < k; ++i) one += (s[i] == '1'), zero += (s[i] == '0');
        for (int i = 1; i <= n - k + 1; ++i)
        {
            one -= (s[i - 1] == '1'), zero -= (s[i - 1] == '0');
            one += (s[i + k - 1] == '1'), zero += (s[i + k - 1] == '0');
            if (one > k / 2 || zero > k / 2) goto fail;
            if (i + k > n) break;
            if (s[i + k] != '?')
            {
                if (s[i] != '?') { if (s[i] != s[i + k]) goto fail; }
                else s[i] = s[i + k];
            }
            else if (s[i] != '?') s[i + k] = s[i];
        }
        one = zero = 0;
        for (int i = 1; i < k; ++i) one += (s[i] == '1'), zero += (s[i] == '0');
        for (int i = 1; i <= n - k + 1; ++i)
        {
            one -= (s[i - 1] == '1'), zero -= (s[i - 1] == '0');
            one += (s[i + k - 1] == '1'), zero += (s[i + k - 1] == '0');
            if (one > k / 2 || zero > k / 2) goto fail;
        }
        printf("%s\n", s + 1);
        puts("YES");
        continue;
    fail:
        puts("NO");
    }
    return 0;
}

B

$a_i := a_i – 1$,$a_j := a_j + 1$,若 $i < j$ 则无需花费,否则花一元。
求多少次后数组变零,保证有解。
考虑先将无需花费的全部消去。
从后往前,维护小于零的数的和,用于消去大于零的数。若无法消去,计答案。

#include <cstdio>
const int maxn = 3e5 + 100;
int T,n;
int a[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; ++i) scanf("%d", a + i);
        long long sum = 0,res = 0;
        for(int i = n;i;--i)
        {
            if(a[i] < 0) sum -= a[i];
            else 
            {
                if(a[i] >= sum) res += a[i] - sum,sum = 0;
                else sum -= a[i];
            }
        }
        printf("%lld\n",res);
    }
}

A

显然倒过来即可。

#include <cstdio>
#include <algorithm>
int T,n,a[110];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i = 1; i <= n; ++i) scanf("%d",a+i);
        for (int i = n; i; --i) printf("%d ", a[i]);
        puts("");
    }
    return 0;
}

D

若干次移动后,若先手能追上后手,则先手胜, 否则后手胜。

  1. 先手一步能追上后手,先手胜。
  2. 先手一步距离大于树的直径的一半,走到中心后一步可到达任意点,先手胜。
  3. 后手距离大于两倍先手距离,则后手总是可以移动到先手一步范围之外,后手胜。
  4. 后手距离小于等于两倍先手距离,则先手不断逼近后手,最后后手无法横跨先手支配领域,而另一方向空间不足,先手必胜。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 1e5 + 100;
struct node
{
    int to, next;
} E[maxn << 1];
int head[maxn], tot;
inline void add(const int& x, const int& y) { E[++tot].next = head[x], E[tot].to = y, head[x] = tot; }
int T, n, a, b, da, db, d;
int dep[maxn], maxx[maxn], secx[maxn];
void dfs(int u, int fa)
{
    maxx[u] = secx[u] = 0;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        dep[v] = dep[u] + 1, dfs(v, u);
        if (maxx[v] + 1 > maxx[u]) secx[u] = maxx[u], maxx[u] = maxx[v] + 1;
        else if (maxx[v] + 1 > secx[u]) secx[u] = maxx[v] + 1;
    }
    d = std::max(maxx[u] + secx[u], d);
}
int main()
{
    read(T);
    while (T--)
    {
        tot = d = 0;
        read(n), read(a), read(b), read(da), read(db);
        for (int i = 1; i <= n; ++i) head[i] = maxx[i] = secx[i] = dep[i] = 0;
        for (int i = 1; i < n; ++i)
        {
            int x, y;
            read(x), read(y), add(x, y), add(y, x);
        }
        dfs(a, 0);
        int dis = dep[b];
        if (dis <= da) puts("Alice");
        else if (da * 2 >= d) puts("Alice");
        else if (db > da * 2) puts("Bob");
        else puts("Alice");
    }
    return 0;
}

E

当 $a_i = i$ 时,可以删除该元素。
每次删除后,其后元素前移。
回答 $q$ 个问题,将前 $x$ 个元素与后 $y$ 个元素替换为 $n+1$ 使它们不可能被删除后,最多能删除多少个数。

预处理:$a_i := i – a_i$,此时 $a_i$ 表示,其前方删除 $a_i$ 个数后当前数可以删除。

若 $a_i < 0$,则显然永远无法删除,令 $a_i = n + 1$.
每次一个数变成 $0$ 后,将其后的所有数减一。

将询问排序,从右向左处理,若能删除则在线段树上区间减一。

若 $a_i > 0$ 则插入线段树等待维护。

每次有零时,更新线段树,再找到最右端的零,继续更新。在此过程中,将零产生的对答案的贡献插入树状数组中。
而已经记过答案的位置,为了避免重复计,赋一个极大值。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <vector>
const int bufSize = 1e6;
using namespace std;
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 3e5 + 100;
int n, m, a[maxn];
struct query
{
    int l, r, id;
} Q[maxn];
int ANS[maxn];
bool cmp(const query& a, const query& b) { return a.l > b.l; }
namespace Bit
{
int sum[maxn];
inline int lowbit(int x) { return x & -x; }
inline void add(int x, int k) { for (; x <= n; x += lowbit(x)) sum[x] += k; }
inline int ask(int x)
{
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res += sum[x];
    return res;
}
inline int ask(int l, int r) { return ask(r) - ask(l - 1); }
}  // namespace Bit
namespace Seg
{
int minr[maxn << 2], minn[maxn << 2], tag[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
inline void pushdown(const int& p)
{
    if (!tag[p]) return;
    minn[ls] += tag[p], minn[rs] += tag[p];
    tag[ls] += tag[p], tag[rs] += tag[p];
    tag[p] = 0;
}
void build(int l, int r, int p)
{
    minr[p] = r, minn[p] = 1 << 30;
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
}
inline void pushup(const int& p)
{
    minn[p] = std::min(minn[ls], minn[rs]);
    if (minn[rs] == minn[p]) minr[p] = minr[rs];
    else minr[p] = minr[ls];
}
void modify(int l, int r, int p, int ll, int rr, int k)
{
    if (ll > rr) return;
    if (l >= ll && r <= rr) return (void)(minn[p] += k, tag[p] += k);
    int mid = l + r >> 1;
    pushdown(p);
    if (ll <= mid) modify(l, mid, ls, ll, rr, k);
    if (rr > mid) modify(mid + 1, r, rs, ll, rr, k);
    pushup(p);
}
void set(int l, int r, int p, int pos, int k)
{
    if (l == r) return (void)(minn[p] = k);
    pushdown(p);
    int mid = l + r >> 1;
    if (pos <= mid) set(l, mid, ls, pos, k);
    else set(mid + 1, r, rs, pos, k);
    pushup(p);
}
pair<int, int> ask(int l, int r, int p, int ll, int rr)
{
    if (l >= ll && r <= rr)
    {
        if (minn[p] == 0) return make_pair(0, minr[p]);
        return make_pair(1 << 30, 0);
    }
    int mid = l + r >> 1;
    pair<int, int> res;
    res.first = 1 << 30, res.second = 0;
    pushdown(p);
    if (ll <= mid) res = ask(l, mid, p << 1, ll, rr);
    if (rr > mid)
    {
        pair<int, int> t = ask(mid + 1, r, p << 1 | 1, ll, rr);
        if (res.first >= t.first) res = t;
    }
    return res;
}
}  // namespace Seg
int main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]), a[i] = i - a[i];
    for (int i = 1; i <= m; ++i) read(Q[i].l), read(Q[i].r), Q[i].l++, Q[i].r = n - Q[i].r, Q[i].id = i;
    std::sort(Q + 1, Q + 1 + m, cmp);
    Seg::build(1, n, 1);
    int p = n;
    for (int i = 1; i <= m; ++i)
    {
        while (p >= Q[i].l)
        {
            if (a[p] > 0) Seg::set(1, n, 1, p, a[p]);
            else if (a[p] == 0)
            {
                Seg::modify(1, n, 1, p + 1, n, -1);
                Bit::add(p, 1);
                pair<int, int> t = Seg::ask(1, n, 1, p + 1, n);
                while (t.first != (1 << 30))
                {
                    Bit::add(t.second, 1);
                    Seg::modify(1, n, 1, t.second + 1, n, -1);
                    Seg::set(1, n, 1, t.second, n + 100);
                    t = Seg::ask(1, n, 1, p + 1, n);
                }
            }
            --p;
        }
        ANS[Q[i].id] = Bit::ask(Q[i].l, Q[i].r);
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ANS[i]);
    return 0;
}
本文标题:[Codeforces]#668 div2
本文作者:Clouder
本文链接: https://www.codein.icu/cf1405/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇