AtCoder Beginner Contest 246（A ~ E）

Skykguj

发布于 2022-09-09 12:07:33

7140

发布于 2022-09-09 12:07:33

文章被收录于专栏：Skykguj 's BlogSkykguj 's Blog

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;
}