第五次上机 题解

提供了部分题目的个人题解,供参考。

E Ausar的非格式化倒序输出

关键点:以 scanf() == EOF 作为递归终止的条件。

#include <stdio.h>

int main()
{
    int x;
    if (scanf("%d", &x) == EOF)
        return 0;
    main();
    printf("%d\n", x);
    return 0;
}

G lx的简单题

两个 int 相减的值可能会超出 int 范围,因此需要使用 long long。

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *a, const void *b)
{
    if( *(long long*)a - *(long long*)b < 0 )
        return -1;
    if( *(long long*)a - *(long long*)b > 0 )
        return 1;
    return 0;
}

long long data[100001];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &data[i]);
    }
    
    qsort(data, n, sizeof(long long), cmpfunc);
    Long long delta = 0x7FFFFFFFFFFFFF, a, b;
    
    for (int i = 1; i < n; i++)
    {
        if (data[i] - data[i - 1] < delta)
        {
            a = data[i - 1];
            b = data[i];
            delta = b - a;
        }
    }
    printf("%lld %lld", a, b);
}

H 酸奶吃羊排

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *a, const void *b)
{
    // 如果此处使用 a - b,则是升序;如果使用 b - a,则是降序
    return (*(int *) b - *(int *) a);
}

int meat[1001];

int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &meat[i]);
    }
    qsort(meat, n, sizeof(int), cmpfunc);
    int meatAmount = 0;
    // meter: 每隔一分钟 meter 降低一次,每次 meter 降低至 0 的时候小伙伴吃羊排
    // t: 消耗的时间
    int meter = 0, t = 0;
    for (int i = 0; i < n; i++)
    {
        t++;
        if (meter == 0)
        {
            // 吃当前羊排
            meatAmount += meat[i];
            // 重置 meter
            meter = x;
            // 跳过酸奶吃的羊排
            i++;
        }
        // meter 降低
        meter--;
    }
    printf("%d %d", meatAmount, t);
}

I HugeGun 学姐的魔法

#include <stdio.h>
#include <math.h>
#include <tgmath.h>

const double pi = acos(-1);

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        double x, y;
        scanf("%lf%lf", &x, &y);
        
        double r = sqrt(x * x + y * y);
        
        double theta;
        if (y == 0)
        {
            // x = 0, y = 0 时 theta 为 0
            if (x >= 0)
                theta = 0;
            else
                theta = pi;
        }
        else if (y > 0)
        {
            theta = atan2(y, x);
        }
        else
        {
            // atan2 返回负数时将其转换为正数
            theta = atan2(y, x) + 2 * pi;
        }
        printf("%.7lf %.7lf\n", r, theta);
    }
}

J login 走迷宫

本题我们将迷宫按圈(Layer)划分。例如,一个 4×5 的迷宫,最外圈有 14 个点(1 – 14),第二圈有 6 个点(15 – 20)。可以看出,如果某点 A 在第 n 圈,则到达 A 需要先经过前 n – 1 圈,然后再从第 n 圈的左上角到达目标。

得到点 A 坐标后,我们先计算 A 点在第几圈(使用 getLayer 函数),然后计算最外圈有几个点(out),再根据等差数列求和公式(每一圈比上一圈点数少 8)计算前 n – 1 圈的点数总和(sum)。然后我们判断 A 点在这一圈的哪个边(上边,右边,下边,左边),再算出从这一圈的左上角到 A 需要多少步。

#include <stdio.h>

#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int n, m;

int getLayer(int x, int y)
{
    if (x > n / 2)
    {
        x = n - x + 1;
    }
    if (y > m / 2)
    {
        y = m - y + 1;
    }
    return MIN(x, y);
}

int main()
{
    int p, q;
    scanf("%d%d%d%d", &n, &m, &p, &q);
    int layer = getLayer(p, q) - 1;
    int out = (m + n) * 2 - 4;
    int sum = (out + out - 8 * (layer - 1)) * layer / 2;
    if (p == layer + 1)
    {
        sum += q - layer; // 从左上角到当前位置
    }
    else if (q == m - layer)
    {
        sum += (m - 2 * layer) - 1; // 上边的总数
        sum += p - layer; // 从右上角到当前位置
    }
    else if (p == n - layer)
    {
        sum += (m - 2 * layer); // 上边
        sum += (n - 2 * layer) - 1; // 右边
        sum += m - layer - q; // 从右下角到当前位置
    }
    else
    {
        sum += (m - 2 * layer);
        sum += (n - 2 * layer) - 1;
        sum += (m - 2 * layer) - 1;
        sum += n - layer - p;
    }
    printf("%d", sum);
}

O lx 放球

本题利用了动态规划(DP) 的思想,dp(n, r) 表示在 r 个箱子里放 n 个球的方法数。

#include <stdio.h>

long long dp(long long n, long long r)
{
    if (n == r)
        return 1;
    if (r == 0)
        return 0;
    return r * dp(n - 1, r) + dp(n - 1, r - 1);
}

int main()
{
    int n, r;
    scanf("%d%d", &n, &r);
    printf("%lld", dp(n, r));
}

N Mogg的简单数论

对于一对满足要求的数 \(x, y\),可以求得 \(g = gcd(x, y)\),有

$$ \left\{ \begin{aligned} x & = & g \times M \\ y & = & g \times N \end{aligned}  \right. $$

(其中 \(M, N\) 互素。)则有

$$\left\{ \begin{aligned} a & = & g \times (M+N) \\ b & = & g \times M \times N \end{aligned} \right.$$

$$\frac{a}{b} = \frac{M + N}{M \times N}$$

将 \(\frac{a}{b}\) 约分(\(g = gcd(a, b), a’ = \frac{a}{g}, b’ = \frac{b}{g}\)),即

$$ \left\{ \begin{aligned} a’ & = & M + N \\ b’ & = & M \times N \end{aligned}  \right. $$

解一元二次方程即可得

$$ \left\{ \begin{aligned} M & = & \frac{a’ + \sqrt{a’^{2} – 4b’}}{2} \\ N & = &\frac{a’ – \sqrt{a’^{2} – 4b’}}{2} \end{aligned}  \right. $$

若该方程有正整数解,则 \(x, y\) 存在;否则无解。

#include <stdio.h>
#include <math.h>

#define MAX(x, y) (((x) > (y)) ? (x) : (y))
#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

// 若有整数平方根则返回之;若无整数平方根则返回 -1。
int mysqrt(int x)
{
    if (x < 0)
        return -1;
    int emmm = (int) (sqrt((double) x) + 0.1);
    if (emmm * emmm == x)
        return emmm;
    return -1;
}

int main()
{
    int a, b;
    while (scanf("%d%d", &a, &b) != EOF)
    {
        int g = gcd(a, b);
        int b1 = b / g, a1 = a / g;
        int result = mysqrt(a1 * a1 - 4 * b1);
        if (result == -1 || (a1 + result) % 2 != 0)
        {
            printf("No Solution\n");
            continue;
        }
        int M = (a1 + result) / 2;
        int N = (a1 - result) / 2;
        printf("%d %d\n", g * N, g * M);
    }
}

 

\(\)

CC BY-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-ShareAlike 4.0 International License.