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

E - Bishop 2

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

题意
有一个 $n \times n$ 的棋盘,能走的地方为 . 不能走的地方为 #,从 $(i, j)$ 出发可一步到达对角线上的任意一个之间无 # 的点。
求从 $(A_x, A_y)$ 到达 $(B_x, B_y)$ 的最少步数。

题解
时限 6s,直接 BFS,每次更新四个方向,能走多远走多远,如果遇到不能更新的地方就直接 break 掉。

最后修改:2022 年 04 月 04 日
赠人玫瑰,手有余香。您的赞赏是对我最大的支持!