AtCoder Beginner Contest 246（A ~ E）

Skykguj

2022 年 04 月 02 日

710 次浏览

暂无评论

1484字数

比赛题解

A - Four Points

题目链接：http://www.cspoi.net/problem/4003

题意
$xy$ 平面上有一个边平行于 $x$ 轴和 $y$ 轴的矩形。已知其中三个顶点，求出另外一个顶点 $(x4,y4)$。

题解
矩形的边平行于坐标轴，问题转化为 $x1,x2,x3$ 中出现次数为 $1$ 次的数为多少， $y1,y2,y3$ 中出现次数为 $1$ 次的数为多少。把 $x,y$ 分别异或起来输出即可。
时间复杂度 $O(1)$。

Code:

#include <iostream>
#include <cstdio>
int x, y, ansx, ansy;
int main()
{
    for (int i = 0; i < 3; i ++ )
    {
        scanf("%d%d", &x, &y);
        ansx ^= x, ansy ^= y;
    }
    printf("%d %d\n", ansx, ansy);
    return 0;
}

B - Get Closer

题目链接：http://www.cspoi.net/problem/4004

题意
给出 $A$ 和 $B$，求出 $(0, 0)$ 向 $(A, B)$ 前进 1 个单位后的坐标。

题解
设 $(0, 0)$ 到 $(A, B)$ 的距离是 $d$，那么答案就是 $(\frac{A}{d}, \frac{B}{d})$；根据两点坐标距离公式，得 $d = \sqrt{A^2 + B^2}$，输出求出的数字即可。

Code:

#include <iostream>
#include <cmath>
#include <algorithm>

int main()
{
    double x, y;
    scanf("%lf%lf", &x, &y);
    double t = std::sqrt(x * x + y * y);
    printf("%.12lf %.12lf\n", x / t, y / t);
    return 0;
}

C - Coupon

题目链接：http://www.cspoi.net/problem/4005

题意
有 $n$ 个商品，每个商品的价格为 $a_i$。有 $k$ 张优惠券，每张优惠券可以让某个商品的价格降低 $x$。
即商品原价为 $a$，使用 $k$ 张优惠券后，商品的现价为 $\max\{a−kx,0\}$。
求使用优惠券买下所有商品所需要的价格。

题解
考虑贪心，先对所有物品尽可能多的使用代金券，让这些优惠券能抵扣的价格等于其面值。
如果还剩余一些代金券，将剩余的面额从大到小排序，依次使用，这样的贪心策略可以使代金券降低的价格最大。
时间复杂度为 $O(n \log n)$。

Code:

#include <iostream>
#include <cmath>
#include <algorithm>

const int N = 2e5 + 10;
int a[N];

int main()
{
    int n, k, x;
    scanf("%d%d%d", &n, &k, &x);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]); 
        int t = std::min(a[i] / x, k);
        k -= t;
        a[i] -= t * x;
    }
    std::sort(a + 1, a + 1 + n, std::greater<int> ());
    long long ans = 0;
    for (int i = k + 1; i <= n; i ++ )
        ans += a[i];

    printf("%lld", ans);
    return 0;
}

D - 2-variable Function

题目链接：http://www.cspoi.net/problem/4006

题意
设 $f(a,b) = a^3 + a^2*b + a*b^2 + b^3$。
给出一个正整数 $N$，找到最小的 $X$，满足 $X \geq N$ 且 $X = f(a,b)$。

题解
考虑从小到大枚举 $a$，在 $f(a,b) \geq n$ 的条件下，最小的 $b$ 一定有单调不升的特性，满足双指针的条件，所以可用双指针解决本题，时间复杂度 $O(可过)$。

Code:

#include <iostream>
#include <cmath>
#include <algorithm>

long long n, ans = 0x3f3f3f3f3f3f3f3f;

long long f(long long a, long long b)
{
    return (a * a * a + b * b * b + a * a * b + b * b * a);
}

int main()
{
    scanf("%lld", &n);
    for (long long i = 0, j = 1e6; i <= 1e6; i ++ )
        while (f(i, j) >= n && j >= 0)
        {
            ans = std::min(ans, f(i, j));
            j -- ;
        }

    printf("%lld\n", ans);
    return 0;
}