526互联

NOJ题解

发布时间 2023-11-13 13:55:15作者: DSHUAIB

NOJ题解

30-40

素数

埃氏筛，欧拉筛都可

可变参数累加/平均

用给出的库函数即可

基思数

根据题意模拟

#include<stdio.h>
#define ll long long
ll num[102];

inline bool IsKeith(ll n)
{
    int tot = 0, t = 0;
    ll s = n;
    while (s)
    {
        num[++tot] = s % 10;
        s /= 10, t++;
    }
    for (int i = 1; i <= tot / 2; i++)
    {
        int tmp = num[i];
        num[i] = num[tot - i + 1];
        num[tot - i + 1] = tmp;
    }
    for (int i = tot + 1; i <= 101; i++)
    {
        for (int j = 1; j <= t; j++)
            num[i] += num[i - j];
        if (num[i] == n)
            return true;
        else if (num[i] > n)
            return false;
    }
    return false;
}

int main()
{
    ll n;
    scanf("%lld", &n);
    if (IsKeith(n))
        printf("Yes");
    else
        printf("No");
    return 0;
}

二进制表示

递归表示，注意递归边界

#include<stdio.h>

void print(int n)
{
    int base = 1, t = 0;
    while ((base << 1) <= n)
        base <<= 1, t++;
    while(n)
    {
        while(n < base)
            base >>= 1, t--;
        if (t == 1 && n > base)
            printf("2+");
        else if (t == 1)
            printf("2");
        else if (t == 0)
            printf("2(0)");
        else if (n > base)
        {
            printf("2(");
            print(t);
            printf(")+");
        }
        else if (n == base)
        {
            printf("2(");
            print(t);
            printf(")");
        }
        n -= base;
    }
}

int main()
{
    int n, base = 1, t = 0;
    scanf("%d", &n);
    print(n);
    return 0;
}

哈沙德数

照的题目给的直接写就行

运行会

得用一点点数论，一个人的坐标（x，y）能被看见当且仅当x，y互质，不然总存在（x/k,y/k）将这个人挡住。用欧拉筛求一遍欧拉函数（φ（x）小于x的与x的正整数互质的数的个数）即可

#include<stdio.h>
#define ll long long
const int N = 1e5 + 5;
int prime[N], phi[N], tot;
bool is[N];

void init()
{
    phi[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!is[i])
        {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; i * prime[j] < N; j++)
        {
            is[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    init();
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += phi[i];
    printf("%lld", ans * 2 + 1);
    return 0;
}

佩尔数

照着题目写

#include<stdio.h>

int PA(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    return 2 * PA(n - 1) + PA(n - 2);
}

int PB(int n)
{
    int p0 = 0, p1 = 1, pn;
    for (int i = 0; i <= n; i++)
    {
        if (i == 0)
            pn = p0;
        else if (i == 1)
            pn = p1;
        else
        {
            pn = 2 * p1 + p0;
            p0 = p1, p1 = pn;
        }
    }
    return pn;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", (n & 1) ? PA(n) : PB(n));
    return 0;
}

冰雹序列

照着题目给的公式写

#include<stdio.h>

int f(int n)
{
    return (n & 1) ? 3 * n + 1 : n / 2;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d", n);
    while (n != 1)
    {
        n = f(n);
        printf(" %d", n);
    }
    return 0;
}

40-50

回文数之和

根据题意模拟就行

#include<stdio.h>

bool check(int n, int k)
{
    int tmp = n, num[110], len = 0;
    while(tmp)
    {
        num[++len] = tmp % 10;
        tmp /= 10;
    }
    for (int i = 1; i <= len / 2; i++)
        if (num[i] != num[len - i + 1])
            return false;
    len = 0, tmp = n;
    while(tmp)
    {
        num[++len] = tmp % k;
        tmp /= k;
    }
    for (int i = 1; i <= len / 2; i++)
        if (num[i] != num[len - i + 1])
            return false;
    return true;
}

int main()
{
    int n, k, ans = 0;
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++)
        if (check(i, k))
            ans += i;
    printf("%d", ans);
    return 0;
}

飞机起飞速度

抽象题，没做

行列式值

高斯消元求行列式值

#include<stdio.h>
using namespace std;
typedef long long ll;

ll n;
ll a[605][605];

ll work()
{
    ll res = 1, w = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            while (a[i][i])
            {
                int d = a[j][i] / a[i][i];
                for (int k = i; k <= n; k++)
                    a[j][k] = a[j][k] - d * a[i][k];
                swap(a[i], a[j]), w *= -1;
            }
            swap(a[i], a[j]), w *= -1;
        }
    }
    for (int i = 1; i <= n; i++)
        res = res * a[i][i];
    res *= w;
    return res;
}

int main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lld", &a[i][j]);
    ll ans = work();
    printf("%lld", ans);
    return 0;
}

蒙特卡洛方法求积分

要用随机数算，也挺抽象的一直过不了

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

