signed

QiShunwang

“诚信为本、客户至上”

AtCoder Beginner Contest 196 题解报告,AC了 A~E,缺 F

2021/3/21 11:58:17   来源:

AtCoder Beginner Contest 196

https://atcoder.jp/contests/abc196/tasks。

A - Difference Max

https://atcoder.jp/contests/abc196/tasks/abc196_a。

签到题,能看懂题目意思,应该就可以完成。给我们四个数字 a,b,c,d,找出一个 a \leq x \leq b 和 c \leq y \leq d,使得 x-y 的结果最大。

由于这四个数据是不相关的,要 x-y 最大,那么要求 x 最大同时 y 最小即可。

本题的数据非常小,用 int 即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int x=max(a,b);
    int y=min(c,d);
    cout<<x-y<<"\n";
    return 0;
}

B - Round Down

https://atcoder.jp/contests/abc196/tasks/abc196_b。

给一个数字,要求将这个数字向下取整。如果不看本题的数据范围,本题是非常简答的一个题目,直接使用 round() 函数即可,也可以直接将 double 类型转化成为整数。而本题的数据范围是 0 \leq X \leq 10^{100},远超出了 C++ 的数据表示范围。因此本题变成输出字符串 X 小数点前面的数据即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin>>s;
    for (int i=0; i<s.length(); i++) {
        if (s[i]!='.') {
            cout<<s[i];
        } else {
            break;
        }
    }
    cout<<"\n";
    return 0;
}

如果本题使用 find 来找到小数点,然后在输出小数点前面的数据。需要注意特例,也就是输入的数据没有小数点的情况。

C - Doubled

https://atcoder.jp/contests/abc196/tasks/abc196_c。

给一个 1 到 10^{12} 范围内的数据 N,问区间 [1, N] 之间有几个数字是左右对称。即满足数据 X 的长度为偶数,而且将 X 分为两个长度相同部分,左边的数据和右边的数据相等。例如 1313 这个数据可以分为 13 和 13

本题如果使用正问题,即从区间 [1, N] 之间暴力枚举每个 X,判断是否满足条件。这样的话,我们需要执行最多 10^{12} 次,哪怕是 O(N) 时间复杂度的算法,本题也是一个超时。

因此我们考虑反问题,即从 1 开始将两个数字 X 合并,看生成的数字是否超过 N。如果超过,则答案为 X-1。这样我们最多需要暴力枚举 \frac{10^{12}}{2}=10^{6} 次,这样 O(N) 时间复杂度可以在 1 秒内完成。

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main() {
    ll n;
    cin>>n;
    ll ans=0;
    for (ll i=1; ; i++) {
        //将 i 合并
        string s=to_string(i)+to_string(i);
        ll t=stoll(s);
        if (t>n) {
            cout<<i-1<<"\n";
            return 0;
        }
    }
    return 0;
}

上面的代码要求 C++11 以上版本,因为使用了 to_string() 和 stoll() 这两个函数。如果是在 NOI 竞赛,不支持 C++11 版本,我们可以使用下面的代码。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
typedef long long ll;

ll to_number(string s) {
    ll ans=0;
    for (int i=0; i<s.length(); i++) {
        ans = ans*10+s[i]-'0';
    }
    return ans;
}

int main() {
    ll n;
    cin>>n;
    ll ans=0;
    for (ll i=1; ; i++) {
        //将 i 合并
        char buf[30];
        sprintf(buf, "%d%d", i, i);
        string s=buf;
        ll t=to_number(s);
        if (t>n) {
            cout<<i-1<<"\n";
            return 0;
        }
    }
    return 0;
}

D - Hanjo

https://atcoder.jp/contests/abc196/tasks/abc196_d。

有一个 H*W 矩形房间,我们有 A 个无法区分 2*1 大小榻榻米和 B 个无法区分 1*1 大小榻榻米,保证 2A+B=H*W。问有几种办法使用这些榻榻米铺满房间,如果榻榻米旋转或者映射都算不同的方法。

题目阅读完后,就知道本题可以使用 DFS 来实现。我们只需要套用 DFS 模板即可。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int h,w;
int ans=0;

/*
第一个参数 i,场所
第二个参数 bit, 榻榻米摆的位置
第三个参数 a,a种榻榻米数量
第四个参数 b,b种榻榻米数量
 */
void dfs(int i, int bit, int a, int b) {
    if (i==h*w) {
        ans++;
        return;
    }
    if (bit & 1<<i) {
        dfs(i+1, bit, a, b);
        return;
    }
    if (b) {
        dfs(i+1, bit|1<<i, a, b-1);
    }
    if (a) {
        if (i%w!=w-1 && (~bit&1<<(i+1))) {
            dfs(i+1, bit|1<<i|1<<(i+1), a-1, b);
        }
        if (i+w<h*w) {
            dfs(i+1, bit|1<<i|1<<(i+w), a-1, b);
        }
    }
}
int main() {
    int a,b;
    cin>>h>>w>>a>>b;
    dfs(0,0,a,b);
    cout<<ans<<"\n";
    return 0;
}

本题使用位操作相对会简单点,也可以定义一个 20*20 的二维数组来表示区域已经给占用。

E - Filters

题目看上去像一个数学题,因为本题 Q 的最大值为 2e5,我们没法去递归。根据题目的意思,我们知道一共有三个 f_i(x) \quad i=1,2,3。我们先分类讨论一下这三个函数的性质。

f_1(x)=x+a_i。我们知道这是一个函数族,是与f_1(x)=x 平行的函数族。该函数的图像如下图,

f_2(x)=max(x, a_i)。当 a_i>x 的时候,是一个平行于 x 轴的直线;当 x>a_i 时候,是一个斜率为 1 的直线。如下图

f_3(x)=min(x, a_i)。同理,如下图

这样,我们结合这三个图形,可以绘制出该函数的总体图像为

注意,上面的图像,取 a_i=0。随着 a_i 的变化,只是影响到斜率为 1 的直线和 x 轴的交点。

因此,我们只要根据输入的数据,定义好最低点 low,最高点 high 和偏移量即可,同时实现一个 clamp() 函数即可。注意一个细节,数据类型要用 long long,我本来以为 int 够了,没想到有一个测试用例 WA 了。哦,想明白了,因为 N 有 2e5 个,在极限情况下,我们的偏移量可能是 2*10^5*10^9=2*10^{14},超过了 int 范围,我真是个🐖。

#include <iostream>

using namespace std;
typedef long long ll;
const ll INF=2e18;

ll clamp(ll x, ll min, ll max) {
    if (x>max) {
        return max;
    }
    if (x<min) {
        return min;
    }
    return x;
}

int main() {
    ll n;
    cin>>n;

    ll low=-INF;
    ll high=INF;
    ll bias=0;

    for (ll i=1; i<=n; i++) {
        ll a,t;
        cin>>a>>t;
        if (1==t) {
            low+=a;
            high+=a;
            bias+=a;
        } else if (2==t) {
            low=max(low, a);
            high=max(high,a);
        } else {
            low=min(low, a);
            high=min(high, a);
        }
    }

    ll q;
    cin>>q;
    for (ll i=1; i<=q; i++) {
        ll x;
        cin>>x;
        cout<<clamp(x+bias, low, high)<<"\n";
    }

    return 0;
}