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

一场有趣的CF比赛

Before the Beginning

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

A

考虑做 $k$ 根火把最少需要 $k$ 个煤炭,需要 $k \times y + k$ 个木棍。
每次交易增加 $x – 1$ 个木棍,做除法向上取整即可。

#include <cstdio>
int T;
long long x,y,k;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld %lld %lld",&x,&y,&k);
        long long need = k * y + k - 1;
        printf("%lld\n",(x - 2 + need) / (x - 1) + k);
    }
    return 0;
}

B

未被锁住的元素可以在未被锁住的位置任意移动。
降序排序即可。
考虑在某个 $j$ 点是最大的前缀和小于零的点,将一个更小的数调换到前缀中,该点前缀和一定更小于零,而位置可能右移使答案更劣。因此贪心地降序排序是正确的。

#include <cstdio>
#include <algorithm>
const int maxn = 110;
int T,n,a[maxn],locked[maxn],b[maxn],bcnt;
int main()
{
    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", locked + i);
        bcnt = 0;
        for (int i = 1; i <= n; ++i) if(!locked[i]) b[++bcnt] = a[i];
        std::sort(b + 1 ,b + 1 + bcnt);
        for (int i = 1; i <= n; ++i) if(!locked[i]) a[i] = b[bcnt--];
        for (int i = 1; i <= n; ++i) printf("%d ",a[i]);
        puts("");
    }
    return 0;
}

C

顺序打怪,可以考虑动态规划。
定义 $f(i,0)$ 为杀前 $i$ 个,最后是朋友杀的,消耗的最少代价。$f(i,1)$ 则最后是你杀的。
随便转移一下即可。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
int T,n,a[maxn],f[maxn][2];
int main()
{
    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) f[i][0] = f[i][1] = 1 << 30;
        f[1][0] = a[1];
        f[2][0] = a[1] + a[2], f[2][1] = a[1];
        for (int i = 3; i <= n; ++i)
        {
            //I killed 1/2 monsters
            f[i][1] = min(f[i-1][0],f[i-2][0]);
            //friend killed 1/2 monsters
            f[i][0] = min(f[i - 1][1] + a[i], f[i - 2][1] + a[i - 1] + a[i]);
        }
        printf("%d\n",min(f[n][0],f[n][1]));
    }
    return 0;
}

D

多组询问修改,每次输出答案,很容易想到是数据结构题。
一条线上若干个点,要扫成两个点,从中间向两边扫。
若从两边向中间扫,扫到某个位置时,代价等价于从其后方向前扫到该位置。
例如:

...*..*....*....*...
.....**....*....*...
......*....*....*...
..........**....*...
...........*........

这种扫法,即从左往右扫,与:

...*..*....*....*...
...*..**........*...
...*..*.........*...
...**...........*...
...*............*...

代价是相同的。
那么直接考虑从内往外扫。
从非边界点的相邻两点开始,往外扫到边界两个点结束,贡献为 $R – L – dis$,其中 $dis$ 代表选择的两点的间隔。

...*..<-*....*->....*...

而且在多个点时依然成立,因为:选择的是相邻两点,其余点都会在路径上被合并到移动的点堆中。

那么要使代价最小,就是选择最大的相邻两点间隙。


静态问题解决了,考虑动态。

每次修改,要么加一个点,要么删一个点。

因为只考虑相邻点,添加一个点或是删除一个点能影响的间隙是有限的。
让每个点记录它到下一个点的距离。

....*....*..#.*...*....*....

可以发现,在 # 位置加入一个点,只会影响:

  1. 上一个点
  2. 下一个点
  3. 插入点

因此只需要获取到上、下点,即可维护。

可以用 multiset 来维护点的间隙,以距离降序排序。

点也可以用 set 来维护,方便寻找上一个、下一个点。

#include <cstdio>
#include <set>
using namespace std;
const int maxn = 1e5 + 100;
int n, m;
set<int> P;
multiset<int> D;
inline void addpoint(int x)
{
    set<int>::iterator it = P.insert(x).first;
    set<int>::iterator nex = it;
    ++nex;
    set<int>::iterator back;
    if (nex != P.end()) D.insert(*nex - x);
    if (it != P.begin()) back = it, D.insert(x - *(--back));
    if (it != P.begin() && nex != P.end()) D.erase(D.find(*nex - *back));
}
inline void delpoint(int x)
{
    set<int>::iterator it = P.find(x);
    set<int>::iterator nex = it;
    ++nex;
    set<int>::iterator back;
    if (nex != P.end()) D.erase(D.find(*nex - x));
    if (it != P.begin()) back = it, D.erase(D.find(x - *(--back)));
    if (it != P.begin() && nex != P.end()) D.insert(*nex - *back);
    P.erase(it);
}
inline void output()
{
    if (P.size() <= 2) return (void)(puts("0"));
    printf("%d\n", *P.rbegin() - *P.begin() - *D.rbegin());
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1, x; i <= n; ++i) scanf("%d", &x), addpoint(x);
    output();
    while (m--)
    {
        int opt, x;
        scanf("%d %d", &opt, &x);
        if (opt) addpoint(x);
        else delpoint(x);
        output();
    }
    return 0;
}

E