double f(double x, int k)
{
    if (k == 1)
        return pow(x, 4) / exp(x);
    else if (k == 2)
        return x * x + 1;
    else if (k == 3)
        return cos(x);
    else if (k == 4)
        return sqrt(x) * (x - 2);
    return 2 * sin(x) - 5 * cos(x);
}

int main()
{
    srand(RAND_MAX);
    int m, N;
    double a, b, ans = 0;
    scanf("%d%lf%lf%d", &m, &a, &b, &N);
    for (int i = 0; i < N; i++)
    {
        double x = a + (double)rand() / RAND_MAX * (b - a);
        ans += f(x, m) * (b - a);
    }
    ans /= N;
    printf("%.6lf", ans);
    return 0;
}

完美矩阵

前缀和判断0/1个数

#include<stdio.h>
#include<math.h>
int num[305][305], nl[305][305], nr[305][305];

int main()
{
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int tmp;
            scanf("%d", &tmp);
            nl[i][j] = nl[i][j - 1] + tmp;
            nr[j][i] = nr[j][i - 1] + tmp;
            num[i][j] = num[i - 1][j] + num[i][j - 1] - num[i - 1][j - 1] + tmp;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int a = i + 1; a <= n; a++)
            {
                for (int b = j + 1; b <= m; b++)
                {
                    if (a - i + 1 != b - j + 1)
                        continue;
                    if (nl[i][b] - nl[i][j - 1] != b - j + 1)
                        break;
                    if (nl[a][b] - nl[a][j - 1] != b - j + 1)
                        break;
                    if (nr[j][a] - nr[j][i - 1] != a - i + 1)
                        break;
                    if (nr[b][a] - nr[b][i - 1] != a - i + 1)
                        continue;
                    if (abs(2 * (num[a - 1][b - 1] - num[a - 1][j] - num[i][b - 1] + num[i][j]) - (a - i - 1) * (b - j - 1)) <= 1)
                        ans++;
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

货运优化

做的有点麻烦，贪心算法，能装满就尽量装满

#include<stdio.h>

int main()
{
    int ls2[4] = {0, 5, 3, 1};
    int a, b, c, d, e, f;
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    while (a + b + c + d + e + f != 0)
    {
        int ans = f;
        if (e > 0)
            ans += e, a -= e * 11;
        if (d > 0)
        {
            ans += d;
            if (d * 5 >= b)
            {
                int tmp = d * 5 - b;
                b = 0;
                a -= tmp * 4;
            }
            else
                b -= d * 5;
        }
        if (c > 0)
        {
            if (c % 4 == 0)
                ans += c / 4;
            else
            {
                ans += c / 4 + 1;
                if (ls2[c % 4] >= b)
                    a -= 36 - b * 4 - c % 4 * 9, b = 0;
                else
                    a -= 36 - b * 4 - c % 4 * 9, b -= ls2[c % 4];
            }
        }
        if (a > 0)
            ans += a / 36 + (a % 36 ? 1 : 0);
        printf("%d\n", ans);
        scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    }
}

航空旅行

判断一下就行

#include<stdio.h>

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int a, b, c, d, e;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
        int tmp = 0;
        if (a <= e)
            tmp = tmp > a ? tmp : a;
        if (b <= e)
            tmp = tmp > b ? tmp : b;
        if (c <= e)
            tmp = tmp > c ? tmp : b;
        int k = a + b + c - tmp;
        if (k <= d && tmp)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

素数筛选法

模版题，就不具体阐述了

#include<stdio.h>
const int N = 1e7 + 5;
bool is[N];
int prime[N], tot;

int main()
{
    is[1] = true;
    for (int i = 2; i < N; i++)
    {
        if (!is[i])
            prime[++tot] = i;
        for (int j = 1; prime[j] * i < N; j++)
        {
            is[prime[j] * i] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
    prime[tot + 1] = 0x3f3f3f3f;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        if (prime[i] > n)
        {
            printf("%d", i - 1);
            break;
        }
    }
    return 0;
}

波士顿房价预测

直接用程序算线性回归方程就行

#include<stdio.h>
const int N = 1e5 + 5;

int x[N], y[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &y[i]);
    double a, b, sxy = 0, sx = 0, sy = 0, sx2 = 0;
    for (int i = 1; i <= n; i++)
    {
        sxy += x[i] * y[i];
        sx += x[i], sy += y[i];
        sx2 += x[i] * x[i];
    }
    b = sxy - sx * sy / n;
    b /= sx2 - sx * sx / n;
    a = sy / n - b * sx / n;
    printf("Y=%.4lf+%.4lf*X", a, b);
    return 0;
}

稀疏矩阵

数一下0的个数？有点没搞懂这题

#include<stdio.h>

int main()
{
    int n, m, num = 0, tot = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int tmp;
            scanf("%d", &tmp);
            tot += tmp;
            if (tmp)
                num++;
        }
    }
    if ((double)num / (n * m) <= 0.05 || (num == n || num == m))
        printf("Yes");
    else
        printf("No");
    return 0;
}