第六次上机 题解

E 悠唯的大数字比较

也可以使用 strcmp。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

#define MAX(a, b) (a > b) ? (a) : (b)
#define MIN(a, b) (a < b) ? (a) : (b)

char A[5003], B[5003];

int main()
{
    int n;
    scanf("%d", &n);
    while (n-- > 0)
    {
        scanf("%s%s", A, B);
        int x1 = strlen(A), x2 = strlen(B), result = 0;
        if (x1 > x2)
            result = 1;
        else if (x1 < x2)
            result = -1;
        else
            for (int i = x1; i > 0; i--)
            {
                if (A[x1 - i] > B[x2 - i]) // 'A' > '9'
                {
                    result = 1;
                    break;
                }
                else if (A[x1 - i] < B[x2 - i])
                {
                    result = -1;
                    break;
                }
            }
        
        if (result == 0)
            printf("EQUAL\n");
        else if (result == 1)
            printf("A\n");
        else
            printf("B\n");
    }
}

F lx 解方程

函数在给定区间内是单调递减函数。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

#define MAX(a, b) (a > b) ? (a) : (b)
#define MIN(a, b) (a < b) ? (a) : (b)
const double pi = acos(-1);

double f(double x)
{
    return (sin(sqrt(x)) + exp(-pow(x, 1.0 / 3.0))) / log(pi * x);
}

int main()
{
    double y;
    scanf("%lf", &y);
    double start = 0.33, end = 10;
    while (end - start > 0.00000001)
    {
        double mid = (start + end) / 2;
        if (f(mid) > y)
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    printf("%.5lf", start);
}

G ArcheyChen的狼题

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

#define size 22
char arr[size];
int n, pos = size - 1;
bool plus(int pos)
{
    if ((size - pos) > n)
        return false;
    arr[pos]++;
    if (arr[pos] > ('A' + n - (size - pos)))
    {
        if (!plus(pos - 1))
            return false;
        arr[pos] = arr[pos - 1] + 1;
    }
    return true;
}

void print()
{
    for (int i = 0; i < size; i++)
    {
        if (arr[i] >= 'A')
        {
            putchar(arr[i]);
            putchar(' ');
        }
    }
    putchar('\n');
}

int main()
{
    for (int i = 0; i < size; i++)
    {
        shit[i] = 'A' - 1;
    }
    scanf("%d", &n);
    while(plus(size - 1))
    {
        print();
    }
}

H 生日蛋糕

容斥原理 – 维基百科

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

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

int main()
{
    int n;
    scanf("%d", &n);
    long long xs[21], ys[21];
    for (long long i = 0; i < n; i++)
    {
        scanf("%lld", &xs[i]);
    }
    long long ans = 0;
    for (int i = 1; i < (1 << n); i++)
    {
        long long gcdval = -1;
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                cnt++;
                if (gcdval == -1)
                    gcdval = xs[j];
                else
                    gcdval = gcd(gcdval, xs[j]);
            }
        }
        if (cnt % 2 == 0)
            ans -= gcdval;
        else
            ans += gcdval;
    }
    printf("%lld", ans);
    
}

I 摸鱼助教MoggⅠ

先合并两个数组，然后用二分查找。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

long long a[10002], b[10002], z[20004];

int main()
{
    int n, m, k;
    while (scanf("%d%d%d", &n, &m, &k) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &a[i]);
        }
        for (int i = m - 1; i >= 0; i--)
        {
            scanf("%lld", &b[i]);
        }
        a[n] = b[m] = 0x812345678;
        int total = m + n;
        for (int posa = 0, posb = 0; posa + posb < total;)
        {
            if (a[posa] < b[posb])
            {
                z[posa + posb] = a[posa];
                posa++;
            }
            else
            {
                z[posa + posb] = b[posb];
                posb++;
            }
        }
        for (int i = 0; i < k; i++)
        {
            long long c;
            scanf("%lld", &c);
            int ans = -1;
            if (c >= z[0] && c <= z[total - 1])
            {
                int start = 0, end = total;
                while(end - start > 1)
                {
                    int mid = (start + end) / 2;
                    if (z[mid] <= c)
                    {
                        start = mid;
                    }
                    else
                    {
                        end = mid;
                    }
                }
                if (z[start] != c)
                    ans = -1;
                else
                    ans = total - start;
            }
            printf("%d ", ans);
        }
        printf("\n");
    }
}

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