排序 $d$ 后,可以用二分找出 $\geq b$ 与 $< b$ 的怪物,将 $\geq b$ 怪物的数量记为 $big$.
考虑每个 $\geq b$ 的怪物,只需要它在 $\geq b$ 的怪物中排前 $a$ 个,那么它的伤害就不计贡献。
所以它的期望为:$d_i \times (1 – \dfrac{a}{big})$
化简为 $(1 – \dfrac{a}{big}) \times \prod d_i(d_i \geq b)$,排序后显然可以用前缀和优化。

而 $< b$ 的数,可以视作在 $big$ 个怪物中插空,共 $big + 1$ 个空,只有插在第 $a$ 个怪物后才能计贡献。
$(1 – \dfrac{a}{big + 1}) \times \prod d_i(d_i \leq b)$,同样用前缀和优化。

特殊地,当 $a > big$ 时,不可能受到伤害。

#include <algorithm>
#include <cstdio>
const int mod = 998244353;
const int maxn = 2e5 + 100;
int n, m, d[maxn], sum[maxn];
void exgcd(int a, int b, int& x, int& y)
{
    if (!b) return (void)(x = 1, y = 0);
    exgcd(b, a % b, y, x), y -= (a / b) * x;
}
inline int inv(int x) { int k1, k2; exgcd(x, mod, k1, k2); return k1; }
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", d + i);
    std::sort(d + 1, d + 1 + n);
    for (int i = 1; i <= n; ++i) sum[i] = (sum[i - 1] + d[i]) % mod;
    for (int i = 1, a, b; i <= m; ++i)
    {
        scanf("%d %d", &a, &b);
        int l = 1, r = n, mid, ans = 0;
        while (l <= r)
        {
            mid = l + r >> 1;
            if (d[mid] < b) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        if (n - ans < a) { puts("0"); continue; }
        long long bres = (1ll * ((sum[n] - sum[ans] + mod) % mod) * ((mod + 1 - 1ll * a * inv(n - ans)) % mod)) % mod;
        long long sres = (1ll * (sum[ans] % mod) * ((mod + 1 - 1ll * a * inv(n - ans + 1)) % mod)) % mod;
        printf("%lld\n", (bres + sres + 2 * mod) % mod);
    }
    return 0;
}

G

考虑使用线段树做标记,从左到右扫描。
当前点作为右端点,每个位置上若为 $0$ 代表可以为左端点,为 $1$ 代表不能为左端点。
考虑左端点何处可能合法,两种情况:恰好三次与零次。
因此就是两个线段:

  1. 零次时,上次出现位置到当前点。
  2. 三次时,倒数第四次到倒数第三次出现位置之间。

而不合法线段就是反过来的部分,每个数都对其不合法部分做标记,就能保证剩下的是所有条件下的合法位置。
不合法线段每次区间加一。
统计答案显然就是数零。
更改时,考虑撤销原先不合法线段,更新当前线段。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 5e5 + 100;
int n,a[maxn];
vector<int> pos[maxn];
int minn[maxn << 2], cnt[maxn << 2], tag[maxn << 2];
#define ls p<<1
#define rs p<<1|1
inline void pushup(int p)
{
    minn[p] = min(minn[ls], minn[rs]);
    cnt[p] = 0;
    if (minn[p] == minn[ls]) cnt[p] += cnt[ls];
    if (minn[p] == minn[rs]) cnt[p] += cnt[rs];
}
inline void pushdown(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)
{
    if (l == r) return (void)(cnt[p] = 1);
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs), pushup(p);
}
void add(int l,int r,int p,int ll,int rr,int k)
{
    if (l >= ll && r <= rr) return (void)(minn[p] += k, tag[p] += k);
    int mid = l + r >> 1;
    pushdown(p);
    if (ll <= mid) add(l, mid, ls, ll, rr, k);
    if (rr > mid) add(mid + 1, r, rs, ll, rr, k);
    pushup(p);
}
int ask(int l,int r,int p,int ll,int rr)
{
    if(l >= ll && r <= rr) return !minn[p] ? cnt[p] : 0;
    int mid = l + r >> 1,res = 0;
    pushdown(p);
    if(ll <= mid) res = ask(l,mid,ls,ll,rr);
    if(rr > mid) res += ask(mid + 1,r,rs,ll,rr);
    return res;
}
int main()
{
    scanf("%d",&n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) pos[i].push_back(0);
    build(1,n,1);
    long long res = 0;
    pos[a[1]].push_back(1), add(1, n, 1, 1, 1, 1);
    for (int i = 2; i <= n; ++i)
    {
        int s = pos[a[i]].size();
        add(1, n, 1, pos[a[i]][s - 1] + 1, i, 1);
        if (s >= 3) add(1, n, 1, pos[a[i]][s - 3] + 1, pos[a[i]][s - 2], -1);
        if (s >= 4) add(1, n, 1, pos[a[i]][s - 4] + 1, pos[a[i]][s - 3], 1);
        pos[a[i]].push_back(i);
        if (minn[1] == 0) res += cnt[1] - (n - i);
    }
    printf("%lld\n",res);
    return 0;
}
本文标题:[Codeforces]Educational Round 95
本文作者:Clouder
本文链接: https://www.codein.icu/cfedu95/
转载请标明。
暂无评论

发送评论 编辑评论

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