头像

码农一个

南海双语实验学校 NBS(NANHAI BILINGUAL SCHOOL)




离线:7天前


最近来访(10)
用户头像
北港城
用户头像
zombotany
用户头像
代码能不能一遍过啊

活动打卡代码 AcWing 3694. A还是B

码农一个
3个月前
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 0, b = 0;
    while (n -- )
    {
        char t;
        cin >> t;

        if (t == 'A') a ++ ;
        else b ++ ;
    }

    if (a == b) puts("T");
    else if (a > b) puts("A");
    else puts("B");

    return 0;
}


活动打卡代码 AcWing 3547. 特殊数字

码农一个
3个月前
#include <bits/stdc++.h>

using namespace std;

int get(int n)
{
    int res = 0;
    while (n)
        res += n % 10, n /= 10;

    return res;
}

int main()
{
    int n;
    cin >> n;

    for (int i = n; ; i ++ )
    {
        if (get(i) % 4 == 0)
        {
            cout << i << endl;
            break;
        }
    }

    return 0;
}



码农一个
4个月前

637.可表示的数 题解

题目描述

有N个整数从左到右排成一行,如果某个数等于它前面的2个数的和,就称这个数是可以表示的数。问给定的数列里有多少个数是可以表示的数。

输入格式

第一行1个整数N,表示数列有多少个整数。1<=N<=10000

第二行N个正整数,每个正整数不超过10000

输出格式

一个整数,有多少可表示的数。


题意分析

本题让我们输入一个数组,遍历数组,在0i - 1的范围里查找2个数,与a[i]相等


解题思路

错误思路❌

用三循环,依次遍历数组,如果在0i - 1的范围内有符合条件的数时,答案+1

但是本题n的范围是10000,极端情况要计算1666 1667 0000次,评测系统一秒内只能计算1 0000 0000次,所以会超时。


正确思路✔

可以定义一个bool数组,来存前面出现过某两个数的和。

const int N2 = 1000010;

bool sum[N2];

然后遍历数组,在循环中,把a[i]0i - 1的数分别计算加和,把sum[a[i] + a[j]]标记为true

再判断sum[a[i]]是否为true即可.

注意:判断应在第二重循环前,因为是在a[i]之前找数。

long long res = 0;
for (int i = 1; i < n; i ++ )
{
    if (sum[a[i]])
        res ++ ;
    for (int j = 0; j < i; j ++ )
        sum[a[i] + a[j]] = true;
}

正确代码最多计算49995000次,评测系统一秒内能计算1 0000 0000次,所以不会超时。


解题反思

做题时,使用for循环,要考虑时间复杂度


参考代码

错误思路❌ 代码
#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int a[N]; // 定义数组

int main()
{
    int n;
    cin >> n; // 输入n

    for (int i = 0; i < n; i ++ ) cin >> a[i]; // 输入数组

    long long res = 0;
    for (int i = 0; i < n; i ++ ) // 最外层循环,遍历整个数组
    {
        bool ff = true; // 如果判断过这个数,就退出第二层循环
        for (int j = 0; j < i; j ++ )
        {
            if (!ff) break; // 如果找到了答案,就退出循环
            for (int k = j + 1; k < i; k ++ )
                if (a[j] + a[k] == a[i])
                {
                    ff = false;
                    res ++ ;
                    break;
                }
        }   
    }

    cout << res << endl; // 输出答案

    return 0;
}
正确思路✔ 代码
#include <bits/stdc++.h>

using namespace std;

const int N1 = 10010;

int a[N1]; // 定义输入的数组

const int N2 = 1000010;

bool sum[N2]; // 定义存和的数组

int main()
{
    int n; 
    cin >> n; // 输入n

    for (int i = 0; i < n; i ++ ) cin >> a[i]; // 输入数组

    long long res = 0; // 定义答案变量
    for (int i = 1; i < n; i ++ )
    {
        if (sum[a[i]]) // 判断如果前面两个数的和是a[i]
            res ++ ; // 答案加1
        for (int j = 0; j < i; j ++ )
            sum[a[i] + a[j]] = true; // 计算a[i] + a[j]的和
    }

    cout << res << endl; // 输出答案

    return 0;
}

笔记

复杂度 数量级 最大规模
O(logN) >> 10 ^ 20 很大
O(N^1 / 2) 10 ^ 12 10 ^ 14
O(N) 10 ^ 6 10 ^ 7
O(NlogN) 10 ^ 5 10 ^ 6
O(N ^ 2) 1000 2500
O(N ^ 3) 100 500
O(N ^ 4) 50 50
O(2 ^ N) 20 20
O(3 ^ N) 14 15
O(N!) 9 10


活动打卡代码 AcWing 898. 数字三角形

码农一个
5个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int n;
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            cin >> f[i][j];

    for (int i = n - 1; i; i -- )
        for (int j = 1; j <= i; j ++ )
            f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);

    cout << f[1][1] << endl;

    return 0;
}


活动打卡代码 AcWing 426. 开心的金明

码农一个
5个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 3e5 + 10;

int f[N];

int main()
{
    int n, m;
    cin >> m >> n;

    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + w * v);
    }

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 433. ISBN号码

码农一个
5个月前
#include <bits/stdc++.h>

using namespace std;

int main()
{
    string a;
    getline(cin, a);

    string b = {a.back()};

    a.pop_back();
    a.pop_back();

    int k = 1, res = 0;
    for (auto x : a)
    {
        if (x >= '0' && x <= '9')
        {
            string t = {x};
            res += stoi(t) * k;
            k ++ ;
        }
    }

    res %= 11;

    if (b == "X") b = "10";
    int n = stoi(b);

    if (n == res) puts("Right");
    else
    {
        if (res == 10) cout << a << "-X";
        else cout << a << '-' << res << endl;
    }

    return 0;
}


活动打卡代码 AcWing 428. 数列

码农一个
5个月前
#include <iostream>

using namespace std;

int check(int a, int b)
{
    int res = 1;
    while (b -- ) res *= a;
    return res;
}

int main()
{
    int k, n;
    cin >> k >> n;

    int res = 0;
    for (int i = 0; i < 10; i ++ )
        if (n >> i & 1)
            res += check(k, i);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 421. 陶陶摘苹果

码农一个
5个月前
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a[15] = {0};
    for (int i = 0; i < 10; i ++ ) cin >> a[i];

    int n;
    cin >> n;
    n += 30;

    int res = 0;
    for (int i = 0; i < 10; i ++ )
        if (n >= a[i])
            res ++ ;

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 445. 数字反转

码农一个
5个月前
#include <bits/stdc++.h>

using namespace std;

int main()
{
    string a;
    cin >> a;

    reverse(a.begin(), a.end());

    if (a.back() == '-')
    {
        cout << '-';
        a.pop_back();
    }

    int k = 0;
    while (k + 1 < a.size() && a[k] == '0') k ++ ;
    while (k < a.size()) cout << a[k ++ ];

    cout << endl;

    return 0;
}


活动打卡代码 AcWing 441. 数字统计

码农一个
5个月前
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int A, B, L;
    int a, b;
    cin >> A >> B >> L;

    double delta = 1e9;
    for (int i = 1; i <= L; i ++ )
        for (int j = 1; j <= L; j ++ )
        {
            double x = (double) i / A;
            double X = (double) j / B;
            if (x >= X && x - X < delta)
                a = i, b = j, delta = x - X;
        }

    cout << a << ' ' << b << endl;

    return 0;
}