[Codeforces]Educational Round 93题解(A-E)
|
64
|
0
|
题解

586 字
|
3 分钟
本文最后更新于 161 天前，其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

补题。ABC都挺水的，D、E有一定难度。

C

求前缀和 $sum(i)$，要求 $sum(i) – sum(j) = i – j$，转化为 $sum(i) – i = sum(j) – j$，用桶记录一下即可。

#include <cstdio>
#include <algorithm>
#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++;
}
inline void read(char *s)
{
    static char c;
    for (; !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) *s++ = c;
    *s = '\0';
}
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 = 1e6 + 100;
int T,n,sum[maxn],cnt[2 * maxn];
char s[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        read(s + 1);
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + s[i] - 48;
        for (int i = 1; i <= n; ++i) cnt[sum[i] - i + maxn] = 0;
        long long ans = 0;
        cnt[0 + maxn] = 1;
        for (int i = 1; i <= n; ++i)
        {
            ans += cnt[sum[i] - i + maxn];
            cnt[sum[i] - i + maxn]++;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

B

删零是没有意义的，只能创造机会给另一个人一次消去更多的一，因此二人都会贪心找最长的一来删除。
找出所有一段长度，然后模拟一下即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#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++;
}
inline void read(char *s)
{
    static char c;
    for (; !isdigit(c); c = nc());
    for (; isdigit(c); c = nc()) *s++ = c;
    *s = '\0';
}
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 = 110;
int T;
char s[maxn];
int bel[maxn],len[maxn],cnt;
int main()
{
    read(T);
    while(T--)
    {
        read(s + 1);
        int n = strlen(s + 1);
        cnt = 0;
        for (int i = 1; i <= n; ++i) bel[i] = 0;
        for (int i = 1; i <= n; ++i)
            if (s[i] == '1')
            {
                if (s[i] == s[i - 1]) bel[i] = bel[i - 1], len[bel[i]]++;
                else bel[i] = ++cnt, len[cnt] = 1;
            }
        std::sort(len + 1, len + 1 + cnt);
        int flag = 1, ans = 0;
        for (int i = cnt; i > 0; i -= 2) ans += len[i];
        printf("%d\n", ans);
    }
    return 0;
}

A

两边之和大于第三边是三角形要求，因此选开头两个数和最后一个数，如果能组成三角形则无解。

#include <cstdio>
#include <algorithm>
#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++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
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;
int T,n;
int a[maxn];
int main()
{
    read(T);
    while(T--)
    {
        read(n);
        for (int i = 1; i <= n; ++i) read(a[i]);
        if(a[1] + a[2] > a[n]) puts("-1");
        else printf("%d %d %d\n",1,2,n);
    }
    return 0;
}

D

构造矩形，考虑怎么搭配可以最大。发现大配大一定是最好的，例如有 $r_1 < r_2$ 与 $g_1 < g_2$，若小配小大配大则 $r_1 \times g_1 + r_2 \times g_2$，若小大配则 $r_1 \times g_2 + r_2 \times g_1$，相减得 $r_1 \times (g_1-g_2) + r_2 \times (g_2 – g_1)$，化简得 $(r_2 – r_1) \times (g_2 – g_1) > 0$，说明小小配、大大配一定更优。
既然如此，维护三个大根堆，每次选最大的两个即可。
然而似乎是假的，那么看数据范围小考虑动态规划。
显然三维，$f(i,j,k)$ 代表用了 $i$ 个 $R$，$j$ 个 $G$，$k$ 个 $B$ 时的最大面积，然后转移顺序懒得想，直接乱打个记搜。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctype.h>

const int bufSize = 1e6;
#define DEBUG
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++;
}
inline void read(char* s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
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 = 210;
int R, G, B;
long long f[maxn][maxn][maxn], ans;
int r[maxn], g[maxn], b[maxn];
bool cmp(const int& a, const int& b) { return a > b; }
void dfs(int i, int j, int k)
{
    if (f[i][j][k] != -1) return;
    f[i][j][k] = 0;
    if (i && j) dfs(i - 1, j - 1, k), f[i][j][k] = std::max(f[i][j][k], f[i - 1][j - 1][k] + r[i] * g[j]);
    if (i && k) dfs(i - 1, j, k - 1), f[i][j][k] = std::max(f[i][j][k], f[i - 1][j][k - 1] + r[i] * b[k]);
    if (j && k) dfs(i, j - 1, k - 1), f[i][j][k] = std::max(f[i][j][k], f[i][j - 1][k - 1] + g[j] * b[k]);
    if (i) dfs(i - 1, j, k), f[i][j][k] = std::max(f[i][j][k], f[i - 1][j][k]);
    if (j) dfs(i, j - 1, k), f[i][j][k] = std::max(f[i][j][k], f[i][j - 1][k]);
    if (k) dfs(i, j, k - 1), f[i][j][k] = std::max(f[i][j][k], f[i][j][k - 1]);
    ans = std::max(ans, f[i][j][k]);
}
int main()
{
    read(R), read(G), read(B);
    for (int i = 1; i <= R; ++i) read(r[i]);
    for (int i = 1; i <= G; ++i) read(g[i]);
    for (int i = 1; i <= B; ++i) read(b[i]);
    std::sort(r + 1, r + 1 + R, cmp);
    std::sort(g + 1, g + 1 + G, cmp);
    std::sort(b + 1, b + 1 + B, cmp);
    memset(f, -1, sizeof(f));
    dfs(R, G, B);
    printf("%lld\n", ans);
    return 0;
}

E

考虑无变化时如何操作，发现每个闪电后面都接上当前伤害最大的法术，可以造成最大的总伤害。也就是总伤害再加上最大的前闪电数量个伤害，即为当前伤害。
显然总伤害开个变量维护即可，问题转化为求前 $k$ 大和，然而特殊情况为前 $k$ 大全是闪电，那么一定有一个闪电没法加倍，而只能让 $k + 1$ 大加倍，特判这种情况，让最小的闪电不加倍即可。
用 set 随便维护一下。实现比较冗杂，交了好多发才过。

#include <cstdio>
#include <set>
#include <algorithm>
#include <ctype.h>
using namespace std;
#define DEBUG
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++;
}
inline void read(char *s)
{
    static char c;
    for (; !isalpha(c); c = nc());
    for (; isalpha(c); c = nc()) *s++ = c;
    *s = '\0';
}
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;
}
int n;
set<pair<int,int>,greater<pair<int,int> > > all;
set<pair<int,int> > sel,selli;
int lightnum;
long long selsum,sum;
inline void maintain()
{
    while(sel.size() < lightnum && !all.empty())
    {
        pair<int,int> t = *all.begin();
        all.erase(all.begin());
        if (t.second) selli.insert(t);
        sel.insert(t), selsum += t.first;
    }
    while(!sel.empty() && !all.empty())
    {
        pair<int,int> t1 = *all.begin(),t2 = *sel.begin();
        if(t2.first < t1.first || (t2.first == t1.first && t2.second == 1 && t1.second == 0))
        {
            all.insert(t2),all.erase(t1);
            sel.insert(t1),sel.erase(t2);
            if(t2.second) selli.erase(t2);
            if(t1.second) selli.insert(t1);
            selsum -= t2.first,selsum += t1.first;
        }
        else break;
    }
    while(sel.size() > lightnum)
    {
        pair<int,int> t = *sel.begin();
        sel.erase(t);
        all.insert(t);
        if(t.second) selli.erase(t);
        selsum -= t.first;
    }
}
inline void insert(int x,int light)
{
    sum += x;
    if(light) ++lightnum;
    all.insert(make_pair(x,light));
    maintain();
}
inline void del(int x,int light)
{
    sum -= x;
    if(light) --lightnum;
    maintain();
    pair<int,int> t = make_pair(x,light);
    if(all.find(t) != all.end()) all.erase(t);
    else if(sel.find(t) != sel.end()) 
    {
        sel.erase(t),selsum -= t.first;
        if(t.second) selli.erase(t);
    }
    maintain();
}
int main()
{
    read(n);
    while(n--)
    {
        int type,x;
        read(type),read(x);
        if(x > 0) insert(x,type);
        else del(-x,type);
        maintain();
        long long ans = sum;
        ans += selsum;
        if(!selli.empty() && selli.size() == sel.size())
        {
            ans -= selli.begin()->first;
            if(!all.empty()) ans += all.begin()->first;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

相关文章

  1. [Atcoder][Codeforces]简单题选做练习笔记 title: ‘Atcoder简单题选做练习笔记’date: 2020-11-12 1 […]...
  2. [Atcoder][CF]简单题选做练习笔记2 一些题的练习笔记。...
  3. [Atcoder]M-Solutions 题解 Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：htt […]...
  4. [Codeforces]Round 657 div2 Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：htt […]...
本文标题：[Codeforces]Educational Round 93题解(A-E)
本文作者：Clouder
本文链接： https://www.codein.icu/cf1398/
转载请标明。
Codeforces比赛
暂无评论

发送评论 编辑评论




























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



上一篇
下一篇