首页 > 其他分享 >NOJ题解

NOJ题解

时间：2023-11-13 13:56:16浏览次数：39  
标签：prime return NOJ int 题解 d% printf include

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

标签：prime,return,NOJ,int,题解,d%,printf,include
From： https://www.cnblogs.com/A2484337545/p/17828942.html

相关文章

  • 问题解答：SAP OData V2 和 V4 里针对日期类型的字段进行过滤操作(filter)的正确语法试
    我的知识星球里有朋友咨询一个问题：我测试了一个S/4HANAcloud的purchaseorder的API,这个是ODATAV4格式的。在对CreationDate做filter后运行有报错Invalidparametertypeusedwithfunction'eq'.对datetime字段做filter，一直搞不清楚格式。请帮忙看一下。本文就安排这......
  • [题解] P6569 [NOI Online #3 提高组] 魔法值
    P6569[NOIOnline#3提高组]魔法值不放简要题意了，题面写的很简要。看到数据范围自然可以想到矩阵快速幂优化。但乘法对异或没有分配律。所以直接拆位，把异或变成加法对二取模就有分配律了。还有一个优化就是提前预处理出矩阵的2的幂次方，然后询问时直接二进制分解乘起来就行......
  • ARC119F 题解
    前言ARC119F好厉害，是没见过的自动机DP。正文[1]分析主要分析一下为什么这么写。[2]状态设计[3]自动机状态转移感觉状态设计中最难的就是如何处理带\(O\)的。见参考资料。[4]代码还没写。写ing这是自动机的初始化（有点麻烦）。intto[Kind][2][2]={{{2,0},{8,0......
  • ABC328F题解
    原题链接洛谷题面提交记录闲话赛场就做了这道和A，喜提\(625\)大分。带权并查集练手题，有点像银河英雄传说。题目大意存在一个长度为\(N\)的数列\(X\)，给定\(Q\)个三元组\((a_i,b_i,d_i)\)，定义一个好集合为集合\(S\subseteq\{1,2,\dots,Q\}\)，使得所有\(x\inS\)满......
  • 题解：[春季测试 2023] 幂次
    题解：[春季测试2023]幂次给定\(n,k\)，求有多少个整数\(i\in[1,n]\),满足\(i=a^b(a,b\inN^+,b\geqk)\)算法一\(k\ge3:\)发现只需要筛到1e6就没有贡献了，加上\(set\)暴力判重即可。\(k=2:\)发现有\(\sqrt{n}\)个完全平方数，考虑如何避免算重它们。考虑完全平......
  • Tenzing and Random Operations CF1842G 题解
    设\(m\)次选的位置分别为\(b_{1\simm}\)。于是答案为\(\mathbbE(\prod\limits_{i=1}^{n}(a_i+\sum\limits_{j=1}^{m}[b_j\lei]\cdotv))=\frac{S}{n^m}\)。首先考虑期望很难做，希望将期望转化为概率形式，发现这样有点困难。再考虑因为所有方案等概率，将求期望转化......
  • P2687 [USACO4.3] 逢低吸纳 题解
    双倍经验分析这是一道求最长下降子序列的题目，且要统计方案，但是会有重复情况，例如以下的的数据，44223我们可以选择\(1,2\),\(1,2\),\(1,4\)这几天来购买，但是\(1,2\)和\(1,3\)本质上是一样的，所以只算一种。根据上面的说明，我们可以得出：当\(dp_j+1=dp_i\)......
  • [题解] P9838 挑战 NPC IV
    P9838挑战NPCIV定义\(f(x)=1+\log_2\operatorname{lowbit}(x)\)。定义一个\(1\simn\)的排列\(p\)的权值是\(\sum_{l=1}^n\sum_{r=l}^n\sum_{i\in[l,r]}f(p_i)。\)求所有\(1\simn\)的排列中权值第\(k\)小的排列的权值，对\(998244353\)取模。......
  • 【2023 #84】 锦城ACM周测 (大二个人赛) 题解
    题目难度\(B<D<E=C<A\)A:提高+/省选-B:普及-C:普及/提高-D:普及/提高-E:普及/提高-CandywarQuestion有\(N\)个盒子摆成环形，第\(i\)和盒子里面有\(a_i\)个糖果，他们开始在\(1\)好盒子，然后每个人取一次，可以取\(1\)，或者小于当前盒子内糖果数的一个质数\(p\),......
  • chatgpt的api联网报错问题解决：openai公司的api联网报错解决
    chatgpt是啥，这里不讲，openai是啥这里也不讲。要知道我们不论是通过网页web使用chatgpt还是使用api方式通过客户端使用chatgpt都是需要使用外国IP的，     ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99