[Atcoder]ABC175 题解(A-E)
本文最后更新于 160 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

乱序开题。

C

移动到最小正数,然后到最大负数。
最小正数和最大负数的绝对值都是 $< d$ 的,而如果剩余步数为偶数次,则一定回到正数,否则一定回到负数。
没看到 $X$ 可以为负连WA两发……给 $X$ 取个绝对值就好了,一样的。

#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;
}
long long X,K,D;
int main()
{
    read(X),read(K),read(D);
    X = std::abs(X);
    long long steps = X / D;
    if(steps >= K)
    {
        printf("%lld\n",X - K * D);
        return 0;
    }
    K -= steps;
    long long mina = X - steps * D, minb = std::abs(mina - D);
    if(K & 1) printf("%lld\n",minb);
    else printf("%lld\n",mina);
    return 0;
}

B

这数据范围属实有点简单,枚举暴力。
注意相同长度不能取。

#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 = 110;
int n;
int a[maxn];
int d[10];
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    int ans = 0;
    for(int i = 1;i<=n;++i) for(int j = i + 1;j<=n;++j) for(int k = j + 1;k<=n;++k)
    {
        if(a[i] == a[j] || a[i] == a[k] || a[j] == a[k]) continue;
        d[1] = a[i],d[2] = a[j],d[3] = a[k];
        std::sort(d + 1,d + 1 + 3);
        if(d[1] + d[2] > d[3]) ++ans;
    }
    printf("%d\n",ans);
    return 0;
}

A

hmmm,按题意模拟即可。

#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;
}
char s[4];
int len[4];
int main()
{
    read(s + 1);
    int ans = 0;
    for(int i = 1;i<=3;++i) if(s[i] == 'R')  len[i] = len[i-1] + 1,ans = std::max(ans,len[i]);
    printf("%d\n",ans);
    return 0;
}

D

从每个点开始,不超过 $N$ 步后一定能回到原来访问过的点,即遇到环。在环内消耗掉剩余的步数即可。
可以证明,每个点开始最多遇到一个简单环,找出环即可。
枚举起始点暴力,然后重复走环消耗次数。
然而说着简单,做着似乎没那么简单……
这里给一个实现方法,记录 $f(i)$ 为最多走 $i$ 次的最大贡献,$sum(i)$ 为走 $i$ 步的前缀和,记录 $vis(i)$ 为访问到 $i$ 点的步数,计算出环长度,然后 $sum(i) – sum(j)$ 获取全环贡献,若 $> 0$ 则加上能走的次数乘上全环贡献,最后再加上 $f(剩余步数)$ 即可。

#include <algorithm>
#include <cstdio>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    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 = 5e3 + 100;
int n, k, P[maxn], C[maxn];
long long sum[maxn], f[maxn];
int vis[maxn];
inline long long check(int s)
{
    for (int i = 0; i <= n; ++i) sum[i] = f[i] = -(1ll << 60), vis[i] = 0;
    sum[0] = 0;
    int u = s, i = 1;
    for (;; ++i)
    {
        u = P[u];
        sum[i] = sum[i - 1] + C[u];
        f[i] = std::max(f[i - 1], sum[i]);
        if (vis[u]) break;
        else vis[u] = i;
    }
    if (k <= i) return f[k];
    long long num = sum[i] - sum[vis[u]];
    if (num <= 0) return f[i];
    int len = i - vis[u];
    int times = (k - vis[u]) / len, pos = k - times * len;
    return f[pos] + num * times;
}
int main()
{
    read(n), read(k);
    for (int i = 1; i <= n; ++i) read(P[i]);
    for (int i = 1; i <= n; ++i) read(C[i]);
    long long ans = check(1);
    for (int i = 2; i <= n; ++i) ans = std::max(ans, check(i));
    printf("%lld\n", ans);
    return 0;
}

E

每次向下、向右,可以选择选与不选当前格上的数计入贡献,每行限制选三个,求左上角到右下角的最大贡献和。
如果没有每行选三个,就是非常经典的普及组难度的动态规划问题。
既然有每行三个的限定,那么我们直接暴力加一维就好了。
感觉空间有点吃紧,但给出了 $1024$ MB 的限制,还是硬着头皮交了一发,结果过了……
如果害怕的话,可以滚动掉第一维。给出两种实现。
不滚动:

const int maxn = 3100;
int n, m, num;
int a[maxn][maxn];
long long f[maxn][maxn][4], g[maxn][maxn];
int main()
{
    read(n), read(m), read(num);
    while (num--)
    {
        int x, y, z;
        read(x), read(y), read(z);
        a[x][y] = z;
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int k = 0; k <= 3; ++k)
            {
                f[i][j][k] = std::max(f[i][j][k], f[i - 1][j][k]);
                f[i][j][k] = std::max(f[i][j][k], f[i][j - 1][k]);
                if (k) 
                {
                    f[i][j][k] = std::max(f[i][j][k], g[i - 1][j] + a[i][j]);
                    f[i][j][k] = std::max(f[i][j][k], f[i][j - 1][k - 1] + a[i][j]);
                }
            }
            for (int k = 0; k <= 3; ++k) g[i][j] = std::max(g[i][j], f[i][j][k]);
        }
    }
    printf("%lld\n", g[n][m]);
    return 0;
}

滚动:

#include <algorithm>
#include <cstdio>
#include <ctype.h>
#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;
}
const int maxn = 3100;
int n, m, num;
int a[maxn][maxn];
long long f[2][maxn][4], g[2][maxn];
int main()
{
    read(n), read(m), read(num);
    while (num--)
    {
        int x, y, z;
        read(x), read(y), read(z);
        a[x][y] = z;
    }
    int now = 1, last = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int k = 0; k <= 3; ++k)
            {
                f[now][j][k] = std::max(f[now][j - 1][k], f[last][j][k]);
                if (k)
                {
                    f[now][j][k] = std::max(f[now][j][k], g[last][j] + a[i][j]);
                    f[now][j][k] = std::max(f[now][j][k], f[now][j - 1][k - 1] + a[i][j]);
                }
            }
            g[now][j] = 0;
            for (int k = 0; k <= 3; ++k) g[now][j] = std::max(g[now][j], f[now][j][k]);
        }
        now ^= 1, last ^= 1;
    }
    printf("%lld\n", g[last][m]);
    return 0;
}

F

暂时不会,等补题。

本文标题:[Atcoder]ABC175 题解(A-E)
本文作者:Clouder
本文链接: https://www.codein.icu/atcoderabc175/
转载请标明。
暂无评论

发送评论 编辑评论

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