[Atcoder]ABC176 题解
本文最后更新于 155 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

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

前言

这次A-E普遍较水,F不会写。等赛后补题。

A

$T$ 秒做 $X$ 贡献,求做 $N$ 贡献的最少时间。
向上取整的除法即可。

#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++;
}
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,x,t;
int main()
{
    read(n), read(x), read(t);
    printf("%d\n", (n + x - 1) / x * t);
    return 0;
}

B

按题意模拟即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctype.h>
const int maxn = 5e6 + 100;
char s[maxn];
int main()
{
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    long long t = 0;
    for (int i = 1; i <= n; ++i) t = t + s[i] - 48;
    if(t % 9 == 0) puts("Yes");
    else puts("No");
    return 0;
}

C

可以给每个人加高度,要求每个人前面没有比他高的。
求最少共加多少高度。
贪心地加高度,不如上一个人高则加到上一个人高。

#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++;
}
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 = 2e5 + 100;
int n;
long long a[maxn];
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    long long ans = 0;
    for (int i = 1; i <= n; ++i) if (a[i] < a[i - 1]) ans += a[i - 1] - a[i], a[i] = a[i - 1];
    printf("%lld\n",ans);
    return 0;
}

D

坑了我三次提交,罚时罚到天上去了。可能是我想复杂了。
给一张矩阵,四向通行,加上一个魔法:在 $(x,y)$ 可以跳跃到 $(x-2,y-2)$ 到 $(x+2,y+2)$ 为左上、右下顶点的子矩阵中的任意可行位置。
给定起点终点,问最少用多少次魔法。

首先四向通行是不计贡献的,可以并查集将每个连通块合起来。
然后直接暴力建图,枚举每个点,枚举它能跳跃到的点,若属于不同的连通块,则在二者之间连边。
然后从起点所属连通块开始广度优先搜索,就能求出最短路。

#include <cstdio>
#include <queue>
#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++;
}
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 = 2e3 + 100;
const int maxm = 2e6 + 100;
const int inf = 1061109567;
int n,m;
char s[maxm];
bool mp[maxn][maxn];
int num[maxn][maxn];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int fa[maxm],cnt;
int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
inline void unite(int x,int y)
{
    x = find(x),y = find(y);
    if(x == y) return;
    fa[x] = y;
}
struct node
{
    int to,next;
}E[5*maxm];
int head[maxm];
inline void add(const int &x,const int &y)
{
    static int tot = 0;
    E[++tot].next = head[x],E[tot].to = y,head[x] = tot;
}
int dis[maxn*maxn];
int main()
{
    read(n),read(m);
    int sx,sy,tx,ty;
    read(sx),read(sy),read(tx),read(ty);
    memset(dis,0x3f,sizeof(dis));
    for (int i = 1; i <= n; ++i) 
    {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; ++j) if (s[j] == '.') mp[i][j] = 1; else mp[i][j] = 0;
    }
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) num[i][j] = ++cnt, fa[cnt] = cnt;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (!mp[i][j]) continue;
            for (int k = 0; k < 4; ++k)
            {
                int nx = i + dx[k], ny = j + dy[k];
                if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
                if(!mp[nx][ny]) continue;
                unite(num[i][j], num[nx][ny]);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int x = std::max(i - 2, 1); x <= i + 2 && x <= n; ++x)
            {
                for (int y = std::max(j - 2, 1); y <= j + 2 && y <= m; ++y)
                {
                    if(!mp[x][y]) continue;
                    if (find(num[x][y]) == find(num[i][j])) continue;
                    add(find(num[x][y]), find(num[i][j]));
                }
            }
        }
    }
    std::queue<int> q;
    q.push(find(num[sx][sy]));
    dis[find(num[sx][sy])] = 0;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int p = head[u]; p; p = E[p].next)
        {
            int v = E[p].to;
            if(dis[v] > dis[u] + 1) dis[v] = dis[u] + 1,q.push(v);
        }
    }
    if(dis[find(num[tx][ty])] < inf) printf("%d\n",dis[find(num[tx][ty])]);
    else puts("-1");
    return 0;
}

E

每个炸弹覆盖所属的整行、整列,放置一个炸弹,问最多炸到多少目标。
一个很自然的想法是对行列开桶,取最大的行、列组成的点。
然而这种方法可能会造成答案偏大,比如下面这个例子:
110
000
101
行最大是第一、第三行,而列最大是第一列,这样统计出来答案是 $4$,但实际答案是 $3$,也就是可能出现重复点。
那么答案下界是 $maxx + maxy – 1$,上界是 $maxx + maxy$,考虑判断能否取到上界即可。
定义 $row(i)$ 为行 $i$ 上的目标个数,$col(i)$ 为列 $i$ 上的目标个数。
答案一定在 $row(x) = maxx$ 且 $col(y) = maxy$ 的某 $(x,y)$ 取到。
问题转化为,判断是否存在 $(x,y)$ 使得 $row(x) = maxx$ 且 $col(y) = maxy$ 且 $(x,y)$ 上无目标。
考虑枚举可行的 $x$,然后依次检查该行中无目标的位置 $i$,看是否存在 $row(i) = maxy$,如果存在则答案可以取到上界。
上述过程可以使用 bitset 进行常数优化。

#include <cstdio>
#include <bitset>
#include <algorithm>
#include <vector>
#include <ctype.h>
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, k;
int row[maxn], col[maxn];
bool vis[maxn];
bitset<maxn> bs;
vector<int> v[maxn];
int main()
{
    read(n), read(m), read(k);
    for (int i = 1; i <= k; ++i) 
    {
        int x, y;
        read(x), read(y), row[x]++, col[y]++, v[x].push_back(y);
    }
    int maxx = 0,maxy = 0;
    for (int i = 1; i <= n; ++i) maxx = std::max(maxx, row[i]);
    for (int i = 1; i <= m; ++i) maxy = std::max(maxy, col[i]);
    for (int i = 1; i <= m; ++i) if (col[i] == maxy) bs.set(i);
    int ans = maxx + maxy - 1;
    for (int i = 1; i <= n; ++i)
        if (row[i] == maxx)
        {
            bitset<maxn> ts;
            for (vector<int>::iterator it = v[i].begin(); it != v[i].end(); ++it) ts.set(*it);
            ts.flip();
            if ((ts & bs).any())
            {
                ans = maxx + maxy;
                break;
            }
        }
    printf("%d\n",ans);
    return 0;
}
本文标题:[Atcoder]ABC176 题解
本文作者:Clouder
本文链接: https://www.codein.icu/atcoderabc176/
转载请标明。
暂无评论

发送评论 编辑评论

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